(→YACC implementation) |
|||
(2 intermediate revisions by the same user not shown) | |||
Line 25: | Line 25: | ||
The problem has a the following solution. | The problem has a the following solution. | ||
− | <text> | + | <source lang="text"> |
− | </ | + | </source> |
All attributes are synthesized (S-attributed grammar). | All attributes are synthesized (S-attributed grammar). | ||
Line 40: | Line 40: | ||
A YACC specification can be obtained by adapting the grammar above: | A YACC specification can be obtained by adapting the grammar above: | ||
− | <text> | + | <source lang="text"> |
%{ | %{ | ||
#include <string> | #include <string> | ||
Line 84: | Line 84: | ||
extern int yyparse(); | extern int yyparse(); | ||
int main() { return yyparse(); } | int main() { return yyparse(); } | ||
− | </ | + | </source> |
− | [[category: | + | A compatible (simplified) lexical specification is as follows: |
− | [[category: | + | |
+ | <source lang="text"> | ||
+ | %option debug noyywrap | ||
+ | %{ | ||
+ | #include <string> | ||
+ | #include "y.tab.h" | ||
+ | %} | ||
+ | %% | ||
+ | [[:alpha:]]+ yylval.s = new std::string(yytext); return tWORD; | ||
+ | [<=>;@!] return *yytext; | ||
+ | .|\n ; | ||
+ | %% | ||
+ | </source> | ||
+ | |||
+ | [[category:Compiladores]] | ||
+ | [[category:Ensino]] |
(appeared in Teste 2 2011/2012)
Pretende-se criar uma gramática atributiva que processe um texto (lista de frases) e calcule no símbolo inicial qual a frase (índice da frase no texto, com início em zero) com maior pontuação. O cálculo da pontuação da frase é definido pelo operador no início de cada linha: > significa que a pontuação da frase é o máximo da pontuação das suas palavras; = significa que a pontuação corresponde ao número de palavras significativas da frase; < significa que a pontuação da frase é o mínimo da pontuação das suas palavras. As palavras são representadas pelo token tWORD que possui um atributo str que transporta o valor correspondente ao seu conteúdo. As frases são separadas umas das outras pelo token ;. O operador de palavra prefixo @ inverte o valor associado a uma dada palavra. O operador ! impõe uma pontuação de 0 a uma palavra (não se considera a palavra assim marcada para o cálculo de nenhuma pontuação).
The problem has a the following solution.
All attributes are synthesized (S-attributed grammar).
The following is the annotated tree for >@maria !maria;.
File:Text-relevance-t2-2011-2012.png
A YACC specification can be obtained by adapting the grammar above:
%{
#include <string>
#include <iostream>
#include <algorithm>
inline void yyerror(const char *msg) { std::cout << msg << std::endl; }
%}
%union { std::string *s; double d; std::pair<int, double> *p; }
%token<s> tWORD
%type<d> eline lline gline line word
%type<p> lines
%%
file: lines { std::cout << "RESULT: " << $1->first << ":" << $1->second << std::endl; }
lines: line { $$ = new std::pair<int,double>(0, $1); }
| lines line { $$ = $1; if ($2 > $1->second) { $$->first++; $$->second = $2; } }
;
line: '=' eline ';' { $$ = $2; }
| '<' lline ';' { $$ = $2; }
| '>' gline ';' { $$ = $2; }
;
eline : word { $$ = $1 ? 1 : 0; }
| eline word { $$ = $1 + ($2 ? 1 : 0); }
;
lline : word { $$ = $1; }
| lline word { if ($1) { $$ = $2 ? std::min($1, $2) : $1; } else { $$ = $2; } }
;
gline : word { $$ = $1; }
| gline word { $$ = $2 ? std::max($1, $2) : $1; }
;
word : tWORD { $$ = $1->length(); delete $1; }
| '@' word { $$ = $2 ? 1/$2 : 0; }
| '!' word { $$ = 0; }
;
%%
extern int yylex();
extern int yyparse();
int main() { return yyparse(); }
A compatible (simplified) lexical specification is as follows:
%option debug noyywrap
%{
#include <string>
#include "y.tab.h"
%}
%%
[[:alpha:]]+ yylval.s = new std::string(yytext); return tWORD;
[<=>;@!] return *yytext;
.|\n ;
%%