Attribute Grammars/Exercise 1: Traffic Light - Revision history

Root: Redirected page to ist:Attribute Grammars/Exercise 1: Traffic Light

2018-12-05T23:07:53Z

Redirected page to ist:Attribute Grammars/Exercise 1: Traffic Light

← Older revision		Revision as of 23:07, 5 December 2018
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:Compiladores]]~~
	~~[[category~~:~~Ensino~~]]

Root at 14:25, 6 April 2015

2015-04-06T14:25:12Z

← Older revision		Revision as of 14:25, 6 April 2015
Line 43:		Line 43:
	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.		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:Compiladores]]
	[[category:~~Teaching~~]]		[[category:Ensino]]

Root: /* Solution */

2015-02-13T11:34:31Z

Solution

← Older revision		Revision as of 11:34, 13 February 2015
Line 16:		Line 16:
	E -> E NEXT		E -> E NEXT
	E -> E PANIC		E -> E PANIC
	E -> ϵ		E -> ε

	Right-recursive:		Right-recursive:
Line 22:		Line 22:
	E -> NEXT E		E -> NEXT E
	E -> PANIC E		E -> PANIC E
	E -> ϵ		E -> ε

	We will consider each case separately and discuss the attributes used in each case:		We will consider each case separately and discuss the attributes used in each case:
Line 30:		Line 30:
	E -> E<sub>1</sub> NEXT { E.val = (E<sub>1</sub>.val + 1)%3; }		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<sub>1</sub> PANIC { E.val = 2; }
	E -> ϵ { E.val = 2; }		E -> ε { E.val = 2; }

	Since there are only synthesized attributes in this grammar, it is an S-attributed grammar.		Since there are only synthesized attributes in this grammar, it is an S-attributed grammar.
Line 39:		Line 39:
	E -> NEXT E<sub>1</sub> { E<sub>1</sub>.cur = (E.cur + 1)%3; E.val = E<sub>1</sub>.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 -> PANIC E<sub>1</sub> { E<sub>1</sub>.cur = 2; E.val = E<sub>1</sub>.val; }
	E -> ϵ { E.val = E.cur; }		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.		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.

Root: /* Solution */

2009-04-19T19:00:04Z

Solution

← Older revision		Revision as of 19:00, 19 April 2009
Line 31:		Line 31:
	E -> E<sub>1</sub> PANIC { E.val = 2; }		E -> E<sub>1</sub> PANIC { E.val = 2; }
	E -> ϵ { 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".		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".
Line 38:		Line 40:
	E -> PANIC E<sub>1</sub> { E<sub>1</sub>.cur = 2; 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; }		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:Compilers]]
	[[category:Teaching]]		[[category:Teaching]]

Root at 18:52, 19 April 2009

2009-04-19T18:52:02Z

@@ Line 7: / Line 7: @@
 == Solution ==
 [[category:Compilers]]
 [[category:Teaching]]

Root: Attribute Grammars/Exercise 1: Semaphore moved to Attribute Grammars/Exercise 1: Traffic Light

2009-04-19T18:37:52Z

Attribute Grammars/Exercise 1: Semaphore moved to Attribute Grammars/Exercise 1: Traffic Light

← Older revision	Revision as of 18:37, 19 April 2009
(No difference)

Root: New page:
Pretende-se controlar um semáforo de 3 estados: Encarnado, Amarelo e Verde, representados pelos valores numéricos 2, 1 e 0, respectivamente.

...

2009-04-18T15:14:24Z

New page: Pretende-se controlar um semáforo de 3 estados: Encarnado, Amarelo e Verde, representados pelos valores numéricos 2, 1 e 0, respectivamente. ...

New page

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.
<ol>
<li> 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. </li>
<li> Realize a árvore semântica anotada para a sequência de tokens NEXT, NEXT, PANIC e NEXT. </li>
</ol>

== Solution ==

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

Attribute Grammars/Exercise 1: Traffic Light - Revision history

Root: Redirected page to ist:Attribute Grammars/Exercise 1: Traffic Light

Root at 14:25, 6 April 2015

Root: /* Solution */

Root: /* Solution */

Root at 18:52, 19 April 2009

Root: Attribute Grammars/Exercise 1: Semaphore moved to Attribute Grammars/Exercise 1: Traffic Light

Root: New page: Pretende-se controlar um semáforo de 3 estados: Encarnado, Amarelo e Verde, representados pelos valores numéricos 2, 1 e 0, respectivamente. ...

Root: New page:
Pretende-se controlar um semáforo de 3 estados: Encarnado, Amarelo e Verde, representados pelos valores numéricos 2, 1 e 0, respectivamente.

...