|
|
| (13 intermediate revisions by the same user not shown) |
| Line 1: |
Line 1: |
| = Problem =
| | #REDIRECT [[ist:Top-Down Parsing/Exercise 3]] |
| | |
| Consider the following grammar, where '''<tt>F</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 expand 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'
| |
| | |
| [[category:Compilers]] | |
| [[category:Teaching]]
| |