Simple Precedence Grammar¶
Use conflict-free precedence relations between grammar symbols to locate reducible handles.
Core Idea¶
A simple precedence grammar is a context-free grammar whose productions induce at most one of three Wirth–Weber relations—yields, equal, or takes precedence—for each relevant ordered pair of grammar symbols, terminals and nonterminals alike; some cells can be blank. The relation table can mark the boundaries of a reducible phrase, or handle, for bottom-up parsing. Under the operational parsing convention used here, right-hand sides are nonempty and no two productions have the same right-hand side, so a found handle can be assigned one reduction.[1][2]
Definitions vary at the boundary: a 1972 formal-language paper calls the conflict-free relation property itself “simple precedence” and states right-hand-side uniqueness separately for its unambiguity theorem. That distinction matters. A conflict-free matrix identifies phrase boundaries, while an inverse production lookup still needs to know which nonterminal replaces the phrase. This entry declares the stronger operational convention and records the narrower formal usage rather than silently merging them.[1]
Structural Signature¶
Sig role-phrases:
- Context-free productions — Rules provide terminals, nonterminals and right-hand sides from which the relations are derived.
- All-symbol pair relations — Equal, yields and takes-precedence compare ordered pairs from the full grammar vocabulary, not only operators or terminals.[2]
- Conflict-free table — At most one of the three relations applies to any ordered pair in the chosen grammar.
- Nonempty distinguishable right sides — Under this entry's operational convention, there are no epsilon right sides and no two productions share the same right side; Hladký treats uniqueness as a separate theorem premise.[1]
- Handle boundary — A takes-precedence relation signals a reduction point; scanning backward to a yields-precedence boundary identifies the handle.[3]
- Reduction map — The handle's right side is replaced by its unique production left side, progressively recovering a derivation.
What It Is Not¶
- Not ordinary arithmetic operator priority. The Wirth–Weber matrix compares nonterminals as well as terminals; operator-precedence grammar uses a restricted terminal-focused relation scheme.[3]
- Not any unambiguous context-free grammar. A grammar may be unambiguous yet its induced pair matrix conflicts.
- Not a proof that a language lacks a simple-precedence presentation. Failure of one grammar form does not settle whether an equivalent transformed grammar exists; grammar class and language class are different questions.[3]
- Not one universal definition of epsilon and duplicate-right-side restrictions. This entry's operational convention includes both, while Hladký's formal definition isolates the conflict-free relation test and his unambiguity theorem adds distinct right sides separately.[1]
- Not a precedence table invented after the fact. Relations must be derived consistently from the productions.
Scope of Application¶
Simple precedence was developed as a way to make bottom-up syntax recognition depend on local table comparisons. A parser shifts symbols until the table indicates a right boundary, scans back for the left boundary and reduces the intervening handle. This is attractive when the grammar's relation table is conflict-free and the production to apply is identifiable.[2][3]
The restriction is on the chosen grammar. Oberlin notes demonstrate a small recursive example and build its table; Sussex notes show how an ordinary expression grammar can fail a precedence test while a modified presentation can satisfy one. Whether a practical programming-language grammar can be transformed simply, and whether the resulting table is manageable, are separate design questions. The method is not best summarized as a blanket loss of language expressive power.[2][3]
Clarity¶
For adjacent grammar symbols, = records that they stand together in a production right-hand side; < can mark entry into a derived phrase; > can mark that the preceding phrase has completed before the next symbol. These are grammar-derived parse relations, not numeric comparison of tokens or the semantic value of an operator. A table entry with both < and = is a conflict under the simple-precedence test.[2]
Suppose the parser has recognized a > boundary between its stack top and the next input symbol. It scans backward through stack relations until a < boundary is found. The enclosed symbols form the candidate handle; if a unique production right side matches them, it is replaced by that production's left side. A conflict-free boundary table without an identifiable production would still leave a reduction choice.[3][1]
Manages Complexity¶
The table turns potentially long derivations into local decisions between ordered symbol pairs. This makes the immediate shift/reduce mechanism easy to state. But the simplicity moves work into grammar design, relation computation and table size. A grammar with conflict-bearing pairs cannot use this direct parser without reformulation or a different parsing method.[2][3]
It also explains why distinct-right-side requirements matter under the operational convention. A boundary can locate text that matches a right side, yet if two productions share exactly that right side, the table alone does not tell which nonterminal to push. Grammar-level uniqueness and table-level uniqueness solve different problems.[1]
Abstract Reasoning¶
Oberlin's worked grammar S→Aab; A→aS|c produces a precedence matrix with unambiguous entries. Its recursive structure is not eliminated; the table lets a parser locate the nested handle as it reduces. In contrast, a standard expression grammar can make one symbol pair receive two different derived relations. The appropriate conclusion is that that grammar fails the table test, not that its language has no possible alternative grammar.[2][3]
A second, deliberately small example is S→[S]|a. Here L(S)={[,a} and R(S)={],a}. Oberlin's four rules give exactly the adjacency equalities [=S and S=]; the left-set rule gives [<[ and [<a; the right-set rule gives ]>] and a>]. The fourth rule adds nothing because no S<y entry is generated. Thus every nonempty ordered-pair cell below has one relation, and both right sides are nonempty and distinct. This author-derived, nonpublished table was independently checked against the published rules.[2]
| Stack symbol / next symbol | [ |
S |
] |
a |
|---|---|---|---|---|
[ |
< |
= |
— | < |
S |
— | — | = |
— |
] |
— | — | > |
— |
a |
— | — | > |
— |
Knowledge Transfer¶
The same all-symbol table method can be applied to different context-free grammar notations after productions and vocabulary are stated. What transfers is the test for conflicting pair relations and the handle-boundary parsing logic. What does not transfer automatically is success of the test, uniqueness of a production after locating a handle, or ease of transforming a large language grammar into this form.[2][1][3]
Examples¶
Recursive grammar in Oberlin compiler notes¶
The notes work with S→Aab and A→aS|c, compute left/right symbol sets and display the relation table. The example demonstrates a small recursive grammar in which no relevant pair needs two incompatible relations.[2]
Mapped back: Grammar → two nonterminals with recursive productions; pair relations → =, <, > derived from right sides and left/right sets; conflict test → worked table has one relation per relevant ordered pair; reduction → table-delimited handles map to distinct nonempty right sides.
Constructed bracket-nesting grammar¶
The grammar S→[S]|a generates a nonempty atom a nested in zero or more bracket pairs. Applying Oberlin's four published rules to L(S)={[,a} and R(S)={],a} yields six occupied ordered-pair cells: [=S, S=], [<[, [<a, ]>], and a>]. None carries two labels, and the productions have unique nonempty right sides. The complete author-derived matrix is displayed above and was independently checked against those rules.[2]
Mapped back: Grammar → one recursive nonterminal; pair relations → six occupied matrix cells derived from L(S) and R(S); conflict test → no ordered pair has two labels; reduction → inner a or [S] can reduce to S; provenance limit → the full table is an independently checked author derivation, not a published worked example.
Structural Tensions¶
Local parsing simplicity versus representation work. For Oberlin's worked recursive grammar, the source explicitly constructs the all-symbol relation table, giving a compact local shift/reduce mechanism once the table is available. A grammar whose pair relations conflict cannot use that mechanism as written; reformulating it or choosing a stronger parser moves work into grammar construction and table analysis. Sussex discusses that design choice, but neither source establishes a numerical rewriting cost or a universal transformation for every language. Diagnostic: Does the concrete grammar's derived matrix remain conflict-free after the proposed rewrite, and how much grammar/table work was needed to obtain the local parser?[2][3]
Locating a handle boundary and identifying one inverse production are separate correctness premises, not two costs that can be traded. The 1972 paper states its conflict-free definition separately from a right-side uniqueness condition used in a theorem; our stronger operational convention should not be silently attributed to every formal definition.[1] The constructed bracket example above includes its full author-derived pair matrix, independently checked against the stated rules.
Structural–Framed Character¶
This is a domain-specific formal-grammar class and parsing affordance. Its core is the absence of conflicts among production-derived pair relations across the full grammar vocabulary. The operational definition adds nonempty and unique right sides for straightforward deterministic reduction. The abstraction is not a generic preference for “simple parsing” or a statement about every language generated by some other grammar.
Its all-symbol relation test is a formal structural condition, not an evaluative claim that a grammar is pedagogically simple or universally better. Grammarians specify the productions and relation conventions, but no external institution makes a grammar satisfy or fail the test after those formal objects are fixed. “Precedence” travels into scheduling and law, whereas importing those uses would erase the grammar-specific handle and conflict criteria. Its character: a highly structural class whose identity is nevertheless bound to formal-language objects and reduction semantics.
Structural Core vs. Domain Accent¶
Skeletal relation. Pairwise local relations resolve boundaries for a structured reduction without contradictory labels.
Domain-bound condition. Context-free productions, terminals and nonterminals, sentential forms, handles and Wirth–Weber relations give the pattern its formal-language meaning.
Prime bar. Conflict-free local relation lookup may resemble processes elsewhere, but the named all-symbol grammar test and handle semantics remain specific to parsing theory.
Parent check. The live Context-Free Grammar genus is necessary: every production still replaces one nonterminal regardless of surrounding context. The all-symbol conflict-free precedence test, with the stated operational right-side restrictions, is a stable narrower condition. A context-free grammar with conflicting pair relations or an empty right side remains in the parent but fails this child's convention. Generic conflict-free lookup is a future-prime question, not a current parent.
Instantiates / Related Primes¶
This entry is a kind of Context-Free Grammar.
The live Context-Free Grammar node is the strict parent: this entry adds the all-symbol precedence condition to context-free productions. Operator-Precedence Grammar is a related but differently scoped class that restricts production form and terminal-pair comparisons; no subsumption edge follows merely because both use precedence tables.[3]
Relationships to Other Abstractions¶
Current abstraction Simple Precedence Grammar Domain-specific
Parents (1) — more general patterns this builds on
-
Simple Precedence Grammar is a kind of Context-Free Grammar Domain-specific
A simple-precedence grammar is a context-free grammar with conflict-free all-symbol precedence relations.Every instance retains context-free productions with one nonterminal on the left. It adds a conflict-free Wirth–Weber relation table over grammar symbols and, under this operational convention, nonempty and unique right-hand sides for handle reduction. Context-free grammars without these restrictions remain in the parent but not this child.
Hierarchy paths (2) — routes to 2 parentless roots
- Simple Precedence Grammar → Context-Free Grammar → Formal System → Formalization → Representation → Abstraction
- Simple Precedence Grammar → Context-Free Grammar → Formal System → Formalization → Transformation → Function (Mapping)
Neighborhood in Abstraction Space¶
Simple Precedence Grammar sits in a moderately populated region (51st percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.
Family — Formal Models & Logical Foundations (33 abstractions)
Nearest neighbors
- Linear Grammar — 0.87
- Propositional formula — 0.86
- Noncontracting Grammar — 0.86
- Conjunctive grammar — 0.86
- Logical or — 0.86
Computed from structural-signature embeddings · 2026-10-08
Not to Be Confused With¶
Wirth–Weber precedence relation is one pairwise relation used to test a grammar; the grammar is the full rule system meeting the conflict criterion. Weak precedence grammar tolerates specified limited conflicts and uses extra constraints. LR parsing uses a different state/lookahead apparatus. Operator precedence concerns a terminal-focused subset. Language ambiguity is about strings and derivations; grammar-level table conflicts must be checked separately, with right-side uniqueness under the relevant theorem.[2][1][3]
References¶
[1] Miroslav Hladký, “Precedence Relations and Their Connection with Unambiguity of Context-free Grammars”, Kybernetika 8(1) (1972), Definition 2.3 and Theorem 2.1, conflict-free definition versus separate right-side uniqueness premise checked. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i
[2] Oberlin College CS 331, “Precedence Grammars”, pp.8–13 worked grammar and precedence-table rules checked. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m
[3] Watson, Des, “Compilers”, January 2009, §§5.2.4–5.2.6, handle parsing, grammar reformulation and operator-precedence distinction checked. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l