Wiki**3

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 maior 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 (maxint.l) is very simple and limited to recognizing the indispensable tokens. <text> %option noyywrap %{

1. include <string>
2. include "y.tab.h"

%} %%

[0-9]*\.[0-9]+([Ee][-+]?[0-9]+)? yylval.d = std::stod(yytext); return tDOUBLE; [0-9]+\.[0-9]*([Ee][-+]?[0-9]+)? yylval.d = std::stod(yytext); return tDOUBLE; [0-9]+([Ee][-+]?[0-9]+) yylval.d = std::stod(yytext); return tDOUBLE;

[,:] return *yytext;

.|\n  ; /* ignore the rest */

%% </text>

The Syntactic Analyzer (YACC) Specification

The syntactic analyzer (maxint.y) will be built to immediately compute the maximum values in a syntax-directed fashion (as they occur). <text> %{

1. include <limits>
2. include <iostream>

inline void yyerror(const char *msg) { std::cerr << msg << std::endl; } %}

%union { double d; }

%token <d> tDOUBLE %type <d> sequence interval

%%

top : sequence { std::cout << "longest interval: " << $1 << std::endl; }

   | /* empty */ { std::cout << "empty sequence"           << std::endl; }
   ;

sequence : interval { $$ = $1; }

        | sequence ',' interval { $$ = std::max($1, $3); }
        ;

interval : tDOUBLE ':' tDOUBLE { $$ = $1 > $3 ? -1 : $3 - $1; }

        ;

%% extern int yylex(); extern int yyparse(); int main() { return yyparse(); } </text>

How to Compile?

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

 flex maxint.l

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

 byacc -dtv maxint.y

Compiling the C/C++ code (it is C++ simply because we programmed the extra code in that language):

 g++ -std=c++11 -c lex.yy.c
 g++ -std=c++11 -c y.tab.c
 g++ -o maxint y.tab.o lex.yy.o