2024年3月26日发(作者：)

rterm? -> rfactor rterm | ε

rfactor -> rprimary rfactor?

rfactor? -> * rfactor? | ε

rprimary -> a | b

d) Is the resulting grammar suitable for top-down parsing?

Yes.

Exercise 4.4.1 For each of the following grammars, derive predictive parsers and show the parsing tables. You may left-factor

and/or eliminate left-recursion from your grammars first.

A predictive parser may be derived by recursive decent or by the table driven approach. Either way you must also show the

predictive parse table.

a) The grammar of exercise 4.2.2(a).

4.2.2 a) S -> 0S1 | 01

This grammar has no left recursion. It could possibly benefit from left factoring. Here is the recursive decent PP code.

s() {

match(…0?);

if (lookahead == …0?)

s();

match(…1?);

}

Or

Left factoring the grammar first:

S -> 0S?

S? -> S1 | 1

s() {

match(…0?); s?();

}

s?() {

if (lookahead == …0?)

s(); match(…1?);

else

match(…1?);

}

Now we will build the PP table

S -> 0S?

S? -> S1 | 1

First(S) = {0}