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

1. Identifique a gramática atributiva correspondente ao problema. Descreva o significado e o tipo de cada atributo. Que tipo de gramática obteve?
2. 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;

3. 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;.

YACC implementation

A YACC specification can be obtained by adapting the grammar above: <text> %{

1. include <string>
2. include <iostream>
3. 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 tWORD %type<d> eline lline gline line word

%type

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>