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 é precedida pelo valor decimal da base e pelo símbolo #.

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

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.

S0 -> S1 + M   { S0.val = S1.val + M.val; }
S -> M         { S.val = M.val; }

M0 -> M1 * N   { M0.val = M1.val + N.val; }
M -> N         { M.val = N.val; }

N0 -> B @ N1   { B.b = N1.val; N0.val = B.val; }
N0 -> N1 DIG       { N0.val = N1.val * 10 + DIG.val; }
N -> DIG       { R.val = DIG.val; }

B0 -> B1 DIG       { B1.b = B0.b; B0.val = B1.val * B1.b + DIG.val; }
B -> DIG       { B.val = DIG.val; }

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.

File:AttrGramEx10Bases1.png