Attribute Grammars/Exercise 9: Text relevance - Revision history

Root: Redirected page to ist:Attribute Grammars/Exercise 9: Text relevance

2018-12-05T23:17:19Z

Redirected page to ist:Attribute Grammars/Exercise 9: Text relevance

← Older revision		Revision as of 23:17, 5 December 2018
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>~~

	~~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>~~

	~~[[category~~:~~Compiladores]]~~
	~~[[category:Ensino~~]]

Root at 14:26, 6 April 2015

2015-04-06T14:26:31Z

← Older revision		Revision as of 14:26, 6 April 2015
Line 101:		Line 101:
	</text>		</text>

	[[category:~~Compilers~~]]		[[category:Compiladores]]
	[[category:~~Teaching~~]]		[[category:Ensino]]

Root: /* YACC implementation */

2012-06-15T12:40:24Z

YACC implementation

@@ Line 84: / Line 84: @@
 extern int yyparse();
 int main() { return yyparse(); }
 </text>
 [[category:Compilers]]
 [[category:Teaching]]

Root: /* YACC implementation */

2012-06-15T12:39:33Z

YACC implementation

@@ Line 41: / Line 41: @@
 A YACC specification can be obtained by adapting the grammar above:
 <text>
 </text>
 [[category:Compilers]]
 [[category:Teaching]]

Root: /* Questions */

2012-06-05T13:23:08Z

Questions

← Older revision		Revision as of 13:23, 5 June 2012
Line 17:		Line 17:
	=== Questions ===		=== Questions ===
	# Identifique a gramática atributiva correspondente ao problema. Descreva o significado e o tipo de cada atributo. Que tipo de gramática obteve?		# Identifique a gramática atributiva correspondente ao problema. Descreva o significado e o tipo de cada atributo. Que tipo de gramática obteve?
	# ~~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).		# 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.		# 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.

Root: Created page with "{{TOCright}} == 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ím..."

2012-06-05T13:13:57Z

Created page with "{{TOCright}} == 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ím..."

New page

{{TOCright}}
== 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?
# 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).
# 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>

</text>

[[category:Compilers]]
[[category:Teaching]]