(→How to Compile?) |
(→Problema) |
||
Line 2: | Line 2: | ||
== Problema == | == Problema == | ||
− | + | Uma máquina reconhece os símbolos '''0''', '''1''', '''*''' e '''#'''. Os símbolos '''0''' e '''1''' são organizados em sequências numéricas separadas umas das outras por '''*''' ou '''#'''. Se a sequência numérica começar por '''0''', então o seu valor inicial é 2 e duplica a cada '''0''' adicional e incrementa em uma unidade a cada '''1''' adicional. Se a sequência numérica for começar por '''1''', então o seu valor inicial é 1, sendo incrementada de 2 a cada '''0''' adicional e duplicada a cada '''1''' adicional. O símbolo '''*''' corresponde ao operador binário “mínimo” e o símbolo '''#''' ao operador binário “máximo” (ambos associativos à esquerda e com a mesma precedência). | |
− | Escreva uma especificação YACC para o problema acima. Codifique toda a especificação (incluindo as zonas de declarações e de regras) e todas as funções auxiliares. '''Não utilizar variáveis globais.''' | + | Exemplo: à sequência '''00100*1100#0010''' corresponde ao valor 10 (decimal). |
+ | |||
+ | Escreva uma especificação YACC para o problema acima. Codifique toda a especificação (incluindo as zonas de declarações e de | ||
+ | regras) e todas as funções auxiliares. '''Não utilizar variáveis globais.''' | ||
== The Lexical Analyzer (Flex) Specification == | == The Lexical Analyzer (Flex) Specification == |
Uma máquina reconhece os símbolos 0, 1, * e #. Os símbolos 0 e 1 são organizados em sequências numéricas separadas umas das outras por * ou #. Se a sequência numérica começar por 0, então o seu valor inicial é 2 e duplica a cada 0 adicional e incrementa em uma unidade a cada 1 adicional. Se a sequência numérica for começar por 1, então o seu valor inicial é 1, sendo incrementada de 2 a cada 0 adicional e duplicada a cada 1 adicional. O símbolo * corresponde ao operador binário “mínimo” e o símbolo # ao operador binário “máximo” (ambos associativos à esquerda e com a mesma precedência).
Exemplo: à sequência 00100*1100#0010 corresponde ao valor 10 (decimal).
Escreva uma especificação YACC para o problema acima. Codifique toda a especificação (incluindo as zonas de declarações e de regras) e todas as funções auxiliares. Não utilizar variáveis globais.
The lexical analyzer (numseq.l) is very simple and limited to recognizing the indispensable tokens.
%option noyywrap
%{
#include <string>
#include "numseq.tab.h"
%}
%%
[01*#] return *yytext;
.|\n ; /* ignore the rest */
%%
The syntactic analyzer (numseq.y) will be built to immediately compute the maximum values in a syntax-directed fashion (as they occur). Note that the use of numeric limits is correct, but other such names would be acceptable (e.g. MAXDOUBLE).
%{
#include <limits>
#include <iostream>
extern int yylex();
inline void yyerror(const char *msg) { std::cerr << msg << std::endl; }
%}
%union { int i; }
%type <i> seq0 seq1 expr
%left '*' '#'
%%
top : expr { std::cout << $1 << std::endl; }
;
expr : seq0 { $$ = $1; }
| seq1 { $$ = $1; }
| expr '#' expr { $$ = std::max($1, $3); }
| expr '*' expr { $$ = std::min($1, $3); }
;
seq0 : '0' { $$ = 2; }
| seq0 '0' { $$ = $1 * 2; }
| seq0 '1' { $$ = $1 + 1; }
;
seq1 : '1' { $$ = 1; }
| seq1 '0' { $$ = $1 + 2; }
| seq1 '1' { $$ = $1 * 2; }
;
%%
extern int yyparse();
int main() { return yyparse(); }
The Flex specification is processed as follows (the file lex.yy.c is produced):
flex numseq.l
The YACC specification is processed as follows (files numseq.tab.h, needed by the Flex-generated code, and numseq.tab.c):
bison -dtv numseq.y
Compiling the C/C++ code (it is C++ simply because we programmed the extra code in that language):
g++ -std=c++17 -c lex.yy.c g++ -std=c++17 -c numseq.tab.c g++ -o numseq numseq.tab.o lex.yy.o