Wiki**3

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). <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); }
    ;

decl: INT ID { $$ = new DeclarationNode(LINE, $1, new cdk::node::expression::Identifier(LINE, $2), NULL); }

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

init: /* empty */ { $$ = NULL; /* must match third argument in DeclarationNode */ }

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

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

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

expr: INTEGER { $$ = new cdk::node::expression::Integer(LINE, $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); }
   ;

</text>