(New page: == Problem == 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 ...) |
|||
(10 intermediate revisions by the same user not shown) | |||
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 14: | Line 14: | ||
== Solution == | == Solution == | ||
− | [[category: | + | 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). |
− | [[category: | + | |
+ | 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 style="border-style: solid; border-width: 1px; border-color: black;" align="center" bgcolor="#f5deb3" valign="top"><b>STACK<br> | ||
+ | </b></td> | ||
+ | <td style="border-style: solid; border-width: 1px; border-color: black;" align="center" bgcolor="#f5deb3" valign="top"><b>INPUT<br> | ||
+ | </b></td> | ||
+ | <td style="border-style: solid; border-width: 1px; border-color: black;" align="center" bgcolor="#f5deb3" valign="top"><b>ACTION<br> | ||
+ | </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">S$<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">hfded</font><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"> S -> hfdS"</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">hfdS"$</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">hfded</font><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">-> hfd<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">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">ed</font><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"> S" -> eBdS'</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">eBdS'$</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">ed</font><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<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">BdS'$</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">d</font><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"> 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">dS'$</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">d</font><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">-> d<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">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> | ||
+ | </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">S' -> ε<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">$</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> | ||
+ | </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:Compiladores]] | ||
+ | [[category:Ensino]] |
Consider the following grammar, where S is the initial symbol and {d,e,f,g,h} 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 | ε
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 A -> C d h | S e 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 C -> g B | h f 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.
d | e | f | g | h | $ | |
---|---|---|---|---|---|---|
S | S -> g B d S" | S -> h f d S" | ||||
S' | S' -> e B d S' | S' -> ε | ||||
S" | S" -> e B d S' | S" -> h B d S' | S" -> ε | |||
B | B -> ε | B -> g |
The following table shows the parsing of the hfded input sequence.
STACK |
INPUT |
ACTION |
S$ |
hfded$ | S -> hfdS" |
hfdS"$ | hfded$ | -> hfd |
S"$ | ed$ | S" -> eBdS' |
eBdS'$ | ed$ | -> e |
BdS'$ | d$ | B -> ε |
dS'$ | d$ | -> d |
S'$ | $ |
S' -> ε |
$ | $ |
ACCEPT |