Operator Grammars
1. Definition
An operator grammar has no ε-productions and no two adjacent non-terminals on any right side — operators and operands alternate (e.g. E → E+E | E*E | id). Ideal for expression parsing via precedence, without full LL/LR tables.
2. Precedence Relations (3 relations between terminals)
For terminals a, b: a ⋖ b (a yields: push b), a ⋗ b (a takes: reduce), a ≐ b (equal: same production, e.g. ( ≐ )).
Built from LEADING and TRAILING sets:
a ⋖ b if ... A → ... a B ... and b in LEADING(B)
a ⋗ b if ... A → ... B b ... and a in TRAILING(B)
a ≐ b if A → ... a b ... or A → ... a B b ...
Classic table for + * ( ) id $:
+ * ( ) id $
+ ⋗ ⋖ ⋖ ⋗ ⋖ ⋗
* ⋗ ⋗ ⋖ ⋗ ⋖ ⋗
( ⋖ ⋖ ⋖ ≐ ⋖ err
) ⋗ ⋗ err ⋗ err ⋗
id ⋗ ⋗ err ⋗ err ⋗
$ ⋖ ⋖ ⋖ err ⋖ acc
3. Operator-Precedence Parsing (shift-reduce with table)
stack has $; compare top terminal with next input via table:
⋖ or ≐ → shift (push); ⋗ → reduce (pop handle); acc → done
Trace id+id*id: shifts id, reduces to E, sees ⋖ on +, shifts, etc. — * binds tighter because + ⋖ * but * ⋗ +.
4. Strengths / Limits
- Simple, fast, hand-built for expressions; used in old calculators.
- Only for operator grammars; cannot handle
()-free adjacency or ε; less powerful than LR.
5. Exam Points
- Define operator grammar + build precedence table — 7 marks, very frequent.
- Trace shift-reduce with ⋖ ⋗ ≐ on expression — 5 marks, frequent.
- LEADING/TRAILING computation — 5 marks, frequent.