Revision as of 20:19, 11 May 2008

The Problem (in Portuguese)

Considere a seguinte gramárica (ε representa a produção nula), onde os operadores WRITE (não associativo), = (associativo à direita) e + (associativo à esquerda) têm precedências crescentes.

1. Construa a árvore sintáctica, utilizando as classes disponibilizadas na CDK (subclasses de cdk::node::Node).
2. Traduza a árvore sintáctica para um programa em C, utilizando o padrão de desenho Visitor (mantenha informação sobre símbolos utilizando as classes cdk::Symbol e cdk::SymbolTable).

<text> prog -> decls exprs '.'

decls -> ε | decls decl ';'

decl -> INT ID | STR ID init

init -> ε | '=' STRING

exprs -> expr | exprs ',' expr

expr -> INTEGER | ID | ID '=' expr | expr '+' expr | WRITE expr </text>

Solution

In the answer to this exercise, we will consider the node tree defined as shown below (in a YACC-like syntax). Note that careful attention must be given to the choices between cdk::node::Nil nodes and NULL pointers (these can be tested for performing special/exceptional actions, while Nil nodes are more useful when tests are undesirable and uniform behavior on the part of the code generator is desired).

We follow the same nomenclature used in the Compact compiler: LINE is a macro corresponding to the source line and all nodes are either CDK nodes or derived from them (as in Compact).

Completing (and, possibly, correcting) the following code, so that it runs, is left as an exercise. <text> %{

1. include <string>
2. include <cdk/nodes/Node.h>
3. include <cdk/nodes/expressions/Expression.h>

%} %union {

 int i;
 std::string *s;
 cdk::node::Node *n;
 cdk::node::expression::Expression *e;

} %token INT STR WRITE %token INTEGER %token ID STRING %type<e> init expr %type<n> prog decls exprs decl init expr %% prog: decls exprs '.' { $$ = new ProgramNode(LINE, $1, $2); }

decls: /* empty */ { $$ = new cdk::node::Nil(LINE); }

    | decls decl ';' { $$ = new cdk::node::Sequence(LINE, $2, $1); }
    ;

   | STR ID init { $$ = new DeclarationNode(LINE, STR, new cdk::node::expression::Identifier(LINE, $2), $3);   }
   ;

   | '=' STRING  { $$ = $2; }
   ;

    | exprs ',' expr   { $$ = new cdk::node::Sequence(LINE, $2, $1); }
    ;

   | ID                { $$ = new cdk::node::expression::Identifier(LINE, $1); }
   | ID '=' expr       { $$ = new AssignmentNode(LINE, $1, $3); }
   | expr '+' expr     { $$ = new cdk::node::expression::ADD(LINE, $1, $3); }
   | WRITE expr        { $$ = new WriteNode(LINE, $2); }
   ;

In this code we assume that each declaration node contains two attributes: an integer, representing the declaration's type; a node, representing the identifier being declared; and an optional expression (NULL if that is the case), representing the initial value of the variable being declared. Likewise, assignment nodes have two children: an identifier, corresponding to the left-value; and the expression to be assigned. Write nodes have a single child (the expression to be printed).