LR-Attributed Grammar¶
An attribute grammar whose semantic values, including any inherited values, can be evaluated during LR parsing under a specified compatible method.
Core Idea¶
An LR-attributed grammar adds semantic attribute equations to a grammar in a way that permits their evaluation while an LR parser recognizes the input.[1][2] A synthesized value can often be computed when the parser reduces a production.[2] An inherited value may be needed earlier, before the parser has recognized the child that needs it.[2] The grammar qualifies only when a specified LR-attribution method can make those values available at the right parser points.[1][2]
This is a kind of L-attributed grammar: its inherited equations follow left-to-right dependencies.[1][2] It adds the stricter requirement that those equations fit LR parser events.[2] Wilhelm, Seidl, and Hack expressly state that L-attributed grammars properly contain the parser-directed classes they discuss.[2]
Scope of Application¶
The literal setting is compiler construction. A declaration checker can carry a set of known names into later statements; an expression checker can carry a type environment into subexpressions.[1][2] Calling either grammar LR-attributed requires its productions and equations, a compatible LR syntax, and an argument for how any inherited inputs arrive in time.[1][2]
The entry describes the formal LR-attributed class. ECLR-attributed grammars have a separate equivalence-class definition, and parser-generator products are implementations rather than formal membership tests.[1]
Clarity¶
LR syntax alone does not settle the semantic question. A parser might recognize the strings yet be unable to select a unique inherited equation before entering a child.[1] Conversely, left-to-right attribute dependencies alone do not guarantee that an LR parser can evaluate them in time.[2] Sassa and colleagues require one consistent expression for each inherited attribute needed in an LR state.[1] Wilhelm, Seidl, and Hack describe copying inherited values and placing empty markers before a child when needed, provided the transformed grammar remains LR(k).[2] These are distinct named methods.[1][2]
Manages Complexity¶
To check a proposed grammar, identify four things: the grammar's LR parse, each inherited input and when it is needed, each synthesized result and its reduction, and the particular rule that makes inherited values available.[1][2] A marker can fix semantic timing but break LR(k), so its transformed syntax must be checked too.[2]
Abstract Reasoning¶
Sassa and colleagues' complete declaration/use grammar first builds a declaration set and then passes it to a later statement list.[1] They show that the possible semantic expressions at the relevant LR states agree, so the inherited env value can be supplied during the parse.[1] The role map is production and equations → LR state → timely inherited environment → synthesized or checked result.
For a different grammar, the same reasoning must be repeated with that grammar's own equations and LR states. Similar names or use of the same parser generator are not substitutes for the check.
Knowledge Transfer¶
The useful idea within compiler theory is to align a semantic dependency with a parser event. An environment may be produced by earlier declarations or supplied by a caller and copied down an expression.[1][2] In both cases, results can flow back on reductions, but the inherited-value argument differs.[1][2] The formal LR-attributed label does not transfer to an unrelated workflow merely because it also processes information in one pass.
Examples¶
Complete declaration and use checking. In Sassa and colleagues' AG1, declarations synthesize a set of names.[1] The statement list inherits that set and checks later uses.[1] The authors give both the complete grammar and an LR-state uniqueness proof.[1] A separate local Bison 2.3 check finds no LALR(1) syntax conflicts; that local result is only a syntax check.[n1]
Bounded expression typechecking. Wilhelm, Seidl, and Hack's AGtypes passes env into expressions, terms, and factors while synthesizing type and validity results.[2] A proper expression subgrammar that omits their assignment alternative retains copying env equations and has no LALR(1) syntax conflicts in our local check.[2][n1] This is our derived subgrammar, not a claim that the complete printed AGtypes grammar is LR.
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
- LR-Attributed Grammar → is a kind of L-Attributed Grammar → presupposes Context-Free Grammar → is a kind of Formal System → presupposes Formalization → is a decomposition of Transformation → is a kind of, typical Function (Mapping)
Neighborhood in Abstraction Space¶
LR-Attributed Grammar sits in a sparse region of the domain-specific corpus (73rd percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Unclustered & Miscellaneous (2769 abstractions)
Nearest neighbors
- ECLR-Attributed Grammar — 0.89
- S-attributed grammar — 0.86
- L-Attributed Grammar — 0.83
- Abstract Syntax Tree — 0.82
- Generalized context-free grammar — 0.82
Computed from structural-signature embeddings · 2026-10-25
Not to Be Confused With¶
An S-attributed grammar has only synthesized attributes; it can be evaluated at reductions when its syntax is LR, but it does not cover the inherited-input challenge.[2] An ECLR-attributed grammar groups inherited attributes into equivalence classes under Sassa's separate definition; the report says that ECLR is not smaller than its LR-AG class, so a universal strict subclass claim would be unwarranted.[1] A named parser generator or a program's global-variable tactic does not establish formal membership.
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). The full printed AGtypes transcription has one shift/reduce conflict; the proper typechecking subgrammar and Sassa G1 syntax have zero. These syntax checks alone do not prove semantic LR attribution. ↩a ↩b
References¶
[1] 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 proof (printed p. 8), and ECLR account (printed p. 9). registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o ↩p ↩q ↩r
[2] 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