Question

Show a trace of the recursive descent parser given in Section4.4.1 for the string a * (b + c).

Please give detailed line by line explanation of the answer below.

Next token is: 11, Next lexeme is a

Enter <expr>

Enter <term>

Enter <factor>

Next token is: 23, Next lexeme is *

Exit <factor>

Next token is: 25, Next lexeme is (

Enter <factor>

Next token is: 11, Next lexeme is b

Enter <expr>

Enter <term>

Enter <factor>

Next token is: 21, Next lexeme is +

Exit <factor>

Exit <term>

Next token is: 11, Next 8 is c

Enter <term>

Enter <factor>

Next token is: 26, Next lexeme is )

Exit <factor>

Exit <term>

Exit <expr>

Next token is: -1, Next lexeme is EOF

Exit <factor>

Exit <term>

Exit <expr>

Answer 1

There is a subprogram for each nonterminal in the grammar, which can parse sentences that can be generated by that nonterminal. EBNF is preferably suited for being the basis for a recursive descent parser, because EBNF minimizes the number of nonterminal

Assume we have a lexical analyzer named lex, which puts the next token code in nextToken. The coding process when there is only one RHS: For each terminal symbol in the RHS, compare it with the next input token; if they match, continue, else there is an error. For each nonterminal symbol in the RHS, call its associated parsing subprogram

Lexeme match a character pattern which is associated with lexical category called token

/* Function expr Parses strings in the language generated by the rule*/

void expr()

{

/* Parse the first term */

term();

/* If the next token is * or +, call lex to get the next token and parse the next term */

while (nextToken == ADD_OP || nextToken == SUB_OP){ lex(); term(); }

}

This routine does not detect errors .

Convention: Every parsing routine leaves the next token in nextToken

A nonterminal that has more than one RHS requires an initial process to determine which RHS it is to parse. The correct RHS is chosen based on the next token of input. The next token is compared with the first token that can be generated by each RHS until a match is found. If no match is found, it is a syntax error

/* term Parses strings in the language generated by the rule:*/

void term()

{

/* Parse the first factor */

factor();

/* As long as the next token is ( or ), next token and parse the next factor */

while (nextToken == MULT_OP || nextToken == DIV_OP)

{ lex();

factor();

}

} /* End of function term */

/* Function factor Parses strings in the language generated by the rule: -> id | () */

void factor()

{ /* Determine which RHS */

if (nextToken) == ID_CODE || nextToken == INT_CODE)

/* For the RHS id, just call lex */ lex(); /*

If the RHS is () – call lex to pass over the left parenthesis, call expr, and check for the right parenthesis */

else if (nextToken == LP_CODE)

{

lex();

expr();

if (nextToken == RP_CODE)

lex();

else error();

}

/* End of else if (nextToken == ... */

else error();

/* Neither RHS matches */