L-Attributed Grammar¶
Constrain inherited attributes to parent context and earlier siblings so parse-tree attributes can be evaluated left to right.
Core Idea¶
An L-attributed grammar, more precisely an L-attributed syntax-directed definition, restricts the dependencies of attributes on a parse tree. In a production A → X₁ … Xₙ, an inherited attribute of Xᵢ may use inherited attributes of A and attributes of siblings to the left of Xᵢ, but not values that will only be available from its right siblings. This permits depth-first left-to-right attribute evaluation.[ref-ac4a2d8dc3b5][ref-a4774d9b4aff]
Scope of Application¶
Compilers use the discipline to propagate types, environments, and other semantic values through syntax trees. A declaration list can receive a type computed from an earlier Type node; an expression tail can receive a value computed from a left sibling. S-attributed definitions, which have no inherited attributes, are a special case.[ref-ac4a2d8dc3b5][ref-a4774d9b4aff]
Clarity¶
The property classifies attribute equations, not the strings recognized by a grammar or the suitability of its syntax for LL parsing. An acyclic attribute grammar may still need a later sibling's value before an earlier child can be visited, so it can fail the L test despite being evaluable in some other order.[^ref-a4774d9b4aff]
Manages Complexity¶
The left-to-right restriction gives a local evaluation schedule: compute a child's inherited inputs from parent context and completed left siblings, visit that child, then pass its synthesized outputs onward. It avoids a general dependency solver for definitions that satisfy the restriction. Bottom-up parser implementations may nevertheless need marker rules or other refactoring to expose inherited values at the right time.[^ref-ac4a2d8dc3b5]
Abstract Reasoning¶
For each inherited attribute of Xᵢ, inspect every value its equation reads. If all come from inherited A attributes or earlier siblings, the local restriction passes. If one comes from a right sibling, a single depth-first left-to-right visit cannot provide it as written. Rewriting the equation or changing the evaluation method becomes necessary.[^ref-a4774d9b4aff]
Knowledge Transfer¶
The exact test transfers among attributed parse-tree applications such as type propagation and expression evaluation. It presupposes a context-free grammar's ordered productions and parse-tree children; those alone do not supply the added semantic dependency rule. Its broader analogy is “use only values already available in the chosen order,” but without grammar productions and inherited/synthesized attributes the named abstraction is not literally present.
[^ref-ac4a2d8dc3b5]: Stony Brook University CSE 504, “Syntax-Directed Definitions”, especially slides 4–7 and 19–22. [^ref-a4774d9b4aff]: East Carolina University, “Synthesized and inherited attributes,” §11.4.
Relationships to Other Abstractions¶
Current abstraction L-Attributed Grammar Domain-specific
Parents (1) — more general patterns this builds on
-
L-Attributed Grammar presupposes Context-Free Grammar Domain-specific
L-attributed equations require ordered context-free productions and their parse-tree children.
Hierarchy paths (2) — routes to 2 parentless roots
- L-Attributed Grammar → Context-Free Grammar → Formal System → Formalization → Representation → Abstraction
- L-Attributed Grammar → Context-Free Grammar → Formal System → Formalization → Transformation → Function (Mapping)
Neighborhood in Abstraction Space¶
L-Attributed Grammar sits in a sparse region of the domain-specific corpus (67th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Program Scope & Nesting Disciplines (10 abstractions)
Nearest neighbors
- Fork–Join Model — 0.84
- Mogensen–Scott encoding — 0.84
- Axiom of Dependent Choice — 0.84
- Algebraic Structure — 0.84
- Well-founded set — 0.84
Computed from structural-signature embeddings · 2026-10-08