Lecture No. 22

Dated: 21-04-2025

Expression Grammar

\[x - 2 \times y\]

Tokenized

\[\text{id} - \text{num} \times \text{id}\]

Step	word	Stack	Handle	Action
1	id	►	- none -	shift
2	–	id ►	<Factor → id,1>	reduce
3	–	Factor ►	<Term → Factor,1>	reduce
4	–	Term ►	<Expr → Term,1>	reduce
5	–	Expr ►	- none -	shift
6	num	Expr – ►	- none -	shift
7	×	Expr – num ►	<Factor → num,3>	reduce
8	×	Expr – Factor ►	<Term → Factor,3>	reduce
9	×	Expr – Term ►	- none -	shift
10	id	Expr – Term × ►	- none -	shift
11	$	Expr – Term × id ►	<Factor → id,5>	reduce
12	$	Expr – Term × Factor ►	<Term → Term × Factor,5>	reduce
13	$	Expr – Term ►	<Expr → Expr – Term,3>	reduce
14	$	Expr ►	<Goal → Expr,1>	reduce
15		Goal	- none -	accept

Handles

The handle finding mechanism is crucial in bottom-up parsing,¹ where the parser² tracks potential handles- substrings matching the right-hand side of productions to guide reductions.
Parsing¹ starts with <Goal → Expr,1> as a potential handle,³ and as it proceeds, new handles³ emerge, representing suffixes that can be reduced.

Count	Handle
1
2
3
4
5
6
7
8
9

The notation reveals identical handles and allows tracking future handle discovery.
For example, in step 6, the parser state Expr → Expr – • Term shows it has recognized Expr – and is waiting for Term.
Once Term is shifted, the handle completes. Each production with k symbols has k + 1 potential handle positions, marked by placeholders between or around symbols.

(The • symbol presents top of the stack)

• Expr → • Expr – Term
• Expr → Expr • – Term
• Expr → Expr – • Term
• Expr → Expr – Term •

References

---

1. Read more about bottom up parsing. ↩↩

2. Read more about parser. ↩

3. Read more about handles. ↩↩