(New page: == Problem (in Portuguese) == E<sub>0</sub> -> E<sub>1</sub> '''+''' T { <font color="blue">E<sub>0</sub>.val = E<sub>1</sub>.val + T.val;</font> } E -> T { <font color="blue"...) |
(→Solution) |
||
(8 intermediate revisions by the same user not shown) | |||
Line 1: | Line 1: | ||
== Problem (in Portuguese) == | == Problem (in Portuguese) == | ||
− | E<sub>0</sub> | + | 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 |
− | E -> T { <font color="blue">E.val = T.val;</font> } | + | # como números inteiros (i.e., sequências de dígitos em base 10, cada um representado pelo token DIG); |
− | T<sub>0</sub> | + | # como somas (+) ou subtracções (-) de expressões; ou |
− | T | + | # como percentagens de expressões (indicada como uma expressão, após o operador @). |
− | F | + | |
− | F | + | O operador @ tem precedência superior aos operadores + (soma) e - (subtracção). Todos os operadores são associativos à esquerda. Podem ser utilizados parêntesis para alteração das precedências. |
− | + | ||
− | N<sub>0</sub> | + | Exemplo: à sequência '''((1@33 + 34)@20 + 70@15 + 2)@10''' corresponde o valor 1.9366. |
− | N | + | |
+ | # 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)@20''' (valor 1.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 == | ||
+ | |||
+ | Since '''+''' and '''-''' have the same precedence, they are defined in the same rule (E), and are defined so that they operate on symbols which may contain the '''@''' operator. Since all operators are left-associative, the corresponding rules in the grammar are left-recursive. | ||
+ | |||
+ | E<sub>0</sub> → E<sub>1</sub> '''+''' T { <font color="blue">E<sub>0</sub>.val = E<sub>1</sub>.val + T.val;</font> } | ||
+ | E<sub>0</sub> → E<sub>1</sub> '''-''' T { <font color="blue">E<sub>0</sub>.val = E<sub>1</sub>.val + T.val;</font> } | ||
+ | E → T { <font color="blue">E.val = T.val;</font> } | ||
+ | T<sub>0</sub> → T<sub>1</sub> '''@''' F { <font color="blue">T<sub>0</sub>.val = T<sub>1</sub>.val * F.val / 100;</font> } | ||
+ | T → F { <font color="blue">T.val = F.val;</font> } | ||
+ | F → '''(''' E ''')''' { <font color="blue">F.val = E.val;</font> } | ||
+ | F → N { <font color="blue">F.val = N.val;</font> } | ||
+ | N<sub>0</sub> → N<sub>1</sub> '''DIG''' { <font color="blue">N<sub>0</sub>.val = N<sub>1</sub>.val * 10 + DIG.val;</font> } | ||
+ | N → '''DIG''' { <font color="blue">N.val = DIG.val;</font> } | ||
The following is the annotated tree. | The following is the annotated tree. | ||
Line 15: | Line 32: | ||
[[Image:AttrGramEx6.png]] | [[Image:AttrGramEx6.png]] | ||
− | [[category: | + | [[category:Compiladores]] |
− | [[category: | + | [[category:Ensino]] |
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
O operador @ tem precedência superior aos operadores + (soma) e - (subtracção). Todos os operadores são associativos à esquerda. Podem ser utilizados parêntesis para alteração das precedências.
Exemplo: à sequência ((1@33 + 34)@20 + 70@15 + 2)@10 corresponde o valor 1.9366.
Since + and - have the same precedence, they are defined in the same rule (E), and are defined so that they operate on symbols which may contain the @ operator. Since all operators are left-associative, the corresponding rules in the grammar are left-recursive.
E0 → E1 + T { E0.val = E1.val + T.val; } E0 → E1 - T { E0.val = E1.val + T.val; } E → T { E.val = T.val; } T0 → T1 @ F { T0.val = T1.val * F.val / 100; } T → F { T.val = F.val; } F → ( E ) { F.val = E.val; } F → N { F.val = N.val; } N0 → N1 DIG { N0.val = N1.val * 10 + DIG.val; } N → DIG { N.val = DIG.val; }
The following is the annotated tree.