Introduction to Syntax/Exercise 1 - Revision history

Root: Redirected page to ist:Introduction to Syntax/Exercise 1

2018-12-05T22:15:43Z

Redirected page to ist:Introduction to Syntax/Exercise 1

Root at 14:28, 6 April 2015

2015-04-06T14:28:10Z

← Older revision		Revision as of 14:28, 6 April 2015
Line 127:		Line 127:
	</graph>		</graph>

	[[category:~~Compilers~~]]		[[category:Compiladores]]
	[[category:~~Teaching~~]]		[[category:Ensino]]

Root at 13:53, 4 April 2010

2010-04-04T13:53:13Z

← Older revision		Revision as of 13:53, 4 April 2010
Line 3:		Line 3:
	Consider the following grammar:		Consider the following grammar:

	~~bexpr~~ -> ~~bexpr~~ or ~~bexpr~~ \| ~~bterm~~		E -> E <font color="blue">'''or'''</font> E \| T
	~~bterm~~ -> ~~bterm~~ and ~~bterm~~ \| ~~bfactor~~		T -> T <font color="blue">'''and'''</font> T \| F
	~~bfactor~~ -> not ~~bfactor~~ \| ( ~~bexpr~~ ) \| true \| false		F -> <font color="blue">'''not'''</font> F \| <font color="blue">'''('''</font> E <font color="blue">''')'''</font> \| <font color="blue">'''true'''</font> \| <font color="blue">'''false'''</font>

	# Identify the terminal and non-terminal symbols of the grammar.		# Identify the terminal and non-terminal symbols of the grammar.
Line 21:		Line 21:
	graph nfa {		graph nfa {
	node [shape=plaintext]		node [shape=plaintext]
	0 [id=0,label="~~bexpr~~"];		0 [id=0,label="E"];
	1 [id=1,label="~~bterm~~"];		1 [id=1,label="T"];
	2 [id=2,label="~~bterm~~"];		2 [id=2,label="T"];
	3 [id=3,label="~~bterm~~"];		3 [id=3,label="T"];
	4 [id=4,label="~~bfactor~~"];		4 [id=4,label="F"];
	5 [id=5,label="true", fontcolor=blue];		5 [id=5,label="true", fontcolor=blue];
	6 [id=6,label="and", fontcolor=blue];		6 [id=6,label="and", fontcolor=blue];
	7 [id=7,label="~~bterm~~"];		7 [id=7,label="T"];
	8 [id=8,label="~~bfactor~~"];		8 [id=8,label="F"];
	9 [id=9,label="false", fontcolor=blue];		9 [id=9,label="false", fontcolor=blue];
	10 [id=10,label="and", fontcolor=blue];		10 [id=10,label="and", fontcolor=blue];
	11 [id=11,label="~~bterm~~"];		11 [id=11,label="T"];
	12 [id=12,label="~~bfactor~~"];		12 [id=12,label="F"];
	13 [id=13,label="true", fontcolor=blue];		13 [id=13,label="true", fontcolor=blue];

	20 [id=20,label="~~bexpr~~"];		20 [id=20,label="E"];
	21 [id=21,label="~~bterm~~"];		21 [id=21,label="T"];
	22 [id=22,label="~~bterm~~"];		22 [id=22,label="T"];
	23 [id=23,label="~~bfactor~~"];		23 [id=23,label="F"];
	24 [id=24,label="true", fontcolor=blue];		24 [id=24,label="true", fontcolor=blue];
	25 [id=25,label="and", fontcolor=blue];		25 [id=25,label="and", fontcolor=blue];
	26 [id=26,label="~~bterm~~"];		26 [id=26,label="T"];
	27 [id=27,label="~~bterm~~"];		27 [id=27,label="T"];
	28 [id=28,label="~~bfactor~~"];		28 [id=28,label="F"];
	29 [id=29,label="false", fontcolor=blue];		29 [id=29,label="false", fontcolor=blue];
	30 [id=30,label="and", fontcolor=blue];		30 [id=30,label="and", fontcolor=blue];
	31 [id=31,label="~~bterm~~"];		31 [id=31,label="T"];
	32 [id=32,label="~~bfactor~~"];		32 [id=32,label="F"];
	33 [id=33,label="true", fontcolor=blue];		33 [id=33,label="true", fontcolor=blue];

Line 77:		Line 77:
	3. To solve the problem found before, a grammar can be written that only accepts one direction for the associativity of the two binary operators present. The following rewritten grammar selects left associativity for the binary operators ('''and''' and '''or'''):		3. To solve the problem found before, a grammar can be written that only accepts one direction for the associativity of the two binary operators present. The following rewritten grammar selects left associativity for the binary operators ('''and''' and '''or'''):

	~~bexpr~~ -> ~~bexpr~~ or ~~bterm~~ \| ~~bterm~~		E -> E <font color="blue">'''or'''</font> T \| T
	~~bterm~~ -> ~~bterm~~ and ~~bfactor~~ \| ~~bfactor~~		T -> T <font color="blue">'''and'''</font> F \| F
	~~bfactor~~ -> not ~~bfactor~~ \| ( ~~bexpr~~ ) \| true \| false		F -> <font color="blue">'''not'''</font> F \| <font color="blue">'''('''</font> E <font color="blue">''')'''</font> \| <font color="blue">'''true'''</font> \| <font color="blue">'''false'''</font>

	4. The following analysis considers the grammar defined in 3 (again, terminals are in blue and non-terminals in black).		4. The following analysis considers the grammar defined in 3 (again, terminals are in blue and non-terminals in black).
Line 86:		Line 86:
	graph nfa {		graph nfa {
	node [shape=plaintext]		node [shape=plaintext]
	0 [id=0,label="~~bexpr~~"];		0 [id=0,label="E"];
	1 [id=1,label="~~bterm~~"];		1 [id=1,label="T"];
	2 [id=2,label="~~bfactor~~"];		2 [id=2,label="F"];
	3 [id=3,label="not",fontcolor=blue];		3 [id=3,label="not",fontcolor=blue];
	4 [id=4,label="~~bfactor~~"];		4 [id=4,label="F"];
	5 [id=5,label="(", fontcolor=blue];		5 [id=5,label="(", fontcolor=blue];
	6 [id=6,label="~~bexpr~~"];		6 [id=6,label="E"];
	7 [id=7,label="~~bexpr~~"];		7 [id=7,label="E"];
	8 [id=8,label="~~bterm~~"];		8 [id=8,label="T"];
	9 [id=9,label="~~bfactor~~"];		9 [id=9,label="F"];
	10 [id=10,label="true", fontcolor=blue];		10 [id=10,label="true", fontcolor=blue];
	11 [id=11,label="or", fontcolor=blue];		11 [id=11,label="or", fontcolor=blue];
	12 [id=12,label="~~bterm~~"];		12 [id=12,label="T"];
	13 [id=13,label="~~bterm~~"];		13 [id=13,label="T"];
	14 [id=14,label="~~bfactor~~"];		14 [id=14,label="F"];
	15 [id=15,label="false", fontcolor=blue];		15 [id=15,label="false", fontcolor=blue];
	16 [id=16,label="and", fontcolor=blue];		16 [id=16,label="and", fontcolor=blue];
	17 [id=17,label="~~bfactor~~"];		17 [id=17,label="F"];
	18 [id=18,label="true", fontcolor=blue];		18 [id=18,label="true", fontcolor=blue];
	19 [id=19,label=")", fontcolor=blue];		19 [id=19,label=")", fontcolor=blue];

Root: /* Solution */

2010-04-03T13:37:39Z

Solution

← Older revision		Revision as of 13:37, 3 April 2010
Line 16:		Line 16:
	1. The terminal symbols are all the symbols not defined by a rule: '''<tt>or</tt>''', '''<tt>and</tt>''', '''<tt>not</tt>''', '''<tt>(</tt>''', '''<tt>)</tt>''', '''<tt>true</tt>''', '''<tt>false</tt>'''.		1. The terminal symbols are all the symbols not defined by a rule: '''<tt>or</tt>''', '''<tt>and</tt>''', '''<tt>not</tt>''', '''<tt>(</tt>''', '''<tt>)</tt>''', '''<tt>true</tt>''', '''<tt>false</tt>'''.

	2. The following trees are possible for '''true and false and true''' (an analogous analysis could be done for '''or'''). ~~Terminals~~ are in blue and non-~~terminals~~ in black.		2. The following two trees are possible for '''true and false and true''' (an analogous analysis could be done for '''or'''). The fact that more than one tree can be found (independently of the method used), is a signal that the grammar is ambiguous. In the case shown, the ambiguity manifests itself in the associativity of the '''and''' operator (similar finding can be shown for '''or''' -- this is left as an exercise). In the trees, terminal symbols (a.k.a. tokens) are in blue and non-terminal symbols are in black.

	<graph>		<graph>
Line 75:		Line 75:


	3. The following grammar selects left associativity for the binary operators ('''and''' and '''or'''):		3. To solve the problem found before, a grammar can be written that only accepts one direction for the associativity of the two binary operators present. The following rewritten grammar selects left associativity for the binary operators ('''and''' and '''or'''):

	bexpr -> bexpr or bterm \| bterm		bexpr -> bexpr or bterm \| bterm

Root: /* Solution */

2010-04-02T21:54:35Z

Solution

← Older revision		Revision as of 21:54, 2 April 2010
Line 81:		Line 81:
	bfactor -> not bfactor \| ( bexpr ) \| true \| false		bfactor -> not bfactor \| ( bexpr ) \| true \| false

	4. The following analysis considers the grammar defined in 3.		4. The following analysis considers the grammar defined in 3 (again, terminals are in blue and non-terminals in black).

	<graph>		<graph>

Root at 21:53, 2 April 2010

2010-04-02T21:53:32Z

@@ Line 16: / Line 16: @@
 . The terminal symbols are all the symbols not defined by a rule: '''<tt>or</tt>''', '''<tt>and</tt>''', '''<tt>not</tt>''', '''<tt>(</tt>''', '''<tt>)</tt>''', '''<tt>true</tt>''', '''<tt>false</tt>'''.
-. The following trees are possible for '''true and false and true''' (an analogous analysis could be done for '''or''')
+. The following trees are possible for '''true and false and true''' (an analogous analysis could be done for '''or'''). Terminals are in blue and non-terminals in black.
 . The following grammar selects left associativity for the binary operators ('''and''' and '''or'''):
@@ Line 24: / Line 81: @@
   bfactor -> not bfactor | ( bexpr ) | true | false
-. The analysis considers the grammar defined in 3.
+. The following analysis considers the grammar defined in 3.
 [[category:Compilers]]
 [[category:Teaching]]

Root at 19:08, 2 April 2010

2010-04-02T19:08:16Z

← Older revision		Revision as of 19:08, 2 April 2010
Line 10:		Line 10:
	# Show that the grammar is ambiguous by deriving two different trees for the same input sequence.		# Show that the grammar is ambiguous by deriving two different trees for the same input sequence.
	# Write a non-ambiguous grammar for the same language.		# Write a non-ambiguous grammar for the same language.
	# Build the tree corresponding to the analysis of the following input sequence: not ( true or false and true )		# Build the tree corresponding to the analysis of the following input sequence: '''not ( true or false and true )'''

	== Solution ==		== Solution ==
Line 16:		Line 16:
	1. The terminal symbols are all the symbols not defined by a rule: '''<tt>or</tt>''', '''<tt>and</tt>''', '''<tt>not</tt>''', '''<tt>(</tt>''', '''<tt>)</tt>''', '''<tt>true</tt>''', '''<tt>false</tt>'''.		1. The terminal symbols are all the symbols not defined by a rule: '''<tt>or</tt>''', '''<tt>and</tt>''', '''<tt>not</tt>''', '''<tt>(</tt>''', '''<tt>)</tt>''', '''<tt>true</tt>''', '''<tt>false</tt>'''.

	2. The following trees are possible for true and false and true (an analogous analysis could be done for '''or''')		2. The following trees are possible for '''true and false and true''' (an analogous analysis could be done for '''or''')

	3. The following grammar selects left associativity for the binary operators ('''and''' and '''or'''):		3. The following grammar selects left associativity for the binary operators ('''and''' and '''or'''):

Root at 19:07, 2 April 2010

2010-04-02T19:07:40Z

← Older revision		Revision as of 19:07, 2 April 2010
Line 14:		Line 14:
	== Solution ==		== Solution ==

	The terminal symbols are all the symbols not defined by a rule: '''<tt>or</tt>''', '''<tt>and</tt>''', '''<tt>not</tt>''', '''<tt>(</tt>''', '''<tt>)</tt>''', '''<tt>true</tt>''', '''<tt>false</tt>'''.		1. The terminal symbols are all the symbols not defined by a rule: '''<tt>or</tt>''', '''<tt>and</tt>''', '''<tt>not</tt>''', '''<tt>(</tt>''', '''<tt>)</tt>''', '''<tt>true</tt>''', '''<tt>false</tt>'''.

			2. The following trees are possible for true and false and true (an analogous analysis could be done for '''or''')

			3. The following grammar selects left associativity for the binary operators ('''and''' and '''or'''):

			bexpr -> bexpr or bterm \| bterm
			bterm -> bterm and bfactor \| bfactor
			bfactor -> not bfactor \| ( bexpr ) \| true \| false

			4. The analysis considers the grammar defined in 3.



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

Root: Introduction to Syntax: Exercise 1 moved to Introduction to Syntax/Exercise 1

2010-04-02T19:03:31Z

Introduction to Syntax: Exercise 1 moved to Introduction to Syntax/Exercise 1

← Older revision	Revision as of 19:03, 2 April 2010
(No difference)

Root at 11:48, 11 April 2008

2008-04-11T11:48:16Z

← Older revision		Revision as of 11:48, 11 April 2008
Line 13:		Line 13:

	== Solution ==		== Solution ==

			The terminal symbols are all the symbols not defined by a rule: '''<tt>or</tt>''', '''<tt>and</tt>''', '''<tt>not</tt>''', '''<tt>(</tt>''', '''<tt>)</tt>''', '''<tt>true</tt>''', '''<tt>false</tt>'''.

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