View source for Attribute Grammars/Exercise 10: Expressions and bases

== Problem (in Portuguese) ==

Pretende-se criar uma gramática atributiva que some uma sequência de inteiros separados por '''+'''. Os inteiros podem estar codificados sob o formato decimal (sequência de dígitos entre 0 e 9, representados pelo elemento lexical '''DIG'''), ou em qualquer base entre 2 e 36 (sequências de dígitos de 0 a 9 e, acima de 10, também contendo as letras de A a Z que forem necessárias para representar todos os valores da base). Quando a base não é decimal, a representação do inteiro é seguida pelo símbolo '''@''' e pelo valor decimal da base. 

O exemplo seguinte tem como resultado 123 + 456 * 789 + B L A H @ 24 = 123 + 359784 + 164417 = 524324.

 1 2 3 + 4 5 6 * 7 8 9 + B L A H @ 2 4

Crie a gramática para realizar a função descrita e construa a árvore semântica anotada para a entrada acima.

== Solution ==

The grammar uses only one set of rules for all bases (the default is 10, as shown in the second production for N). The inherited attribute '''b''' contains the base value, while the synthesized attribute '''val''' contains the actual number value.

 S<sub>0</sub> -> S<sub>1</sub> '''+''' M   { <font color="blue">S<sub>0</sub>.val = S<sub>1</sub>.val + M.val;</font> }
 S -> M         { <font color="blue">S.val = M.val;</font> }
 
 M<sub>0</sub> -> M<sub>1</sub> '''*''' N   { <font color="blue">M<sub>0</sub>.val = M<sub>1</sub>.val * N.val;</font> }
 M -> N         { <font color="blue">M.val = N.val;</font> }
 
 N<sub>0</sub> -> B @ N<sub>1</sub>   { <font color="brown">B.b = N<sub>1</sub>.val;</font> <font color="blue">N<sub>0</sub>.val = B.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> }
 
 B<sub>0</sub> -> B<sub>1</sub> '''DIG'''       { <font color="brown">B<sub>1</sub>.b</font> = <font color="brown">B<sub>0</sub>.b</font>; <font color="blue">B<sub>0</sub>.val = B<sub>1</sub>.val * <font color="brown">B<sub>1</sub>.b</font> + DIG.val;</font> }
 B -> '''DIG'''       { <font color="blue">B.val = DIG.val;</font> }

The following is the annotated tree for the string

 1 2 3 + 4 5 6 * 7 8 9 + B L A H @ 2 4

Note that the order of evaluation for the attributes is, first inherited, then synthesized.

Note that, in addition, although this grammar has inherited attibutes, it is not a L-attributed grammar, since there are dependencies from symbols to the right of the value being evaluated.


[[Image:AttrGramEx10Bases1.png]]

[[category:Compiladores]]
[[category:Ensino]]