Shift-reduce parsing; handles; viable prefixes; shift/reduce and reduce/reduce conflicts

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the end of this lesson.

• In the LL(1) parser, what is on the stack at the start, and what happens when a terminal is on top? from Lesson 2.3.3
• What does a recursive-descent parser do when the next token cannot decide the production? from Lesson 2.3.1
• Push 1, push 2, pop, push 3: what is on top? from Lesson 0.2.4

1 · The Story

📖

Working from the words up

Kabir tries the opposite of Chetan’s method. He does not guess from the top category down. Instead he slides words one at a time onto a pile on his desk.

After each word he looks at the top of the pile. If the top few cards form the full right side of a rule, and folding them is the right move now, he removes those cards and puts the rule’s category card in their place. “the price” folds into Subject. Later “Subject Verb” folds into Sentence. If the pile ends as a single Sentence card with no words left, the speech is proper.

The art is choosing the right moment. Sometimes the top of the pile matches a rule, but folding now would make the rest of the sentence impossible to finish. And sometimes two moves both look possible: read another word, or fold now; fold by one rule, or by another. Kabir needs a way to know which.

2 · Predict First

🤔

Parsing id + id * id bottom-up with the expression grammar, the pile holds E + T and the next token is *. Should Kabir fold E + T into E now, or read the * first? Write your guess down. The answer is in the vault.

3 · Core Concept

Bottom-up parsing

A bottom-up parser builds the parse tree from the leaves up to the root. Read backwards, its steps form a rightmost derivation: the parser finds the reverse of S ⇒rm … ⇒rm w.

Shift-reduce parsing

A shift-reduce parser keeps a stack of grammar symbols (bottom marker $) and the remaining input. Four actions:

• shift: move the next input token onto the stack;
• reduce by A → β: the top of the stack is β; pop it and push A;
• accept: stack is $ S and input is $;
• error.

Handles

In a right-sentential form γ = αβw (w all terminals), a handle is a production A → β at a position such that replacing β by A gives the previous right-sentential form in the rightmost derivation. Informally: the substring that must be reduced next. Handles always appear on top of the stack, never buried inside it. Reducing a substring that matches a right side but is not the handle leads to a dead end.

Viable prefixes

A viable prefix is a prefix of a right-sentential form that does not extend past the right end of its handle. These are exactly the stack contents that can appear in a correct shift-reduce parse. Example for the expression grammar: E + T * is viable (just before shifting id), but T * E is not (E can never follow T * on the stack). The set of viable prefixes of any grammar is a regular language, so a finite automaton can recognise it: that is the key idea behind the LR parsers of the next lessons.

Conflicts

• Shift/reduce conflict: the parser cannot decide whether to shift the next token or reduce.
• Reduce/reduce conflict: it cannot decide which of two productions to reduce by.

An ambiguous grammar always produces a conflict: for E → E + E | E * E | id, with E + E on the stack and * next, shifting gives E + (E * E) and reducing gives (E + E) * E.

Story → compiler term

4 · Visual

Shift-reduce parse of id + id * id (moves computed by the parser of Lesson 2.4.3; only symbols shown here). Notice the shift of * while E + T is on the stack.

Handles of each right-sentential form, read off the rightmost derivation in reverse.

5 · Worked Examples

Example 1 Easy

Give the right-sentential forms and their handles for id + id * id.

Solution

See the handle table above: the first handle is the leftmost id (reduce F → id), then F (T → F), then T (E → T), …, ending with E + T (E → E + T). Each handle is on top of the stack at the moment it is reduced, like Kabir’s folds always happening at the top of his pile.

Example 2 Medium

Which of these are viable prefixes of the expression grammar: E + T *, E + T * F, T * E, E + E, ( ( E, E + ( id?

Solution

Viable: E + T *, E + T * F, ( ( E, E + ( id. Not viable: T * E (only F can follow * in this grammar) and E + E (only T can follow +). Checked by running each prefix through the automaton of viable prefixes built in the next lesson.

Example 3 GATE

Show the conflict that the ambiguous grammar E → E + E | E * E | id causes on id + id * id.

Solution

After shifting id + id and reducing both ids, the stack is $ E + E and the next token is *. The parser may reduce E → E + E (giving (id + id) * id) or shift * (giving id + (id * id)): a shift/reduce conflict. Every LR table for this grammar contains conflicts (4 conflicting cells in the 7-state table).

6 · Shortcuts

⚡

Reductions = interior nodes: a shift-reduce parse of a sentence makes one reduce per interior node of its parse tree and one shift per token. Valid when: counting moves in a successful parse.

⚡

Viable prefix test: a stack string is viable if it can be extended by more input to a right-sentential form whose handle ends at or after its last symbol. Quick check: could the next symbols in the grammar really follow? Valid when: MSQs listing candidate stack contents.

7 · GATE Traps

⚠️

• Bottom-up parsers trace a rightmost derivation in reverse.
• A substring that matches a right side is not necessarily the handle.
• The handle is always on top of the stack.
• Viable prefixes never extend past the handle.
• An ambiguous grammar always gives a conflict in every shift-reduce table.

8 · Memory Hook

🧠

Shift to collect, reduce to fold; fold only the handle, and only on top.

9 · Connect the Dots

The question left open: how does the parser know whether the top of the stack is a handle? The next lesson builds a finite automaton over “progress cards” (items) that answers it, and turns the automaton into a parsing table.

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markBottom-up

A shift-reduce parser for a sentence traces:

• (A) a leftmost derivation
• (B) a rightmost derivation in reverse
• (C) a leftmost derivation in reverse
• (D) no derivation

Q2NAT1 markMoves

How many reduce moves does a shift-reduce parser make on id * id + id in E → E + T | T, T → T * F | F, F → ( E ) | id?

Numerical answer: ________

Q3MSQ2 marksViable prefixes

Which are viable prefixes of E → E + T | T, T → T * F | F, F → ( E ) | id?

• (A) E + T *
• (B) T * E
• (C) ( ( E
• (D) E + E

Q4MCQ1 markConflicts

With $ E + E on the stack and * as the next token in E → E + E | E * E | id, the parser faces:

• (A) a reduce/reduce conflict
• (B) a shift/reduce conflict
• (C) no conflict
• (D) an error

Q5MCQ1 markHandles

Where on the stack does the handle appear in shift-reduce parsing?

• (A) at the bottom
• (B) anywhere
• (C) always on top
• (D) in the input

11 · Rule Card

• Bottom-up = leaves to root = rightmost derivation in reverse.
• Actions: shift, reduce A → β (β on top), accept ($S, $), error.
• Handle: the right side to reduce next; always on top of the stack.
• Viable prefix: stack content that can still lead to a handle; the set is regular.
• Conflicts: shift/reduce, reduce/reduce; ambiguous grammars always have them.
• Reduces = interior nodes; shifts = tokens.

12 · Concept Ledger

bottom-up parsingshiftreduceacceptshift-reduce parserhandleright-sentential formviable prefixshift/reduce conflictreduce/reduce conflict

13 · Answer Vault