|
|
| Line 1: |
Line 1: |
| == Problema ==
| | #REDIRECT [[ist:The YACC Parser Generator/Exercise 4]] |
| Pretende-se fazer uma calculadora de expressões lógicas usando a interpretação dirigida pela sintaxe. A calculadora utiliza 10 variáveis designadas pelos números 0 a 9 da variável ival associada ao token '''VAR'''. Os literais verdadeiro e falso são designados pelos tokens '''VERD''' e '''FALS''', respectivamente. O cálculo é efectuado através de uma sequência de expressões terminadas por ';' ou ',' consoante o resultado da expressão deva ser impresso ou não, respectivamente. A atribuição de uma expressão a uma variável é efectuada pelo operador '=', não associativo. As expressões utilizam os seguintes operadores, por ordem decrescente de prioridade:
| |
| | |
| * '''negação lógica:''' operador unário pré-fixado, não associativo, designado por '!'.
| |
| * '''E lógico:''' operador binário, associativo à esquerda, designado por '&'.
| |
| * '''OU inclusivo lógico:''' operador binário, associativo à esquerda, designado por '|'.
| |
| * '''OU exclusivo lógico:''' operador binário, associativo à direita, designado por ' ~ '.
| |
| * '''comparação:''' operadores binários, '==', e '!=', associativos à esquerda, designados por '''EQ''' e '''NE'''.
| |
| | |
| A prioridade dos operadores pode ser alterada utilizando parenteses curvos '(' e ')'. No início todos os registos têm o valor lógico falso.
| |
| | |
| Todas as rotinas auxiliares devem ser codificadas.
| |
| | |
| == The Lexical Analyzer (Flex) Specification ==
| |
| | |
| The lexical analyzer (<tt>vars.l</tt>) is very simple and limited to recognizing variable names (token '''tVAR'''), integers numbers (token '''tVAL'''), and the operators themselves.
| |
| <text>
| |
| %option noyywrap
| |
| %{
| |
| #include <cstdlib>
| |
| #include "y.tab.h" | |
| %}
| |
| %%
| |
| [[:digit:]] yylval.i = strtol(yytext, NULL, 10); return tVAR; | |
| "VERD" yylval.i = !0; return tVAL;
| |
| "FALS" yylval.i = 0; return tVAL;
| |
| [!&|~<>()=] return *yytext;
| |
| "==" return tEQ;
| |
| "!=" return tNE;
| |
| .|\n ; /* ignore all the rest */
| |
| %%
| |
| </text>
| |
| | |
| == The Syntactic Analyzer (YACC) Specification ==
| |
| | |
| The syntactic analyzer will be built to immediately compute the expressions in a syntax-directed fashion as they occur. It is, thus, important to use trees that build nodes as the expressions occur (left-recursive grammars). If the grammar were right-recursive, the last node would be the first to be built and the (syntax-directed) evaluation would be from the last expression to the first.
| |
| <text>
| |
| %{
| |
| #include <iostream>
| |
| #include <string>
| |
| #include <map>
| |
| namespace { int vars[10]; }
| |
| %}
| |
| | |
| %union { int i; }
| |
| | |
| %token tEQ tNE
| |
| %token<i> tVAR tVAL
| |
| %type<i> expr lval
| |
| | |
| %right '='
| |
| %left tEQ tNE
| |
| %right '~'
| |
| %left '|'
| |
| %left '&'
| |
| %nonassoc '!'
| |
| | |
| %%
| |
| list: stmt
| |
| | list stmt
| |
| ;
| |
| | |
| stmt: expr ','
| |
| | expr ';' { std::cout << ($1 ? "true" : "false") << std::endl; }
| |
| ;
| |
| | |
| expr: tVAL { $$ = $1; }
| |
| | lval { $$ = vars[$1]; }
| |
| | lval '=' expr { $$ = vars[$1] = $3; }
| |
| | expr '~' expr { $$ = $1 != $3; }
| |
| | expr '|' expr { $$ = $1 | $3; }
| |
| | expr '&' expr { $$ = $1 & $3; }
| |
| | expr tEQ expr { $$ = $1 == $3; }
| |
| | expr tNE expr { $$ = $1 != $3; }
| |
| | '!' expr { $$ = !$2; }
| |
| | '(' expr ')' { $$ = $2; }
| |
| ;
| |
| | |
| lval : tVAR { $$ = $1; }
| |
| ;
| |
| | |
| %%
| |
| extern int yylex();
| |
| extern int yyparse();
| |
| void yyerror(char *s) { std::cout << s << std::endl; }
| |
| int main() { yyparse(); }
| |
| </text>
| |
| | |
| == How to Compile? ==
| |
| | |
| The Flex specification is processed as follows (the file <tt>lex.yy.c</tt> is produced):
| |
| | |
| flex vars.l
| |
| | |
| The YACC specification is processed as follows (files <tt>y.tab.h</tt>, needed by the Flex-generated code, and <tt>y.tab.c</tt>):
| |
| | |
| yacc -dtv vars.y
| |
| | |
| Compiling the C/C++ code (it is C++ simply because we programmed the extra code in that language):
| |
| | |
| g++ -c lex.yy.c
| |
| g++ -c y.tab.c
| |
| g++ -o vars y.tab.o lex.yy.o
| |
| [[category:Compiladores]]
| |
| [[category:Ensino]]
| |