Attribute Grammars/Exercise 2: Numbers: Difference between revisions

From Wiki**3

< Attribute Grammars
 
(8 intermediate revisions by the same user not shown)
Line 1: Line 1:
<p><span lang="pt">Considere a seguinte gram&aacute;tica atributiva:</span></p>
#REDIRECT [[ist:Attribute Grammars/Exercise 2: Numbers]]
<table border="0" cellpadding="3">
<tr>
<td align="right">s</td>
<td align="left">-&gt;</td>
<td align="left"><em>symbol</em> <sub>1</sub> <strong>#</strong> <em>symbol</em> <sub>2</sub></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>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">-&gt;</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">-&gt;</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).
 
Temporary handwritten solution.
 
[[Image:attrgrams-ex02-semantic-tree-1.png]]
 
=== 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:
 
<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 }
</text>
 
"val" is a synthesized attribute (propagation in red).
 
Temporary handwritten solution.
 
[[Image:attrgrams-ex02-semantic-tree-2.png]]
 
[[category:Compilers]]
[[category:Teaching]]

Latest revision as of 23:13, 5 December 2018

Redirect to:

Retrieved from "https://www.hlt.inesc-id.pt/~david/wiki/pt/index.php?title=Attribute_Grammars/Exercise_2:_Numbers&oldid=11030"