LR-Attributed Grammar¶

An attribute grammar whose semantic values, including any inherited values, can be evaluated during LR parsing under a specified compatible method.

Version: v1 · 2026-10-25 · History
Domain-specific #: 14414
Domain group: Applied Sciences & Engineering
Origin domain: Computer Science & Software Engineering
Subdomains: Compiler Construction, Attribute Grammars → Computer Science & Software Engineering

Core Idea¶

An LR-attributed grammar couples a context-free grammar and semantic attribute equations so that the attribute values needed for semantic analysis can be computed while an LR parser reads the input and performs its shifts and reductions.^[1]^[2] When inherited information is present, it creates an additional challenge: a reduction can compute a synthesized result from available values, but a child nonterminal may require context before it is parsed.^[1] A successful LR-attribution construction makes that value available consistently at the required parser point.^[2]

The literature gives more than one precise construction.^[3] Sassa and colleagues require an L-attributed grammar and a unique semantic expression for each inherited attribute needed in each LR state.^[2] Wilhelm, Seidl, and Hack describe copying inherited values through a parser state and, for noncopying values, inserting empty marker productions; in their construction the transformed syntax must still be LR(k).^[1] These are method-labelled membership tests, not interchangeable statements of one universal algorithm.^[3]

Two complete cases show why the class concerns attribute flow rather than a parser product name. In Sassa and colleagues' miniature language, declarations build a set of known identifiers and a later list of uses inherits that set; the authors explicitly show that the needed inherited expressions are unique in the LR states.^[2] In a proper expression-typechecking subgrammar derived from Wilhelm, Seidl, and Hack's AGtypes example, a supplied environment is copied into each expression part while types and validity results are synthesized at reductions.^[1] The second case excludes the assignment production of the printed grammar; the full printed AGtypes grammar is not certified as LR by this example.^[n1]

Structural Signature¶

Role map: syntax and attribute equations → LR parser states and reductions → inherited values available when present → synthesized results computed at reductions when present → one-pass semantic evaluation under the named construction.

Carrier. A context-free grammar defines productions; associated equations define inherited and synthesized attributes.^[1] Syntax alone does not say whether its semantic dependencies fit LR-time evaluation.^[2]
Parser schedule. The LR parser reads left to right and reduces recognized right-hand sides. When synthesized equations are present, the right-hand side and its values are available at the reduction.^[1]^[2]
Inherited input. When an inherited input exists, the nonterminal needing context must receive it before the corresponding parse work.^[1] In Sassa's formulation, all possible derivations represented by an LR state must yield the same semantic expression for that input.^[2]
Compatibility condition. In Wilhelm, Seidl, and Hack's marker formulation, a computation that cannot be copied may be moved to an empty-production reduction before the affected nonterminal.^[1] This only establishes LR attribution when the inserted markers leave the grammar LR(k).^[1]
Result. The parser and attribute evaluator can work in one pass without first building a complete parse tree merely to evaluate the attributes. This is a property of the grammar and the specified scheduling method, not a blanket property of every LR parser or every L-attributed grammar.^[2]

What It Is Not¶

An S-attributed grammar uses only synthesized attributes.^[1] If its syntax is LR, its results can be computed on reductions, making it a simple boundary case of LR-compatible evaluation.^[1] The S-attributed label by itself does not assert that the syntax is LR, and it does not test the difficult inherited-value role.

An L-attributed grammar allows inherited equations whose dependencies are available in a left-to-right traversal of a parse tree.^[1] That dependency rule does not by itself ensure that a bottom-up LR parser knows which inherited equation to apply in time. Wilhelm, Seidl, and Hack give an L-attributed Boolean-expression example whose necessary markers destroy LR(k); under their construction it is not LR-attributed.^[1]

An ECLR-attributed grammar adds equivalence-class treatment of inherited attributes in Sassa and colleagues' method.^[2] Their report says its ECLR class is not smaller than their LR-AG class under the stated partition definition.^[2] It should be compared under its own definition rather than declared a universally strict subclass. A context-free grammar supplies only the syntactic carrier; a parser generator is an implementation vehicle, not a proof of LR-attributed membership.

Scope of Application¶

The literal scope is compiler construction and formal language semantics where a grammar's semantic equations need evaluation during LR parsing. Suitable uses include checking identifiers against declarations, determining expression types from an environment, and generating semantic actions together with a parser. The claim must identify the actual grammar, its equations, the LR parser construction, and the chosen way inherited inputs become available.^[2]^[1]

The scope has an important exit. A grammar may be L-attributed yet fail the chosen LR evaluation test; a syntax grammar may be LR yet carry inherited equations that the parser state cannot determine uniquely; and adding markers can preserve the language but remove LR(k). Those are different failure points and must be reported separately.^[1]^[2]

Clarity¶

The word LR concerns the parser's left-to-right bottom-up schedule, while attributed concerns the semantic values attached to grammar symbols. At a reduction, synthesized output can be formed from known children. An inherited input may be needed earlier. Therefore an LR syntax check alone is insufficient, and a left-to-right attribute-dependency check alone is also insufficient. Both parser timing and equations matter.^[1]^[2]

The full AGtypes grammar printed by Wilhelm, Seidl, and Hack contains an assignment alternative.^[1] Our exact local Bison 2.3 transcription of that syntax reports one shift/reduce conflict.^[n1] The typechecking case below is explicitly a proper subgrammar without the assignment alternative. Its syntax has zero LALR(1) conflicts in the same local check.^[n1] The remaining env equations are the textbook's copying equations.^[1] These facts warrant the bounded case, not a statement that the original full grammar is LR(k).

Manages Complexity¶

The classification turns an informal claim of “one-pass semantics” into inspectable questions. First, can the parser recognize the syntax with the claimed LR method? Second, what inherited value must be known at each parser point? Third, can every represented derivation supply that value by one consistent expression, or can a marker compute it while preserving LR(k)? Fourth, can each synthesized result be produced when its reduction occurs? A candidate that fails any needed part cannot borrow the label from a similar grammar.^[2]^[1]

This separation also prevents source overreach. Sassa's AG1 is a complete grammar with a source-provided LR-state proof.^[2] Wilhelm, Seidl, and Hack's AGscopes is an instructive local marker transformation that retains LR(k) in the shown example, but their earlier presentation says that displayed grammar omits further productions needed for a complete language.^[1] The latter illustrates a mechanism; it is not used here as a second complete positive grammar.

Abstract Reasoning¶

For a proposed grammar, begin with a concrete production and its equations. On an LR state before a nonterminal, list the possible inherited expressions induced by the items in that state. Under Sassa's criterion, if an inherited attribute has more than one distinct expression there, the parser cannot assign it one unambiguous value under that method. If all such expressions are unique and the grammar is L-attributed, the inherited values can be scheduled as the parser enters the states; synthesized values follow reductions.^[2]

Under the marker method, identify a noncopying inherited equation, put an empty marker immediately before the nonterminal that needs its value, and ask whether the transformed grammar remains LR(k).^[1] A marker can make the semantic calculation timely while making the syntax unparseable by the intended LR method. Wilhelm, Seidl, and Hack's Boolean-expression counterexample demonstrates that this risk is real.^[1]

Knowledge Transfer¶

The transferable reasoning within compiler construction is the distinction between a semantic dependency graph and the parser event that must satisfy it. In the declaration/use case, an environment is synthesized from declarations and then inherited by later uses. In the expression-type case, an existing environment is copied down the expression structure and results flow back up. Both meet the role map through different attribute flows, while relying on different explicitly identified LR-attribution arguments.^[2]^[1]

One may apply the same diagnostic to another grammar only after checking that grammar's productions, equations, LR states or marker transformation. Similar words such as “inherited,” “bottom-up,” or “one pass” do not transfer a membership proof automatically.

Examples¶

Complete declaration and use checking¶

Sassa and colleagues specify a small language with dcl id; declarations followed by use id; statements.^[2] Their complete grammar G1 forms a declaration list and a statement list.^[2] Its attribute grammar AG1 synthesizes the set of declared names at dclist, gives that set to stlist.env, copies it into st.env, and checks each used name against it.^[2] The report examines LR states and explicitly concludes that AG1 is LR-attributed because each required inherited semantic expression is unique.^[2] A separate local Bison 2.3 check of G1's syntax reports zero LALR(1) conflicts.^[n1]

Mapped back: carrier = G1 plus AG1 equations; parser schedule = LR states for the declaration and use lists; inherited input = one consistent declaration-set expression for each needed env; synthesized result = the declaration set built at reductions (while the context checks run at their stated points); compatibility = Sassa's unique-expression criterion for the complete grammar. These roles permit semantic evaluation during LR parsing.^[2]

Derived expression typechecking subgrammar¶

Wilhelm, Seidl, and Hack's AGtypes assigns inherited env to expression, term, and factor nonterminals and synthesizes typ and ok.^[1] Consider the complete expression subgrammar with E → E aop T | T, T → T mop F | F, and F → (E) | const | var | var().^[1] It is a proper subgrammar of their printed example: E → var = E is removed.^[1] A separate Bison 2.3 LALR(1) check of these exact productions reports zero conflicts.^[n1] All retained right-side env equations are copying; the start expression receives its environment from the caller, and type/validity results can be computed as factors, terms, and expressions reduce.^[1] This is our bounded derivation from the source's equations, not a full-grammar theorem claimed by the authors.

Mapped back: carrier = the proper expression subgrammar plus retained source equations; parser schedule = conflict-free LR reductions in the local syntax check; inherited input = caller-supplied env copied through expression, term, and factor; synthesized result = typ and ok computed from available values at reductions; compatibility = copying-rule transport plus the independently checked LALR(1) syntax of this bounded subgrammar.^[1]^[n1]

Structural Tensions¶

These sources establish a concrete constraint, rather than a universal two-sided tradeoff: inherited attributes let the grammar express contextual dependencies directly, while LR-time evaluation still requires that information to be known at the parser point that needs it. Marker insertion can restore semantic timing while breaking LR(k). The diagnostic is whether the claimed grammar still has both a valid parser schedule and consistent inherited equations after the proposed repair.^[1]

No general theorem here says that more semantic expressiveness always costs parser determinism, or that ECLR optimization always improves a given grammar. Those broader comparisons require their own methods and measurements.

Structural–Framed Character¶

This entry lies toward the structural end of the structural–framed spectrum: productions, equations, and parser-state behavior supply formal tests for membership.^[2]^[1] Its evaluative weight is low; “LR-attributed” identifies a scheduling property, not a judgment that a compiler is good. Human practice chooses the language, semantic checks, notation, and evaluation method, but once those are fixed the stated formal test constrains the answer. Its institutional origin is research in compiler construction rather than a status granted by a standards body or a parser generator's branding. Its vocabulary—“dependency,” “inherited,” “state,” and “one pass”—can travel, but the complete name cannot travel literally without grammar productions and LR parsing. An unseen grammar meeting the same formal condition would be recognized as another instance; calling an unrelated workflow “LR-attributed” would be an imported analogy.

The portable skeleton is a dependency calculation synchronized with an incremental recognizer; its portability beyond compiler theory remains an explicit future-Prime question, not a claim made by this entry. Its character: a formal, low-evaluation-weight, domain-specific class whose membership depends on the chosen LR evaluation construction and its grammar-level proof, while implementation and historical naming remain contingent.

Structural Core vs. Domain Accent¶

The skeletal relation is a dependency computation synchronized with the events of an incremental recognizer. The domain-bound mechanism is specific: a context-free grammar and attribute equations must fit LR parser states, reductions, and any method-specific inherited-value rule.^[2]^[1] This named entry does not clear the Prime bar because replacing grammar symbols, inherited attributes, or LR states with generic task nodes would erase the membership test rather than preserve it. The broad skeleton is marked as a future-Prime question, pending unlike cross-domain cases and a separate admission review; no present Prime parent is inferred from the vocabulary alone.

This entry is a kind of L-Attributed Grammar.

The related L-Attributed Grammar constrains left-to-right attribute dependencies; LR-attribution asks whether those dependencies can be served during an LR parse under a specified method. S-Attributed Grammar covers the synthesized-only boundary when its syntax is LR. ECLR-Attributed Grammar treats inherited attributes by equivalence classes under its own formal definition. Context-Free Grammar supplies productions but not the attribute equations. The L-attributed grammar is the typed parent: every instance under the method-labelled LR-attribution criteria retains its left-to-right dependency rule, while the LR parser schedule adds a stricter membership test. Wilhelm, Seidl, and Hack expressly state that L-attributed grammars properly contain the parser-directed classes they discuss.^[2]^[1]

Relationships to Other Abstractions¶

Current abstraction LR-Attributed Grammar Domain-specific

Parents (1) — outgoing typed relations

LR-Attributed Grammar is a kind of L-Attributed Grammar Domain-specific

LR-attribution retains L-attributed dependencies and adds LR parser-directed evaluability.

Hierarchy paths (2) — routes to 2 parentless roots

LR-Attributed Grammar → is a kind of L-Attributed Grammar → presupposes Context-Free Grammar → is a kind of Formal System → presupposes Formalization → presupposes Representation → presupposes Abstraction

Show alternative path (1)

Neighborhood in Abstraction Space¶

LR-Attributed Grammar sits in a sparse region of the domain-specific corpus (73^rd percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (2769 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-25

Not to Be Confused With¶

An LR parser. A parser for syntax does not automatically schedule all inherited semantic values.
An L-attributed grammar. A left-to-right tree evaluation condition does not alone prove LR parser-directed evaluation.
A source program's use of yacc globals or a named generator. Implementation tactics are not a formal membership proof.
A full printed AGtypes LR theorem. The typechecking positive here is a proper subgrammar derived from that example; the local syntax result is separately documented.^[n1]

Notes¶

[n1] Local reproducibility record: workspace/ds_densification_remaining_queue_2026_10_02/cohort_174/bundles/001_lr_attributed_grammar/LOCAL_BISON_REPRODUCIBILITY_2026_10_23_01.json (SHA-256 8e29dd89a623f039331d3045a881a079e012c9c5dd0445333a6e11a97c5607d9). It pins the exact three .y grammars, Bison 2.3 automaton reports, and their hashes. The full printed AGtypes transcription has one shift/reduce conflict; the proper typechecking subgrammar and complete Sassa G1 syntax have zero. These are syntax checks, not stand-alone proofs of semantic LR attribution. ↩a ↩b ↩c ↩d ↩e ↩f ↩g

References¶

[1] Reinhard Wilhelm, Helmut Seidl, and Sebastian Hack, “Attribute Grammars”, 2011 course draft of chapter 4 of Compiler Design: Syntactic and Semantic Analysis (Saarland University), especially Example 4.2.3 (printed pp. 124–125) and §4.3 / Examples 4.3.7–4.3.8 (printed pp. 140–145). 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 ↩27 ↩28 ↩29 ↩30 ↩31 ↩32

[2] Masataka Sassa, Harushi Ishizuka, Motoki Sawatani, and Ikuo Nakata, Rie: Introduction and User's Manual, University of Tsukuba Technical Report ISE-TR-90-82 (1990), especially G1 and AG1 (printed pp. 3–4), LR-attribution test and proof (printed p. 8), and ECLR/Rie account (printed pp. 9–10). 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

[3] Rieks op den Akker, Bořivoj Melichar, and Jorma Tarhio, “The Hierarchy of LR-Attributed Grammars” (1990). Cited for the existence of multiple formal LR-attribution variants, not for a claim that their criteria coincide. registry ↩a ↩b