Wiki**3

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.

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:

%{
#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    ;
%%