Line 19: | Line 19: | ||
== Solution == | == 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 <tt>cdk::node::Nil</tt> nodes and <tt>NULL</tt> 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: <tt>LINE</tt> is a macro corresponding to the source line and all nodes are either CDK nodes or derived from them (as in Compact). | ||
+ | <text> | ||
+ | %{ | ||
+ | #include <string> | ||
+ | #include <cdk/nodes/Node.h> | ||
+ | #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<i> INTEGER | ||
+ | %token<s> 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> | ||
[[category:Compilers]] | [[category:Compilers]] | ||
[[category:Teaching]] | [[category:Teaching]] |
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.
<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>
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> %{
%} %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>