Wiki**3

Problema

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 (vars.l) is very simple and limited to recognizing variable names (token tVAR), integers numbers (token tVAL), and the operators themselves.

%option noyywrap
%{
#include <string>
#include "y.tab.h"
%}
%%
[[:digit:]]     yylval.i = std::stoi(yytext); 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 */
%%

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.

%{
#include <iostream>
#include <string>
extern int yylex();
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 yyparse();
void yyerror(const char *s) { std::cout << s << std::endl; }
int main() { yyparse(); }

How to Compile?

The Flex specification is processed as follows (the file lex.yy.c is produced):

 flex vars.l

The YACC specification is processed as follows (files y.tab.h, needed by the Flex-generated code, and y.tab.c):

 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