View source for Attribute Grammars/Exercise 1: Traffic Light

<p><span lang="pt">Pretende-se controlar um sem&aacute;foro de 3 estados: Encarnado, Amarelo e Verde, representados pelos valores num&eacute;ricos 2, 1 e 0, respectivamente.</span></p>
<p><span lang="pt">O sem&aacute;foro &eacute; controlado por um temporizador que emite, regularmente, o token    <strong>NEXT</strong> que faz o sem&aacute;foro evoluir para o estado seguinte, na sequ&ecirc;ncia (Encarnado, Verde, Amarelo e novamente Encarnado). O sem&aacute;foro tem um bot&atilde;o de p&acirc;nico que gera o token    <strong>PANIC</strong> e coloca o sem&aacute;foro no estado Encarnado, independentemente do estado anterior. O estado inicial do sistema &eacute; Encarnado.</span></p>
<ol>
<li> <span lang="pt">Construa a gram&aacute;tica atributiva que permite controlar o estado do sem&aacute;foro (considere apenas os tokens indicados). Indique que tipo de gram&aacute;tica atributiva que obteve.</span> </li>
<li> <span lang="pt">Realize a &aacute;rvore sem&acirc;ntica anotada para a sequ&ecirc;ncia de tokens      <strong>NEXT</strong>,      <strong>NEXT</strong>,      <strong>PANIC</strong> e      <strong>NEXT</strong>.</span> </li>
</ol>

== Solution ==

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 -> E<sub>1</sub> NEXT { E.val = (E<sub>1</sub>.val + 1)%3; }
  E -> E<sub>1</sub> 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 E<sub>1</sub> { E<sub>1</sub>.cur = (E.cur + 1)%3; E.val = E<sub>1</sub>.val; }
  E -> PANIC E<sub>1</sub> { E<sub>1</sub>.cur = 2; E.val = E<sub>1</sub>.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.

[[category:Compilers]]
[[category:Teaching]]