Chapter 4, Problem 4PS

Explanation of Solution

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.

The recursive descent parser works on the following EBNF for the arithmetic expressions:

{(+|-)}

{(*|/)}

id|int_constant|()

We know that, the following tokens are returned by the lexical analyzer for the lexemes:

Token	Lexeme
11	Identifier
21	+ Operator
23	* Operator
25	(
26	)

In the table the left column having the heading token refers to the token codes to the different types of the categories like:-

a) 11 = identifier

b) 21 =ADD operator

c) 23 = MULTIPLY operator

d) 25 = left brace lexeme

The example given in the problem is $a\ast \left(b+c\right)$. The recursive descent parser will start working from the left most term. First the whole statement is taken as an expression and it enters into expression category then the first term is taken which enters into the term category which further enters into the factor group