There are two restrictions on the type of grammars that can be used with a recur
ID: 3932004 • 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
Left recursion is not able to be directly processed when making use of a simple LL(1) parsing algorithm,LL parsing which parses the input from left to right and make use of leftmost derivation.The parser cannot parse a grammar that contains left recursion as the grammar go into an infinite loop.
For example, a simple LL(1) parser written in C is as follows:
int term ()
{
int d;
token(); /* look ahead a token */
switch(last_token) {
case '0': /* if last token is a number */
d = value; /* put the number to d */
token(); /* look ahead a token */
return d; /* return d */
}
}
By using term() above, a multiplying function is as below:
int mexpr()
{
int d;
d = term(); /* calculate term */
switch(last_token) { /* if last token */
case '*': /* is '*' */
d *= mexpr(); /* recurse mexpr() and the result multiply d */
return d; /* return d */
}
}
The grammar above can be expressed as "<mexpr> -> term * mexpr" in CFG; anyway, in case of "<mexpr> -> mexpr * term", the grammar will go into an infinite loop as following the function:
int mexpr()
{
int d;
d = mexpr(); /* calculate mexpr. This is a problem. */
switch(last_token) { /* if last token */
case '*': /* is '*' */
d *= term(); /* recurse mexpr() and the result multiply d */
return d; /* return d */
}
}
The grammar requires only one token look ahead to prevent from backtracking that lowers execution efficiency.
a)
-> if exp then state |
if exp then state else state
b)
-> if exp then state SD
-> else state |
Backtracking can be avoided by changing expression (a) to (b).LL(k) parsing where k > 1 which needs two or more tokens look ahead, but the method is impractical because of inefficiency.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.