Operator Precedence Parsing: Build the Table and Parse an Expression Step by Step

You may know that multiplication binds more tightly than addition, yet still find it difficult to explain how a parser turns that rule into shift and reduce decisions. The missing piece is a table of relations between terminals. The table derives from a grammar and gives explicit shift and reduce decisions for i+i*i.

Related reading: parsing MCQs and top-down and bottom-up parsing.

Operator precedence parsing: the decision behind 2+3*4

Take the token sequence i + i * i, and assign the three i tokens the values 2, 3, and 4. The intended structure is 2+(3*4)=2+12=14. The control expression (2+3)*4=5*4=20 gives a different answer, proving that precedence changes the parse tree before evaluation begins. This distinction sits inside the wider topic of top-down and bottom-up parsing.

An operator-precedence parser is a restricted bottom-up, shift-reduce parser that compares the topmost stack terminal with the next input terminal. Relations < and = mean shift across a handle boundary, while > means reduce the handle on the stack. These symbols are parsing relations, not arithmetic comparisons.

Operator-precedence grammar and the three terminal relations

The grammar is:

E -> E + T | T
T -> T * F | F
F -> ( E ) | i

Its terminals are {i,+,*,(,)}, and E is the start symbol. An operator grammar has no epsilon production and no two adjacent nonterminals on the right-hand side of any production. It becomes an operator-precedence grammar only when every table cell receives at most one relation.

For terminals a and b, and a nonterminal B, the relations come from these patterns:

• a = b if a right-hand side contains ab or aBb.

• a < b if a right-hand side contains aB and b belongs to FIRSTVT(B).

• a > b if a right-hand side contains Bb and a belongs to LASTVT(B).

The boundary marker adds # < FIRSTVT(E), LASTVT(E) > #, and # = # for acceptance. For example, F -> ( E ) gives ( = ). Equality says that two terminals surround one nonterminal. It does not say that the terminals have equal arithmetic precedence.

FIRSTVT and LASTVT: compute the exact sets bottom up

FIRSTVT is not ordinary FIRST and FOLLOW. Here, FIRST(E) = {"(", "i"}, but FIRSTVT(E) also contains + and * because it records terminals that can become the first visible terminal beside a nonterminal in a sentential form.

Start at F and propagate upward:

• From F -> ( E ) | i, FIRSTVT(F) = {"(", "i"} and LASTVT(F) = {")", "i"}.

• From T -> T * F | F, add * and inherit the sets of F. Therefore, FIRSTVT(T) = {"*", "(", "i"} and LASTVT(T) = {"*", ")", "i"}.

• From E -> E + T | T, add + and inherit the sets of T. Therefore, FIRSTVT(E) = {"+", "*", "(", "i"} and LASTVT(E) = {"+", "*", ")", "i"}.

The propagation chain is: i belongs to FIRSTVT(F), so it enters FIRSTVT(T) through T -> F, and then FIRSTVT(E) through E -> T.

Operator-precedence table: fill every defined cell

Rows show the topmost stack terminal, and columns show the next input terminal. A blank cell is an error, not an implied relation.

+ < * follows because +T occurs and * belongs to FIRSTVT(T). * > + follows because E+ occurs and * belongs to LASTVT(E). The entries + > + and * > * encode left associativity. The relation ( = ) comes directly from (E).

If one cell receives two different relations, the grammar is not usable as an operator-precedence grammar in that form.

Operator-precedence parsing worked example: trace i+i*i#

Each reduced nonterminal is written as N, which can stand for the appropriate F, T, or E. Precedence decisions depend only on terminals.

The decisive shift happens at step 5. Since + < *, the parser shifts multiplication instead of reducing addition. At step 8, * > # reduces N*N first. With our values, that is 3*4=12, followed by 2+12=14.

Operator-precedence parsing traps and limits

Four traps cause most mistakes:

• Confusing FIRST with FIRSTVT: recompute the exact sets instead of copying ordinary FIRST.

• Reducing on < or =: shift on both, and reduce only on >.

• Treating a blank as precedence: reject malformed input such as adjacent i i, since the i,i cell is blank.

• Assuming every operator grammar is conflict-free: fill every cell and check for multiple relations.

Associativity is also visible in the table. The entry + > + makes i+i+i reduce the left pair first, and * > * does the same for multiplication. Unary minus cannot simply be inserted as another binary terminal. Its grammar and table must distinguish the unary role.

This method handles a useful class of expression grammars, not arbitrary context-free grammars or a whole programming language. When a grammar needs general LR states and conflict analysis, continue with SLR, CLR, and LALR parsers for GATE.

Operator-precedence exam patterns: what to practise

Practise five concrete question forms: test the two operator-grammar restrictions, compute FIRSTVT and LASTVT, derive a missing relation such as + < *, identify a conflict or blank error cell, and predict the next shift or reduction for a given stack and input.

Self-check: for stack #N+N with input *i#, the topmost terminal is +, so + < * means shift. For stack #N+N*N with input #, * > # means reduce N*N. These are parser actions, not arithmetic comparisons.

Use focused Operator Precedence questions to practise these decisions. For the wider preparation route, use the GATE CS Exam Preparation category to connect Compiler Design with the rest of the syllabus.

Operator precedence parsing: the short version and next step

The complete method has four steps: verify the grammar, compute FIRSTVT and LASTVT, construct a conflict-free table, then shift on < or = and reduce on > until #N with input # accepts. In the worked expression, i+i*i becomes 2+(3*4)=14.

Rebuild the table once without looking, then retrace all ten actions for i+i*i#. If you want Compiler Design sequenced with the wider GATE CS syllabus, GATE Guidance by Sanchit Sir is the relevant course path.