|
|
| (18 intermediate revisions by the same user not shown) |
| Line 1: |
Line 1: |
| == Problem ==
| | #REDIRECT [[ist:Top-Down Parsing/Example 1]] |
| | |
| Consider the following grammar:
| |
| | |
| 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 a 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 '''a*(b+c)''' 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 (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.
| |
| | |
| FIRST(E) = FIRST(T E') = FIRST(T) = {(, id}
| |
| FIRST(E') = FIRST(+ T E') ∪ FIRST(- T E') ∪ {ε} = {+, -, ε}
| |
| FIRST(T) = FIRST(F T') = FIRST(F) = {(, 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 -> 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; 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 -> 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; 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;"|
| |
| |}
| |
| | |
| [[category:Compilers]]
| |
| [[category:Teaching]]
| |