The YACC Parser Generator/Exercise 9

Problema

Uma máquina reconhece os símbolos de 0 a 9, %, + e " (aspa). Os símbolos de 0 a 9 são organizados em sequências, possivelmente delimitadas por ". Se a sequência numérica não estiver delimitada, então o seu valor é simplesmente o do seu maior dígito (em base 10). Sequências numéricas delimitadas têm o valor correspondente ao número indicado pelos dígitos em base 10. O símbolo % pode ser usado como prefixo de uma sequência numérica delimitada: nesse caso, o valor da sequência é 1/100 do indicado pela sequência original. O operador + calcula o valor da soma dos seus argumentos (este operador é associativo à esquerda).

Exemplo: à sequência 1234+"26"+%”50” corresponde o valor 4+26+0.50 = 30.50.

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"
%}
%%
[0-9]                 yylval.d = std::stoi(yytext); return tDIG;
[%+"]                 return *yytext;
.|\n                  ; /* ignore the rest */
%%

The Syntactic Analyzer (YACC) Specification

The syntactic analyzer (numseq.y) computes the various segments and combines them.

%{
#include <limits>
#include <iostream>
extern int yylex();
inline void yyerror(const char *msg) { std::cerr << msg << std::endl; }
%}

%union { double d; }
%token <d> tDIG
%type <d> seqd seqn exprs expr

%%

top  : exprs             { std::cout << $1 << std::endl; }
     ;

exprs : expr             { $$ = $1;      }
      | exprs '+' expr   { $$ = $1 + $3; }

expr :     '"' seqd '"'  { $$ = $2; }
     | '%' '"' seqd '"'  { $$ = $3 / 100.0; }
     |         seqn      { $$ = $1; }
     ;

seqd :      tDIG { $$ = $1; }
     | seqd tDIG { $$ = $1 * 10 + $2; }
     ;

seqn :      tDIG { $$ = $1; }
     | seqn tDIG { $$ = std::max($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