Difference between revisions of "Semantic Analysis/Exercise 01"

From Wiki**3

< Semantic Analysis
(Created page with "{{TOCright}} == The Problem (in Portuguese) == Considere o analisador sintáctico da linguagem Simple (abaixo). Considere que as variáveis só podem ser utilizadas em expressõe...")
 
(→‎Solution)
 
(11 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
{{TOCright}}
 
{{TOCright}}
−
== The Problem (in Portuguese) ==
+
== Problema ==
−
Considere o analisador sintáctico da linguagem Simple (abaixo). Considere que as variáveis só podem ser utilizadas em expressões (ID ou ASSIGN) depois de declaradas (LET); que variáveis com o mesmo nome não podem ser declaradas no mesmo bloco; e que os tokens INT e STRING correspondem a  literais, respectivamente, dos tipos inteiro e cadeia de caracteres.
+
Considere o analisador sintáctico da linguagem Let (abaixo). Considere que as variáveis só podem ser utilizadas em expressões ('''tID''' ou '''tASSIGN''') depois de declaradas ('''tLET'''); que variáveis com o mesmo nome não podem ser declaradas no mesmo bloco; e que os tokens '''tINT''' e '''tSTRING''' correspondem a  literais, respectivamente, dos tipos inteiro e cadeia de caracteres.
  
−
Traduza para C (visitor em C++) e valide semanticamente (visitor em C++) a árvore sintáctica abstracta, emitindo mensagens se forem detectados erros de validação semântica. Utilize as classes da CDK (cdk::SymbolTable, nós, etc.) na resolução do problema. Pode ser útil definir outras classes auxiliares de validação de tipos (Symbol, etc.). Nos visitors, implemente apenas os métodos process. O acesso às sub-árvores de nós binários faz-se através dos métodos left() e right() e às sub-árvores de nós unários através do método argument().
+
Traduza para C (visitor em C++: '''c_writer''') e valide semanticamente (visitor em C++: '''type_checker''') a árvore sintáctica abstracta, emitindo mensagens se forem detectados erros de validação semântica. Utilize as classes da CDK ('''cdk::symbol_table''', nós, etc.) na resolução do problema. Pode ser útil definir outras classes auxiliares de validação de tipos ('''symbol''', etc.). Nos visitors, implemente apenas os métodos '''do_XXX''' (onde '''XXX''' é o nome da classe do nó). O acesso às sub-árvores de nós binários faz-se através dos métodos '''left()''' e '''right()''' e às sub-árvores de nós unários através do método '''argument()'''.
  
−
<text>
+
<source lang="text">
 
%token tSTART tBLOCK tEND tLET tPRINT tASSIGN
 
%token tSTART tBLOCK tEND tLET tPRINT tASSIGN
 
%token <str>    tID tSTRING
 
%token <str>    tID tSTRING
Line 13: Line 13:
 
%right tASSIGN
 
%right tASSIGN
 
%left '-'
 
%left '-'
−
%nonassoc tUMINUS
+
%nonassoc tUNARY
  
 
%%
 
%%
−
program : tSTART block  { _compiler->ast(new ProgramNode(LINE, $2)); }
+
program : tSTART block  { _compiler->ast(new program_node(LINE, $2)); }
 
         ;
 
         ;
−
block  : tBLOCK decls instrs tEND { $$ = new BlockNode(LINE, $2, $3); }
+
block  : tBLOCK decls instrs tEND { $$ = new block_node(LINE, $2, $3); }
 
         ;
 
         ;
−
decls  : decl                   { $$ = new Sequence(LINE, $1); }
+
decls  : decl                     { $$ = new cdk::sequence_node(LINE, $1); }
−
         | decls decl             { $$ = new Sequence(LINE, $2, $1); }
+
         | decls decl               { $$ = new cdk::sequence_node(LINE, $2, $1); }
 
         ;
 
         ;
−
decl    : tLET tID             { $$ = new DeclNode(LINE, $2); }
+
decl    : tLET tID           { $$ = new declaration_node(LINE, $2); }
 
         ;
 
         ;
−
instrs  : instr                   { $$ = new Sequence(LINE, $1); }
+
instrs  : instr                   { $$ = new cdk::sequence_node(LINE, $1); }
−
         | instrs instr           { $$ = new Sequence(LINE, $2, $1); }
+
         | instrs instr             { $$ = new cdk::sequence_node(LINE, $2, $1); }
 
         ;
 
         ;
−
instr  :                ';'     { $$ = new Nil(LINE); }
+
instr  :                ';'       { $$ = new cdk::nil_node(LINE); }
−
         | block          ';'     { $$ = $1; }
+
         | block          ';'       { $$ = $1; }
−
         | tPRINT expr    ';'     { $$ = new PrintExpNode(LINE, $2); }
+
         | tPRINT expr    ';'       { $$ = new print_exp_node(LINE, $2); }
−
         | tPRINT tSTRING ';'     { $$ = new PrintStrNode(LINE, $2); }
+
         | tPRINT tSTRING ';'       { $$ = new print_str_node(LINE, $2); }
 
         ;
 
         ;
−
expr    : tID                     { $$ = new Identifier(LINE, $1); }
+
expr    : tID                     { $$ = new rvalue_node(LINE, new cdk::variable_node(LINE, $1)); }
−
         | tINT                   { $$ = new Integer(LINE, $1); }
+
         | tINT                     { $$ = new cdk::integer_node(LINE, $1); }
−
         | tID tASSIGN expr       { $$ = new AssignmentNode(LINE, $1, $3); }
+
         | expr '-' expr            { $$ = new cdk::sub_node(LINE, $1, $3); }
−
         | expr '-' expr           { $$ = new SUB(LINE, $1, $3); }
+
         | '-' expr %prec tUNARY    { $$ = new cdk::neg_node(LINE, $2); }
−
         | '-' expr %prec tUMINUS  { $$ = new NEG(LINE, $2); }
+
         | tID tASSIGN expr         { $$ = new assignment_node(LINE, $1, $3); }
 
         ;
 
         ;
 
%%
 
%%
−
</text>
+
</source>
  
 
== Solution ==
 
== Solution ==
  
−
[[category:Compilers]]
+
The solution is straightforward and very similar to that obtained for the [[Semantic Analysis/The Tiny language: semantic analysis example and C generation|the Tiny language]]. The main difference is in block generation ('''c_writer'''): '''_symtab.push();''' and '''_symtab.pop();''' are needed at the beginning and ending of the generation method.
−
[[category:Teaching]]
+
 
 +
[[category:Compiladores]]
 +
[[category:Ensino]]

Latest revision as of 19:18, 2 June 2023

Problema

Considere o analisador sintáctico da linguagem Let (abaixo). Considere que as variáveis só podem ser utilizadas em expressões (tID ou tASSIGN) depois de declaradas (tLET); que variáveis com o mesmo nome não podem ser declaradas no mesmo bloco; e que os tokens tINT e tSTRING correspondem a literais, respectivamente, dos tipos inteiro e cadeia de caracteres.

Traduza para C (visitor em C++: c_writer) e valide semanticamente (visitor em C++: type_checker) a árvore sintáctica abstracta, emitindo mensagens se forem detectados erros de validação semântica. Utilize as classes da CDK (cdk::symbol_table, nós, etc.) na resolução do problema. Pode ser útil definir outras classes auxiliares de validação de tipos (symbol, etc.). Nos visitors, implemente apenas os métodos do_XXX (onde XXX é o nome da classe do nó). O acesso às sub-árvores de nós binários faz-se através dos métodos left() e right() e às sub-árvores de nós unários através do método argument(). 

%token tSTART tBLOCK tEND tLET tPRINT tASSIGN
%token <str>     tID tSTRING
%token <i>       tINT 
%type <node>     program block decl instr
%type <sequence> decls instrs
%right tASSIGN
%left '-'
%nonassoc tUNARY

%%
program : tSTART block  { _compiler->ast(new program_node(LINE, $2)); }
        ;
block   : tBLOCK decls instrs tEND { $$ = new block_node(LINE, $2, $3); }
        ;
decls   : decl                     { $$ = new cdk::sequence_node(LINE, $1); }
        | decls decl               { $$ = new cdk::sequence_node(LINE, $2, $1); }
        ;
decl    : tLET tID	           { $$ = new declaration_node(LINE, $2); }
        ;
instrs  : instr                    { $$ = new cdk::sequence_node(LINE, $1); }
        | instrs instr             { $$ = new cdk::sequence_node(LINE, $2, $1); }
        ;
instr   :                ';'       { $$ = new cdk::nil_node(LINE); }
        | block          ';'       { $$ = $1; }
        | tPRINT expr    ';'       { $$ = new print_exp_node(LINE, $2); }
        | tPRINT tSTRING ';'       { $$ = new print_str_node(LINE, $2); }
        ;
expr    : tID                      { $$ = new rvalue_node(LINE, new cdk::variable_node(LINE, $1)); }
        | tINT                     { $$ = new cdk::integer_node(LINE, $1); }
        | expr '-' expr            { $$ = new cdk::sub_node(LINE, $1, $3); }
        | '-' expr %prec tUNARY    { $$ = new cdk::neg_node(LINE, $2); }
        | tID tASSIGN expr         { $$ = new assignment_node(LINE, $1, $3); }
        ;
%%

Solution

The solution is straightforward and very similar to that obtained for the the Tiny language. The main difference is in block generation (c_writer): _symtab.push(); and _symtab.pop(); are needed at the beginning and ending of the generation method.

Retrieved from "https://web.tecnico.ulisboa.pt/~david.matos/w/pt/index.php?title=Semantic_Analysis/Exercise_01&oldid=15762"