|
|
| (3 intermediate revisions by the same user not shown) |
| Line 1: |
Line 1: |
| == Problem ==
| | #REDIRECT [[ist:Top-Down Parsing/Example 3]] |
| | |
| Consider the following grammar, where '''<tt>S</tt>''' is the initial symbol and '''<tt>{u,v,x,y,z}</tt>''' is the set of terminal symbols:
| |
| | |
| S -> u B z
| |
| B -> B v | D
| |
| D -> E u E | B y E
| |
| E -> v | v x
| |
| | |
| # 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>uvuvxz</tt>''' input sequence.
| |
| | |
| == 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 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):
| |
| | |
| S -> u B z
| |
| B -> B v | E u E | B y E
| |
| <font color="red">D -> E u E | B y E</font>
| |
| 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):
| |
| | |
| S -> u B z
| |
| B -> B v | v u E | v x u E | B y E
| |
| E -> v | v x
| |
| | |
| Now, left recursion can be eliminated:
| |
| | |
| S -> u B z
| |
| B -> v u E B1 | v x u E B1
| |
| B1 -> v B1 | y E B1 | ε
| |
| E -> v | v x
| |
| | |
| Factoring...
| |
| | |
| S -> u B z
| |
| B -> v B2
| |
| B1 -> v B1 | y E B1 | ε
| |
| B2 -> u E B1 | x u E B1
| |
| E -> v E1
| |
| E1 -> x | ε
| |
| | |
| The FIRST and FOLLOW sets are as follows:
| |
| | |
| FIRST(S) = FIRST(u B z) = {u}
| |
| FIRST(B) = FIRST(v B2) = {v}
| |
| 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(E) = FIRST(v E1) = {v}
| |
| FIRST(E1) = {x} ∪ {ε} = {x, ε}
| |
| | |
| FOLLOW(S) = {$} FOLLOW(B) = {z} FOLLOW(B1) ⊇ FOLLOW(B2) FOLLOW(B2) ⊇ FOLLOW(B)
| |
| 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}
| |
| | |
| For building the parse table, we will consider the FIRST and FOLLOW sets above.
| |
| | |
| <table>
| |
| <tr>
| |
| <td></td>
| |
| <th style="border: 1px solid black; background: wheat none repeat scroll 0% 50%; padding-left: 20px; padding-right: 20px;">u</th>
| |
| <th style="border: 1px solid black; background: wheat none repeat scroll 0% 50%; padding-left: 20px; padding-right: 20px; -moz-background-clip: -moz-initial; -moz-background-origin: -moz-initial; -moz-background-inline-policy: -moz-initial;">v</th>
| |
| <th style="border: 1px solid black; background: wheat none repeat scroll 0% 50%; padding-left: 20px; padding-right: 20px; -moz-background-clip: -moz-initial; -moz-background-origin: -moz-initial; -moz-background-inline-policy: -moz-initial;">x</th>
| |
| <th style="border: 1px solid black; background: wheat none repeat scroll 0% 50%; padding-left: 20px; padding-right: 20px; -moz-background-clip: -moz-initial; -moz-background-origin: -moz-initial; -moz-background-inline-policy: -moz-initial;">y</th>
| |
| <th style="border: 1px solid black; background: wheat none repeat scroll 0% 50%; padding-left: 20px; padding-right: 20px; -moz-background-clip: -moz-initial; -moz-background-origin: -moz-initial; -moz-background-inline-policy: -moz-initial;">z</th>
| |
| <th style="border: 1px solid black; background: wheat none repeat scroll 0% 50%; padding-left: 20px; padding-right: 20px; -moz-background-clip: -moz-initial; -moz-background-origin: -moz-initial; -moz-background-inline-policy: -moz-initial;">$</th>
| |
| </tr>
| |
| <tr>
| |
| <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;">S</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">S -> u B z</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>
| |
| <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"></font></th>
| |
| </tr>
| |
| <tr>
| |
| <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;">B</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">B -> v B2</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>
| |
| <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>
| |
| <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;">B1</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 -> v 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"></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"></font></th>
| |
| </tr>
| |
| <tr>
| |
| <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;">B2</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">B2 -> u 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"></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">B2 -> x u 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"></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>
| |
| <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;">E</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">E -> v E1</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>
| |
| <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>
| |
| <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">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 -> </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>
| |
| </tr>
| |
| </table>
| |
| | |
| The following table shows the parsing of the '''<tt>uvuvxz</tt>''' input sequence.
| |
| | |
| <table border="0" cellpadding="2" cellspacing="2" width="346">
| |
| <tr>
| |
| <td style="border: 1px solid black;" align="center"
| |
| bgcolor="#f5deb3" valign="top"><b>STACK<br>
| |
| </b></td>
| |
| <td style="border: 1px solid black;" align="center"
| |
| bgcolor="#f5deb3" valign="top"><b>INPUT<br>
| |
| </b></td>
| |
| <td style="border: 1px solid black;" align="center"
| |
| bgcolor="#f5deb3" valign="top"><b>ACTION<br>
| |
| </b></td>
| |
| </tr>
| |
| <tr>
| |
| <td style="border: 1px solid black;" align="right"
| |
| bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">S $</font><font
| |
| face="Courier New, Courier, monospace"><br>
| |
| </font></td>
| |
| <td style="border: 1px solid black;" align="right"
| |
| bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">u v u v x z $</font></td>
| |
| <td style="border: 1px solid black;" align="center"
| |
| bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">S -> u B z</font><font
| |
| face="Courier New, Courier, monospace"></font></td>
| |
| </tr>
| |
| <tr>
| |
| <td style="border: 1px solid black;" align="right"
| |
| bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">u B z $<br>
| |
| </font></td>
| |
| <td style="border: 1px solid black;" align="right"
| |
| bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">u v u v x z $</font><font
| |
| face="Courier New, Courier, monospace"></font></td>
| |
| <td style="border: 1px solid black;" align="center"
| |
| bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">-> u<br>
| |
| </font></td>
| |
| </tr>
| |
| <tr>
| |
| <td style="border: 1px solid black;" align="right"
| |
| bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">B z $</font></td>
| |
| <td style="border: 1px solid black;" align="right"
| |
| bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">v u v x z $</font><font
| |
| face="Courier New, Courier, monospace"></font></td>
| |
| <td style="border: 1px solid black;" align="center"
| |
| bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">B -> v B2</font></td>
| |
| </tr>
| |
| <tr>
| |
| <td style="border: 1px solid black;" align="right"
| |
| bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">v B2 z $</font></td>
| |
| <td style="border: 1px solid black;" align="right"
| |
| bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">v u v x z $</font><font
| |
| face="Courier New, Courier, monospace"></font></td>
| |
| <td style="border: 1px solid black;" align="center"
| |
| bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">-> v<br>
| |
| </font></td>
| |
| </tr>
| |
| <tr>
| |
| <td style="border: 1px solid black;" align="right"
| |
| bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">B2 z $</font></td>
| |
| <td style="border: 1px solid black;" align="right"
| |
| bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">u v x z $</font><font
| |
| face="Courier New, Courier, monospace"></font></td>
| |
| <td style="border: 1px solid black;" align="center"
| |
| bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">B2 -> u E B1<br>
| |
| </font></td>
| |
| </tr>
| |
| <tr>
| |
| <td style="border: 1px solid black;" align="right"
| |
| bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">u E B1</font><font
| |
| face="Courier New, Courier, monospace"> z $</font></td>
| |
| <td style="border: 1px solid black;" align="right"
| |
| bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">u v x z $</font><font
| |
| face="Courier New, Courier, monospace"></font></td>
| |
| <td style="border: 1px solid black;" align="center"
| |
| bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">-> u<br>
| |
| </font></td>
| |
| </tr>
| |
| <tr>
| |
| <td style="border: 1px solid black;" align="right"
| |
| bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">E B1</font><font
| |
| face="Courier New, Courier, monospace"> z $</font></td>
| |
| <td style="border: 1px solid black;" align="right"
| |
| bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">v x z $</font></td>
| |
| <td style="border: 1px solid black;" align="center"
| |
| bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">E -> v E1</font></td>
| |
| </tr>
| |
| <tr>
| |
| <td style="border: 1px solid black;" align="right"
| |
| bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">v E1 </font><font
| |
| face="Courier New, Courier, monospace">B1</font><font
| |
| face="Courier New, Courier, monospace"> z $</font></td>
| |
| <td style="border: 1px solid black;" align="right"
| |
| bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">v x z $</font></td>
| |
| <td style="border: 1px solid black;" align="center"
| |
| bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">-> v<br>
| |
| </font></td>
| |
| </tr>
| |
| <tr>
| |
| <td style="border: 1px solid black;" align="right"
| |
| bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">E1 </font><font
| |
| face="Courier New, Courier, monospace">B1</font><font
| |
| face="Courier New, Courier, monospace"> z $</font></td>
| |
| <td style="border: 1px solid black;" align="right"
| |
| bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">x z $</font></td>
| |
| <td style="border: 1px solid black;" align="center"
| |
| bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">E1 -> x</font></td>
| |
| </tr>
| |
| <tr>
| |
| <td style="border: 1px solid black;" align="right"
| |
| bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">x B1</font><font
| |
| face="Courier New, Courier, monospace"> z $</font></td>
| |
| <td style="border: 1px solid black;" align="right"
| |
| bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">x z $</font></td>
| |
| <td style="border: 1px solid black;" align="center"
| |
| bgcolor="#ffffcc" valign="top">-> x<br>
| |
| </td>
| |
| </tr>
| |
| <tr>
| |
| <td style="border: 1px solid black;" align="right"
| |
| bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">B1</font><font
| |
| face="Courier New, Courier, monospace"> z $</font></td>
| |
| <td style="border: 1px solid black;" align="right"
| |
| bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">z $</font></td>
| |
| <td style="border: 1px solid black;" align="center"
| |
| bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">B1 -> </font><font
| |
| face="Courier New, Courier, monospace">ε</font></td>
| |
| </tr>
| |
| <tr>
| |
| <td style="border: 1px solid black;" align="right"
| |
| bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">z $</font></td>
| |
| <td style="border: 1px solid black;" align="right"
| |
| bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">z $</font></td>
| |
| <td style="border: 1px solid black;" align="center"
| |
| bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">-> z<br>
| |
| </font></td>
| |
| </tr>
| |
| <tr>
| |
| <td style="border: 1px solid black;" align="right"
| |
| bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">$</font></td>
| |
| <td style="border: 1px solid black;" align="right"
| |
| bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">$</font></td>
| |
| <td style="border: 1px solid black;" align="center"
| |
| bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">ACCEPT<br>
| |
| </font></td>
| |
| </tr>
| |
| </table>
| |
| | |
| [[category:Compilers]]
| |
| [[category:Teaching]]
| |