|
|
| (2 intermediate revisions by the same user not shown) |
| Line 1: |
Line 1: |
| <p><span lang="pt">Pretende-se controlar um semáforo de 3 estados: Encarnado, Amarelo e Verde, representados pelos valores numéricos 2, 1 e 0, respectivamente.</span></p>
| | #REDIRECT [[ist:Attribute Grammars/Exercise 1: Traffic Light]] |
| <p><span lang="pt">O semáforo é controlado por um temporizador que emite, regularmente, o token <strong>NEXT</strong> 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 <strong>PANIC</strong> e coloca o semáforo no estado Encarnado, independentemente do estado anterior. O estado inicial do sistema é Encarnado.</span></p>
| |
| <ol>
| |
| <li> <span lang="pt">Construa a gramática atributiva que permite controlar o estado do semáforo (considere apenas os tokens indicados). Indique que tipo de gramática atributiva que obteve.</span> </li>
| |
| <li> <span lang="pt">Realize a árvore semântica anotada para a sequê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]]
| |