Chapter 4, Problem 2E

Explanation of Solution

Modifying the grammar based on Figure 2.25:

• In Figure 2.25, they used LR grammar to obtain a realistic example.
• Figure 2.25 uses a left recursive production for stmt_list.
• Using left recursion allows the parser to break the long statement lists as it goes along, rather than waiting until the entire list is on the stack and then break it from the end.
• It also uses left recursive productions for expr and term.
• These two productions captured using left associativity while keeping an operator and its operands together in the same right-hand side.
• The following grammar shows the use of at least one write statement with grammar provided in Figure 2.25.

$\begin{array}{l}\text{program}\to \text{other\_stmt\_list write expr stmt\_list \$\$}\\ \text{other\_stmt\_list}\to \text{other\_stmt\_list other\_stmt | }\in \\ \text{other\_stmt}\to \text{id := expr | read id}\\ \text{stmt\_list}\to \text{stmt\_list stmt |}\end{array}$

Explanation of Solution

Modifying the grammar based on Example 2.17:

• The Example 2.17 shows the recursive descent parser.
• In this method, the execution starts in procedure program. And then the recursive calls are traced out to form a traversal of the parse tree.

$\begin{array}{l}\text{program }\to \text{ other\_stmt\_list writing\_stmt stmt\_list \$\$}\\ \text{other\_stmt\_list }\to \text{ other\_stmt\_list other\_stmt | }\in \\ \text{other\_stmt }\to \text{ id := expr | read id}\\ \text{| if condition then other\_stmt\_list fi}\\ \text{| while condition do other\_stmt\_list od}\\ \text{writing\_stmt }\to \text{ write expr}\\ \text{| if condition then other\_stmt\_list writing\_stmt stmt\_list fi}\\ \text{| while condition do other\_stmt\_list writing\_}\end{array}$