4.3 Using the Context-Free Level

Consider the references:

P: ^ProcDcl; B: ^Block; N: ^nameDecl

P.getBody refers to the block of P, and after executing the assignment P.getBody -> B[], B will refer to this block. P.getName->N[]; N.GetText will return the name of the procedure as a text.

Consider a tool for investigating the contents of a block, where part of the investigation is to count the number of imperatives in the block. In addition the number of different types of imperatives will be counted.

This tool may be implemented by adding the operation Investigate to the pattern Block. Investigate makes use of the virtual operation Count which is added to the pattern Imp. Count is further specialized in the sub-patterns of Imp.

Small: Treelevel
  (# ImpCount, AssignmentCount,
     ProcCallCount, ICount: @Integer;
     Block: Cons
       (# Investigate:
            (# do
               0 Æ ImpCount Æ AssignmentCount
                 Æ ProcCallCount Æ IfCount;
               ImpPart.Scan(# do Current.Count #);
               ... (* Use ImpCount, ProcCallCount, ... *)
     Imp: Cons
       (# Count:< (# do ImpCount.Add1; inner #) #);
     IfImp: Imp
       (# Count::<
            (# do
               ThenPart.Scan(#do Current.Count #);
               ElsePart.Scan(#do Current.Count #);
     AssignmentImp: Imp
       (# Count::< (# do AssignmentCount.Add1 #) #);
     ProcCall: Imp
       (# Count::< (# do ProcCallCount.Add1 #) #);

B can now be investigated by B.Investigate.

In spite of the limited usefulness of the above example it gives a flavour of how semantic attributes may be added to the generated patterns. Tools like a semantic analyzer, a code generator, a program interpreter, a browser, presentation tools, program analyzers, transformation tools benefit from the possibility to add semantic attributes.

The next example will demonstrate how the syntax directed editor of the Mjølner BETA System can be extended to provide the user of the editor with transformations.

The editor is an ordinary syntax directed editor which presents an AST in a window by means of a pretty-printer, it allows the user to navigate in the AST and to edit it. The pattern describing the editor has the outline:

  (# Grammar:< TreeLevel;
     G: @Grammar;
     Root, CurrentSelection: ^G.AST;
     ... (* a lot of other stuff *)

Grammar describes which grammar is actually used. An editor for Pascal may be constructed by binding the context-free level generated for Pascal to Grammar. The reference Root denotes the program fragment being edited by the user. CurrentSelection denotes the sub-AST which is the current focus of the user.

To extend the editor with transformations the pattern SdeWithTransformations is declared as a sub-pattern to Sde. SdeWithTransformations declares the pattern Transformation, which has three virtual operations Init, EnablingCondition and Perform and a static reference Name.

SdeWithTransformations keeps a list containing an instance of each sub-pattern of Transformation. This list is created by means of initialization operations not shown here.

When the user selects a new node in the tree EnablingCondition will be tested for all transformations. The Names of those that are enabled will be presented to the user in a menu, and if the user selects one of the items in this menu, Perform for the corresponding transformation will be called.

SdeWithTransformations: Sde
  (# Transformation:
       (# Name: (* Presented in the menu *) @Text;
          Init:< (* Called when an instance is created *)
            (# do ... inner; ... #);
            (* Virtual operation to test if transformation
             * is applicable for the current selection of
             * the editor.
            (# Enabled: @Boolean
            do inner 
            exit Enabled
            (* Operation to be performed if the user 
             * selects this transformation
            (# do inner #);

Assume a grammar for Pascal has been written, structured as Small, and including the rule

<WhileImp>::= while <Condition:Exp> do <DoPart:ImpLst>

A syntax directed editor for Pascal with a transformation that will allow the user to transform an IfImp into a WhileImp could be created by the pattern:

PascalEditor: SdeWithTransformations
  (# Grammar::< PascalGrammar;
     IfToWhileTransformation: Transformation
       (# Init::< (# do 'IfImp to WhileImp' -> Name #)
            (# do (CurrentSelection## = G.IfImp##)
                    -> Enabled
            (# theIfImp: ^G.IfImp;
               theWhileImp: ^G.WhileImp;
               frag: ^fragmentForm;
            do CurrentSelection[] -> theIfImp[];
               (whileImp, frag[]) -> newAst
                 -> theWhileImp[];
                 -> theWhileImp.putCondition;
               theWhileImp -> ReplaceCurrentSelection;
     ... (* More Pascal-transformations *)

The pattern ReplaceCurrentSelection used by Perform is an attribute of pattern Sde.

The IfToWhileTransformation is a simple tree-match transformation. In the same way more advanced context-sensitive transformations could be added to the Pascal-editor. A transformation that extends a <Procedure-Identifier> with a template for the list of actual parameters is an example of this. This list could be generated with the correct number of parameters, and the parameters could be specialized such that a <Variable> nonterminal is inserted if the formal parameter is a <Var-Parameter>, an <Exp> nonterminal if it is a <Value-Parameter>, etc.

The context-free level provides the programmer with much more structure and security than the tree level alone. Consider the declaration P: ^ProcDcl. The body part of P may be denoted by P.getBody. If only the tree level is used, the corresponding declaration and denotation will be P: ^AST and P.getson2. This is less readable and it is solely the responsibility of the programmer that P actually denotes an AST for <ProcDcl> otherwise P.getson2 will not return an AST for <Block>.

The Metaprogramming System - Reference Manual
© 1991-2004 Mjølner Informatics
[Modified: Friday April 6th 2001 at 12:43]