The YACC Parser Generator/Exercise 7 - Revision history

Root: Redirected page to ist:The YACC Parser Generator/Exercise 7

2018-12-05T23:43:49Z

Redirected page to ist:The YACC Parser Generator/Exercise 7

← Older revision		Revision as of 23:43, 5 December 2018
Line 1:		Line 1:
	~~{{TOCright}}~~		#REDIRECT [[ist:The YACC Parser Generator/Exercise 7]]
	~~== 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 ('''minint.l''') is very simple and limited to recognizing the indispensable tokens.~~
	~~<text>~~
	~~%option noyywrap~~
	%{
	#~~include <string>~~
	~~#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 ('''minint.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''').
	~~<text>~~
	%{
	~~#include <limits>~~
	~~#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 << "shortest interval: " << $1 << std::endl; }~~
	~~\| /* empty */ { std::cout << "empty sequence" << std::endl; }~~
	;

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

	~~interval : tDOUBLE ':' tDOUBLE { $$ = $1 > $3 ? std::numeric_limits<double>::max() : $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 minint.l~~

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

	~~byacc -dtv minint.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 minint y.tab.o lex.yy.o~~

	~~[[category:Compiladores]]~~
	~~[[category:Ensino~~]]

Root: Created page with "{{TOCright}} == Problema == Considere uma linguagem constituída por uma sequência de intervalos, possivelmente vazia. Os intervalos são definidos por valores reais (os li..."

2016-06-21T18:53:43Z

Created page with "{{TOCright}} == Problema == Considere uma linguagem constituída por uma sequência de intervalos, possivelmente vazia. Os intervalos são definidos por valores reais (os li..."

New page

{{TOCright}}
== 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 ('''minint.l''') is very simple and limited to recognizing the indispensable tokens.
<text>
%option noyywrap
%{
#include <string>
#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 ('''minint.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''').
<text>
%{
#include <limits>
#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 << "shortest interval: " << $1 << std::endl; }
| /* empty */ { std::cout << "empty sequence" << std::endl; }
;

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

interval : tDOUBLE ':' tDOUBLE { $$ = $1 > $3 ? std::numeric_limits<double>::max() : $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 minint.l

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

byacc -dtv minint.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 minint y.tab.o lex.yy.o

[[category:Compiladores]]
[[category:Ensino]]