|
|
| (3 intermediate revisions by the same user not shown) |
| Line 1: |
Line 1: |
| == Problem ==
| | #REDIRECT [[ist:Top-Down Parsing/Example 1]] |
| | |
| Consider the following grammar with the following set of non-terminal symbols '''<tt>{+,-,*,/,(,),id}</tt>''':
| |
| | |
| E -> E + T | E - T | T
| |
| T -> T * F | T / F | F
| |
| F -> ( E ) | id
| |
| | |
| # Rewrite the grammar so that it can be analyzed by an LL(1) predictive parser.
| |
| # Compute the FIRST and FOLLOW sets for the non-terminal symbols.
| |
| # Build the parse table for the predictive parser.
| |
| # Process the input phrase '''<tt>a*(b+c)</tt>''' detailing the contents of the stack, the input and each action performed by the parser.
| |
| | |
| == Solution ==
| |
| | |
| 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 left recursion is present in both E and T rules. Also, there are left corners that may hide ambiguity.
| |
| | |
| The first step, then, is to rewrite the grammar so that left recursion is eliminated:
| |
| | |
| E -> T E'
| |
| E' -> + T E' | - T E' | ε
| |
| T -> F T'
| |
| T' -> * F T' | / F T' | ε
| |
| F -> ( E ) | id
| |
| | |
| The new grammar still has left corners, but a cursory inspection shows that they are not problematic. Nevertheless, they should be eliminated:
| |
| | |
| 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(T) = FIRST(( E ) T') ∪ FIRST(id T') = {(, id}
| |
| FIRST(T') = FIRST(* F T') ∪ FIRST(/ F T') ∪ {ε} = {*, /, ε}
| |
| FIRST(F) = FIRST(( E )) ∪ FIRST(id) = {(, id}
| |
| | |
| FOLLOW(E) = {$} ∪ {)} = {), $}
| |
| FOLLOW(E') = FOLLOW(E) = {), $}
| |
| FOLLOW(T) = FIRST(E')\{ε} ∪ FOLLOW(E) ∪ FOLLOW(E') = {+, -, ), $}
| |
| FOLLOW(T') = FOLLOW(T) = {+, -, ), $}
| |
| FOLLOW(F) = FIRST(T')\{ε} ∪ FOLLOW(T) ∪ FOLLOW(T') = {*, /, +, -, ), $}
| |
| | |
| For building the parse table, we will consider the FIRST and FOLLOW sets above.
| |
| {|
| |
| |
| |
| ! style="border-style: solid; border-width: 1px; border-color: black; padding-left: 20px; padding-right: 20px; background: wheat;" | +
| |
| ! style="border-style: solid; border-width: 1px; border-color: black; padding-left: 20px; padding-right: 20px; background: wheat;" | -
| |
| ! style="border-style: solid; border-width: 1px; border-color: black; padding-left: 20px; padding-right: 20px; background: wheat;" | *
| |
| ! style="border-style: solid; border-width: 1px; border-color: black; padding-left: 20px; padding-right: 20px; background: wheat;" | /
| |
| ! style="border-style: solid; border-width: 1px; border-color: black; padding-left: 20px; padding-right: 20px; background: wheat;" | id
| |
| ! style="border-style: solid; border-width: 1px; border-color: black; padding-left: 20px; padding-right: 20px; background: wheat;" | (
| |
| ! style="border-style: solid; border-width: 1px; border-color: black; padding-left: 20px; padding-right: 20px; background: wheat;" | )
| |
| ! style="border-style: solid; border-width: 1px; border-color: black; padding-left: 20px; padding-right: 20px; background: wheat;" | $
| |
| |-
| |
| ! style="border-style: solid; border-width: 1px; border-color: black; padding-left: 10px; padding-right: 10px; background: wheat;" | 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;"|
| |
| ! 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 -> ( 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; background: wheat;" | 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' -> - 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;"|
| |
| ! style="border-style: solid; border-width: 1px; border-color: black; padding-left: 10px; padding-right: 10px; font-weight: normal; align: center; background: #ffffcc;"| 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' -> ε
| |
| |-
| |
| ! style="border-style: solid; border-width: 1px; border-color: black; padding-left: 10px; padding-right: 10px; background: wheat;" | 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;"|
| |
| ! 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 -> ( 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; background: wheat;" | 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' -> ε
| |
| ! style="border-style: solid; border-width: 1px; border-color: black; padding-left: 10px; padding-right: 10px; font-weight: normal; align: center; background: #ffffcc;"| 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' -> / 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;"|
| |
| ! 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' -> ε
| |
| ! style="border-style: solid; border-width: 1px; border-color: black; padding-left: 10px; padding-right: 10px; font-weight: normal; align: center; background: #ffffcc;"| T' -> ε
| |
| |-
| |
| ! style="border-style: solid; border-width: 1px; border-color: black; padding-left: 10px; padding-right: 10px; background: wheat;" | F
| |
| ! 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;"| F -> id
| |
| ! style="border-style: solid; border-width: 1px; border-color: black; padding-left: 10px; padding-right: 10px; font-weight: normal; align: center; background: #ffffcc;"| F -> ( 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;"|
| |
| |}
| |
| | |
| The following table show the parsing of the '''a*(b+c)''' input sequence.
| |
| <table border="0" cellpadding="2" cellspacing="2" height="631" width="346">
| |
| <tr>
| |
| <td style="border-style: solid; border-width: 1px; border-color: black;" align="center" bgcolor="#f5deb3" valign="top"><b>STACK</b></td>
| |
| <td style="border-style: solid; border-width: 1px; border-color: black;" align="center" bgcolor="#f5deb3" valign="top"><b>INPUT</b></td>
| |
| <td style="border-style: solid; border-width: 1px; border-color: black;" align="center" bgcolor="#f5deb3" valign="top"><b>ACTION</b></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">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"> 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">idT'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">-> id ≡ a</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">T'E'$<br>
| |
| </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">*(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>
| |
| </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'$<br>
| |
| </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">*(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">-> *<br>
| |
| </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">(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 -> ( 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">(E)T'E'$<br>
| |
| </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">(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">-> (<br>
| |
| </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">E)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">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>
| |
| </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">idT'E')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">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">-> id ≡ b</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">T'</font><font
| |
| face="Courier New, Courier, monospace">E'</font><font
| |
| face="Courier New, Courier, monospace">)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">+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' -> ε</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">E'</font><font
| |
| face="Courier New, Courier, monospace">)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">+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>
| |
| </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><font
| |
| face="Courier New, Courier, monospace">)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">+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">-> +<br>
| |
| </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">TE'</font><font
| |
| face="Courier New, Courier, monospace">)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">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>
| |
| <td style="border-style: solid; border-width: 1px; border-color: black;" align="right" bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">idT'</font><font
| |
| face="Courier New, Courier, monospace">E'</font><font
| |
| face="Courier New, Courier, monospace">)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">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">-> id ≡ c<br>
| |
| </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">T'</font><font
| |
| face="Courier New, Courier, monospace">E'</font><font
| |
| face="Courier New, Courier, monospace">)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">)$</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' -> ε</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">E'</font><font
| |
| face="Courier New, Courier, monospace">)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">)$</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' -> ε</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">)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">)$</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">-> )</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">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">$</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' -> ε</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">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">$</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' -> ε</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">$</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">$</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">ACCEPT<br>
| |
| </font></td>
| |
| </tr>
| |
| </table>
| |
| | |
| | |
| [[category:Compilers]]
| |
| [[category:Teaching]]
| |