Difference between revisions of "Attribute Grammars/Exercise 6: Expressions with bases percentages"

From Wiki**3

< Attribute Grammars
(→‎Problem (in Portuguese))
(→‎Solution)
 
Line 18: Line 18:
 
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.
 
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<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> }
+
  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<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> }
+
  T → F        { <font color="blue">T.val = F.val;</font> }
−
  F -> '''(''' E ''')'''        { <font color="blue">F.val = E.val;</font> }
+
  F → '''(''' E ''')'''        { <font color="blue">F.val = E.val;</font> }
−
  F -> N      { <font color="blue">F.val = N.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<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> }
+
  N → '''DIG'''      { <font color="blue">N.val = DIG.val;</font> }
  
 
The following is the annotated tree.
 
The following is the annotated tree.

Latest revision as of 12:02, 2 May 2024

Problem (in Portuguese)

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

  1. como números inteiros (i.e., sequências de dígitos em base 10, cada um representado pelo token DIG);
  2. como somas (+) ou subtracções (-) de expressões; ou
  3. como percentagens de expressões (indicada como uma expressão, após o operador @).

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.

  1. Identifique a gramática atributiva correspondente ao problema. Descreva o significado e o tipo de cada atributo. Que tipo de gramática obteve?
  2. Identifique a árvore de sintaxe decorada e o grafo de dependências para a frase (15@30 + 3)@20 (valor 1.5).
  3. 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. 

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.

File:AttrGramEx6.png

Retrieved from "https://web.tecnico.ulisboa.pt/~david.matos/w/pt/index.php?title=Attribute_Grammars/Exercise_6:_Expressions_with_bases_percentages&oldid=16350"