Show a complete parse, including the parse stack contents, input string, and action for the string (id + id) * id, using the grammar and parse table in Section 4.5.3.

Table in Section 4.5.3.

Consider the traditional grammar for arithmetic expressions that follows:

1. E→E+T

2. E→T
3. T→T*F

4. T→F

5. F→(E)

6. F→id

Figure 4.5 parse table

Following is a trace of a parse of the string id + id, using the LR parsing algorithm and the parsing table shown in Figure 4.5.

Stack Input Action Shift 5 Reduce 6 (use GOTO|0, F) Reduce 4 (use GOTO[0, T]) Reduce 2 (use GOTOJ0, El) Shift 6 Shift 5 Reduce 6 (use GOTO[6, F) Reduce 4 (use GOTO(6, T]) Shift 7 Shift 5 Reduce 6 (use GOTO[7, F) Reduce 3 (use GOTO[6, T]) Reduce 1 (use GOTO[0, El) Accept id + id * id S Oid5 OF3 OT2 + id * id $ SP!. P! + + id * id $ OEI OE1+6 S P!. P! + OE1+6ids OE1+6F3 id * id S * id S *id S SP!. id $ OE1+6T9 OE1+6T9*7 $ OE1+6T9*7id5 OE1+6T9*7F10 OE1+6T9 OE1