Top-Down Parsing/Example 1 - Revision history

Root at 14:40, 6 April 2015

2015-04-06T14:40:10Z

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

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

Root at 20:18, 12 April 2010

2010-04-12T20:18:04Z

← Older revision		Revision as of 20:18, 12 April 2010
Line 1:		Line 1:
	== Problem ==		== Problem ==

	Consider the following grammar with the following set of ~~non-~~terminal symbols '''<tt>{+,-,*,/,(,),id}</tt>''':		Consider the following grammar with the following set of terminal symbols '''<tt>{+,-,*,/,(,),id}</tt>''':

	E -> E + T \| E - T \| T		E -> E + T \| E - T \| T

Root at 16:50, 12 April 2010

2010-04-12T16:50:05Z

← Older revision		Revision as of 16:50, 12 April 2010
Line 42:		Line 42:
	FOLLOW(E) = {$} ∪ {)} = {), $}		FOLLOW(E) = {$} ∪ {)} = {), $}
	FOLLOW(E') = FOLLOW(E) = {), $}		FOLLOW(E') = FOLLOW(E) = {), $}
	FOLLOW(T) = FIRST(E')\{ε} ~~∪ FOLLOW(E)~~ ∪ FOLLOW(E') = {+, -, ), $}		FOLLOW(T) = FIRST(E')\{ε} ∪ FOLLOW(E') = {+, -, ), $}
	FOLLOW(T') = FOLLOW(T) = {+, -, ), $}		FOLLOW(T') = FOLLOW(T) = {+, -, ), $}
	FOLLOW(F) = FIRST(T')\{ε} ~~∪ FOLLOW(T)~~ ∪ FOLLOW(T') = {*, /, +, -, ), $}		FOLLOW(F) = FIRST(T')\{ε} ∪ FOLLOW(T') = {*, /, +, -, ), $}

	For building the parse table, we will consider the FIRST and FOLLOW sets above.		For building the parse table, we will consider the FIRST and FOLLOW sets above.

Root at 17:57, 10 April 2010

2010-04-10T17:57:36Z

← Older revision		Revision as of 17:57, 10 April 2010
Line 120:		Line 120:
	<td style="border-style: solid; border-width: 1px; border-color: black;" align="right" bgcolor="#ffffcc" valign="top"><font face="Courier New, Courier, monospace">a*(b+c)$</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">a*(b+c)$</font></td>
	<td style="border-style: solid; border-width: 1px; border-color: black;" align="center" bgcolor="#ffffcc" valign="top"><font face="Courier New, Courier, monospace"> E -> id T' E'</font></td>		<td style="border-style: solid; border-width: 1px; border-color: black;" align="center" bgcolor="#ffffcc" valign="top"><font face="Courier New, Courier, monospace"> E -> id T' E'</font></td>
	~~</tr>~~
	~~<tr>~~
	~~<td style="border-style: solid; border-width: 1px; border-color: black;" align="right" bgcolor="#ffffcc" valign="top"><font face="Courier New, Courier, monospace">id T'E'$</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">a*(b+c)$</font></td>~~
	~~<td style="border-style: solid; border-width: 1px; border-color: black;" align="center" bgcolor="#ffffcc" valign="top"><font face="Courier New, Courier, monospace"> T -> id T'</font></td>~~
	</tr>		</tr>
	<tr>		<tr>

Root at 17:56, 10 April 2010

2010-04-10T17:56:40Z

← Older revision		Revision as of 17:56, 10 April 2010
Line 119:		Line 119:
	<td style="border-style: solid; border-width: 1px; border-color: black;" align="right" bgcolor="#ffffcc" valign="top"><font face="Courier New, Courier, monospace">E$</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">E$</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">a*(b+c)$</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">a*(b+c)$</font></td>
	<td style="border-style: solid; border-width: 1px; border-color: black;" align="center" bgcolor="#ffffcc" valign="top"><font face="Courier New, Courier, monospace"> E -> T E'</font></td>		<td style="border-style: solid; border-width: 1px; border-color: black;" align="center" bgcolor="#ffffcc" valign="top"><font face="Courier New, Courier, monospace"> E -> id T' E'</font></td>
	</tr>		</tr>
	<tr>		<tr>
	<td style="border-style: solid; border-width: 1px; border-color: black;" align="right" bgcolor="#ffffcc" valign="top"><font face="Courier New, Courier, monospace">TE'$</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">id T'E'$</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">a*(b+c)$</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">a*(b+c)$</font></td>
	<td style="border-style: solid; border-width: 1px; border-color: black;" align="center" bgcolor="#ffffcc" valign="top"><font face="Courier New, Courier, monospace"> T -> id T'</font></td>		<td style="border-style: solid; border-width: 1px; border-color: black;" align="center" bgcolor="#ffffcc" valign="top"><font face="Courier New, Courier, monospace"> T -> id T'</font></td>

Root at 17:16, 10 April 2010

2010-04-10T17:16:02Z

@@ Line 174: / Line 174: @@
   face="Courier New, Courier, monospace">b+c)$</font></td>
        <td style="border-style: solid; border-width: 1px; border-color: black;" align="center" bgcolor="#ffffcc" valign="top"><font
-  face="Courier New, Courier, monospace"> E -&gt; T E'</font></td>
+  face="Courier New, Courier, monospace"> E -&gt; id T' E'</font></td>
      </tr>
      <tr>
@@ Line 231: / Line 217: @@
   face="Courier New, Courier, monospace">c)$</font></td>
        <td style="border-style: solid; border-width: 1px; border-color: black;" align="center" bgcolor="#ffffcc" valign="top"><font
-  face="Courier New, Courier, monospace"> T -&gt; F T'</font></td>
+  face="Courier New, Courier, monospace"> T -&gt; id T'</font></td>
      </tr>
      <tr>

Root at 17:14, 10 April 2010

2010-04-10T17:14:50Z

← Older revision		Revision as of 17:14, 10 April 2010
Line 124:		Line 124:
	<td style="border-style: solid; border-width: 1px; border-color: black;" align="right" bgcolor="#ffffcc" valign="top"><font face="Courier New, Courier, monospace">TE'$</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">TE'$</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">a*(b+c)$</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">a*(b+c)$</font></td>
	<td style="border-style: solid; border-width: 1px; border-color: black;" align="center" bgcolor="#ffffcc" valign="top"><font face="Courier New, Courier, monospace"> T -> F T'~~</font></td>~~		<td style="border-style: solid; border-width: 1px; border-color: black;" align="center" bgcolor="#ffffcc" valign="top"><font face="Courier New, Courier, monospace"> T -> id T'</font></td>
	~~</tr>~~
	~~<tr>~~
	~~<td style="border-style: solid; border-width: 1px; border-color: black;" align="right" bgcolor="#ffffcc" valign="top"><font face="Courier New, Courier, monospace">FT'E'$</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">a*(b+c)$</font></td>~~
	~~<td style="border-style: solid; border-width: 1px; border-color: black;" align="center" bgcolor="#ffffcc" valign="top"><font face="Courier New, Courier, monospace"> F -> id~~</font></td>
	</tr>		</tr>
	<tr>		<tr>

Root at 17:12, 10 April 2010

2010-04-10T17:12:07Z

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

2010-04-09T14:29:25Z

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

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

Root: /* Solution */

2009-04-06T17:27:26Z

Solution

← Older revision		Revision as of 17:27, 6 April 2009
Line 26:		Line 26:
	F -> ( E ) \| id		F -> ( E ) \| id

	The new grammar still has left corners, but a cursory inspection shows that they are not problematic ~~(we will leave them as~~ they ~~are for simplicity). Eliminating these left corners would mean replacing the definitions of F in T and of T in E.~~		The new grammar still has left corners, but a cursory inspection shows that they are not problematic. Nevertheless, they should be eliminated:

	FIRST(E) = FIRST(T E') = FIRST(T) = {(, id}		E -> ( E ) T' E' \| id T' E'
			E' -> + T E' \| - T E' \| ε
			T -> ( E ) T' \| id T'
			T' -> * F T' \| / F T' \| ε
			F -> ( E ) \| id

			FIRST(E) = FIRST(( E ) T' E') ∪ FIRST(id T' E') = {(, id}
	FIRST(E') = FIRST(+ T E') ∪ FIRST(- T E') ∪ {ε} = {+, -, ε}		FIRST(E') = FIRST(+ T E') ∪ FIRST(- T E') ∪ {ε} = {+, -, ε}
	FIRST(T) = FIRST(F T') = FIRST(F) = {(, id}		FIRST(T) = FIRST(( E ) T') ∪ FIRST(id T') = {(, id}
	FIRST(T') = FIRST(* F T') ∪ FIRST(/ F T') ∪ {ε} = {*, /, ε}		FIRST(T') = FIRST(* F T') ∪ FIRST(/ F T') ∪ {ε} = {*, /, ε}
	FIRST(F) = FIRST(( E )) ∪ FIRST(id) = {(, id}		FIRST(F) = FIRST(( E )) ∪ FIRST(id) = {(, id}

← Older revision		Revision as of 17:12, 10 April 2010
Line 63:		Line 63:
	! 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;"\| E -> T E'		! style="border-style: solid; border-width: 1px; border-color: black; padding-left: 10px; padding-right: 10px; font-weight: normal; align: center; background: #ffffcc;"\| E -> id T' E'
	! style="border-style: solid; border-width: 1px; border-color: black; padding-left: 10px; padding-right: 10px; font-weight: normal; align: center; background: #ffffcc;"\| E -> T E'		! style="border-style: solid; border-width: 1px; border-color: black; padding-left: 10px; padding-right: 10px; font-weight: normal; align: center; background: #ffffcc;"\| E -> ( E ) T' E'
	! 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 83:		Line 83:
	! 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;"\| T -> F T'		! style="border-style: solid; border-width: 1px; border-color: black; padding-left: 10px; padding-right: 10px; font-weight: normal; align: center; background: #ffffcc;"\| T -> id T'
	! style="border-style: solid; border-width: 1px; border-color: black; padding-left: 10px; padding-right: 10px; font-weight: normal; align: center; background: #ffffcc;"\| T -> F T'		! style="border-style: solid; border-width: 1px; border-color: black; padding-left: 10px; padding-right: 10px; font-weight: normal; align: center; background: #ffffcc;"\| T -> ( E ) T'
	! 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;"\|