Homework SourseThere are two restrictions on the type of grammars that can
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.
Solution
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.
