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:

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


The Metaprogramming System - Reference Manual
© 1991-2004 Mjølner Informatics
[Modified: Wednesday April 4th 2001 at 16:28]