Browse Prior Art Database

Parse Tree Data Abstract Data Type

IP.com Disclosure Number: IPCOM000121313D
Original Publication Date: 1991-Aug-01
Included in the Prior Art Database: 2005-Apr-03
Document File: 4 page(s) / 151K

Publishing Venue

IBM

Related People

Shum, P: AUTHOR [+2]

Abstract

The Parse Tree Abstract Data Type (ADT) is an efficient and flexible method used to verify the syntactic correctness of a hierarchical language, such as Distributed Data Management (DDM). The Parse Tree ADT provides a roadmap for DDM Parsing, encapsulating rules about the ordering of the parameters, the optionality of the parameter, as well as the level of the parameter.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Parse Tree Data Abstract Data Type

      The Parse Tree Abstract Data Type (ADT) is an efficient
and flexible method used to verify the syntactic correctness of a
hierarchical language, such as Distributed Data Management (DDM).
The Parse Tree ADT provides a roadmap for DDM Parsing, encapsulating
rules about the ordering of the parameters, the optionality of the
parameter, as well as the level of the parameter.

      The Distributed Data Management (DDM) Architecture is defined
by a Dictionary of Terms that describe the concepts, the structures,
and protocols of DDM.  The DDM Model is based on objects and
operations on these objects.  Objects are elements of classes, and
classes are hierarchically related.  This means that an object (data,
operation on data) is defined in terms of some other object with some
superclass.  There exists, therefore, a natural recursive
relationship between DDM Objects.

      The DDM Dictionary for the Parsing algorithm consists of a set
of expanded DDM Definitions.  The tree is represented in the
dictionary in a depth-first search manner.  Each node of the tree has
certain characteristics, such as required, optional, or ignorable.
Also, if an internal node is required, then it must appear in the
received data stream that we intend to parse.  If it is optional or
ignorable, it may or may not appear in the data stream.  If an
internal node is optional, then its entire subtree is optional.
However, once the node has been parsed (i.e., received) all its
required children are now required.

      In addition, the DDM Architecture stipulates that the parameter
at each level in the tree can/must be accepted in any order.  For
example, if we just have processed the root, we must process its
children in any order.  However, once we visit a child, the entire
subtree rooted by that child must be visited before its sibling can
be processed.  By "visited" we mean that all the required children of
the definition must be matched against the data stream. Optional
children may or may not be visited.

      This article describes an Abstract Data Type, i.e., an object,
data and operations which will provide a roadmap to the DDM data
stream.  It encapsulates all the DDM rules about required, optional,
etc. and provides its callers with easy operations to step through
the data stream and verify its syntactic correctness.
The Parse Tree Data Abstract Data Type

      The purpose of the Parse Tree is to provide a road map to the
definition as well as a che...