Eli   Documents
Eli: Translator Construction Made Easy

General Information

o Eli: Translator Construction Made Easy
o Global Index
o Frequently Asked Questions
o Typical Eli Usage Errors

Tutorials

o Quick Reference Card
o Guide For new Eli Users
o Release Notes of Eli
o Tutorial on Name Analysis
o Tutorial on Scope Graphs
o Tutorial on Type Analysis
o Typical Eli Usage Errors

Reference Manuals

o User Interface
o Eli products and parameters
o LIDO Reference Manual
o Typical Eli Usage Errors

Libraries

o Eli library routines
o Specification Module Library

Translation Tasks

o Lexical analysis specification
o Syntactic Analysis Manual
o Computation in Trees

Tools

o LIGA Control Language
o Debugging Information for LIDO
o Graphical ORder TOol

o FunnelWeb User's Manual

o Pattern-based Text Generator
o Property Definition Language
o Operator Identification Language
o Tree Grammar Specification Language
o Command Line Processing
o COLA Options Reference Manual

o Generating Unparsing Code

o Monitoring a Processor's Execution

Administration

o System Administration Guide
Mail Home

Pattern-based Text Generator

Previous Chapter Next Chapter Table of Contents

A Complete Example

In this chapter we demonstrate the use of PTG for translating a simple assignment language into C code. This example shows PTG techniques in the context of a complete translator specification. It especially demonstrates how PTG patterns are applied in LIDO specifications.

When this manual is read online, the browser's Run command can be used to obtain a copy of the complete specification for further experiments. You will get a Funnelweb file PtgEx.fw containing the content of this chapter (see FunnelWeb). It can be used for example to derive the specified processor by 

PtgEx.fw :exe >.

or to derive the set of files described below: 

PtgEx.fw :fwGen >.

Source Language Structure

Programs of this example language are sequences of assignments, input statements, and output statements, like

simple[1]== 

   input a;
   output a;
   x := a + 1;
   y := x - 5;
   output x;
   output y + x;

This macro is attached to a product file.

The values of variables and expressions are integral numbers. There are only the binary operators + and -. The above program is to be translated into the following C program:

simple.out[2]== 

   #include <stdio.h>

   int a = 0, x = 0, y = 0;

   int main (void) {

   scanf ("%d", &(a));
   printf ("%d\n",a);
   x = a+1;
   y = x-5;
   printf ("%d\n",x);
   printf ("%d\n",y+x);

   exit (0);
   }

This macro is attached to a product file.

The structure of the source programs is specified by the following concrete grammar:

Program.con[3]== 

   Program:     Statement*.

   Statement:   Variable ':=' Expression ';'.
   Statement:   'input' Variable ';'.
   Statement:   'output' Expression ';'.

   Expression:  Expression Operator Operand / Operand.

   Operator:    '+' / '-'.

   Operand:     Variable.
   Operand:     IntLit.
   Variable:    Ident.

This macro is attached to a product file.

In the tree grammar Expressions and Operands are represented both by Expression nodes, as specified by the type .sym rule:

Expr.sym[4]== 

   Expression ::= Operand .

This macro is attached to a product file.

Identifier tokens, number literals, and comments are denoted as in Pascal, as stated by the following type .gla specification:

Mini.gla[5]== 

   Ident:   PASCAL_IDENTIFIER
   IntLit:  PASCAL_INTEGER
            PASCAL_COMMENT

This macro is attached to a product file.

Program Frame

In this section the overall structure of the target programs is specified, the name of the output file is determined, and its contents is produced by a PTG output function. We first specify a pattern for target program frame:

Frame.ptg[6]== 

   Frame:
      "#include <stdio.h>\n\n"

      $1 /* declarations */

      "\nint main (void) {\n\n"

      $2 /* statements */

      "\nexit (0);\n}\n"

This macro is attached to a product file.

It has two insertion points, one for variable declarations and one for the statement sequence. The text to be inserted is obtained from the attributes Program.DeclPtg and Program.StmtPtg of type PTGNode It is shown below how they are computed. Here they are used as arguments of the Frame pattern application:

TransProg.lido[7]== 

   ATTR DeclPtg, StmtPtg: PTGNode;

   SYMBOL Program COMPUTE
     PTGOutFile (CatStrStr(SRCFILE, ".c"),
                 PTGFrame (THIS.DeclPtg, THIS.StmtPtg));
   END;

This macro is attached to a product file.

The above call of the output function PTGOutFile (see see Output Functions) writes to a file which name is derived from the file name of the source program by appending ".c". The concatenation function is imported from the specification module library. See String Concatenation of Specification Module Library: Common Problems, for further details on the Strings module.

TransProg.specs[8]== 

$/Tech/Strings.specs

This macro is attached to a product file.

The macro SRCFILE is obtained from the source program module, see Text Input of Library Reference Manual. That module is included automatically into every Eli specification. So, only it's interface has to be made known by the attribute evaluator:

TransProg.head[9]== 

#include "source.h"

This macro is attached to a product file.

Expressions

In this section we specify the translation of expressions. Target expressions are composed by applications of patterns that construct the text in a bottom-up way, i.e. from the leaves up to the complete expression.

In our simple example this translation is one-to-one as specified by the three patterns:

TransExpr.ptg[10]== 

   BinOperation: $ $ $
   Number:       $ int
   String:       $ string

This macro is attached to a product file.

The BinOperation pattern composes a left operand, an operator, and a right operand. The Number pattern just converts an integral number into text. The String pattern reproduces its argument. It is used here for output of operators and of identifiers.

These patterns are applied in computations of Expression contexts. Attributes Ptg of type PTGNode are used for the intermediate results:

TransExpr.lido[11]== 

   ATTR Ptg: PTGNode;

   RULE: Expression ::= Expression Operator Expression COMPUTE
      Expression[1].Ptg =
         PTGBinOperation (
            Expression[2].Ptg, Operator.Ptg, Expression[3].Ptg);
   END;

   RULE: Operator ::= '+' COMPUTE
      Operator.Ptg = PTGString ("+");
   END;

   RULE: Operator ::= '-' COMPUTE
      Operator.Ptg = PTGString ("-");
   END;

   RULE: Expression ::= Variable COMPUTE
      Expression.Ptg = Variable.Ptg;
   END;

   RULE: Expression ::= IntLit COMPUTE
      Expression.Ptg = PTGNumber (IntLit);
   END;

   RULE: Variable ::= Ident COMPUTE
      Variable.Ptg = PTGString (StringTable (Ident));
   END;

   ATTR Sym: int;

This macro is attached to a product file.

The last two computations use values obtained from named terminal symbols: IntLit supplies an integer value to the Number pattern, the token code of Ident is used to access the identifier string from the StringTable. The String pattern then reproduces the identifier.

Using LIDO CHAINs

In this sections the translation of statement sequences is shown. The LIDO CHAIN construct is used to compose a sequence of translated statements in left-to-right order.

Assignments, input statements, and output statements are translated by the following patterns:

TransStmt.ptg[12]== 

   AssignStmt:  $1 /* lhs */ " = " $2 /* rhs */ ";\n"
   InputStmt:   "scanf (\"%d\", &(" $1 /* variable */ "));\n"
   OutPutStmt:  "printf (\"%d\\n\","  $1 /* expression */ ");\n"

   Seq:         $  $

This macro is attached to a product file.

The last pattern is used to combine two text components (statement sequences in this case) into one (see See Output of Sequences).

A CHAIN named StmtChn is defined to compose PTGNodes in left-to-right order through the tree. The CHAIN starts in the root context with an empty text. The result is obtained at the end of the CHAIN by TAIL.StmtChn:

TransStChn.lido[13]== 

   CHAIN StmtChn: PTGNode;

   SYMBOL Program COMPUTE
      CHAINSTART HEAD.StmtChn = PTGNULL;
      SYNT.StmtPtg = TAIL.StmtChn;
   END;

This macro is attached to a product file.

In each of the three statement contexts the translation is produced by application of the corresponding pattern and appended to the end of the CHAIN using the Seq pattern:

TransStmt.lido[14]== 

   RULE: Statement ::= Variable ':=' Expression ';' COMPUTE
      Statement.StmtChn = PTGSeq (Statement.StmtChn,
         PTGAssignStmt (Variable.Ptg, Expression.Ptg));
   END;

   RULE: Statement ::= 'input' Variable ';' COMPUTE
      Statement.StmtChn = PTGSeq (Statement.StmtChn,
         PTGInputStmt (Variable.Ptg));
   END;

   RULE: Statement ::= 'output' Expression ';' COMPUTE
      Statement.StmtChn = PTGSeq (Statement.StmtChn,
         PTGOutPutStmt (Expression.Ptg));
   END;

This macro is attached to a product file.

Using LIDO CONSTITUENTS

In this section the construction of a declarator sequence is described using the LIDO CONSTITUENTS construct. It is also shown how a list with separators is produced, and how text is generated only once for each identifier that occurs in the program.

The source language does not have declarations; variables are introduced by just using them. Hence, we have to generate declarations in the target program, one for each variable that occurs in the source.

A variable may occur several times, but its declaration must be generated only once. For that purpose each variable is identified by a key which is associated to every occurrence of the variable.

This task is an instance of a name analysis task. We can use the AlgScope module of the module library to solve it:

ScopeLib.specs[15]== 

   $/Name/AlgScope.gnrc:inst

This macro is attached to a product file.

The computational role IdDefScope provided by that module is associated to the grammar symbol Variable:

Scope.lido[16]== 

   SYMBOL Variable INHERITS IdDefScope COMPUTE
      SYNT.Sym = TERM;
   END;

This macro is attached to a product file.

The computations of that module yield an attribute Variable.Key. It has the same value for each occurrence of a variable identifier.

We now associate a property IsDeclared to variables by a type .pdl specification:

Decl.pdl[17]== 

   IsDeclared: int;

This macro is attached to a product file.

It describes a state of that variable with respect to the translation process: A declaration is only produced if IsDeclared is not yet set, and then IsDeclared is set. The attribute Variable.DeclPtg takes the result, either the generated target declaration or PTGNULL.

VarDecl.lido[18]== 

   RULE: Variable ::= Ident COMPUTE
      Variable.DeclPtg =
         IF (GetIsDeclared (Variable.Key, 0),
             PTGNULL,
             ORDER (ResetIsDeclared (Variable.Key, 1),
                    PTGDeclVariable (StringTable (Ident))));
   END;

This macro is attached to a product file.

The pattern DeclVariable is used here to reproduce the variable name from the StringTable and to add the initialization to it: A single variable declarator is specified by the pattern

Decl.ptg[19]== 

   DeclVariable:  $ string " = 0"
   Declaration:   "int " $ ";\n"

This macro is attached to a product file.

The second pattern constitutes a complete declaration where the declarator list is inserted.

The declarator list is collected in the Program context using a CONSTITUENTS construct. It combines the PTGNode values of all Variable.DeclPtg attributes of the tree:

ProgDecl.lido[20]== 

   SYMBOL Program COMPUTE
      SYNT.DeclPtg =
         PTGDeclaration (
            CONSTITUENTS Variable.DeclPtg
            WITH (PTGNode, PTGCommaSeq, IDENTICAL, PTGNull));
   END;

This macro is attached to a product file.

The WITH clause of the CONSTITUENTS construct specifies the type of the combined values, PTGNode, and three functions which are applied to obtain the resulting value: PTGNull is the nullary predefined function producing no text. IDENTICAL is a unary function predefined in LIDO; it is applied to each Variable.DeclPtg attributes reproducing its value. PTGCommaSeq is a pattern function that combines two PTG texts, and separates them by a comma if none of them is empty. That pattern is specified using PTG's optional clause (see See Output of Sequences):

Comma.ptg[21]== 

   CommaSeq:  $ {", "} $

This macro is attached to a product file.

Previous Chapter Next Chapter Table of Contents