Top-Down Parsing/Example 2 - Revision history

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

2018-12-05T22:18:19Z

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

Root at 14:40, 6 April 2015

2015-04-06T14:40:20Z

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

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

Root: /* Solution */

2010-04-14T19:35:10Z

Solution

@@ Line 179: / Line 179: @@
        <td style="border-style: solid; border-width: 1px; border-color: black;" align="right" bgcolor="#ffffcc" valign="top"><font
   face="Courier New, Courier, monospace">S'$</font></td>
        <td style="border-style: solid; border-width: 1px; border-color: black;" align="right" bgcolor="#ffffcc" valign="top"><font
   face="Courier New, Courier, monospace">$<br>

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

2010-04-09T14:29:44Z

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

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

Root at 18:30, 10 January 2009

2009-01-10T18:30:01Z

← Older revision		Revision as of 18:30, 10 January 2009
Line 6:		Line 6:
	A -> C d h \| S e		A -> C d h \| S e
	C -> g B \| h f		C -> g B \| h f
	B -> g \| Îµ		B -> g \| ε

	# Examine the grammar and rewrite it so that an LL(1) predictive parser can be built for the corresponding language.		# Examine the grammar and rewrite it so that an LL(1) predictive parser can be built for the corresponding language.
Line 23:		Line 23:
	<font color="red">A -> C d h \| S e</font>		<font color="red">A -> C d h \| S e</font>
	C -> g B \| h f		C -> g B \| h f
	B -> g \| Îµ		B -> g \| ε

	Now we handle the left corner (C in S) (C also becomes unreachable and can be removed from the grammar):		Now we handle the left corner (C in S) (C also becomes unreachable and can be removed from the grammar):
Line 29:		Line 29:
	S -> g B d h B d \| h f d h B d \| S e B d \| g B d \| h f d		S -> g B d h B d \| h f d h B d \| S e B d \| g B d \| h f d
	<font color="red">C -> g B \| h f</font>		<font color="red">C -> g B \| h f</font>
	B -> g \| Îµ		B -> g \| ε

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

	S -> g B d h B d S' \| h f d h B d S' \| g B d S' \| h f d S'		S -> g B d h B d S' \| h f d h B d S' \| g B d S' \| h f d S'
	S' -> e B d S' \| Îµ		S' -> e B d S' \| ε
	B -> g \| Îµ		B -> g \| ε

	Factoring...		Factoring...

	S -> g B d S" \| h f d S"		S -> g B d S" \| h f d S"
	S' -> e B d S' \| Îµ		S' -> e B d S' \| ε
	S" -> h B d S' \| S'		S" -> h B d S' \| S'
	B -> g \| Îµ		B -> g \| ε

	Removing the left corner S' from S":		Removing the left corner S' from S":

	S -> g B d S" \| h f d S"		S -> g B d S" \| h f d S"
	S' -> e B d S' \| Îµ		S' -> e B d S' \| ε
	S" -> h B d S' \| e B d S' \| Îµ		S" -> h B d S' \| e B d S' \| ε
	B -> g \| Îµ		B -> g \| ε

	The FIRST and FOLLOW sets are as follows:		The FIRST and FOLLOW sets are as follows:

	FIRST(S) = FIRST(g B d S") ~~âˆª~~ FIRST(h f d S") = {g, h}		FIRST(S) = FIRST(g B d S") ∪ FIRST(h f d S") = {g, h}
	FIRST(S') = FIRST(e B d S') ~~âˆª~~ {Îµ} = {e, Îµ}		FIRST(S') = FIRST(e B d S') ∪ {ε} = {e, ε}
	FIRST(S") = FIRST(h B d S') ~~âˆª~~ FIRST(e B d S') ~~âˆª~~ {Îµ} = {e, h, Îµ}		FIRST(S") = FIRST(h B d S') ∪ FIRST(e B d S') ∪ {ε} = {e, h, ε}
	FIRST(B) = FIRST(g) ~~âˆª~~ {Îµ} = {g, Îµ}		FIRST(B) = FIRST(g) ∪ {ε} = {g, ε}

	FOLLOW(S) = {$}		FOLLOW(S) = {$}
	FOLLOW(S') ~~âŠ‡~~ FOLLOW(S") ~~âŠ‡~~ FOLLOW(S)		FOLLOW(S') ⊇ FOLLOW(S") ⊇ FOLLOW(S)
	FOLLOW(S') = FOLLOW(S") = FOLLOW(S) = {$}		FOLLOW(S') = FOLLOW(S") = FOLLOW(S) = {$}
	FOLLOW(B) = {d}		FOLLOW(B) = {d}
Line 87:		Line 87:
	! style="border-style: solid; border-width: 1px; border-color: black; padding-left: 10px; padding-right: 10px; font-weight: normal; align: center; background: #ffffcc;"\|		! style="border-style: solid; border-width: 1px; border-color: black; padding-left: 10px; padding-right: 10px; font-weight: normal; align: center; background: #ffffcc;"\|
	! style="border-style: solid; border-width: 1px; border-color: black; padding-left: 10px; padding-right: 10px; font-weight: normal; align: center; background: #ffffcc;"\|		! style="border-style: solid; border-width: 1px; border-color: black; padding-left: 10px; padding-right: 10px; font-weight: normal; align: center; background: #ffffcc;"\|
	! style="border-style: solid; border-width: 1px; border-color: black; padding-left: 10px; padding-right: 10px; font-weight: normal; align: center; background: #ffffcc;"\| S' -> Îµ		! style="border-style: solid; border-width: 1px; border-color: black; padding-left: 10px; padding-right: 10px; font-weight: normal; align: center; background: #ffffcc;"\| S' -> ε
	\|-		\|-
	! style="border-style: solid; border-width: 1px; border-color: black; padding-left: 10px; padding-right: 10px; background: wheat;" \| S"		! style="border-style: solid; border-width: 1px; border-color: black; padding-left: 10px; padding-right: 10px; background: wheat;" \| S"
Line 95:		Line 95:
	! style="border-style: solid; border-width: 1px; border-color: black; padding-left: 10px; padding-right: 10px; font-weight: normal; align: center; background: #ffffcc;"\|		! style="border-style: solid; border-width: 1px; border-color: black; padding-left: 10px; padding-right: 10px; font-weight: normal; align: center; background: #ffffcc;"\|
	! style="border-style: solid; border-width: 1px; border-color: black; padding-left: 10px; padding-right: 10px; font-weight: normal; align: center; background: #ffffcc;"\| S" -> h B d S'		! style="border-style: solid; border-width: 1px; border-color: black; padding-left: 10px; padding-right: 10px; font-weight: normal; align: center; background: #ffffcc;"\| S" -> h B d S'
	! style="border-style: solid; border-width: 1px; border-color: black; padding-left: 10px; padding-right: 10px; font-weight: normal; align: center; background: #ffffcc;"\| S" -> Îµ		! style="border-style: solid; border-width: 1px; border-color: black; padding-left: 10px; padding-right: 10px; font-weight: normal; align: center; background: #ffffcc;"\| S" -> ε
	\|-		\|-
	! style="border-style: solid; border-width: 1px; border-color: black; padding-left: 10px; padding-right: 10px; background: wheat;" \| B		! style="border-style: solid; border-width: 1px; border-color: black; padding-left: 10px; padding-right: 10px; background: wheat;" \| B
	! style="border-style: solid; border-width: 1px; border-color: black; padding-left: 10px; padding-right: 10px; font-weight: normal; align: center; background: #ffffcc;"\| B -> Îµ		! style="border-style: solid; border-width: 1px; border-color: black; padding-left: 10px; padding-right: 10px; font-weight: normal; align: center; background: #ffffcc;"\| B -> ε
	! style="border-style: solid; border-width: 1px; border-color: black; padding-left: 10px; padding-right: 10px; font-weight: normal; align: center; background: #ffffcc;"\|		! style="border-style: solid; border-width: 1px; border-color: black; padding-left: 10px; padding-right: 10px; font-weight: normal; align: center; background: #ffffcc;"\|
	! style="border-style: solid; border-width: 1px; border-color: black; padding-left: 10px; padding-right: 10px; font-weight: normal; align: center; background: #ffffcc;"\|		! style="border-style: solid; border-width: 1px; border-color: black; padding-left: 10px; padding-right: 10px; font-weight: normal; align: center; background: #ffffcc;"\|
Line 164:		Line 164:
	face="Courier New, Courier, monospace">$</font></td>		face="Courier New, Courier, monospace">$</font></td>
	<td style="border-style: solid; border-width: 1px; border-color: black;" align="center" bgcolor="#ffffcc" valign="top"><font		<td style="border-style: solid; border-width: 1px; border-color: black;" align="center" bgcolor="#ffffcc" valign="top"><font
	face="Courier New, Courier, monospace"> B -> Îµ</font></td>		face="Courier New, Courier, monospace"> B -> ε</font></td>
	</tr>		</tr>
	<tr>		<tr>

Root: /* Solution */

2008-04-11T14:15:21Z

Solution

Root: /* Solution */

2008-04-10T11:23:37Z

Solution

← Older revision		Revision as of 11:23, 10 April 2008
Line 106:		Line 106:
	\|}		\|}

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

	<table border="0" cellpadding="2" cellspacing="2" height="185"		<table border="0" cellpadding="2" cellspacing="2" height="185"

Root: /* Solution */

2008-04-10T11:23:21Z

Solution

@@ Line 105: / Line 105: @@
 ! style="border-style: solid; border-width: 1px; border-color: black; padding-left: 10px; padding-right: 10px; font-weight: normal; align: center; background: #ffffcc;"|
 |}
 [[category:Compilers]]
 [[category:Teaching]]

Root: /* Solution */

2008-04-10T11:17:36Z

Solution

@@ Line 63: / Line 63: @@
    FOLLOW(B)  = {d}
 [[category:Compilers]]
 [[category:Teaching]]

Root at 10:58, 10 April 2008

2008-04-10T10:58:47Z

← Older revision		Revision as of 10:58, 10 April 2008
Line 60:		Line 60:
	FOLLOW(S) = {$}		FOLLOW(S) = {$}
	FOLLOW(S') âŠ‡ FOLLOW(S") âŠ‡ FOLLOW(S)		FOLLOW(S') âŠ‡ FOLLOW(S") âŠ‡ FOLLOW(S)
	FOLLOW(S') = FOLLOW(S") = {$}		FOLLOW(S') = FOLLOW(S") = FOLLOW(S) = {$}
	FOLLOW(B) = {d}		FOLLOW(B) = {d}

← Older revision		Revision as of 14:15, 11 April 2008
Line 111:		Line 111:
	width="346">		width="346">
	<tr>		<tr>
	<td align="center" bgcolor="#f5deb3" valign="top"><b>STACK<br>		<td style="border-style: solid; border-width: 1px; border-color: black;" align="center" bgcolor="#f5deb3" valign="top"><b>STACK<br>
	</b></td>		</b></td>
	<td align="center" bgcolor="#f5deb3" valign="top"><b>INPUT<br>		<td style="border-style: solid; border-width: 1px; border-color: black;" align="center" bgcolor="#f5deb3" valign="top"><b>INPUT<br>
	</b></td>		</b></td>
	<td align="center" bgcolor="#f5deb3" valign="top"><b>ACTION<br>		<td style="border-style: solid; border-width: 1px; border-color: black;" align="center" bgcolor="#f5deb3" valign="top"><b>ACTION<br>
	</b></td>		</b></td>
	</tr>		</tr>
	<tr>		<tr>
	<td align="right" bgcolor="#ffffcc" valign="top"><font		<td style="border-style: solid; border-width: 1px; border-color: black;" align="right" bgcolor="#ffffcc" valign="top"><font
	face="Courier New, Courier, monospace">S$<br>		face="Courier New, Courier, monospace">S$<br>
	</font></td>		</font></td>
	<td align="right" bgcolor="#ffffcc" valign="top"><font		<td style="border-style: solid; border-width: 1px; border-color: black;" align="right" bgcolor="#ffffcc" valign="top"><font
	face="Courier New, Courier, monospace">hfded</font><font		face="Courier New, Courier, monospace">hfded</font><font
	face="Courier New, Courier, monospace">$</font></td>		face="Courier New, Courier, monospace">$</font></td>
	<td align="center" bgcolor="#ffffcc" valign="top"><font		<td style="border-style: solid; border-width: 1px; border-color: black;" align="center" bgcolor="#ffffcc" valign="top"><font
	face="Courier New, Courier, monospace"> S -> hfdS"</font></td>		face="Courier New, Courier, monospace"> S -> hfdS"</font></td>
	</tr>		</tr>
	<tr>		<tr>
	<td align="right" bgcolor="#ffffcc" valign="top"><font		<td style="border-style: solid; border-width: 1px; border-color: black;" align="right" bgcolor="#ffffcc" valign="top"><font
	face="Courier New, Courier, monospace">hfdS"$</font></td>		face="Courier New, Courier, monospace">hfdS"$</font></td>
	<td align="right" bgcolor="#ffffcc" valign="top"><font		<td style="border-style: solid; border-width: 1px; border-color: black;" align="right" bgcolor="#ffffcc" valign="top"><font
	face="Courier New, Courier, monospace">hfded</font><font		face="Courier New, Courier, monospace">hfded</font><font
	face="Courier New, Courier, monospace">$</font></td>		face="Courier New, Courier, monospace">$</font></td>
	<td align="center" bgcolor="#ffffcc" valign="top"><font		<td style="border-style: solid; border-width: 1px; border-color: black;" align="center" bgcolor="#ffffcc" valign="top"><font
	face="Courier New, Courier, monospace">-> hfd<br>		face="Courier New, Courier, monospace">-> hfd<br>
	</font></td>		</font></td>
	</tr>		</tr>
	<tr>		<tr>
	<td align="right" bgcolor="#ffffcc" valign="top"><font		<td style="border-style: solid; border-width: 1px; border-color: black;" align="right" bgcolor="#ffffcc" valign="top"><font
	face="Courier New, Courier, monospace">S"$</font></td>		face="Courier New, Courier, monospace">S"$</font></td>
	<td align="right" bgcolor="#ffffcc" valign="top"><font		<td style="border-style: solid; border-width: 1px; border-color: black;" align="right" bgcolor="#ffffcc" valign="top"><font
	face="Courier New, Courier, monospace">ed</font><font		face="Courier New, Courier, monospace">ed</font><font
	face="Courier New, Courier, monospace">$</font></td>		face="Courier New, Courier, monospace">$</font></td>
	<td align="center" bgcolor="#ffffcc" valign="top"><font		<td style="border-style: solid; border-width: 1px; border-color: black;" align="center" bgcolor="#ffffcc" valign="top"><font
	face="Courier New, Courier, monospace"> S" -> eBdS'</font></td>		face="Courier New, Courier, monospace"> S" -> eBdS'</font></td>
	</tr>		</tr>
	<tr>		<tr>
	<td align="right" bgcolor="#ffffcc" valign="top"><font		<td style="border-style: solid; border-width: 1px; border-color: black;" align="right" bgcolor="#ffffcc" valign="top"><font
	face="Courier New, Courier, monospace">eBdS'$</font></td>		face="Courier New, Courier, monospace">eBdS'$</font></td>
	<td align="right" bgcolor="#ffffcc" valign="top"><font		<td style="border-style: solid; border-width: 1px; border-color: black;" align="right" bgcolor="#ffffcc" valign="top"><font
	face="Courier New, Courier, monospace">ed</font><font		face="Courier New, Courier, monospace">ed</font><font
	face="Courier New, Courier, monospace">$</font></td>		face="Courier New, Courier, monospace">$</font></td>
	<td align="center" bgcolor="#ffffcc" valign="top"><font		<td style="border-style: solid; border-width: 1px; border-color: black;" align="center" bgcolor="#ffffcc" valign="top"><font
	face="Courier New, Courier, monospace">-> e<br>		face="Courier New, Courier, monospace">-> e<br>
	</font></td>		</font></td>
	</tr>		</tr>
	<tr>		<tr>
	<td align="right" bgcolor="#ffffcc" valign="top"><font		<td style="border-style: solid; border-width: 1px; border-color: black;" align="right" bgcolor="#ffffcc" valign="top"><font
	face="Courier New, Courier, monospace">BdS'$</font></td>		face="Courier New, Courier, monospace">BdS'$</font></td>
	<td align="right" bgcolor="#ffffcc" valign="top"><font		<td style="border-style: solid; border-width: 1px; border-color: black;" align="right" bgcolor="#ffffcc" valign="top"><font
	face="Courier New, Courier, monospace">d</font><font		face="Courier New, Courier, monospace">d</font><font
	face="Courier New, Courier, monospace">$</font></td>		face="Courier New, Courier, monospace">$</font></td>
	<td align="center" bgcolor="#ffffcc" valign="top"><font		<td style="border-style: solid; border-width: 1px; border-color: black;" align="center" bgcolor="#ffffcc" valign="top"><font
	face="Courier New, Courier, monospace"> B -> Îµ</font></td>		face="Courier New, Courier, monospace"> B -> Îµ</font></td>
	</tr>		</tr>
	<tr>		<tr>
	<td align="right" bgcolor="#ffffcc" valign="top"><font		<td style="border-style: solid; border-width: 1px; border-color: black;" align="right" bgcolor="#ffffcc" valign="top"><font
	face="Courier New, Courier, monospace">dS'$</font></td>		face="Courier New, Courier, monospace">dS'$</font></td>
	<td align="right" bgcolor="#ffffcc" valign="top"><font		<td style="border-style: solid; border-width: 1px; border-color: black;" align="right" bgcolor="#ffffcc" valign="top"><font
	face="Courier New, Courier, monospace">d</font><font		face="Courier New, Courier, monospace">d</font><font
	face="Courier New, Courier, monospace">$</font></td>		face="Courier New, Courier, monospace">$</font></td>
	<td align="center" bgcolor="#ffffcc" valign="top"><font		<td style="border-style: solid; border-width: 1px; border-color: black;" align="center" bgcolor="#ffffcc" valign="top"><font
	face="Courier New, Courier, monospace">-> d<br>		face="Courier New, Courier, monospace">-> d<br>
	</font></td>		</font></td>
	</tr>		</tr>
	<tr>		<tr>
	<td align="right" bgcolor="#ffffcc" valign="top"><font		<td style="border-style: solid; border-width: 1px; border-color: black;" align="right" bgcolor="#ffffcc" valign="top"><font
	face="Courier New, Courier, monospace">S'$</font></td>		face="Courier New, Courier, monospace">S'$</font></td>
	<td align="right" bgcolor="#ffffcc" valign="top"><font		<td style="border-style: solid; border-width: 1px; border-color: black;" align="right" bgcolor="#ffffcc" valign="top"><font
	face="Courier New, Courier, monospace">$<br>		face="Courier New, Courier, monospace">$<br>
	</font></td>		</font></td>
	<td align="center" bgcolor="#ffffcc" valign="top"><font		<td style="border-style: solid; border-width: 1px; border-color: black;" align="center" bgcolor="#ffffcc" valign="top"><font
	face="Courier New, Courier, monospace">ACCEPT<br>		face="Courier New, Courier, monospace">ACCEPT<br>
	</font></td>		</font></td>