Difference between revisions of "Attribute Grammars/Exercise 9: Text relevance"

Revision as of 14:40, 15 June 2012

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

File: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 ~~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> A compatible (simplified) lexical specification is as follows: <text> %option debug noyywrap %{
include <string>

include "y.tab.h"
%} %% alpha:+ yylval.s = new std::string(yytext); return tWORD; [<=>;@!] return *yytext; .|\n ; %% </text>