Top-Down Parsing/Exercise 3 - Revision history

Root: Redirected page to ist:Top-Down Parsing/Exercise 3

2018-12-05T22:19:05Z

Redirected page to ist:Top-Down Parsing/Exercise 3

← Older revision		Revision as of 22:19, 5 December 2018
Line 1:		Line 1:
	~~{{TOCright}}~~		#REDIRECT [[ist:Top-Down Parsing/Exercise 3]]
	~~= Problem =~~

	~~Consider the following grammar, where '''<tt>G</tt>''' is the initial symbol and '''<tt>{a,b,c,d,e}</tt>''' is the set of terminal symbols:~~

	~~O -> a~~
	~~G -> F c \| O c d \| (eps)~~
	~~F -> G b \| O c F e~~

	# ~~Examine the grammar and rewrite it so that an LL(1) predictive parser can be built for the corresponding language.~~
	~~# Compute the FIRST and FOLLOW sets for all non-terminal symbols in the new grammar and build the parse table.~~
	~~# Show the analysis table (stack, input, and actions) for the parsing process of the '''<tt>acbec</tt>''' input sequence.~~

	~~= Solution =~~

	~~Something to keep in mind at all times: '''never eliminate the rules corresponding to the initial symbol'''~~
	~~<!--~~
	~~There are two ways of handling the mutual recursion: either expanding F in G or G in F.~~

	~~== Expanding G in F ==~~

	~~Initial grammar:~~

	~~O -> a~~
	~~G -> F c \| O c d \| (eps)~~
	~~F -> G b \| O c F e~~

	~~Eliminating the singularity (O->a):~~

	~~G -> F c \| a c d \| (eps)~~
	~~F -> G b \| a c F e~~

	~~Expanding G in F:~~

	~~G -> F c \| a c d \| (eps)~~
	~~F -> F c b \| a c d b \| b \| a c F e~~

	~~Eliminate left recursion in F:~~

	~~G -> F c \| a c d \| (eps)~~
	~~F -> a c d b F' \| b F' \| a c F e F'~~
	~~F' -> c b F' \| (eps)~~

	~~Factor F prefixes and expand it in G:~~

	~~G -> a c F" c \| b F' c \| a c d \| (eps)~~
	~~F -> a c F" \| b F'~~
	~~F' -> c b F' \| (eps)~~
	~~F" -> d b F' \| F e F'~~

	~~Note that we still have common prefixes to factor in G and a non-terminal left-corner in F''. The next step will handle those cases:~~

	~~G -> a c G' \| b F' c \| (eps)~~
	~~G' -> F" c \| d~~
	~~F' -> c b F' \| (eps)~~
	~~F" -> d b F' \| a c F" e F' \| b F' e F'~~

	~~F was eliminated because it became unreachable from the start symbol. The grammar still has a non-terminal left corner in G', so we need to eliminate it.~~

	~~G -> a c G' \| b F' c \| (eps)~~
	~~G' -> d b F' c \| a c F" e F' c \| b F' e F' c \| d~~
	~~F' -> c b F' \| (eps)~~
	~~F" -> d b F' \| a c F" e F' \| b F' e F'~~

	~~Factoring prefixes in G', we get to the final version:~~

	~~G -> a c G' \| b F' c \| (eps)~~
	~~G' -> d G" \| a c F" e F' c \| b F' e F' c~~
	~~G" -> b F' c \| (eps)~~
	~~F' -> c b F' \| (eps)~~
	~~F" -> d b F' \| a c F" e F' \| b F' e F'~~
	~~-->~~
	~~=== Elimination of Mutual Recursion: Expanding F in G ===~~

	~~Initial grammar:~~

	~~O -> a~~
	~~G -> F c \| O c d \| (eps)~~
	~~F -> G b \| O c F e~~

	~~Eliminating the singularity (O->a):~~

	~~G -> F c \| a c d \| (eps)~~
	~~F -> G b \| a c F e~~

	~~Expanding F in G:~~

	~~G -> G b c \| a c F e c \| a c d \| (eps)~~
	~~F -> G b \| a c F e~~

	~~Eliminating left recursion in G:~~

	~~G -> a c F e c G' \| a c d G' \| G'~~
	~~G' -> b c G' \| (eps)~~
	~~F -> G b \| a c F e~~

	~~Factoring G prefixes:~~

	~~G -> a c G" \| b c G' \| (eps)~~
	~~G' -> b c G' \| (eps)~~
	~~G" -> F e c G' \| d G'~~
	~~F -> a c G" b \| b c G' b \| b \| a c F e~~

	~~Factoring F prefixes:~~

	~~G -> a c G" \| b c G' \| (eps)~~
	~~G' -> b c G' \| (eps)~~
	~~G" -> F e c G' \| d G'~~
	~~F -> a c F' \| b F"~~
	~~F' -> G" b \| F e~~
	~~F" -> c G' b \| (eps)~~

	~~Eliminating non-terminal left corners (note that F becomes unreachable):~~

	~~G -> a c G" \| b c G' \| (eps)~~
	~~G' -> b c G' \| (eps)~~
	~~G" -> a c F' e c G' \| b F" e c G' \| d G'~~
	~~F' -> a c F' e c G' b \| b F" e c G' b \| d G' b \| a c F' e \| b F" e~~
	~~F" -> c G' b \| (eps)~~

	~~Factoring F' prefixes, we get to the final version:~~

	~~G -> a c G" \| b c G' \| (eps)~~
	~~G' -> b c G' \| (eps)~~
	~~G" -> a c F' e c G' \| b F" e c G' \| d G'~~
	~~F' -> a c F' e F" \| b F" e F" \| d G' b~~
	~~F" -> c G' b \| (eps)~~

	~~=== FIRST & FOLLOW sets ===~~

	~~FIRST(G) = { a, b, (eps) } FOLLOW(G) = { $ }~~
	~~FIRST(G') = { b, (eps) } FOLLOW(G') = { $, b }~~
	~~FIRST(G") = { a, b, d } FOLLOW(G") = { $ }~~
	~~FIRST(F') = { a, b, d } FOLLOW(F') = { e }~~
	~~FIRST(F") = { c, (eps) } FOLLOW(F") = { e }~~


	[[~~category~~:~~Compiladores]]~~
	~~[[category:Ensino~~]]

Root at 14:40, 6 April 2015

2015-04-06T14:40:50Z

← Older revision		Revision as of 14:40, 6 April 2015
Line 136:		Line 136:


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

Root: /* FIRST & FOLLOW sets */

2015-03-27T15:01:30Z

FIRST & FOLLOW sets

← Older revision		Revision as of 15:01, 27 March 2015
Line 129:		Line 129:
	=== FIRST & FOLLOW sets ===		=== FIRST & FOLLOW sets ===

	FIRST(G) = { a, b, (eps) }		FIRST(G) = { a, b, (eps) } FOLLOW(G) = { $ }
	FIRST(G') = { b, (eps) }		FIRST(G') = { b, (eps) } FOLLOW(G') = { $, b }
	FIRST(G") = { a, b, d }		FIRST(G") = { a, b, d } FOLLOW(G") = { $ }
	FIRST(F') = { a, b, d }		FIRST(F') = { a, b, d } FOLLOW(F') = { e }
	FIRST(F") = { c, (eps) }		FIRST(F") = { c, (eps) } FOLLOW(F") = { e }

	~~FOLLOW(G) = { $ }~~
	~~FOLLOW(G') = { $, b }~~
	~~FOLLOW(G") = { $ }~~
	~~FOLLOW(F') = { e }~~
	~~FOLLOW(F") = { e }~~

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

Root: /* Elimination of Mutual Recursion: Expanding F in G */

2015-03-27T14:55:49Z

Elimination of Mutual Recursion: Expanding F in G

@@ Line 126: / Line 126: @@
   F' -> a c F' e F" | b F" e F" | d G' b
   F" -> c G' b | (eps)
 [[category:Compilers]]
 [[category:Teaching]]

Root: /* ELimination of Mutual Recursion: Expanding F in G */

2015-03-27T14:04:33Z

ELimination of Mutual Recursion: Expanding F in G

← Older revision		Revision as of 14:04, 27 March 2015
Line 71:		Line 71:
	F" -> d b F' \| a c F" e F' \| b F' e F'		F" -> d b F' \| a c F" e F' \| b F' e F'
	-->		-->
	== ~~ELimination~~ of Mutual Recursion: Expanding F in G ==		=== Elimination of Mutual Recursion: Expanding F in G ===

	Initial grammar:		Initial grammar:

Root: /* Solution */

2015-03-27T14:04:16Z

Solution

← Older revision		Revision as of 14:04, 27 March 2015
Line 15:		Line 15:

	Something to keep in mind at all times: '''never eliminate the rules corresponding to the initial symbol'''		Something to keep in mind at all times: '''never eliminate the rules corresponding to the initial symbol'''
			<!--
	There are two ways of handling the mutual recursion: either expanding F in G or G in F.		There are two ways of handling the mutual recursion: either expanding F in G or G in F.

Line 70:		Line 70:
	F' -> c b F' \| (eps)		F' -> c b F' \| (eps)
	F" -> d b F' \| a c F" e F' \| b F' e F'		F" -> d b F' \| a c F" e F' \| b F' e F'
			-->
	== Expanding F in G ==		== ELimination of Mutual Recursion: Expanding F in G ==

	Initial grammar:		Initial grammar:

Root: /* Expanding F in G */

2011-03-21T10:15:05Z

Expanding F in G

← Older revision		Revision as of 10:15, 21 March 2011
Line 124:		Line 124:
	G' -> b c G' \| (eps)		G' -> b c G' \| (eps)
	G" -> a c F' e c G' \| b F" e c G' \| d G'		G" -> a c F' e c G' \| b F" e c G' \| d G'
	F' -> a c F' e F" \| b F" e F"		F' -> a c F' e F" \| b F" e F" \| d G' b
	F" -> c G' b \| (eps)		F" -> c G' b \| (eps)

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

Root: /* Solution */

2010-04-16T19:19:48Z

Solution

← Older revision		Revision as of 19:19, 16 April 2010
Line 16:		Line 16:
	Something to keep in mind at all times: '''never eliminate the rules corresponding to the initial symbol'''		Something to keep in mind at all times: '''never eliminate the rules corresponding to the initial symbol'''

	There are two ways of handling the mutual recursion: either ~~expand~~ F in G or G in F.		There are two ways of handling the mutual recursion: either expanding F in G or G in F.

	== Expanding G in F ==		== Expanding G in F ==

Root: /* Expanding F in G */

2010-04-16T19:16:48Z

Expanding F in G

← Older revision		Revision as of 19:16, 16 April 2010
Line 119:		Line 119:
	F" -> c G' b \| (eps)		F" -> c G' b \| (eps)

	Factoring F' prefixes:		Factoring F' prefixes, we get to the final version:

	G -> a c G" \| b c G' \| (eps)		G -> a c G" \| b c G' \| (eps)

Root at 19:15, 16 April 2010

2010-04-16T19:15:36Z

← Older revision		Revision as of 19:15, 16 April 2010
Line 1:		Line 1:
			{{TOCright}}
	= Problem =		= Problem =

	Consider the following grammar, where '''<tt>F</tt>''' is the initial symbol and '''<tt>{a,b,c,d,e}</tt>''' is the set of terminal symbols:		Consider the following grammar, where '''<tt>G</tt>''' is the initial symbol and '''<tt>{a,b,c,d,e}</tt>''' is the set of terminal symbols:

	O -> a		O -> a

← Older revision		Revision as of 22:19, 5 December 2018
Line 1:		Line 1:
	~~{{TOCright}}~~		#REDIRECT [[ist:Top-Down Parsing/Exercise 3]]
	~~= Problem =~~

	~~Consider the following grammar, where '''<tt>G</tt>''' is the initial symbol and '''<tt>{a,b,c,d,e}</tt>''' is the set of terminal symbols:~~

	~~O -> a~~
	~~G -> F c \| O c d \| (eps)~~
	~~F -> G b \| O c F e~~

	# ~~Examine the grammar and rewrite it so that an LL(1) predictive parser can be built for the corresponding language.~~
	~~# Compute the FIRST and FOLLOW sets for all non-terminal symbols in the new grammar and build the parse table.~~
	~~# Show the analysis table (stack, input, and actions) for the parsing process of the '''<tt>acbec</tt>''' input sequence.~~

	~~= Solution =~~

	~~Something to keep in mind at all times: '''never eliminate the rules corresponding to the initial symbol'''~~
	~~<!--~~
	~~There are two ways of handling the mutual recursion: either expanding F in G or G in F.~~

	~~== Expanding G in F ==~~

	~~Initial grammar:~~

	~~O -> a~~
	~~G -> F c \| O c d \| (eps)~~
	~~F -> G b \| O c F e~~

	~~Eliminating the singularity (O->a):~~

	~~G -> F c \| a c d \| (eps)~~
	~~F -> G b \| a c F e~~

	~~Expanding G in F:~~

	~~G -> F c \| a c d \| (eps)~~
	~~F -> F c b \| a c d b \| b \| a c F e~~

	~~Eliminate left recursion in F:~~

	~~G -> F c \| a c d \| (eps)~~
	~~F -> a c d b F' \| b F' \| a c F e F'~~
	~~F' -> c b F' \| (eps)~~

	~~Factor F prefixes and expand it in G:~~

	~~G -> a c F" c \| b F' c \| a c d \| (eps)~~
	~~F -> a c F" \| b F'~~
	~~F' -> c b F' \| (eps)~~
	~~F" -> d b F' \| F e F'~~

	~~Note that we still have common prefixes to factor in G and a non-terminal left-corner in F''. The next step will handle those cases:~~

	~~G -> a c G' \| b F' c \| (eps)~~
	~~G' -> F" c \| d~~
	~~F' -> c b F' \| (eps)~~
	~~F" -> d b F' \| a c F" e F' \| b F' e F'~~

	~~F was eliminated because it became unreachable from the start symbol. The grammar still has a non-terminal left corner in G', so we need to eliminate it.~~

	~~G -> a c G' \| b F' c \| (eps)~~
	~~G' -> d b F' c \| a c F" e F' c \| b F' e F' c \| d~~
	~~F' -> c b F' \| (eps)~~
	~~F" -> d b F' \| a c F" e F' \| b F' e F'~~

	~~Factoring prefixes in G', we get to the final version:~~

	~~G -> a c G' \| b F' c \| (eps)~~
	~~G' -> d G" \| a c F" e F' c \| b F' e F' c~~
	~~G" -> b F' c \| (eps)~~
	~~F' -> c b F' \| (eps)~~
	~~F" -> d b F' \| a c F" e F' \| b F' e F'~~
	~~-->~~
	~~=== Elimination of Mutual Recursion: Expanding F in G ===~~

	~~Initial grammar:~~

	~~O -> a~~
	~~G -> F c \| O c d \| (eps)~~
	~~F -> G b \| O c F e~~

	~~Eliminating the singularity (O->a):~~

	~~G -> F c \| a c d \| (eps)~~
	~~F -> G b \| a c F e~~

	~~Expanding F in G:~~

	~~G -> G b c \| a c F e c \| a c d \| (eps)~~
	~~F -> G b \| a c F e~~

	~~Eliminating left recursion in G:~~

	~~G -> a c F e c G' \| a c d G' \| G'~~
	~~G' -> b c G' \| (eps)~~
	~~F -> G b \| a c F e~~

	~~Factoring G prefixes:~~

	~~G -> a c G" \| b c G' \| (eps)~~
	~~G' -> b c G' \| (eps)~~
	~~G" -> F e c G' \| d G'~~
	~~F -> a c G" b \| b c G' b \| b \| a c F e~~

	~~Factoring F prefixes:~~

	~~G -> a c G" \| b c G' \| (eps)~~
	~~G' -> b c G' \| (eps)~~
	~~G" -> F e c G' \| d G'~~
	~~F -> a c F' \| b F"~~
	~~F' -> G" b \| F e~~
	~~F" -> c G' b \| (eps)~~

	~~Eliminating non-terminal left corners (note that F becomes unreachable):~~

	~~G -> a c G" \| b c G' \| (eps)~~
	~~G' -> b c G' \| (eps)~~
	~~G" -> a c F' e c G' \| b F" e c G' \| d G'~~
	~~F' -> a c F' e c G' b \| b F" e c G' b \| d G' b \| a c F' e \| b F" e~~
	~~F" -> c G' b \| (eps)~~

	~~Factoring F' prefixes, we get to the final version:~~

	~~G -> a c G" \| b c G' \| (eps)~~
	~~G' -> b c G' \| (eps)~~
	~~G" -> a c F' e c G' \| b F" e c G' \| d G'~~
	~~F' -> a c F' e F" \| b F" e F" \| d G' b~~
	~~F" -> c G' b \| (eps)~~

	~~=== FIRST & FOLLOW sets ===~~

	~~FIRST(G) = { a, b, (eps) } FOLLOW(G) = { $ }~~
	~~FIRST(G') = { b, (eps) } FOLLOW(G') = { $, b }~~
	~~FIRST(G") = { a, b, d } FOLLOW(G") = { $ }~~
	~~FIRST(F') = { a, b, d } FOLLOW(F') = { e }~~
	~~FIRST(F") = { c, (eps) } FOLLOW(F") = { e }~~


	[[~~category~~:~~Compiladores]]~~
	~~[[category:Ensino~~]]