Operator-precedence parsing decides whether to shift or reduce by comparing the topmost terminal on the stack with the next input terminal. It does not compare arbitrary nonterminals or evaluate the expression's arithmetic value. The operator-precedence parser generates the sets, relation table, precedence functions and trace used here.
Every table below comes from that tool's library for this grammar:
E -> E + T | T
T -> T * F | F
F -> ( E ) | id
The grammar separates addition, multiplication and factors. It has no empty production and no two adjacent nonterminals on a right side, so it passes the tool's operator-grammar check. Passing that structural check is a prerequisite, not a guarantee that every possible relation table is conflict-free.
LEADING and TRAILING are not ordinary FIRST and FOLLOW
LEADING includes terminals that can appear at the left edge after at most one leading nonterminal is skipped. TRAILING is the corresponding right-edge construction. In compiler notes these sets are often called FIRSTVT and LASTVT. They are used to relate neighboring terminals across a nonterminal, which is why their contents need not match ordinary FIRST and LAST sets of generated terminal strings.
A rule beginning with a terminal contributes it directly to LEADING. A rule beginning with a nonterminal propagates that nonterminal's set, and contributes the next symbol when it is a terminal. Repeat until the sets stop changing. Reverse the direction for TRAILING. The generated fixed point is:
| Variable | LEADING | TRAILING |
|---|---|---|
| E | +, *, (, id | +, *, ), id |
| T | *, (, id | *, ), id |
| F | (, id | ), id |
For example, multiplication appears in LEADING(T) because T -> T * F begins with a nonterminal followed by that operator. This does not claim that a valid expression can begin with a multiplication token. Confusing that fact with FIRST(T) is a common source of wrong relation tables.
Derive the three terminal relations
The relation ⋖ means yields precedence and tells the parser to shift. The relation ⋗ means takes precedence and tells it to look for a handle to reduce. The relation ≐ joins terminals inside a handle; it is not an arithmetic equality test.
For adjacent terminals, add ≐. For a terminal followed by a nonterminal, add ⋖ to that variable's LEADING terminals. For a nonterminal followed by a terminal, add ⋗ from that variable's TRAILING terminals. A terminal–nonterminal–terminal pattern contributes ≐ between its outer terminals; parentheses provide the familiar example. The end marker yields to LEADING(start), and TRAILING(start) takes precedence over end.
The full generated table uses the stack terminal as the row and lookahead as the column. A dash is an undefined relation, not permission to shift:
| Stack / next | + | * | ( | ) | id | $ |
|---|---|---|---|---|---|---|
| + | ⋗ | ⋖ | ⋖ | ⋗ | ⋖ | ⋗ |
| * | ⋗ | ⋗ | ⋖ | ⋗ | ⋖ | ⋗ |
| ( | ⋖ | ⋖ | ⋖ | ≐ | ⋖ | — |
| ) | ⋗ | ⋗ | — | ⋗ | — | ⋗ |
| id | ⋗ | ⋗ | — | ⋗ | — | ⋗ |
| end | ⋖ | ⋖ | ⋖ | — | ⋖ | — |
The generated conflict count is 0. If a cell had incompatible relations, it would need attention before treating the table as a deterministic shift-reduce policy. Do not silently choose whichever relation appears first in a handwritten list.
Replace known relations with f and g comparisons
Precedence functions assign a number f(a) to a stack terminal and g(b) to a lookahead terminal. A defined ⋖ relation requires f(a) < g(b); ≐ requires equality; ⋗ requires greater-than. The tool merges equality constraints, builds the strict comparison graph and finds longest-path values when that graph has no cycle.
For this table the computed functions are:
| Terminal | f | g |
|---|---|---|
| + | 2 | 1 |
| * | 4 | 3 |
| ( | 0 | 5 |
| ) | 4 | 0 |
| id | 4 | 5 |
| end | 0 | 0 |
The values are one satisfying assignment, not arithmetic operator values or a uniquely normalized answer. Adding the same constant everywhere would retain the comparisons. A cyclic constraint system can prevent functions from existing even for a relation table you can still inspect directly.
An undefined table entry remains undefined. Numeric functions alone can assign a less/equal/greater comparison to such a pair, but that comparison does not make the original grammar relation valid. The tool's parser follows the relation table, including its error cells; do not replace the table with unconditional numeric comparisons and expect identical error detection.
Generated trace for id + id * id
The initial stack contains end. Compare its topmost terminal with the next token. Shift on ⋖ or ≐; on ⋗, scan back across terminals until the handle's opening ⋖ boundary, then replace the handle by the matching production's nonterminal.
| Stack before action | Remaining input | Action |
|---|---|---|
| end | id + id * id end | end ⋖ id: shift id |
| end id | + id * id end | id ⋗ +: reduce by F → id |
| end F | + id * id end | end ⋖ +: shift + |
| end F + | id * id end | + ⋖ id: shift id |
| end F + id | * id end | id ⋗ *: reduce by F → id |
| end F + F | * id end | + ⋖ *: shift * |
| end F + F * | id end | * ⋖ id: shift id |
| end F + F * id | end | id ⋗ end: reduce by F → id |
| end F + F * F | end | * ⋗ end: reduce by T → T * F |
| end F + T | end | + ⋗ end: reduce by E → E + T |
| end E | end | Accept |
The result is accepted. Multiplication's handle reduces before the pending addition. Parenthesizing the earlier addition would instead change the handle boundaries through the parenthesis relations. This trace is generated from the complete table, not a manually shortened narrative with some reductions omitted.
Why unit productions do not appear as separate reductions
The supplied expression grammar contains unit rules such as E -> T. This operator-precedence implementation matches nonterminal positions by shape during handle reduction and does not apply those unit rules as independent steps. Consequently, intermediate stack labels can differ from an LR parse of the same word. The tool explains this convention; compare terminal boundaries and handle shapes before assuming that two traces must print identical nonterminal labels.
This is a teaching parser for the documented operator-grammar method, not a complete replacement for a generated LR parser or a general-purpose grammar recognizer. It does not compute a semantic expression value or build an AST from declarations of numeric operator priorities. Use infix conversion for an expression tree and evaluation trace, or the LR parser for LR state/item tables.
Check an exam answer systematically
First verify the operator-grammar restrictions. Recompute LEADING/TRAILING to a fixed point rather than stopping after one scan. Check table orientation before applying ⋖ and ⋗. Preserve blank entries, keep the end marker explicit and compare the topmost terminal rather than the top stack element when a nonterminal is above it.
Finally, distinguish a conflict-free table from a numeric function representation and from the acceptance of a particular word. These are different checks. Return to the interactive parser to change the grammar or word and inspect the rule reason attached to each relation. The compiler lab groups the related predictive, precedence and LR parsing exercises.
For a related walkthrough, read FIRST and FOLLOW Sets Example, Step by Step.