Pretende-se controlar um semáforo de 3 estados: Encarnado, Amarelo e Verde, representados pelos valores numéricos 2, 1 e 0, respectivamente.
O semáforo é controlado por um temporizador que emite, regularmente, o token NEXT que faz o semáforo evoluir para o estado seguinte, na sequência (Encarnado, Verde, Amarelo e novamente Encarnado). O semáforo tem um botão de pânico que gera o token PANIC e coloca o semáforo no estado Encarnado, independentemente do estado anterior. O estado inicial do sistema é Encarnado.
The first task is to write the grammar for recognizing the input. Since, in essence, the input in this case is a simple list of tokens, the grammar is also very simple.
There are two possible grammar types:
Left-recursive:
E -> E NEXT E -> E PANIC E -> ε
Right-recursive:
E -> NEXT E E -> PANIC E E -> ε
We will consider each case separately and discuss the attributes used in each case:
In the case of a left recursive grammar, the empty string is accepted at the beginning and further nodes are built from the previous tree and the new token. Thus, the traffic light's initial state can be defined in the last production above and further states are controlled/defined by the other two productions. "val" is the (synthesized) attribute used to represent the current (and, since each new tree is built from the previous) the final color of the traffic light (subscript "1" does not indicate a new non-terminal symbol, but rather another -- different -- instance of E).
E -> E1 NEXT { E.val = (E1.val + 1)%3; }
E -> E1 PANIC { E.val = 2; }
E -> ε { E.val = 2; }
Since there are only synthesized attributes in this grammar, it is an S-attributed grammar.
When we consider a right-recursive grammar (and a top-down parser), the first node to be built will be the one corresponding to the empty string at the end of the input (in this case, the parser must wait for the end of the input to build the tree). Considering that we must define the traffic light's initial state, clearly this production is not the place (as it was before). To get around the problem, we will consider a new production to set the initial value of an inherited attribute "cur", that will carry the current color until the end of the input. When the end is reached, the final color will be brought to the root of the tree by a synthesized attribute "val".
I -> E { E.cur = 2; I.val = E.val; }
E -> NEXT E1 { E1.cur = (E.cur + 1)%3; E.val = E1.val; }
E -> PANIC E1 { E1.cur = 2; E.val = E1.val; }
E -> ε { E.val = E.cur; }
Since the inherited attributes in this grammar only depend on the attributes of the rule's head or on the attributes of older (to the left) siblings, it is an L-attributed grammar.