|
|
| (2 intermediate revisions by the same user not shown) |
| Line 1: |
Line 1: |
| {{TOCright}}
| | #REDIRECT [[ist:Attribute Grammars/Exercise 9: Text relevance]] |
| == 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í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).
| |
| | |
| === Examples ===
| |
| * Frase com pontuação 2: '''=maria @maria !maria !@maria;'''
| |
| * Frase com pontuação 5: '''>@maria maria;'''
| |
| * Frase com pontuação 0.2: '''<@maria maria;'''
| |
| * Texto com resultado (2,2) (frase 2, pontuação 2)
| |
| ::::'''>@maria !maria;'''
| |
| ::::'''<!extraordinariamente amarela @finalmente;'''
| |
| ::::'''=!maria @maria maria;'''
| |
| | |
| === Questions ===
| |
| # 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.
| |
| | |
| == Solution ==
| |
| | |
| The problem has a the following solution.
| |
| | |
| <text>
| |
| | |
| </text>
| |
| | |
| All attributes are synthesized (S-attributed grammar).
| |
| | |
| === Semantic Tree ===
| |
| | |
| The following is the annotated tree for '''>@maria !maria;'''.
| |
| | |
| [[Image:text-relevance-t2-2011-2012.png]] | |
| | |
| === YACC implementation ===
| |
| | |
| A YACC specification can be obtained by adapting the grammar above:
| |
| <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; } }
| |
| ;
| |
| | |
| 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(); }
| |
| </text>
| |
| | |
| [[category:Compilers]]
| |
| [[category:Teaching]]
| |