Chapter 4, Problem 3PS

Explanation of Solution

Trace of the recursive descent parser for the string: $a\text{+}b\text{x}c$

STEP-1:

Next token is: 11 Next lexeme is a

Enter

Enter

Enter <factor>

STEP-2:

Next token is: 21 Next lexeme is +

Exit

Exit

STEP-3:

Next token is: 11 Next lexeme is b

Enter

Enter

STEP-4:

Next token is: 23 Next lexeme is x

Exit

STEP-5:

Next token is: 11 Next lexeme is c

Enter

STEP-6:

Next token is -1: Next lexeme is EOF

Exit

Exit

Exit

Extended Backus-Naur Form (EBNF):

BNF is a natural notation for describing syntax described by John Backus and Peter Naur. By extending it, we had EBNF which only enhances the readability and writability of BNF