Attribute Grammars/Exercise 8: Arithmetic - Revision history

Root: /* Solution */

2024-05-02T10:04:28Z

Solution

← Older revision		Revision as of 10:04, 2 May 2024
Line 25:		Line 25:

	<source lang="text">		<source lang="text">
	P -> A { std::cout << "RESULT: " << (P.val = A.val) << std::endl;}		P → A { std::cout << "RESULT: " << (P.val = A.val) << std::endl;}

	A_0 -> A_1 # M { A_0.val = A_1.val + M.val; }		A_0 → A_1 # M { A_0.val = A_1.val + M.val; }
	A_0 -> A_1 ! M { A_0.val = A_1.val - M.val; }		A_0 → A_1 ! M { A_0.val = A_1.val - M.val; }
	A -> M { A_0.val = M.val; }		A → M { A_0.val = M.val; }

	M_0 -> M_1 @ I { M_0.val = M_1.val * I.val / 100; }		M_0 → M_1 @ I { M_0.val = M_1.val * I.val / 100; }
	M -> I { M_0.val = I.val; }		M → I { M_0.val = I.val; }

	I -> T > { I.val =T.val + 1; }		I → T > { I.val =T.val + 1; }
	I -> < T { I.val = T.val - 1; }		I → < T { I.val = T.val - 1; }
	I -> T { I.val = T.val; }		I → T { I.val = T.val; }

	T -> N { T.val = N.val; }		T → N { T.val = N.val; }
	T -> ( A ) { T.val = A.val; }		T → ( A ) { T.val = A.val; }

	N -> DIG { N.val = DIG.val; }		N → DIG { N.val = DIG.val; }
	N_0 -> N_1 DIG { N_0.val = N_1.val * 10 + DIG.val; }		N_0 → N_1 DIG { N_0.val = N_1.val * 10 + DIG.val; }
	</source>		</source>

Root at 10:48, 12 February 2019

2019-02-12T10:48:20Z

← Older revision		Revision as of 10:48, 12 February 2019
Line 24:		Line 24:
	The problem has a simple solution, if you remember to define a non-terminal symbol for each precedence.		The problem has a simple solution, if you remember to define a non-terminal symbol for each precedence.

	<text>		<source lang="text">
	P -> A { std::cout << "RESULT: " << (P.val = A.val) << std::endl;}		P -> A { std::cout << "RESULT: " << (P.val = A.val) << std::endl;}

Line 43:		Line 43:
	N -> DIG { N.val = DIG.val; }		N -> DIG { N.val = DIG.val; }
	N_0 -> N_1 DIG { N_0.val = N_1.val * 10 + DIG.val; }		N_0 -> N_1 DIG { N_0.val = N_1.val * 10 + DIG.val; }
	</~~text~~>		</source>

	All attributes are synthesized (S-attributed grammar): '''val''' encodes the value associated with each grammar symbol.		All attributes are synthesized (S-attributed grammar): '''val''' encodes the value associated with each grammar symbol.
Line 56:		Line 56:

	A YACC specification can be obtained by adapting the grammar above:		A YACC specification can be obtained by adapting the grammar above:
	<text>		<source lang="text">
	%{		%{
	#include <cstdlib>		#include <cstdlib>
Line 88:		Line 88:
	extern int yyparse();		extern int yyparse();
	int main() { return yyparse(); }		int main() { return yyparse(); }
	</~~text~~>		</source>

	This specification uses the following Flex specification (others could be used -- indeed, this is a very simple definition):		This specification uses the following Flex specification (others could be used -- indeed, this is a very simple definition):
	<text>		<source lang="text">
	%option debug noyywrap		%option debug noyywrap
	%{		%{
Line 101:		Line 101:
	.\|\n ;		.\|\n ;
	%%		%%
	</~~text~~>		</source>

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

Root at 14:26, 6 April 2015

2015-04-06T14:26:19Z

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

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

Root: /* Solution */

2012-03-25T23:53:11Z

Solution

← Older revision		Revision as of 23:53, 25 March 2012
Line 34:		Line 34:
	M -> I { M_0.val = I.val; }		M -> I { M_0.val = I.val; }

	~~I_0~~ -> ~~I_1~~ > { ~~I_0~~.val = ~~I_1~~.val + 1; }		I -> T > { I.val =T.val + 1; }
	~~I_0~~ -> < ~~I_1~~ { ~~I_0~~.val = ~~I_1~~.val - 1; }		I -> < T { I.val = T.val - 1; }
	I -> T { I.val = T.val; }		I -> T { I.val = T.val; }

	T -> N { T.val = N.val; }		T -> N { T.val = N.val; }
Line 50:		Line 50:

	The following is the annotated tree for '''(15@30#<3)>!4'''. The green boxes represent print operations (of the displayed value).		The following is the annotated tree for '''(15@30#<3)>!4'''. The green boxes represent print operations (of the displayed value).

	~~(this tree is for an older version of the grammar in which I -> T > and I -> < T )~~

	[[Image:arithmetic-t21011-153034.png\|500px]]		[[Image:arithmetic-t21011-153034.png\|500px]]

Root: /* Semantic Tree */

2012-03-25T23:50:00Z

Semantic Tree

← Older revision		Revision as of 23:50, 25 March 2012
Line 50:		Line 50:

	The following is the annotated tree for '''(15@30#<3)>!4'''. The green boxes represent print operations (of the displayed value).		The following is the annotated tree for '''(15@30#<3)>!4'''. The green boxes represent print operations (of the displayed value).

			(this tree is for an older version of the grammar in which I -> T > and I -> < T )

	[[Image:arithmetic-t21011-153034.png\|500px]]		[[Image:arithmetic-t21011-153034.png\|500px]]

Root: /* Solution */

2012-03-25T23:47:48Z

Solution

← Older revision		Revision as of 23:47, 25 March 2012
Line 34:		Line 34:
	M -> I { M_0.val = I.val; }		M -> I { M_0.val = I.val; }

	I -> T > { I.val = T.val + 1; }		I_0 -> I_1 > { I_0.val = I_1.val + 1; }
	I -> < T { I.val = T.val - 1; }		I_0 -> < I_1 { I_0.val = I_1.val - 1; }
	I -> T { I.val = T.val; }		I -> T { I.val = T.val; }

Root: /* Semantic Tree */

2011-06-15T18:17:23Z

Semantic Tree

← Older revision		Revision as of 18:17, 15 June 2011
Line 51:		Line 51:
	The following is the annotated tree for '''(15@30#<3)>!4'''. The green boxes represent print operations (of the displayed value).		The following is the annotated tree for '''(15@30#<3)>!4'''. The green boxes represent print operations (of the displayed value).

	[[Image:arithmetic-t21011-153034.png]]		[[Image:arithmetic-t21011-153034.png\|500px]]

	=== YACC implementation ===		=== YACC implementation ===

Root: /* Solution */

2011-06-15T16:19:59Z

Solution

← Older revision		Revision as of 16:19, 15 June 2011
Line 46:		Line 46:

	All attributes are synthesized (S-attributed grammar): '''val''' encodes the value associated with each grammar symbol.		All attributes are synthesized (S-attributed grammar): '''val''' encodes the value associated with each grammar symbol.

			=== Semantic Tree ===

	The following is the annotated tree for '''(15@30#<3)>!4'''. The green boxes represent print operations (of the displayed value).		The following is the annotated tree for '''(15@30#<3)>!4'''. The green boxes represent print operations (of the displayed value).

	[[Image:arithmetic-t21011-153034.png]]		[[Image:arithmetic-t21011-153034.png]]

			=== YACC implementation ===

	A YACC specification can be obtained by adapting the grammar above:		A YACC specification can be obtained by adapting the grammar above:

Root: Created page with "{{TOCright}} == Problem (in Portuguese) == (appeared in Teste 2 2010/2011) Pretende-se criar uma gramática atributiva que calcule no símbolo inicial o valor das expressões f..."

2011-06-15T16:19:07Z

Created page with "{{TOCright}} == Problem (in Portuguese) == (appeared in Teste 2 2010/2011) Pretende-se criar uma gramática atributiva que calcule no símbolo inicial o valor das expressões f..."

New page

{{TOCright}}
== Problem (in Portuguese) ==

(appeared in Teste 2 2010/2011)

Pretende-se criar uma gramática atributiva que calcule no símbolo inicial o valor das expressões fornecidas. As expressões são codificadas (i) como números inteiros (i.e., sequências de algarismos em base 10, cada um representado pelo token '''DIG''', ao qual está associado o atributo val com o valor do algarismo); (ii) como somas ou subtracções unárias de uma unidade a uma expressão (respectivamente, '''>''' e '''<'''); (iii) somas ou subtracções binárias (respectivamente, '''#''' e '''!''') de expressões; ou (iii) como percentagens de expressões (indicada como uma expressão, após o operador '''@''').

Os operadores unários têm precedência sobre todos os operadores binários. O operador '''@''' tem precedência superior aos operadores '''#''' e '''!'''. Todos os operadores binários são associativos à esquerda. Podem ser utilizados parênteses para alteração das precedências.

=== Examples ===
* '''37''' é representado pela sequência DIG DIG (o primeiro token tem o atributo val com valor 3 e o segundo com o valor 7).
* '''4>''' tem o valor 5
* '''<3''' tem o valor 2
* '''36@20''' tem o valor 7.2
* '''(24>#25)@20#7!<15#6''' tem o valor 9

=== 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 árvore de sintaxe decorada e o grafo de dependências para a frase '''(15@30#<3)>!4''' (valor 3.5).
# 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. Não utilizar variáveis globais.

== Solution ==

The problem has a simple solution, if you remember to define a non-terminal symbol for each precedence.

<text>
P -> A { std::cout << "RESULT: " << (P.val = A.val) << std::endl;}

A_0 -> A_1 # M { A_0.val = A_1.val + M.val; }
A_0 -> A_1 ! M { A_0.val = A_1.val - M.val; }
A -> M { A_0.val = M.val; }

M_0 -> M_1 @ I { M_0.val = M_1.val * I.val / 100; }
M -> I { M_0.val = I.val; }

I -> T > { I.val = T.val + 1; }
I -> < T { I.val = T.val - 1; }
I -> T { I.val = T.val; }

T -> N { T.val = N.val; }
T -> ( A ) { T.val = A.val; }

N -> DIG { N.val = DIG.val; }
N_0 -> N_1 DIG { N_0.val = N_1.val * 10 + DIG.val; }
</text>

All attributes are synthesized (S-attributed grammar): '''val''' encodes the value associated with each grammar symbol.

The following is the annotated tree for '''(15@30#<3)>!4'''. The green boxes represent print operations (of the displayed value).

[[Image:arithmetic-t21011-153034.png]]

A YACC specification can be obtained by adapting the grammar above:
<text>
%{
#include <cstdlib>
#include <iostream>
inline void yyerror(const char *msg) { std::cout << msg << std::endl; }
%}
%union { int i; double d; }
%token<i> DIG
%type<d> expr num
%left '#' '!'
%left '@'
%nonassoc '<' '>'
%%
print: expr { std::cout << "RESULT: " << $1 << std::endl;}
;

expr: num { $$ = $1; }
| '<' expr { $$ = $2 - 1; }
| expr '>' { $$ = $1 + 1; }
| expr '#' expr { $$ = $1 + $3; }
| expr '!' expr { $$ = $1 - $3; }
| expr '@' expr { $$ = $1 * $3 / 100; }
| '(' expr ')' { $$ = $2; }
;

num : DIG { $$ = $1; }
| num DIG { $$ = 10 * $1 + $2; }
;
%%
extern int yylex();
extern int yyparse();
int main() { return yyparse(); }
</text>

This specification uses the following Flex specification (others could be used -- indeed, this is a very simple definition):
<text>
%option debug noyywrap
%{
#include "y.tab.h"
%}
%%
[[:digit:]] yylval.i = atoi(yytext); return DIG;
[@()<>!#] return *yytext;
.|\n ;
%%
</text>

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