(New page: Considere a seguinte gramática atributiva: s -> symbol 1 # symbol 2 { s. val = symbol 1. val + symbol 2. val symbol 1. x = 1 symbol 2. x = 1 ...) |
(→Attribute grammar using only synthesized attributes) |
||
(14 intermediate revisions by the same user not shown) | |||
Line 1: | Line 1: | ||
− | + | <p><span lang="pt">Considere a seguinte gramática atributiva:</span></p> | |
− | s | + | <table border="0" cellpadding="3"> |
− | + | <tr> | |
− | + | <td align="right">s</td> | |
− | + | <td align="left">→</td> | |
− | + | <td align="left"><em>symbol</em> <sub>1</sub> <strong>#</strong> <em>symbol</em> <sub>2</sub></td> | |
− | symbol 1 | + | <td align="left">{</td> |
− | + | <td align="left"> </td> | |
− | + | </tr> | |
− | + | <tr> | |
− | symbol | + | <td align="right"> </td> |
− | + | <td align="left"> </td> | |
− | + | <td align="left"> </td> | |
+ | <td align="left"> </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"> </td> | ||
+ | <td align="left"> </td> | ||
+ | <td align="left"> </td> | ||
+ | <td align="left"> </td> | ||
+ | <td align="left"><em>symbol</em> <sub>1</sub>. <em>x</em> = 1</td> | ||
+ | </tr> | ||
+ | <tr> | ||
+ | <td align="right"> </td> | ||
+ | <td align="left"> </td> | ||
+ | <td align="left"> </td> | ||
+ | <td align="left"> </td> | ||
+ | <td align="left"><em>symbol</em> <sub>2</sub>. <em>x</em> = 1</td> | ||
+ | </tr> | ||
+ | <tr> | ||
+ | <td align="right"> </td> | ||
+ | <td align="left"> </td> | ||
+ | <td align="left"> </td> | ||
+ | <td align="left">}</td> | ||
+ | <td align="left"> </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"> </td> | ||
+ | </tr> | ||
+ | <tr> | ||
+ | <td align="right"> </td> | ||
+ | <td align="left"> </td> | ||
+ | <td align="left"> </td> | ||
+ | <td align="left"> </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"> </td> | ||
+ | <td align="left"> </td> | ||
+ | <td align="left"> </td> | ||
+ | <td align="left"> </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"> </td> | ||
+ | <td align="left"> </td> | ||
+ | <td align="left"> </td> | ||
+ | <td align="left">}</td> | ||
+ | <td align="left"> </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"> </td> | ||
+ | </tr> | ||
+ | <tr> | ||
+ | <td align="right"> </td> | ||
+ | <td align="left"> </td> | ||
+ | <td align="left"> </td> | ||
+ | <td align="left"> </td> | ||
+ | <td align="left">symbol.val = <strong>dig</strong>.val * symbol.x</td> | ||
+ | </tr> | ||
+ | <tr> | ||
+ | <td align="right"> </td> | ||
+ | <td align="left"> </td> | ||
+ | <td align="left"> </td> | ||
+ | <td align="left">}</td> | ||
+ | <td align="left"> </td> | ||
+ | </tr> | ||
+ | </table> | ||
+ | <p><span lang="pt"> <br /> O elemento lexical <strong>dig</strong> representa um dígito de <strong>0</strong> a <strong>9</strong>, e o seu atributo <em>val</em> representa o valor numérico correspondente.</span></p> | ||
+ | <ol> | ||
+ | <li> <span lang="pt">Represente a àrvore semântica para a entrada <strong>328#37</strong>.</span> </li> | ||
+ | <li> <span lang="pt">Apresente uma gramá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"): | ||
− | + | <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> | ||
− | + | "val" is a synthesized attribute (propagation in red). | |
− | |||
− | + | [[Image:attrgrams-ex02-semantic-tree-2.png|600px|Temporary handwritten solution]] | |
− | [[category: | + | [[category:Compiladores]] |
− | [[category: | + | [[category:Ensino]] |
Considere a seguinte gramática atributiva:
s | → | symbol 1 # symbol 2 | { | |
s. val = symbol 1. val + symbol 2. val | ||||
symbol 1. x = 1 | ||||
symbol 2. x = 1 | ||||
} | ||||
symbol 1 | → | symbol 2 dig | { | |
symbol 2. x = symbol 1. x * 5 | ||||
symbol 1.val = symbol 2.val + dig.val * symbol 1.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.
"x" is an inherited attribute (propagation in blue); "val" is a synthesized attribute (propagation in red).
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).