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 production-derived yields, equal and takes-precedence relations do not conflict for any ordered pair of grammar symbols. A table of these relations can locate reducible phrases for bottom-up parsing. In the operational convention used here, right-hand sides must also be nonempty and unique so a located phrase identifies one reduction. Hladký defines the conflict-free class first and imposes right-side uniqueness separately for an unambiguity theorem.[ref-62d2d04ddd47][ref-68ce1647c9cb]
Scope of Application¶
The class is used in formal-language and compiler theory to characterize grammars suited to local precedence-table parsing. It compares terminals and nonterminals, unlike operator precedence's narrower terminal-focused scheme. The condition belongs to a particular grammar's form; failure of one expression grammar does not by itself prove that its language has no equivalent precedence grammar.[ref-62d2d04ddd47][ref-ca382caf7bd4]
Clarity¶
The table labels neighboring symbols with one of three relations. A takes-precedence boundary prompts a reduction; scanning back to a yields-precedence boundary locates the handle, and a matching production supplies the replacement nonterminal. Two different labels for the same ordered pair would make this simple local choice unavailable.[ref-62d2d04ddd47][ref-ca382caf7bd4]
Manages Complexity¶
The relation matrix turns a potentially deep derivation into local shift/reduce decisions. The construction cost shifts into computing a conflict-free table and, for a conflicting grammar, possibly rewriting its presentation or choosing another parser; the cited sources do not quantify that cost or prove an easy universal rewrite. A unique boundary does not settle which production to apply if two rules share the same right side. That is a separate correctness premise under the operational convention, not a tradeoff. The constructed bracket matrix below was independently checked against Oberlin's rules; it is not a source-published example.[ref-62d2d04ddd47][ref-ca382caf7bd4][^ref-68ce1647c9cb]
Abstract Reasoning¶
Oberlin notes work a recursive grammar S→Aab; A→aS|c and show its conflict-free table. For a smaller constructed example, S→[S]|a, the author-derived left/right sets are L(S)={[,a} and R(S)={],a}; the six occupied pair cells are [=S, S=], [<[, [<a, ]>], and a>], with no pair conflict and distinct nonempty right sides. The derivation was independently checked against the published rules, but the example itself is not published. Neither example proves that all recursive languages are simple precedence.[^ref-62d2d04ddd47]
Knowledge Transfer¶
The live Context-Free Grammar identity is the strict parent: every simple-precedence grammar retains context-free productions and adds a conflict-free all-symbol relation test, with the stated operational right-side restrictions. The same relation construction can test different context-free grammars once productions are explicit. What does not transfer automatically is an easy grammar transformation, table size, or a theorem about an entire language class from one chosen grammar.[ref-62d2d04ddd47][ref-ca382caf7bd4]
[^ref-62d2d04ddd47]: Oberlin College CS 331, “Precedence Grammars”, pp.8–13. [^ref-68ce1647c9cb]: Miroslav Hladký, “Precedence Relations and Their Connection with Unambiguity of Context-free Grammars”, Kybernetika 8(1) (1972), Definition 2.3 and Theorem 2.1. [^ref-ca382caf7bd4]: Watson, Des, “Compilers”, January 2009, §§5.2.4–5.2.6.
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.
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