Difference between revisions of "Attribute Grammars/Exercise 2: Numbers"

Latest revision as of 11:57, 2 May 2024

Considere a seguinte gramática atributiva:

s	→	symbol ₁ # symbol ₂	{
				s. val = symbol ₁. val + symbol ₂. val
				symbol ₁. x = 1
				symbol ₂. x = 1
			}
symbol ₁	→	symbol ₂ dig	{
				symbol ₂. x = symbol ₁. x * 5
				symbol ₁.val = symbol ₂.val + dig.val * symbol ₁.x
			}
symbol	→	dig	{
				symbol.val = dig.val * symbol.x
			}

O elemento lexical dig representa um dígito de 0 a 9, e o seu atributo val representa o valor numérico correspondente.

Represente a àrvore semântica para a entrada 328#37.
Apresente uma gramática atributiva equivalente que apenas contenha atributos sintetizados.

Solution

Semantic tree and dependency graph

"x" is an inherited attribute (propagation in blue); "val" is a synthesized attribute (propagation in red).

Attribute grammar using only synthesized attributes

We start by noting that the semantic computed by the previous grammar corresponds to base 5-like numbering (although the digits do not belong to base 5).

The new grammar is trivial to write (_1 and _2 are subscripts to differentiate instances of "symbol"):

s 	 → symbol_1 # symbol_2  { s.val = symbol_1.val + symbol_2.val } 
symbol_1 → symbol_2 dig 	 { symbol_1.val = symbol_2.val * 5 + dig.val }
symbol 	 → dig                  { symbol.val = dig.val }

"val" is a synthesized attribute (propagation in red).

@@ Line 1: / Line 1: @@
- Considere a seguinte gramática atributiva:
+<p><span lang="pt">Considere a seguinte gram&aacute;tica atributiva:</span></p>
-s 	-> 	symbol 1 # symbol 2 	{
+<table border="0" cellpadding="3">
-  	  	  	  	s. val = symbol 1. val + symbol 2. val
+<tr>
-  	  	  	  	symbol 1. x = 1
+<td align="right">s</td>
-  	  	  	  	symbol 2. x = 1
+<td align="left">→</td>
-  	  	  	}
+<td align="left"><em>symbol</em> <sub>1</sub> <strong>#</strong> <em>symbol</em> <sub>2</sub></td>
-symbol 1 	-> 	symbol 2 dig 	{
+<td align="left">{</td>
-  	  	  	  	symbol 2. x = symbol 1. x * 5
+<td align="left">&nbsp;</td>
-  	  	  	  	symbol 1.val = symbol 2.val + dig.val * symbol 1.x
+</tr>
-  	  	  	}
+<tr>
-symbol 	-> 	dig 	{
+<td align="right">&nbsp;</td>
-  	  	  	  	symbol.val = dig.val * symbol.x
+<td align="left">&nbsp;</td>
-  	  	  	}
+<td align="left">&nbsp;</td>
+<td align="left">&nbsp;</td>
+<td align="left"><em>s</em>.        <em>val</em> =        <em>symbol</em> <sub>1</sub>.        <em>val</em> +        <em>symbol</em> <sub>2</sub>.        <em>val</em></td>
+</tr>
+<tr>
+<td align="right">&nbsp;</td>
+<td align="left">&nbsp;</td>
+<td align="left">&nbsp;</td>
+<td align="left">&nbsp;</td>
+<td align="left"><em>symbol</em> <sub>1</sub>.        <em>x</em> = 1</td>
+</tr>
+<tr>
+<td align="right">&nbsp;</td>
+<td align="left">&nbsp;</td>
+<td align="left">&nbsp;</td>
+<td align="left">&nbsp;</td>
+<td align="left"><em>symbol</em> <sub>2</sub>.        <em>x</em> = 1</td>
+</tr>
+<tr>
+<td align="right">&nbsp;</td>
+<td align="left">&nbsp;</td>
+<td align="left">&nbsp;</td>
+<td align="left">}</td>
+<td align="left">&nbsp;</td>
+</tr>
+<tr>
+<td align="right"><em>symbol</em> <sub>1</sub></td>
+<td align="left">→</td>
+<td align="left"><em>symbol</em> <sub>2</sub> <strong>dig</strong></td>
+<td align="left">{</td>
+<td align="left">&nbsp;</td>
+</tr>
+<tr>
+<td align="right">&nbsp;</td>
+<td align="left">&nbsp;</td>
+<td align="left">&nbsp;</td>
+<td align="left">&nbsp;</td>
+<td align="left"><em>symbol</em> <sub>2</sub>.        <em>x</em> =        <em>symbol</em> <sub>1</sub>.        <em>x</em> * 5</td>
+</tr>
+<tr>
+<td align="right">&nbsp;</td>
+<td align="left">&nbsp;</td>
+<td align="left">&nbsp;</td>
+<td align="left">&nbsp;</td>
+<td align="left">symbol        <sub>1</sub>.val = symbol        <sub>2</sub>.val +        <strong>dig</strong>.val * symbol        <sub>1</sub>.x</td>
+</tr>
+<tr>
+<td align="right">&nbsp;</td>
+<td align="left">&nbsp;</td>
+<td align="left">&nbsp;</td>
+<td align="left">}</td>
+<td align="left">&nbsp;</td>
+</tr>
+<tr>
+<td align="right"><em>symbol</em></td>
+<td align="left">→</td>
+<td align="left"><strong>dig</strong></td>
+<td align="left">{</td>
+<td align="left">&nbsp;</td>
+</tr>
+<tr>
+<td align="right">&nbsp;</td>
+<td align="left">&nbsp;</td>
+<td align="left">&nbsp;</td>
+<td align="left">&nbsp;</td>
+<td align="left">symbol.val =        <strong>dig</strong>.val * symbol.x</td>
+</tr>
+<tr>
+<td align="right">&nbsp;</td>
+<td align="left">&nbsp;</td>
+<td align="left">&nbsp;</td>
+<td align="left">}</td>
+<td align="left">&nbsp;</td>
+</tr>
+</table>
+<p><span lang="pt"> <br /> O elemento lexical    <strong>dig</strong> representa um d&iacute;gito de    <strong>0</strong> a    <strong>9</strong>, e o seu atributo    <em>val</em> representa o valor num&eacute;rico correspondente.</span></p>
+<ol>
+<li> <span lang="pt">Represente a &agrave;rvore sem&acirc;ntica para a entrada      <strong>328#37</strong>.</span> </li>
+<li> <span lang="pt">Apresente uma gram&aacute;tica atributiva equivalente que apenas contenha atributos sintetizados.</span> </li>
+</ol>
+== Solution ==
+=== Semantic tree and dependency graph ===
+"x" is an inherited attribute (propagation in blue); "val" is a synthesized attribute (propagation in red).
+[[Image:attrgrams-ex02-semantic-tree-1.jpg|600px|Temporary handwritten solution.]]
+=== Attribute grammar using only synthesized attributes ===
+We start by noting that the semantic computed by the previous grammar corresponds to base 5-like numbering (although the digits do not belong to base 5).
+The new grammar is trivial to write (_1 and _2 are subscripts to differentiate instances of "symbol"):
-O elemento lexical dig representa um dígito de 0 a 9, e o seu atributo val representa o valor numérico correspondente.
+<source lang="text">
+s 	 → symbol_1 # symbol_2  { s.val = symbol_1.val + symbol_2.val }
+symbol_1 → symbol_2 dig 	 { symbol_1.val = symbol_2.val * 5 + dig.val }
+symbol 	 → dig                  { symbol.val = dig.val }
+</source>
-. Represente a àrvore semântica para a entrada 328#37.
+"val" is a synthesized attribute (propagation in red).
-. Apresente uma gramática atributiva equivalente que apenas contenha atributos sintetizados.
-== Solution ==
+[[Image:attrgrams-ex02-semantic-tree-2.png|600px|Temporary handwritten solution]]
-[[category:Compilers]]
+[[category:Compiladores]]
-[[category:Teaching]]
+[[category:Ensino]]