(Created page with "{{TOCright}} == Problem (in Portuguese) == (appeared in Teste 2 2011/2012) Pretende-se criar uma gramática atributiva que processe um texto (lista de frases) e calcule no sím...") |
|||
(4 intermediate revisions by the same user not shown) | |||
Line 17: | Line 17: | ||
=== Questions === | === Questions === | ||
# Identifique a gramática atributiva correspondente ao problema. Descreva o significado e o tipo de cada atributo. Que tipo de gramática obteve? | # Identifique a gramática atributiva correspondente ao problema. Descreva o significado e o tipo de cada atributo. Que tipo de gramática obteve? | ||
− | # | + | # Apresente a árvore de sintaxe decorada e o grafo de dependências correspondente à análise do texto com a seguinte frase (resultado da execução: frase 0, pontuação 0.2). |
+ | #:::'''>@maria !maria;''' | ||
# Escreva uma especificação YACC que implemente a gramática descrita em 1. Codifique toda a especificação (incluindo as zonas de declarações e de regras) e todas as funções auxiliares. Pode utilizar estruturas de dados C++, tais como '''std::string''', '''std::pair''', etc. Não deve utilizar variáveis globais. | # Escreva uma especificação YACC que implemente a gramática descrita em 1. Codifique toda a especificação (incluindo as zonas de declarações e de regras) e todas as funções auxiliares. Pode utilizar estruturas de dados C++, tais como '''std::string''', '''std::pair''', etc. Não deve utilizar variáveis globais. | ||
Line 24: | 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 39: | 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 <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; } } | ||
+ | ; | ||
− | [[category: | + | line: '=' eline ';' { $$ = $2; } |
− | [[category: | + | | '<' 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(); } | ||
+ | </source> | ||
+ | |||
+ | A compatible (simplified) lexical specification is as follows: | ||
+ | |||
+ | <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 ;
%%