Revision as of 17:36, 27 May 2022

Problema

Considere uma linguagem constituída por uma sequência de intervalos, possivelmente vazia. Os intervalos são definidos por valores reais (os limites inferior e superior são separados por :). Os intervalos são separados entre si por vírgulas (,). A representação dos números reais é como em C++. Pretende-se determinar a largura do menor intervalo da sequência, ignorando os intervalos inválidos (em que o limite superior é menor que o limite inferior).

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 (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 (YACC) Specification

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(); }

How to Compile?

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