ECLR-Attributed Grammar

An L-attributed grammar paired with a partition of inherited attributes whose members have the same unique semantic expression in each relevant LR parser state.

Version

v3 · 2026-10-25 · History

Domain-specific #

4301

Domain group

Applied Sciences & Engineering

Origin domain

Computer Science & Software Engineering

Subdomains

Compiler Construction, Attribute Grammars → Computer Science & Software Engineering

Aliases

Equivalence-class LR-attributed grammar

Core Idea

An ECLR-attributed grammar is an L-attributed grammar considered with a partition of its inherited attributes.^[1][2] In every LR parser state, the inherited attributes of one class that are needed there must all have the same unique semantic expression: one symbolic way to compute their value from attributes available in that state.^[1][2] The evaluator may then compute and store one value for that class at the relevant parser point instead of one value per inherited attribute.^[1] The class is relative to a specified partition, not to syntax or a product name alone.^[1]

How would you explain it like I'm…

Grouping Look-Alike Notes

When a computer reads a program, it uses a rulebook and reads from start to end only once. As it reads, it passes little notes down from bigger parts to smaller parts. An ECLR-attributed grammar sorts those notes into groups that behave the same way, so the computer can handle each group in one go. It is only allowed if the grouping never changes what the notes mean or when they get used.

One-Pass Grouped Grammar

Programs that read code, called parsers, use a grammar: rules saying how pieces of code fit together. Some grammars also attach extra information to each piece. Some of that information is 'inherited,' meaning it is handed down from the surrounding piece to the pieces inside it. An ECLR-attributed grammar sorts these handed-down pieces of information into matching groups, so the parser can share work instead of repeating it. This still has to work in a single left-to-right reading pass, and the grouping must never change the answers.

Equivalence-Classed LR Attributes

An attribute grammar attaches values, called attributes, to grammar symbols, along with equations for computing them. Inherited attributes flow downward from a parent or from left siblings. LR-attributed grammars restrict those dependencies so the values can be computed during a single bottom-up LR parse. An ECLR-attributed grammar adds an equivalence relation that groups inherited-attribute occurrences with compatible evaluation behavior. The parser generator can then merge or precompute their handling instead of repeating it. It only counts as ECLR if the grouping changes no semantic equation and no evaluation order, so it is a safe optimization, not just a relabeling.

 

An ECLR-attributed grammar is a variant of an LR-attributed grammar. It targets practical one-pass attribute evaluation during LR parsing. Its defining extra structure is an equivalence relation that partitions inherited-attribute occurrences into classes. Occurrences in the same class have compatible evaluation behavior, so the parser generator can share or precompute their handling instead of duplicating it per occurrence. Two conditions are constitutive. First, the grammar must satisfy the ECLR dependency restrictions, which keep attribute dependencies compatible with LR parsing. Second, the declared classes must preserve every semantic equation and evaluation order the generated parser relies on. If either condition fails, you have some other grammar class, not an ECLR one. The key idea is equivalence-class optimization of inherited attributes, not compiler construction in general.

Scope of Application

The definition applies to compiler construction when productions, attribute equations, LR states, and a proposed partition can all be examined.^[1] IN(I) contains inherited attributes of nonterminals immediately after the dot in LR items of state I; each class is tested on its intersection with that set.^[1] Equal values on a few inputs do not establish equal symbolic expressions in all relevant states.

Clarity

EC refers to equivalence classes of inherited attributes, and LR to the parsing states in which those values are needed.^[1] Sassa's criterion requires both L-attributedness and a common singleton semantic-expression set for every relevant class/state combination.^[1] A singleton partition reduces this to his LR-attributed uniqueness criterion.^[1] Thus his ECLR class is not smaller than his LR-attributed class; the ECLR label should not be described as a universally strict LR subclass.^[1]

Manages Complexity

The partition groups attributes only after a statewise proof establishes that their needed calculations agree.^[1] A larger class may permit shared storage, while a class that combines different expressions invalidates the proposed classification.^[1] Sassa reports particular storage and runtime improvements for implementations he studied; the definition itself promises no fixed improvement for every grammar.^[1]

Abstract Reasoning

Given a grammar and its equations, check the L-attributed dependency rule.^[1] Build the chosen LR state structure and find each IN(I).^[1] Derive the possible semantic expressions for every inherited attribute needed in a state.^[1] Within each proposed class, all such expressions must coincide and each set must contain just one expression.^[1] If an attribute has two expressions in one state, even a singleton class cannot rescue it.^[1]

Knowledge Transfer

The proof method transfers between grammars with different inherited meanings.^[1][2] A declaration environment in one grammar and parenthesis depth in another both qualify only when class members share one statewise expression.^[1][2] Their actual semantic equations do not transfer from one case to the other.^[1][2]

Examples

Declaration environment. In the complete AG1 of Sassa and colleagues' 1990 Rie manual, stlist.env and st.env both resolve in a displayed LR state to {dclist₁,₂.env}.^[1] The report groups them into one class and states that the same condition holds in the other relevant states.^[1] The role map is grammar plus environment equations → LR-state demand for two inherited environments → shared singleton expression → one classwise environment value.

Parenthesis depth. Sassa's separate 1988 expression AG1 has seven productions.^[2] They include E → E + T | T, T → T * F | F, and F → ( E ) | i.^[2] Its inherited lev counts enclosing parentheses; the parenthesis production increments it.^[2] The partition EC1 = {E.lev, T.lev, F.lev} has the common singleton {0} in the initial state and a common expression from a prior class value plus one in the displayed state after an open parenthesis.^[2] The role map is expression grammar plus depth equations → LR-state demand for E/T/F levels → EC1 → one statewise level value.

Failure. An altered equation in the 1990 declaration grammar creates two distinct semantic expressions for one inherited attribute in a state.^[1] It fails the uniqueness requirement whatever partition is chosen.^[1]

Structural Core vs. Domain Accent

The broad pattern is grouping demands that share a computation. ECLR's literal identity requires inherited attributes, LR parser states, and a common singleton symbolic expression; outside that typed setting the phrase is only an analogy. The typed parent is L-attributed grammar, whose dependency rule is necessary but does not by itself establish ECLR's statewise condition. Equivalence Relation is a mathematical component, not the strict superclass of the whole grammar pair.^[1]

Relationships to Other Abstractions

Current abstraction ECLR-Attributed Grammar Domain-specific

Parents (1) — outgoing typed relations

• ECLR-Attributed Grammar is a kind of L-Attributed Grammar Domain-specific

  ECLR's formal definition requires L-attributedness and adds statewise equal, unique expressions for a partition of inherited attributes.

Hierarchy paths (2) — routes to 2 parentless roots

• ECLR-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

ECLR-Attributed Grammar sits in a crowded region of the domain-specific corpus (26^th percentile for distinctiveness): several abstractions share nearly its structure, so a description that fits it tends to fit its neighbors too.

Family — Formal Grammars & String Rewriting (21 abstractions)

Nearest neighbors

• S-attributed grammar — 0.92
• Context-sensitive grammar — 0.89
• Generalized context-free grammar — 0.89
• LR-Attributed Grammar — 0.89
• Deterministic context-free grammar — 0.89

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

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 AG1 (printed pp. 3–4), LR criterion and counterexample (printed p. 8), and ECLR definition and evaluator (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 ↩z

[2] Masataka Sassa, Incremental Attribute Evaluation and Parsing Based on ECLR-attributed Grammars, University of Tsukuba Technical Report ISE-TR-88-66 (1988), especially expression AG1 (printed p. 12), EC1 and LR-state expression calculations (printed pp. 13–16), and the ECLR definition (printed p. 16). registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i