|
|
| (One intermediate revision by the same user not shown) |
| Line 1: |
Line 1: |
| {{TOCright}}
| | #REDIRECT [[ist:Top-Down Parsing/Exercise 3]] |
| = Problem =
| |
| | |
| Consider the following grammar, where '''<tt>G</tt>''' is the initial symbol and '''<tt>{a,b,c,d,e}</tt>''' is the set of terminal symbols:
| |
| | |
| O -> a
| |
| G -> F c | O c d | (eps)
| |
| F -> G b | O c F e
| |
| | |
| # 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>acbec</tt>''' input sequence.
| |
| | |
| = Solution =
| |
| | |
| Something to keep in mind at all times: '''never eliminate the rules corresponding to the initial symbol'''
| |
| <!--
| |
| There are two ways of handling the mutual recursion: either expanding F in G or G in F.
| |
| | |
| == Expanding G in F ==
| |
| | |
| Initial grammar:
| |
| | |
| O -> a
| |
| G -> F c | O c d | (eps)
| |
| F -> G b | O c F e
| |
| | |
| Eliminating the singularity (O->a):
| |
| | |
| G -> F c | a c d | (eps)
| |
| F -> G b | a c F e
| |
| | |
| Expanding G in F:
| |
| | |
| G -> F c | a c d | (eps)
| |
| F -> F c b | a c d b | b | a c F e
| |
| | |
| Eliminate left recursion in F:
| |
| | |
| G -> F c | a c d | (eps)
| |
| F -> a c d b F' | b F' | a c F e F'
| |
| F' -> c b F' | (eps)
| |
| | |
| Factor F prefixes and expand it in G:
| |
| | |
| G -> a c F" c | b F' c | a c d | (eps)
| |
| F -> a c F" | b F'
| |
| F' -> c b F' | (eps)
| |
| F" -> d b F' | F e F'
| |
| | |
| Note that we still have common prefixes to factor in G and a non-terminal left-corner in F''. The next step will handle those cases:
| |
| | |
| G -> a c G' | b F' c | (eps)
| |
| G' -> F" c | d
| |
| F' -> c b F' | (eps)
| |
| F" -> d b F' | a c F" e F' | b F' e F'
| |
| | |
| F was eliminated because it became unreachable from the start symbol. The grammar still has a non-terminal left corner in G', so we need to eliminate it.
| |
| | |
| G -> a c G' | b F' c | (eps)
| |
| G' -> d b F' c | a c F" e F' c | b F' e F' c | d
| |
| F' -> c b F' | (eps)
| |
| F" -> d b F' | a c F" e F' | b F' e F'
| |
| | |
| Factoring prefixes in G', we get to the final version:
| |
| | |
| G -> a c G' | b F' c | (eps)
| |
| G' -> d G" | a c F" e F' c | b F' e F' c
| |
| G" -> b F' c | (eps)
| |
| F' -> c b F' | (eps)
| |
| F" -> d b F' | a c F" e F' | b F' e F'
| |
| -->
| |
| === Elimination of Mutual Recursion: Expanding F in G ===
| |
| | |
| Initial grammar:
| |
| | |
| O -> a
| |
| G -> F c | O c d | (eps)
| |
| F -> G b | O c F e
| |
| | |
| Eliminating the singularity (O->a):
| |
| | |
| G -> F c | a c d | (eps)
| |
| F -> G b | a c F e
| |
| | |
| Expanding F in G:
| |
| | |
| G -> G b c | a c F e c | a c d | (eps)
| |
| F -> G b | a c F e
| |
| | |
| Eliminating left recursion in G:
| |
| | |
| G -> a c F e c G' | a c d G' | G'
| |
| G' -> b c G' | (eps)
| |
| F -> G b | a c F e
| |
| | |
| Factoring G prefixes:
| |
| | |
| G -> a c G" | b c G' | (eps)
| |
| G' -> b c G' | (eps)
| |
| G" -> F e c G' | d G'
| |
| F -> a c G" b | b c G' b | b | a c F e
| |
| | |
| Factoring F prefixes:
| |
| | |
| G -> a c G" | b c G' | (eps)
| |
| G' -> b c G' | (eps)
| |
| G" -> F e c G' | d G'
| |
| F -> a c F' | b F"
| |
| F' -> G" b | F e
| |
| F" -> c G' b | (eps)
| |
| | |
| Eliminating non-terminal left corners (note that F becomes unreachable):
| |
| | |
| G -> a c G" | b c G' | (eps)
| |
| G' -> b c G' | (eps)
| |
| G" -> a c F' e c G' | b F" e c G' | d G'
| |
| F' -> a c F' e c G' b | b F" e c G' b | d G' b | a c F' e | b F" e
| |
| F" -> c G' b | (eps)
| |
| | |
| Factoring F' prefixes, we get to the final version:
| |
| | |
| G -> a c G" | b c G' | (eps)
| |
| G' -> b c G' | (eps)
| |
| G" -> a c F' e c G' | b F" e c G' | d G'
| |
| F' -> a c F' e F" | b F" e F" | d G' b
| |
| F" -> c G' b | (eps)
| |
| | |
| === FIRST & FOLLOW sets ===
| |
| | |
| FIRST(G) = { a, b, (eps) } FOLLOW(G) = { $ }
| |
| FIRST(G') = { b, (eps) } FOLLOW(G') = { $, b }
| |
| FIRST(G") = { a, b, d } FOLLOW(G") = { $ }
| |
| FIRST(F') = { a, b, d } FOLLOW(F') = { e }
| |
| FIRST(F") = { c, (eps) } FOLLOW(F") = { e }
| |
| | |
| | |
| [[category:Compilers]] | |
| [[category:Teaching]]
| |