|
|
| (5 intermediate revisions by the same user not shown) |
| Line 1: |
Line 1: |
| == Problem ==
| | #REDIRECT [[ist:Top-Down Parsing/Example 2]] |
| | |
| Consider the following grammar, where '''<tt>S</tt>''' is the initial symbol and '''<tt>{d,e,f,g,h}</tt>''' is the set of terminal symbols:
| |
| | |
| S -> A B d | C d
| |
| A -> C d h | S e
| |
| C -> g B | h f
| |
| B -> g | ε
| |
| | |
| # 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>hfded</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 S and A. Also, there are left corners that may hide ambiguity (C).
| |
| | |
| The first step, then, is to rewrite the grammar so that multual recursion is eliminated (A becomes unreachable and can be removed from the grammar):
| |
| | |
| S -> C d h B d | S e B d | C d
| |
| <font color="red">A -> C d h | S e</font>
| |
| C -> g B | h f
| |
| B -> g | ε
| |
| | |
| Now we handle the left corner (C in S) (C also becomes unreachable and can be removed from the grammar):
| |
| | |
| 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>
| |
| B -> g | ε
| |
| | |
| 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' -> e B d S' | ε
| |
| B -> g | ε
| |
| | |
| Factoring...
| |
| | |
| S -> g B d S" | h f d S"
| |
| S' -> e B d S' | ε
| |
| S" -> h B d S' | S'
| |
| B -> g | ε
| |
| | |
| Removing the left corner S' from S":
| |
| | |
| S -> g B d S" | h f d S"
| |
| S' -> e B d S' | ε
| |
| S" -> h B d S' | e B d S' | ε
| |
| B -> g | ε
| |
| | |
| 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(e B d S') ∪ {ε} = {e, ε}
| |
| FIRST(S") = FIRST(h B d S') ∪ FIRST(e B d S') ∪ {ε} = {e, h, ε}
| |
| FIRST(B) = FIRST(g) ∪ {ε} = {g, ε}
| |
| | |
| FOLLOW(S) = {$}
| |
| FOLLOW(S') ⊇ FOLLOW(S") ⊇ FOLLOW(S)
| |
| FOLLOW(S') = FOLLOW(S") = FOLLOW(S) = {$}
| |
| FOLLOW(B) = {d}
| |
| | |
| 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;" | d
| |
| ! style="border-style: solid; border-width: 1px; border-color: black; padding-left: 20px; padding-right: 20px; background: wheat;" | e
| |
| ! style="border-style: solid; border-width: 1px; border-color: black; padding-left: 20px; padding-right: 20px; background: wheat;" | f
| |
| ! style="border-style: solid; border-width: 1px; border-color: black; padding-left: 20px; padding-right: 20px; background: wheat;" | g
| |
| ! style="border-style: solid; border-width: 1px; border-color: black; padding-left: 20px; padding-right: 20px; background: wheat;" | h
| |
| ! 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;" | S
| |
| ! 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 -> g 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 f 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;"|
| |
| |-
| |
| ! 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; 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' -> e 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;"|
| |
| ! 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; background: wheat;" | S"
| |
| ! 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" -> e 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;"|
| |
| ! 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" -> ε
| |
| |-
| |
| ! 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;"|
| |
| ! 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;"| B -> g
| |
| ! 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 shows the parsing of the '''<tt>hfded</tt>''' input sequence.
| |
| | |
| <table border="0" cellpadding="2" cellspacing="2" height="185"
| |
| width="346">
| |
| <tr>
| |
| <td align="center" bgcolor="#f5deb3" valign="top"><b>STACK<br>
| |
| </b></td>
| |
| <td align="center" bgcolor="#f5deb3" valign="top"><b>INPUT<br>
| |
| </b></td>
| |
| <td align="center" bgcolor="#f5deb3" valign="top"><b>ACTION<br>
| |
| </b></td>
| |
| </tr>
| |
| <tr>
| |
| <td align="right" bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">S$<br>
| |
| </font></td>
| |
| <td align="right" bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">hfded</font><font
| |
| face="Courier New, Courier, monospace">$</font></td>
| |
| <td align="center" bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace"> S -> hfdS"</font></td>
| |
| </tr>
| |
| <tr>
| |
| <td align="right" bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">hfdS"$</font></td>
| |
| <td align="right" bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">hfded</font><font
| |
| face="Courier New, Courier, monospace">$</font></td>
| |
| <td align="center" bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">-> hfd<br>
| |
| </font></td>
| |
| </tr>
| |
| <tr>
| |
| <td align="right" bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">S"$</font></td>
| |
| <td align="right" bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">ed</font><font
| |
| face="Courier New, Courier, monospace">$</font></td>
| |
| <td align="center" bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace"> S" -> eBdS'</font></td>
| |
| </tr>
| |
| <tr>
| |
| <td align="right" bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">eBdS'$</font></td>
| |
| <td align="right" bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">ed</font><font
| |
| face="Courier New, Courier, monospace">$</font></td>
| |
| <td align="center" bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">-> e<br>
| |
| </font></td>
| |
| </tr>
| |
| <tr>
| |
| <td align="right" bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">BdS'$</font></td>
| |
| <td align="right" bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">d</font><font
| |
| face="Courier New, Courier, monospace">$</font></td>
| |
| <td align="center" bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace"> B -> ε</font></td>
| |
| </tr>
| |
| <tr>
| |
| <td align="right" bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">dS'$</font></td>
| |
| <td align="right" bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">d</font><font
| |
| face="Courier New, Courier, monospace">$</font></td>
| |
| <td align="center" bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">-> d<br>
| |
| </font></td>
| |
| </tr>
| |
| <tr>
| |
| <td align="right" bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">S'$</font></td>
| |
| <td align="right" bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">$<br>
| |
| </font></td>
| |
| <td align="center" bgcolor="#ffffcc" valign="top"><font
| |
| face="Courier New, Courier, monospace">ACCEPT<br>
| |
| </font></td>
| |
| </tr>
| |
| </table>
| |
| | |
| [[category:Compilers]]
| |
| [[category:Teaching]]
| |