Revision as of 19:35, 13 June 2010

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 241+33=274.

2 4 1 + 1 7 # 1 G

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.

E0 -> E1 + N   { E0.val = E1.val + N.val; }
E -> N         { E.val = N.val; }
N -> R1 # R2   { R1.b = 10; R2.b = R1.val; N.val = R2.val; }
N -> R         { R.b = 10; N.val = R.val; }
R0 -> R1 DIG   { R1.b = R0.b; R0.val = R1.val * R0.b + DIG.val; }
R -> DIG       { R.val = DIG.val; }

The following is the annotated tree for the string above. Note that the order or evaluation for the attributes is first inherited, then synthesized.