3 The Tree Level

As mentioned in the introduction, certain tools like syntax directed editors are usually table-driven in the sense that the code is independent of the actual grammar. The AST is manipulated as an ordinary tree. The context-free level must therefore be integrated with a level where the AST is viewed as an ordinary tree. This is straight forward using subclassing. The patterns generated from the grammar are all subpatterns of the general patterns Cons and List. These patterns are actually subpatterns of more general patterns describing ASTs as ordinary trees. In this section these general patterns are described. The general patterns are called the tree level.

At the tree level, an AST is modelled as an instance of the pattern AST. The pattern AST is further specialized into a number of sub-patterns. Some of these sub-patterns correspond to the rule types of a structured context-free grammar. The tree level corresponds to an ordinary data type for a tree. The specialization hierarchy for the patterns defined in the tree level is:

The following is a verbal description of these patterns:

• AST describes all ASTs. Operations of this pattern are: Symbol returns the nonterminal symbol of the AST. Kind returns the type of the AST (e.g. List). Father returns the father. SonNo returns the index of this AST in the list of sons of the father of this AST. NextBrother returns the next brother of this AST in the list of sons of the father of this AST. AddComment updates an associated comment, GetComment returns an associated comment, and HasComment tests whether a comment is associated with this AST. HasSemanticError and SemanticError is used by language-dependent tools to mark ASTs with information on semantic errors in the AST. Copy returns a copy. Match, Equal and Lt perform different kinds of comparisons of ASTs, and copy enables copying an entire AST. NearestCommonAncestor returns the nearest common ancestor of this AST and some other AST. GetAttribute, putAttribute, getNodeAttribute, putNodeAttribute, getSlotAttribute, putSlotAttribute, getSlotNodeAttribute and putSlotNodeAttribute are operations for accessing and changing the different attributes, that are specified for this kind of ASTs. The number of attributes are defined as part of the grammar specification. Finally, the putCommentProp and getCommentProp are used for associating properties directly with individual ASTs. For a description of properties, see chapter 7.
• Expanded describes ASTs that are expanded into trees (i.e. something has been derived from the nonterminal of this AST). Get returns a son at a given position. Put updates a son at a given position. NoOfSons returns the number of sons of this AST. Scan iterates over the sons in this AST. SuffixWalk and SuffixWalkforProd perform preorder traversal of the tree with this node as root. Insert will insert an AST before a given son. Finally, expanded defines getson1 ..., getson9 and putson1 ..., putson9 for direct access to the given son number.
• Cons describes all nodes derived by a constructor rule. Delete deletes a son at a given position.
• List describes all nodes derived by a list rule. SonCat describes the category of the ASTs of the list. Delete deletes an AST with a given position and Insert inserts an AST at a given position. Append inserts an AST as the last son in the list. NewScan iterates over the ASTs in this list.
• Lexem describes all nodes derived by one of the predefined nonterminals (e.g. Const). No special operations.
• LexemText describes leaves having textual contents. GetText returns the textual contents. PutText updates the textual contents. CurLength returns the length of the textual contents. GetChar and putChar allows for accessing and changing the individual chars in the textual contents. Clear empties the textual contents.
• NameDecl describes all name declarations. ScanUsage iterates over the name applications that use this declaration. This information is context-sensitive and if used it must be set up by a language specific tool. AddUsage and removeUsage is used by these language-specific tools to set-up and remove such informations.
• NameAppl describes all name applications. GetDecl returns a reference to the AST, containing the declaration of this name application. This information is context-sensitive and if used it must be set up by a language specific tool. NextUsage returns the next usage (reference to an AST) of this nameAppl, if any exists. DeclSet tells whether any language-specific tools have setup declaration information for this name application.
• String describes all strings. No special operations.
• Const describes all numeric constants. GetValue returns the value of the constant, PutValue updates the value of the constant.
• Comment describes comments associated with ASTs. CommentType returns the type of this comment.
• UnExpanded describes ASTs where nothing yet has been derived from the nonterminal of this AST. NonterminalSymbol returns the kind of nonterminal associated with this AST (Note that this(AST).symbol returns unExpanded). The kind of nonterminals are defined in the kinds object. The available kinds are: kinds.interior, kinds.unExpanded, kinds.optional, kinds.nameDecl, etc).
• Optional describes ASTs that are unexpanded, and where the nonterminal symbol of this AST is defined by an optional rule. No special operations.
• SlotDesc describes AST representing SLOTs. More on SLOTs later.

Assuming the patterns AssignmentImp, IfImp and ProcCall corresponding to ASTs generated from the respective nonterminals. These patterns are sub-patterns of the pattern Imp. Assume that a tool for counting the number of imperatives in an instance of ImpList is to be implemented. In addition the tool should count the number of different types of imperatives. The tool may be implemented by adding a virtual pattern attribute Count to the pattern Imp. The definition of Count may then be extended in the sub-patterns:

Imp: Cons(# Count:< (# do ImpCount.Add1; inner #) #) AssignmentImp: Imp(# ... Count::< (# do AssignmentCount.Add1 #) #); ... ImpList: List(# ... #) IL: ImpList; ... IL.Scan(# do thisElm.Count #)

The virtual pattern Count in AssignmentImp will be a sub-pattern of the Count pattern in Imp. ThisElm in IL.scan... will in turn refer to each element in IL. If ThisElm in IL.Scan denotes an instance of AssignmentImp then ThisElm.Count will result in execution of ImpCount.Add1 followed by AssignmentCount.Add1