There are two restrictions on the type of grammars that can be used with a recur
ID: 3560969 • Letter: T
Question
There are two restrictions on the type of grammars that can be used with a recursive descent parser. The first is that the grammar cannot have any left recursive productions. Give an example of a left recursive production and explain why such productions would be a problem.
The second restriction is that the grammar must not require more than one token look ahead. Give an example of a production that does not have this property. Explain why this restriction is necessary for recursive descent parsing.
Explanation / Answer
One of the most straightforward forms of parsing is recursive descent parsing. This is a top-down process in which the parser attempts to verify that the syntax of the input stream is correct as it is read from left to right. A basic operation necessary for this involves reading characters from the input stream and matching then with terminals from the grammar that describes the syntax of the input. Our recursive descent parsers will look ahead one character and advance the input stream reading pointer when proper matches occur. The routine presented in figure 1 accomplishes this matching and reading process.
Figure 1 - Symbol Matching Routine
Note that the variable called 'next' looks ahead and always provides the next character that will be read from the input stream. This feature is essential if we wish our parsers to be able to predict what is due to arrive as input. Note also that an error indicator is returned.
What a recursive descent parser actually does is to perform a depth-first search of the derivation tree for the string being parsed. This provides the 'descent' portion of the name. The 'recursive' portion comes from the parser's form, a collection of recursive procedures.
As our first example, consider the simple grammar
E ® x+T
T ® (E)
T ® x
and the derivation tree in figure 2 for the expression x+(x+x)
Figure 2 - Derivation Tree for x+(x+x)
A recursive descent parser traverses the tree by first calling a procedure to recognize an E. This procedure reads an 'x' and a '+' and then calls a procedure to recognize a T. This would look like the following routine.
example, namely the old favorite, a grammar that generates strings of the form anbn shown below.
S ® aSb
S ® ab
Factoring brings us:
S ® aZ
Z ® Sb
Z ® b
which is not quite the form we want since it is unclear when to apply the Z-productions. Substituting for S will solve this problem and produce the following productions that are exactly what we want to have.
S ® aZ
Z ® aZb
Z ® b
The general algorithm for substitution appears as figure 4. Capital Roman letters are nonterminals and Greek letters represent (possibly empty) strings of terminals and nonterminals.
Consider the following grammar.
S ® AB
A ® a | SA
B ® b | SB
We first order the nonterminals S, A, and B. The first step is to get the right hand sides in descending order. S ® AB is fine as is A ® a. The next production, A ® SA, is not what we wish to have, so, we follow the steps in the for loop and transform this production as indicated below:
Original
Þ
Substitute
Þ
Remove Recursion
A ® SA
A ® ABA
A ® aA'
A' ® e
A' ® BAA'
To continue, B ® b is what we want, but B ® SB needs some substitution.
Original
Þ
Substitute
Þ
Substitute
B ® SB
B ® ABB
B ® aBB
B ® aA'BB
The final grammar is the following.
S ® AB
A ® a | aA'
A' ® e | BAA'
B ® b | aBB | aA'BB
The grammar is now in a form that will lend itself to recursive descent parser construction after some factoring and substitution.
Original
Þ
Substitute
Þ
Remove Recursion
A ® SA
A ® ABA
A ® aA'
A' ® e
A' ® BAA'
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.