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. Considere a frase: >@maria !maria; Apresente a árvore de sintaxe decorada e o grafo de dependências correspondente à análise desta frase (resultado da execução: frase 0, pontuação 0.2).
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>

</text>