Top-Down Parsing/Example 3 - Revision history

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

2018-12-05T22:18:37Z

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

Root at 14:40, 6 April 2015

2015-04-06T14:40:29Z

← Older revision		Revision as of 14:40, 6 April 2015
Line 313:		Line 313:
	</table>		</table>

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

Root: /* Solution */

2015-03-23T19:26:28Z

Solution

← Older revision		Revision as of 19:26, 23 March 2015
Line 16:		Line 16:
	The grammar can be parsed by an LL(1) parser if it does not have left recursion and no ambiguity is present (i.e., the LOOKAHEADs for all productions of each non-terminal are disjoint).		The grammar can be parsed by an LL(1) parser if it does not have left recursion and no ambiguity is present (i.e., the LOOKAHEADs for all productions of each non-terminal are disjoint).

	A simple inspection of the grammar shows that indirect left recursion is present in rules B and D. Also, there are left corners that may hide ambiguity (E).		A simple inspection of the grammar shows that indirect left recursion is present in rules '''B''' and '''D'''. Also, there are left corners that may hide ambiguity ('''E''').

	The first step, then, is to rewrite the grammar so that mutual recursion is eliminated (A becomes unreachable and can be removed from the grammar):		The first step, then, is to rewrite the grammar so that mutual recursion is eliminated ('''D''' becomes unreachable and can be removed from the grammar):

	S -> u B z		S -> u B z
Line 25:		Line 25:
	E -> v \| v x		E -> v \| v x

	Now we handle the left corner (E in B) (since E is not completely replaced, it cannot be removed from the grammar):		Now we handle the left corner ('''E''' in '''B''') (since '''E''' is not completely replaced, it cannot be removed from the grammar):

	S -> u B z		S -> u B z
Line 129:		Line 129:
	</table>		</table>

	The following table shows the parsing of the '''~~<tt>~~uvuvxz~~</tt>~~''' input sequence.		The following table shows the parsing of the '''uvuvxz''' input sequence.

	<table border="0" cellpadding="2" cellspacing="2" width="346">		<table border="0" cellpadding="2" cellspacing="2" width="346">

Root: Recursive Descent Parsing: Example 3 moved to Top-Down Parsing/Example 3

2010-04-09T14:30:04Z

Recursive Descent Parsing: Example 3 moved to Top-Down Parsing/Example 3

← Older revision	Revision as of 14:30, 9 April 2010
(No difference)

Root at 18:31, 10 January 2009

2009-01-10T18:31:23Z

← Older revision		Revision as of 18:31, 10 January 2009
Line 35:		Line 35:
	S -> u B z		S -> u B z
	B -> v u E B1 \| v x u E B1		B -> v u E B1 \| v x u E B1
	B1 -> v B1 \| y E B1 \| Îµ		B1 -> v B1 \| y E B1 \| ε
	E -> v \| v x		E -> v \| v x

Line 42:		Line 42:
	S -> u B z		S -> u B z
	B -> v B2		B -> v B2
	B1 -> v B1 \| y E B1 \| Îµ		B1 -> v B1 \| y E B1 \| ε
	B2 -> u E B1 \| x u E B1		B2 -> u E B1 \| x u E B1
	E -> v E1		E -> v E1
	E1 -> x \| Îµ		E1 -> x \| ε

	The FIRST and FOLLOW sets are as follows:		The FIRST and FOLLOW sets are as follows:
Line 51:		Line 51:
	FIRST(S) = FIRST(u B z) = {u}		FIRST(S) = FIRST(u B z) = {u}
	FIRST(B) = FIRST(v B2) = {v}		FIRST(B) = FIRST(v B2) = {v}
	FIRST(B1) = FIRST(v B1) ~~âˆª~~ FIRST(y E B1) ~~âˆª~~ {Îµ} = {v, y, Îµ}		FIRST(B1) = FIRST(v B1) ∪ FIRST(y E B1) ∪ {ε} = {v, y, ε}
	FIRST(B2) = FIRST(u E B1) ~~âˆª~~ FIRST(x u E B1) = {u, x}		FIRST(B2) = FIRST(u E B1) ∪ FIRST(x u E B1) = {u, x}
	FIRST(E) = FIRST(v E1) = {v}		FIRST(E) = FIRST(v E1) = {v}
	FIRST(E1) = {x} ~~âˆª~~ {Îµ} = {x, Îµ}		FIRST(E1) = {x} ∪ {ε} = {x, ε}

	FOLLOW(S) = {$} FOLLOW(B) = {z} FOLLOW(B1) ~~âŠ‡~~ FOLLOW(B2) FOLLOW(B2) ~~âŠ‡~~ FOLLOW(B)		FOLLOW(S) = {$} FOLLOW(B) = {z} FOLLOW(B1) ⊇ FOLLOW(B2) FOLLOW(B2) ⊇ FOLLOW(B)
	FOLLOW(B1) = FOLLOW(B2) = FOLLOW(B) = {z}		FOLLOW(B1) = FOLLOW(B2) = FOLLOW(B) = {z}
	FOLLOW(E) = FIRST(B1)\{Îµ} ~~âˆª~~ FOLLOW(B1) ~~âˆª~~ FOLLOW(B2) = {v, y, z}		FOLLOW(E) = FIRST(B1)\{ε} ∪ FOLLOW(B1) ∪ FOLLOW(B2) = {v, y, z}
	FOLLOW(E1) = FOLLOW(E) = {v, y, z}		FOLLOW(E1) = FOLLOW(E) = {v, y, z}

Line 97:		Line 97:
	<th style="border: 1px solid black; background: rgb(255, 255, 204) none repeat scroll 0% 50%; padding-left: 10px; padding-right: 10px; font-weight: normal; -moz-background-clip: -moz-initial; -moz-background-origin: -moz-initial; -moz-background-inline-policy: -moz-initial;"><font face="Courier New, Courier, monospace"></font></th>		<th style="border: 1px solid black; background: rgb(255, 255, 204) none repeat scroll 0% 50%; padding-left: 10px; padding-right: 10px; font-weight: normal; -moz-background-clip: -moz-initial; -moz-background-origin: -moz-initial; -moz-background-inline-policy: -moz-initial;"><font face="Courier New, Courier, monospace"></font></th>
	<th style="border: 1px solid black; background: rgb(255, 255, 204) none repeat scroll 0% 50%; padding-left: 10px; padding-right: 10px; font-weight: normal; -moz-background-clip: -moz-initial; -moz-background-origin: -moz-initial; -moz-background-inline-policy: -moz-initial;"><font face="Courier New, Courier, monospace">B1 -> y E B1</font></th>		<th style="border: 1px solid black; background: rgb(255, 255, 204) none repeat scroll 0% 50%; padding-left: 10px; padding-right: 10px; font-weight: normal; -moz-background-clip: -moz-initial; -moz-background-origin: -moz-initial; -moz-background-inline-policy: -moz-initial;"><font face="Courier New, Courier, monospace">B1 -> y E B1</font></th>
	<th style="border: 1px solid black; background: rgb(255, 255, 204) none repeat scroll 0% 50%; padding-left: 10px; padding-right: 10px; font-weight: normal; -moz-background-clip: -moz-initial; -moz-background-origin: -moz-initial; -moz-background-inline-policy: -moz-initial;"><font face="Courier New, Courier, monospace">B1 -> </font><font face="Courier New, Courier, monospace">Îµ</font></th>		<th style="border: 1px solid black; background: rgb(255, 255, 204) none repeat scroll 0% 50%; padding-left: 10px; padding-right: 10px; font-weight: normal; -moz-background-clip: -moz-initial; -moz-background-origin: -moz-initial; -moz-background-inline-policy: -moz-initial;"><font face="Courier New, Courier, monospace">B1 -> </font><font face="Courier New, Courier, monospace">ε</font></th>
	<th style="border: 1px solid black; background: rgb(255, 255, 204) none repeat scroll 0% 50%; padding-left: 10px; padding-right: 10px; font-weight: normal; -moz-background-clip: -moz-initial; -moz-background-origin: -moz-initial; -moz-background-inline-policy: -moz-initial;"><font face="Courier New, Courier, monospace"></font></th>		<th style="border: 1px solid black; background: rgb(255, 255, 204) none repeat scroll 0% 50%; padding-left: 10px; padding-right: 10px; font-weight: normal; -moz-background-clip: -moz-initial; -moz-background-origin: -moz-initial; -moz-background-inline-policy: -moz-initial;"><font face="Courier New, Courier, monospace"></font></th>
	</tr>		</tr>
Line 121:		Line 121:
	<th style="border: 1px solid black; background: wheat none repeat scroll 0% 50%; padding-left: 10px; padding-right: 10px; -moz-background-clip: -moz-initial; -moz-background-origin: -moz-initial; -moz-background-inline-policy: -moz-initial;">E1</th>		<th style="border: 1px solid black; background: wheat none repeat scroll 0% 50%; padding-left: 10px; padding-right: 10px; -moz-background-clip: -moz-initial; -moz-background-origin: -moz-initial; -moz-background-inline-policy: -moz-initial;">E1</th>
	<th style="border: 1px solid black; background: rgb(255, 255, 204) none repeat scroll 0% 50%; padding-left: 10px; padding-right: 10px; font-weight: normal; -moz-background-clip: -moz-initial; -moz-background-origin: -moz-initial; -moz-background-inline-policy: -moz-initial;"><font face="Courier New, Courier, monospace"></font></th>		<th style="border: 1px solid black; background: rgb(255, 255, 204) none repeat scroll 0% 50%; padding-left: 10px; padding-right: 10px; font-weight: normal; -moz-background-clip: -moz-initial; -moz-background-origin: -moz-initial; -moz-background-inline-policy: -moz-initial;"><font face="Courier New, Courier, monospace"></font></th>
	<th style="border: 1px solid black; background: rgb(255, 255, 204) none repeat scroll 0% 50%; padding-left: 10px; padding-right: 10px; font-weight: normal; -moz-background-clip: -moz-initial; -moz-background-origin: -moz-initial; -moz-background-inline-policy: -moz-initial;"><font face="Courier New, Courier, monospace">E1 -> </font><font face="Courier New, Courier, monospace">Îµ</font></th>		<th style="border: 1px solid black; background: rgb(255, 255, 204) none repeat scroll 0% 50%; padding-left: 10px; padding-right: 10px; font-weight: normal; -moz-background-clip: -moz-initial; -moz-background-origin: -moz-initial; -moz-background-inline-policy: -moz-initial;"><font face="Courier New, Courier, monospace">E1 -> </font><font face="Courier New, Courier, monospace">ε</font></th>
	<th style="border: 1px solid black; background: rgb(255, 255, 204) none repeat scroll 0% 50%; padding-left: 10px; padding-right: 10px; font-weight: normal; -moz-background-clip: -moz-initial; -moz-background-origin: -moz-initial; -moz-background-inline-policy: -moz-initial;"><font face="Courier New, Courier, monospace">E1 -> x</font></th>		<th style="border: 1px solid black; background: rgb(255, 255, 204) none repeat scroll 0% 50%; padding-left: 10px; padding-right: 10px; font-weight: normal; -moz-background-clip: -moz-initial; -moz-background-origin: -moz-initial; -moz-background-inline-policy: -moz-initial;"><font face="Courier New, Courier, monospace">E1 -> x</font></th>
	<th style="border: 1px solid black; background: rgb(255, 255, 204) none repeat scroll 0% 50%; padding-left: 10px; padding-right: 10px; font-weight: normal; -moz-background-clip: -moz-initial; -moz-background-origin: -moz-initial; -moz-background-inline-policy: -moz-initial;"><font face="Courier New, Courier, monospace">E1 -> </font><font face="Courier New, Courier, monospace">Îµ</font></th>		<th style="border: 1px solid black; background: rgb(255, 255, 204) none repeat scroll 0% 50%; padding-left: 10px; padding-right: 10px; font-weight: normal; -moz-background-clip: -moz-initial; -moz-background-origin: -moz-initial; -moz-background-inline-policy: -moz-initial;"><font face="Courier New, Courier, monospace">E1 -> </font><font face="Courier New, Courier, monospace">ε</font></th>
	<th style="border: 1px solid black; background: rgb(255, 255, 204) none repeat scroll 0% 50%; padding-left: 10px; padding-right: 10px; font-weight: normal; -moz-background-clip: -moz-initial; -moz-background-origin: -moz-initial; -moz-background-inline-policy: -moz-initial;"><font face="Courier New, Courier, monospace">E1 -> </font><font face="Courier New, Courier, monospace">Îµ</font></th>		<th style="border: 1px solid black; background: rgb(255, 255, 204) none repeat scroll 0% 50%; padding-left: 10px; padding-right: 10px; font-weight: normal; -moz-background-clip: -moz-initial; -moz-background-origin: -moz-initial; -moz-background-inline-policy: -moz-initial;"><font face="Courier New, Courier, monospace">E1 -> </font><font face="Courier New, Courier, monospace">ε</font></th>
	<th style="border: 1px solid black; background: rgb(255, 255, 204) none repeat scroll 0% 50%; padding-left: 10px; padding-right: 10px; font-weight: normal; -moz-background-clip: -moz-initial; -moz-background-origin: -moz-initial; -moz-background-inline-policy: -moz-initial;"><font face="Courier New, Courier, monospace"></font></th>		<th style="border: 1px solid black; background: rgb(255, 255, 204) none repeat scroll 0% 50%; padding-left: 10px; padding-right: 10px; font-weight: normal; -moz-background-clip: -moz-initial; -moz-background-origin: -moz-initial; -moz-background-inline-policy: -moz-initial;"><font face="Courier New, Courier, monospace"></font></th>
	</tr>		</tr>
Line 285:		Line 285:
	bgcolor="#ffffcc" valign="top"><font		bgcolor="#ffffcc" valign="top"><font
	face="Courier New, Courier, monospace">B1 -> </font><font		face="Courier New, Courier, monospace">B1 -> </font><font
	face="Courier New, Courier, monospace">Îµ</font></td>		face="Courier New, Courier, monospace">ε</font></td>
	</tr>		</tr>
	<tr>		<tr>

Root: /* Solution */

2008-04-11T20:57:48Z

Solution

Show changes

Root: /* Solution */

2008-04-11T20:56:22Z

Solution

@@ Line 60: / Line 60: @@
    FOLLOW(E)  = FIRST(B1)\{Îµ} âˆª FOLLOW(B1) âˆª FOLLOW(B2) = {v, y, z}
    FOLLOW(E1) = FOLLOW(E) = {v, y, z}
 [[category:Compilers]]
 [[category:Teaching]]

Root: /* Solution */

2008-04-11T20:43:39Z

Solution

← Older revision		Revision as of 20:43, 11 April 2008
Line 36:		Line 36:
	B -> v u E B1 \| v x u E B1		B -> v u E B1 \| v x u E B1
	B1 -> v B1 \| y E B1 \| Îµ		B1 -> v B1 \| y E B1 \| Îµ
			E -> v \| v x

	Factoring...		Factoring...
Line 43:		Line 44:
	B1 -> v B1 \| y E B1 \| Îµ		B1 -> v B1 \| y E B1 \| Îµ
	B2 -> u E B1 \| x u E B1		B2 -> u E B1 \| x u E B1
			E -> v E1
			E1 -> x \| Îµ

	The FIRST and FOLLOW sets are as follows:		The FIRST and FOLLOW sets are as follows:
Line 50:		Line 53:
	FIRST(B1) = FIRST(v B1) âˆª FIRST(y E B1) âˆª {Îµ} = {v, y, Îµ}		FIRST(B1) = FIRST(v B1) âˆª FIRST(y E B1) âˆª {Îµ} = {v, y, Îµ}
	FIRST(B2) = FIRST(u E B1) âˆª FIRST(x u E B1) = {u, x}		FIRST(B2) = FIRST(u E B1) âˆª FIRST(x u E B1) = {u, x}
			FIRST(E) = FIRST(v E1) = {v}
			FIRST(E1) = {x} âˆª {Îµ} = {x, Îµ}

	FOLLOW(S) = {$} FOLLOW(B1) âŠ‡ FOLLOW(B2)		FOLLOW(S) = {$} FOLLOW(B) = {z} FOLLOW(B1) âŠ‡ FOLLOW(B2) FOLLOW(B2) âŠ‡ FOLLOW(B)
	~~FOLLOW(B) = {z}~~ FOLLOW(B2) âŠ‡ FOLLOW(B)

	FOLLOW(B1) = FOLLOW(B2) = FOLLOW(B) = {z}		FOLLOW(B1) = FOLLOW(B2) = FOLLOW(B) = {z}
			FOLLOW(E) = FIRST(B1)\{Îµ} âˆª FOLLOW(B1) âˆª FOLLOW(B2) = {v, y, z}
			FOLLOW(E1) = FOLLOW(E) = {v, y, z}

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

Root: /* Solution */

2008-04-11T20:36:26Z

Solution

← Older revision		Revision as of 20:36, 11 April 2008
Line 25:		Line 25:
	E -> v \| v x		E -> v \| v x

	Now we handle the left corner (E in B) (E ~~also becomes unreachable and can~~ be removed from the grammar):		Now we handle the left corner (E in B) (since E is not completely replaced, it cannot be removed from the grammar):

	S -> u B z		S -> u B z
	B -> B v \| v u v \| v x u ~~v x~~ \| B y ~~v \| B y v x~~		B -> B v \| v u E \| v x u E \| B y E
	~~<font color="red">~~E -> v \| v x~~</font>~~		E -> v \| v x

	Now, left recursion can be eliminated:		Now, left recursion can be eliminated:

	S -> u B z		S -> u B z
	B -> v u v B1 \| v x u ~~v x~~ B1		B -> v u E B1 \| v x u E B1
	B1 -> v B1 \| y ~~v B1 \| y v x~~ B1 \| Îµ		B1 -> v B1 \| y E B1 \| Îµ

	Factoring...		Factoring...
Line 41:		Line 41:
	S -> u B z		S -> u B z
	B -> v B2		B -> v B2
	B1 -> v B1 \| y ~~v B3 \| Îµ~~		B1 -> v B1 \| y E B1 \| Îµ
	~~B2 -> u v B1 \| x u v x B1~~		B2 -> u E B1 \| x u E B1
	~~B3 -> B1 \| x B1~~

	~~Eliminating the left corner in B3 (note that we do not completely replace B1, since a new factorization would be needed):~~

	~~S -> u B z~~
	~~B -> v B2~~
	~~B1 -> v~~ B1 ~~\| y v B3~~ \| Îµ
	B2 -> u v B1 \| x u ~~v x~~ B1
	~~B3 -> v B1 \| y v B3 \| x B1 \| Îµ~~

	The FIRST and FOLLOW sets are as follows:		The FIRST and FOLLOW sets are as follows:
Line 57:		Line 48:
	FIRST(S) = FIRST(u B z) = {u}		FIRST(S) = FIRST(u B z) = {u}
	FIRST(B) = FIRST(v B2) = {v}		FIRST(B) = FIRST(v B2) = {v}
	FIRST(B1) = FIRST(v B1) âˆª FIRST(y ~~v B3~~) âˆª {Îµ} = {v, y, Îµ}		FIRST(B1) = FIRST(v B1) âˆª FIRST(y E B1) âˆª {Îµ} = {v, y, Îµ}
	FIRST(B2) = FIRST(u v B1) âˆª FIRST(x u ~~v x~~ B1) = {u, x}		FIRST(B2) = FIRST(u E B1) âˆª FIRST(x u E B1) = {u, x}
	~~FIRST(B3) = FIRST(v B1) âˆª FIRST(y v B3) âˆª FIRST(x B1) âˆª {Îµ} = {v, x, y, Îµ~~}

	FOLLOW(S) = {$} FOLLOW(B1) âŠ‡ FOLLOW(B2) ~~FOLLOW(B2) âŠ‡ FOLLOW(B) FOLLOW(B3) âŠ‡ FOLLOW(B1)~~		FOLLOW(S) = {$} FOLLOW(B1) âŠ‡ FOLLOW(B2)
	FOLLOW(B) = {z} FOLLOW(B1) âŠ‡ FOLLOW(B3)		FOLLOW(B) = {z} FOLLOW(B2) âŠ‡ FOLLOW(B)

	FOLLOW(B1) = FOLLOW(B2~~) = FOLLOW(B3~~) = FOLLOW(B) = {z}		FOLLOW(B1) = FOLLOW(B2) = FOLLOW(B) = {z}

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

Root: /* Solution */

2008-04-11T20:06:37Z

Solution

← Older revision		Revision as of 20:06, 11 April 2008
Line 63:		Line 63:
	FOLLOW(S) = {$} FOLLOW(B1) âŠ‡ FOLLOW(B2) FOLLOW(B2) âŠ‡ FOLLOW(B) FOLLOW(B3) âŠ‡ FOLLOW(B1)		FOLLOW(S) = {$} FOLLOW(B1) âŠ‡ FOLLOW(B2) FOLLOW(B2) âŠ‡ FOLLOW(B) FOLLOW(B3) âŠ‡ FOLLOW(B1)
	FOLLOW(B) = {z} FOLLOW(B1) âŠ‡ FOLLOW(B3)		FOLLOW(B) = {z} FOLLOW(B1) âŠ‡ FOLLOW(B3)

	FOLLOW(B1) = FOLLOW(B2) = FOLLOW(B3) = FOLLOW(B) = {z}		FOLLOW(B1) = FOLLOW(B2) = FOLLOW(B3) = FOLLOW(B) = {z}

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