Operator Precedence Parser
A bottom-up parser that specifically evaluates mathematical expressions and operator grammars using relational precedence tables instead of automata.
Before constructing an Operator Precedence parser, the grammar must strictly be an Operator Grammar. It must follow two primary constraints:
- No empty transitions (no
εproductions). The RHS of any rule cannot derive the empty string. - No adjacent non-terminals. You cannot have rules like
A → B C. Terminals must always visually separate non-terminals if they are back-to-back.
Unlike LR parsers that use state numbers or shifts and reduces, Operator Precedence uses relational symbols. Between any two terminals a and b, one of three relations holds:
- a
<·ba yields precedence to b - a
·>ba takes precedence over b - a
=·ba has the same precedence as b
Note: The relation ·> essentially signals the parser to perform a "Reduce" operation. The parser evaluates the string from left to right, inserting <·, =·, and ·> until it isolates the target segment surrounded by <· and ·>.
Precedence Table Example
Standard precedence for arithmetic: * has higher precedence than +. id has the highest precedence.
| id | + | * | $ | |
|---|---|---|---|---|
| id | - | ·> | ·> | ·> |
| + | <· | ·> | <· | ·> |
| * | <· | ·> | ·> | ·> |
| $ | <· | <· | <· | Accept |
Let's evaluate the string id + id * id using the relational table above. We pad the string with $ on both ends. The parser's sole rule is: Shift on <· or =·, and Reduce on ·>.
| Stack | Relation | Input | Action |
|---|---|---|---|
| $ | <· | id + id * id $ | Shift |
| $ id | ·> | + id * id $ | Reduce (pop id) |
| $ E | <· | + id * id $ | Shift |
| $ E + | <· | id * id $ | Shift |
| $ E + id | ·> | * id $ | Reduce (pop id) |
| $ E + E | <· | * id $ | Shift |
| $ E + E * | <· | id $ | Shift |
| $ E + E * id | ·> | $ | Reduce (pop id) |
| $ E + E * E | ·> | $ | Reduce (pop E * E) |
| $ E + E | ·> | $ | Reduce (pop E + E) |
| $ E | $ | Accept |
Notice how the multiplication * is shifted onto the stack instead of reducing the addition +. This is because the relational table says + <· *, forcing the parser to delay the addition until the multiplication completes!