Operator-precedence grammar¶
A context-free grammar in operator form whose production-derived terminal-pair precedence matrix is conflict-free.
Core Idea¶
An operator-precedence grammar, also called a Floyd grammar, is a context-free grammar in operator form whose precedence relations, derived from its productions for ordered pairs of terminals, form a conflict-free matrix. Operator form means that a production right-hand side has no adjacent nonterminals. Conflict-free means that each ordered terminal pair bears at most one of the derived yields-, equal-, or takes-precedence relations. The second test is indispensable: an operator-form grammar with a conflicting cell is not an operator-precedence grammar.[1]
This is a property of a grammar, not a name for a particular shift-reduce parser. Its local terminal relations can delimit bottom-up reductions, and Floyd grammars generate a subclass of deterministic context-free languages. A parser and its end markers may exploit those relations, but neither the machine's implementation nor parallel execution is a fifth defining condition.[1]
Structural Signature¶
Signature: context-free production system → operator-form right-hand sides → production-derived terminal-pair relations → conflict-free matrix. Together these constrain the grammar's generated language and make local parsing possible.[1]
- Production system and alphabets. Terminals, nonterminals, a start symbol, and productions supply the grammatical object under test. A priority table without a particular grammar has no Floyd-grammar status.[1]
- Operator-form productions. No right-hand side contains two adjacent nonterminals. Remove this restriction and the grammar fails the operator-form prerequisite, even if an unrelated parser assigns priorities.[1]
- Derived terminal-pair relations. The yields, equal, and takes-precedence relations are obtained from productions and left/right terminal sets, rather than merely declared as a programmer's binding policy. Without that derivation, the matrix cannot test this grammar.[1]
- Conflict-free matrix. For every ordered terminal pair, at most one of those relations holds. A pair assigned two relations leaves the grammar outside the Floyd class despite passing the operator-form test.[1]
What It Is Not¶
The grammar is not just an arithmetic operator-priority declaration. A Prolog or Pratt-style parser may use numerical precedence and associativity, but those declarations alone do not exhibit operator-form productions or a conflict-free matrix derived from a particular grammar. Nor does the name mean Harris's linguistic Operator Grammar; the live entry concerns a different theory of human-language structure.[1]
It is also not identical to its language, parse tree, Floyd automaton, or parsing procedure. Those may witness what the grammar generates or how it is analyzed, but the grammar-level membership test rests on the production system and derived matrix. The paper's special end marker and Fischer normal form support an operational presentation; the latter even permits a possible \(S\to\varepsilon\) exception, so an unconditional ban on empty productions is not the minimal identity.[1]
Scope of Application¶
Lonati, Mandrioli and Pradella give a small arithmetic-expression grammar without parentheses, with terminal symbols \(a,+,\times\), operator-form productions, and its printed precedence matrix. Their later derivation and automaton computation for \(a\times a+a\) illustrate what the local relations enable; the computation is evidence of use, not another condition of grammar membership.[1]
Barenghi and colleagues give a distinct data-description setting. Their Fig. 9 starts from an official JSON grammar and replaces the CHARS/CHAR productions with the right-recursive CHARS → char | char CHARS form to obtain an operator-precedence grammar for their parser. The positive instance is this adapted grammar. The authors do not print the adapted JSON terminal-pair matrix cell by cell, so their explicit classification supports the instance without supplying any particular cell value for us to quote.[2]
Operator-precedence grammars can support deterministic bottom-up or local analysis. The studied parser's parallel scanner, end-marker convention, generated code, and measured speed are application details. The formal class does not require every source grammar to be transformed, every program to be parsed in parallel, or every equivalent grammar to preserve the same parse-tree or semantic choices.[1][2]
Clarity¶
Ask two questions in order. First, is the particular grammar operator-form? Second, when its terminal relations are derived from the productions, does any ordered terminal pair receive more than one relation? A “yes” to the first question alone is insufficient; a conflict in the second defeats membership. This separates the seed's right-hand-side restriction from the distinguishing Floyd test.[1]
Keep the level of description fixed. A relation matrix is computed for a grammar; a parser reads it; an input string is analyzed with it. Conversely, a successful parse of one string cannot certify that every matrix cell is conflict-free. Barenghi's adapted JSON grammar is the positive grammar case, whereas the paper's scanner and PAPAGENO results describe one way to use it.[1][2]
Manages Complexity¶
The three terminal relations compress information about derivation boundaries into a local matrix. Rather than treating every nonterminal symbol as an unrelated parser decision, a bottom-up analysis can consult the relation between nearby terminals to locate a reducible segment. This is useful because the matrix is derived once from the productions and can guide many input analyses under that grammar.[1]
The compression has a price: a desired source grammar may require refactoring before it belongs to the class. In Barenghi's comparison, JSON needed one specified right-recursive replacement, while Lua required more involved adaptation. That observation is about the studied grammars and parser engineering; it is not a proof that every language has a convenient operator-precedence presentation.[2]
Abstract Reasoning¶
For a proposed grammar \(G\), inspect every production right-hand side for adjacent nonterminals. If the operator-form test passes, derive its three precedence relations for each ordered terminal pair using the grammar's terminal sets and productions. Place the resulting relations in the matrix. If an occupied cell contains two distinct relations, \(G\) fails the Floyd test. If all cells contain at most one, \(G\) is an operator-precedence grammar under Lonati and colleagues' Definition 1.[1]
This reasoning distinguishes a property of a formal object from a property of an implementation. A parsing trace can illustrate the matrix in action, but it cannot replace the all-cell test. Likewise, changing the parser without changing the qualifying grammar does not remove its class membership. In the other direction, swapping in a new grammar for the same intended language requires the tests to be run again.[1]
Knowledge Transfer¶
The arithmetic example teaches the matrix test directly because both the productions and the matrix are printed. The JSON example tests transfer to a different terminal vocabulary and production system: the authors alter the grammar's character-list rules to obtain OP form, then use it in an applied parser. The transferable method of classification is to inspect the grammar and derive/check its terminal relations, not to copy arithmetic priority values into JSON.[1][2]
That transfer is bounded. JSON object and string productions do not become arithmetic expressions, and the sources do not supply a JSON matrix from which this entry could assert specific yields, equal, or takes-precedence cells. A future grammar in yet another domain would need its own production-level and matrix-level evidence.[2]
Examples¶
Arithmetic expressions. Lonati and colleagues print \(S\to E\), \(E\to E+T\mid T\times a\mid a\), and \(T\to T\times a\mid a\), with terminals \(a,+,\times\). Mapped roles: \(S,E,T\), the terminals, and those productions are the production system; every displayed right-hand side avoids adjacent nonterminals; Example 1 derives and prints the ordered terminal-pair relations; each printed cell has at most one relation, so Definition 1 classifies this grammar as Floyd. Their \(a\times a+a\) trace demonstrates analysis of a generated string, not a fifth constitutive role. This example has no parentheses.[1]
Adapted JSON syntax. Barenghi and colleagues print an object-root grammar beginning S → OBJECT, with productions including OBJECT → { } | { MEMBERS }, PAIR → STRING : VALUE, and VALUE → STRING | number | OBJECT | ARRAY | bool. They replace the original CHARS/CHAR rules by CHARS → char | char CHARS. Mapped roles: Fig. 9's terminals, nonterminals, start symbol and adapted productions supply the production system; the revised right-hand sides meet operator form; the relevant terminal-pair relations are derivable from those adapted productions; the authors classify the result as OP, which warrants the conflict-free condition under the formal definition. The paper does not print individual JSON matrix cells, and this entry claims none. JSON data syntax and arithmetic-expression syntax are unlike carriers of the same grammar-level condition.[2][1]
Structural Tensions¶
There is a qualified parser-engineering tension when an existing language specification is to be used with an operator-precedence parser. Preserving the source grammar unchanged and satisfying the parser's restricted grammar class cannot both be achieved if that source grammar is not already in OP form; one must adapt the grammar or forgo that parser route. Barenghi's JSON case needed a small rule change, while Lua required more work. This is an application-level tradeoff evidenced by those cases, not an intrinsic cost incurred by every operator-precedence grammar, and it does not guarantee that every adaptation preserves all intended syntactic or semantic distinctions.[2]
The autonomy question is grammatical: the formal class is determined by operator form and a conflict-free derived matrix even when no parallel parser is commissioned. Treating the local-parsing benefit as the defining condition would reduce the grammar to one implementation. That is a scope diagnostic, not a second intrinsic tension.[1][2]
Structural–Framed Character¶
This entry is structural within formal-language theory. Its membership test is fixed by production form and a derived matrix, independent of whether a particular parser is fast, elegant, or profitable. Human practice selects a grammar, terminal vocabulary and implementation, but those choices do not replace the all-cell conflict test. The institutional origin is the formal-language and compiler-research tradition that defined and publishes the grammar class; the condition itself is checkable once the productions are given.[1]
The word precedence travels to arithmetic priority rules and other parsing techniques, but a shared word is not proof of the Floyd condition. The move from arithmetic expressions to adapted JSON recognizes the same production-and-matrix constraint in another grammar; it does not import arithmetic's concrete matrix cells into JSON. A wider local-relations-to-global-analysis skeleton would require evidence outside formal grammars before it could be advanced as a new Prime. Its character: a formally defined grammar subclass whose parser applications remain contingent, with a conflict-free derived terminal matrix as its distinguishing invariant.[1][2]
Structural Core vs. Domain Accent¶
The core is the conjunction of a context-free production system, operator-form right-hand sides, production-derived terminal-pair relations, and the conflict-free matrix invariant. Remove the grammar and there is only a policy or table; remove operator form or permit a conflicting cell and the named class disappears. The terminal letters in the arithmetic example, JSON's braces and string tokens, a particular end marker, and the choice of sequential or parallel parser are accents. Local analyzability follows from the formal class but is not itself the grammar object.[1][2]
The nearer live genus is Deterministic Context-Free Grammar, whose identity is a CFG generating a deterministically recognizable language. Floyd grammars satisfy that genus and add the production and matrix restrictions, so the recorded edge is strict subsumption. The present entry does not clear the Prime bar: its defining relations are production and terminal-pair conditions in formal-language theory. Could an analogous local-relation constraint organize global analysis in non-grammar domains? That is a future-Prime question, requiring unlike nonlinguistic evidence and a separate identity test; no such edge is asserted here.[1]
Instantiates / Related Primes¶
This entry is a kind of Deterministic context-free grammar.
- Deterministic Context-Free Grammar — broader, in every case. Every Floyd grammar generates a deterministic context-free language; its conflict-free matrix supplies an additional grammar-specific restriction.[1]
- Context-Free Grammar and Formal Grammar — broader still, not listed directly. Being a grammar of those kinds already follows at the grammar level, so the nearer deterministic category is the one given here and the broader ones are not listed again as direct relations.
- Operator Grammar — a different concept with a similar name. That entry describes Harris's theory of human language, not the formal operator-form condition; the shared spelling does not make it broader.
- Parsing — related, not broader. A parser may exploit the matrix, but executing a parse is neither the grammar's carrier nor a prerequisite for its formal identity.
Relationships to Other Abstractions¶
Current abstraction Operator-precedence grammar Domain-specific
Parents (1) — more general patterns this builds on
-
Operator-precedence grammar is a kind of Deterministic context-free grammar Domain-specific
Every Floyd grammar generates a deterministic context-free language, while its operator form and conflict-free derived terminal matrix add stricter conditions.The live Deterministic Context-Free Grammar genus identifies a context-free grammar by the deterministic pushdown recognizability of its generated language. Lonati, Mandrioli and Pradella place Floyd grammars within deterministic context-free languages. An operator-precedence grammar remains a CFG with a generated language in that class, but additionally requires operator-form productions and at most one production-derived precedence relation per ordered terminal pair. Other deterministic context-free grammars need not satisfy those two additional tests. This is grammar-level strict subsumption, not a claim that a chosen parser or every parse-tree presentation is constitutive of the grammar.
Hierarchy path (1) — routes to 1 parentless root
- Operator-precedence grammar → Deterministic context-free grammar → Determinism → Causality → Dependency
Neighborhood in Abstraction Space¶
Operator-precedence grammar sits in a sparse region of the domain-specific corpus (69th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Grammar Derivation & Word Complexity (8 abstractions)
Nearest neighbors
- Left Recursion — 0.86
- LL Grammar — 0.86
- Simple Precedence Grammar — 0.84
- Context-Free Grammar — 0.84
- Linear Grammar — 0.83
Computed from structural-signature embeddings · 2026-10-08
Not to Be Confused With¶
An operator-form grammar has no adjacent nonterminals but may still have a conflicting terminal-pair matrix. An operator-priority declaration may configure a parser without defining a Floyd grammar. A Floyd automaton or an end-marked reduction trace is an operational companion, not the productions themselves. The authors' adapted JSON grammar is positive; their unmodified official JSON grammar is not claimed as positive. Fischer normal form's possible \(S\to\varepsilon\) exception prevents turning a parser convention into a universal empty-production prohibition.[1][2]
References¶
[1] Violetta Lonati, Dino Mandrioli, and Matteo Pradella, Precedence Automata and Languages, author-hosted original PDF, §1 pp.1–2; §2 Definition 1, Example 1, and Definition 2, PDF pp.3–4; §4.1 Example 3 and Fig. 4, PDF p.9. The source directly defines operator form and the conflict-free production-derived matrix, prints the arithmetic grammar and matrix, and depicts the later arithmetic computation. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o ↩p ↩q ↩r ↩s ↩t ↩u ↩v ↩w ↩x ↩y ↩z
[2] Alessandro Barenghi, Stefano Crespi Reghizzi, Dino Mandrioli, Federica Panella, and Matteo Pradella, Parallel Parsing Made Practical, author-hosted original preprint, abstract PDF p.1; §4.1 and Fig. 9 PDF p.24 (printed p.23); §4.2 PDF pp.24–26; §5–6 on parser and experiments. Fig. 9 distinguishes the official JSON character rules from the right-recursive replacement; the authors call the adapted grammar operator-precedence form but do not print a derived JSON matrix cell table. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l