Attribute Grammars/Exercise 2: Numbers

Considere a seguinte gramática atributiva:

s	→	symbol 1 # symbol 2	{
				s. val = symbol 1. val + symbol 2. val
				symbol 1. x = 1
				symbol 2. x = 1
			}
symbol 1	→	symbol 2 dig	{
				symbol 2. x = symbol 1. x * 5
				symbol 1.val = symbol 2.val + dig.val * symbol 1.x
			}
symbol	→	dig	{
				symbol.val = dig.val * symbol.x
			}

O elemento lexical dig representa um dígito de 0 a 9, e o seu atributo val representa o valor numérico correspondente.

1. Represente a àrvore semântica para a entrada 328#37.
2. Apresente uma gramática atributiva equivalente que apenas contenha atributos sintetizados.

Solution

Semantic tree and dependency graph

"x" is an inherited attribute (propagation in blue); "val" is a synthesized attribute (propagation in red).

Attribute grammar using only synthesized attributes

We start by noting that the semantic computed by the previous grammar corresponds to base 5-like numbering (although the digits do not belong to base 5).

The new grammar is trivial to write (_1 and _2 are subscripts to differentiate instances of "symbol"):

s 	 → symbol_1 # symbol_2  { s.val = symbol_1.val + symbol_2.val } 
symbol_1 → symbol_2 dig 	 { symbol_1.val = symbol_2.val * 5 + dig.val }
symbol 	 → dig                  { symbol.val = dig.val }

"val" is a synthesized attribute (propagation in red).