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, or Floyd grammar, is a context-free grammar that passes two tests. Its production rules have no adjacent nonterminals on the right-hand side, making it an operator-form grammar. Then the yields-, equal-, and takes-precedence relations derived from those productions must form a conflict-free matrix: each ordered pair of terminals can have at most one relation. Operator form alone is insufficient; a conflicting matrix cell excludes the grammar.[^ref-243b6a84a422]
This definition concerns the grammar. A parser can use the matrix to find local boundaries for reductions, but no particular parser, end marker, or parallel implementation is required for the grammar to belong to the class. Floyd grammars generate deterministic context-free languages.[^ref-243b6a84a422]
Scope of Application¶
Lonati, Mandrioli and Pradella's arithmetic-expression example prints productions over the terminals \(a,+,\times\), followed by the grammar's terminal-pair matrix. Their later computation for \(a\times a+a\) shows how that grammar can be analyzed. This small example has no parentheses.[^ref-243b6a84a422]
A different setting is Barenghi and colleagues' JSON grammar. They change the official grammar's character-list productions to the right-recursive CHARS → char | char CHARS form, yielding an adapted operator-precedence grammar used with their parser. The adapted grammar is the positive case; the paper does not claim that its unchanged official JSON grammar already passes the test. It also does not print individual matrix cells for the adapted JSON grammar.[^ref-9744fab4f4cb]
Clarity¶
Begin with the grammar's productions, not with a parser's priority declarations. Check that no production right-hand side places two nonterminals next to each other. Derive the precedence relations for ordered terminal pairs from the productions and their left/right terminal sets. If any pair receives two relations, the grammar is operator-form but not a Floyd grammar.[^ref-243b6a84a422]
The matrix, parser, and input string are different things. A successful parse of one string does not prove that the entire matrix is conflict-free. Likewise, a parser's end marker and a special normal form are presentation or implementation choices, not universal defining parts of every operator-precedence grammar.[^ref-243b6a84a422]
Manages Complexity¶
The relation matrix summarizes local information about derivation boundaries. A bottom-up analyzer can use it to locate segments for reduction instead of deciding afresh from every nonterminal name. That is a benefit of the grammar class, not a substitute for the two formal membership tests.[^ref-243b6a84a422]
An existing grammar may need alteration to enter the class. Barenghi's JSON case required one specified right-recursive replacement, while their Lua case needed more work. These observations do not show that every language can be adapted conveniently or that every adaptation preserves all desired parse trees and meanings.[^ref-9744fab4f4cb]
Abstract Reasoning¶
Given a proposed grammar, identify its terminals, nonterminals, start symbol and productions. Test operator form on every right-hand side. Next, derive the three kinds of terminal-pair relation and inspect every matrix cell. Only when all cells have at most one relation does the grammar meet the conflict-free condition in Lonati and colleagues' Definition 1.[^ref-243b6a84a422]
This explains the strict parent relation to live Deterministic Context-Free Grammar. Floyd grammars generate deterministically recognizable context-free languages, but add operator-form productions and the conflict-free derived matrix. Other deterministic context-free grammars need not satisfy those extra restrictions. A different parser for the same qualifying grammar does not change its membership.[^ref-243b6a84a422]
Knowledge Transfer¶
The arithmetic and adapted JSON examples use different terminals and productions, yet ask the same two questions about operator form and the derived matrix. The transferable idea is the test applied to each grammar, not the arithmetic example's particular symbols or matrix values. For JSON, the authors explicitly call their adapted grammar operator-precedence form; because they do not print its matrix cell by cell, no individual JSON precedence relation is asserted here.[ref-243b6a84a422][ref-9744fab4f4cb]
Example¶
Arithmetic expressions. The printed grammar has \(S\to E\), \(E\to E+T\mid T\times a\mid a\), and \(T\to T\times a\mid a\). Mapped roles: \(S,E,T\), \(a,+,\times\), and these productions form the grammar; no displayed right-hand side has adjacent nonterminals; Example 1 derives and prints the terminal-pair relations; each printed cell has at most one relation. The later \(a\times a+a\) trace shows a use of the grammar, not an extra defining condition.[^ref-243b6a84a422]
Adapted JSON. Fig. 9 prints a grammar beginning S → OBJECT, with productions for objects, pairs, values, arrays and strings; it replaces the original CHARS/CHAR rules by CHARS → char | char CHARS. Mapped roles: those adapted productions and their terminal/nonterminal symbols form the grammar; their revised right-hand sides meet operator form; terminal-pair relations are derived from those productions; the authors' explicit OP classification warrants the conflict-free condition. The paper does not display specific JSON matrix cells, so this entry supplies none.[^ref-9744fab4f4cb]
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.
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¶
A grammar that merely has no adjacent nonterminals is operator-form, but may fail the conflict-free matrix test. Programmer-declared operator priorities, including a Prolog or Pratt-style parser policy, are not by themselves Floyd grammars. The live Operator Grammar node concerns a separate linguistic theory. An operator-precedence parser or Floyd automaton is an operational companion to the grammar, not the grammar itself. An unconditional ban on empty productions is also too strong: the cited Fischer normal form permits a possible \(S\to\varepsilon\) exception.[^ref-243b6a84a422]
References¶
[^ref-243b6a84a422]: 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.
[^ref-9744fab4f4cb]: 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.