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 (equivalence-class LR-attributed grammar) is an attribute grammar considered together with a partition of its inherited attributes.^[1][2] In the formulation of Sassa and colleagues, the grammar must first be L-attributed.^[1][2] At each LR parser state, the inherited attributes from any one partition class that are needed there must all have the same unique semantic expression.^[1] A semantic expression is the symbolic calculation from the state's kernel items that would supply an inherited value; uniqueness means that the parser state does not leave competing calculations for it.^[1]

The partition is constitutive: class membership is relative to a specified partition, not a label attached to syntax alone.^[1] The shared expression lets an evaluator compute and store one inherited value for a class at a relevant parser point, rather than separate copies for each inherited attribute.^[1] That implementation possibility is distinct from an unconditional speedup claim; the report's measured savings concern its studied implementation.^[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.

Structural Signature

Role map: productions and attribute equations → an LR state with inherited attributes about to be needed → a proposed partition class → a common singleton semantic expression → one classwise value usable by the evaluator.

• Carrier: an L-attributed grammar, an LR item-state structure for its syntax, and a disjoint partition EC of all its inherited attributes.^[1]
• State demand: IN(I) is the set of inherited attributes of nonterminals immediately after the dot in LR items of state I.^[1]
• Expression test: for every class C and state I, each member of C ∩ IN(I) has the same semantic-expression set, and that set contains exactly one expression.^[1] Empty intersections impose no classwise equality obligation at that state under this quantified definition.^[1]
• Consequence: the evaluator can treat these simultaneously demanded inherited attributes as one classwise evaluation and storage unit at that state.^[1]
• Failure boundary: a non-L-attributed grammar, a state with a nonunique expression, or two class members with different expressions at the same relevant state fails the proposed classification.^[1]

The expression test is symbolic and state-dependent. Two attributes having the same value on one example input is not enough; the parser must have the same unique expression at every state in which both belong to the demand set.^[1][2]

What It Is Not

An LR-attributed grammar under Sassa's criterion requires one unique expression for each demanded inherited attribute in every LR state.^[1] The singleton partition recovers that criterion, so the ECLR class is not smaller than Sassa's LR-attributed class.^[1] This does not establish a universal strict subclass or equality relationship across every published variant of LR attribution.

An equivalence relation is also insufficient by itself. The ECLR object is a grammar with semantic equations, LR states, and an admissible partition; many equivalence relations have nothing to do with that typed carrier. An equivalence relation organizes the partition, but it is not a superclass of the grammar pair.^[1]

Rie is a compiler generator that accepts ECLR-style specifications.^[1] A product name or yacc-like syntax does not establish that any particular grammar meets the statewise expression test.

Scope of Application

This class is useful when a compiler generator evaluates inherited attributes while parsing and wants to combine attributes with a common statewise calculation.^[1][2] It applies to a fully specified grammar, attribute equations, parser-state construction, and partition.^[1] Sassa's manual uses declaration environments and its earlier report uses the depth of nested parentheses; those are different semantic meanings sharing the same classwise criterion.^[1][2]

The report's partition is assumed given for its definition.^[1][2] Finding an admissible or optimal partition is a separate construction problem.^[1][2] An implementation may allocate per-class stack fields, but membership should be tested before inferring storage or runtime effects.^[1]

Clarity

The EC denotes an equivalence class of inherited attributes.^[1] The LR denotes the parser schedule in which those attributes must be available.^[1] In state I, compute the possible symbolic expressions for every attribute in IN(I).^[1] Then compare the expressions of attributes placed together in each class. One common singleton permits a classwise action.^[1] A differing expression or a set with two alternatives defeats that action under this criterion.^[1]

This explains why the same observed value is a weak shortcut. A zero environment and a copied environment might coincide on a small test, but their expressions differ and cannot be merged on that evidence. Conversely, two different grammar-symbol attributes may have distinct names while carrying the same symbolic expression in every state where both are demanded.

Manages Complexity

A parser state can represent several possible derivations, each suggesting a source for an inherited value.^[1] ECLR reduces the evaluator's bookkeeping only after those paths collapse to one expression for each member of a class.^[1] The partition then compresses multiple attribute slots into a class slot.^[1]

The compression has a formal cost: every class must be checked across the relevant states. Combining attributes too aggressively can invalidate the grammar-class claim even if it appears to save space. The reports describe concrete evaluator layouts, but they do not warrant a universal performance ratio for all ECLR grammars.^[1][2]

Abstract Reasoning

To classify a proposed instance, first check the usual L-attributed dependency restriction.^[1] Enumerate LR states for the chosen syntax and calculate IN(I) from the items.^[1] For every inherited attribute demanded there, derive its possible semantic expressions from kernel attributes.^[1] Choose a partition and compare those expression sets within each C ∩ IN(I). Membership requires the same singleton for every comparison.^[1]

A singleton partition is a useful control: it removes cross-attribute equality but leaves each attribute's uniqueness obligation.^[1] If that control fails, merging names into larger classes cannot repair the nonuniqueness.^[1] If it succeeds, larger admissible classes may permit shared evaluation and storage.^[1]

Knowledge Transfer

The declaration-set case and the parenthesis-depth case transfer a method of proof, not each other's semantic equations. Both require an LR state, a set of inherited demands, and a common singleton expression for members of one class.^[1][2] The first carries an environment through statement-list roles; the second carries an integer depth through expression, term, and factor roles.^[1][2]

Outside attribute-grammar evaluation, grouping similar values may be a useful analogy, but it does not transfer ECLR membership. Grammar productions, attribute equations, and LR states are necessary to run its formal test.

Examples

Declaration environment in AG1

Sassa and colleagues' complete AG1 has declaration-list and statement-list productions.^[1] A declaration list synthesizes an environment; the following statement list and statements inherit it to check uses of identifiers.^[1] The report groups stlist.env and st.env into one class.^[1] In its displayed LR state I1, both semantic expressions reduce to the singleton {dclist₁,₂.env}; the authors state that the corresponding condition holds in the other states.^[1] Rie's evaluator can therefore assign a classwise inherited value at such a state.^[1]

Mapped back: carrier = complete AG1 plus its equations; inherited demand = statement-list and statement environments in LR states; partition = {stlist.env, st.env}; invariant = one common singleton expression in every relevant state; consequence = one classwise environment value. Merely noticing that the two names often denote the same set would not prove the invariant.

Parenthesis depth in a separate AG1

Sassa's 1988 report gives a different complete expression grammar: E → E + T | T, T → T * F | F, and F → ( E ) | i, with an augmented start.^[2] Its inherited lev gives the number of enclosing parentheses.^[2] The start supplies zero, productions otherwise copy the level, and F → ( E ) sends F.lev + 1 to the enclosed expression.^[2]

The partition EC1 = {E.lev, T.lev, F.lev} is the report's class.^[2] At initial state I0, the three demanded expressions are all the singleton {0}.^[2] In its displayed state I4, they have the same singleton expression formed from a prior class value plus one; the report checks the remaining states in its formal example.^[2] This case is not a renamed declaration environment: the inherited value is a numeric nesting depth, and the parenthesis production creates the increment.^[2]

Mapped back: carrier = seven-production expression AG1 plus lev equations; inherited demand = E, T, and F levels before their parser work; partition = EC1; invariant = same unique expression per state; consequence = one level value for the class at a relevant parser point.^[2]

Counterexample: nonunique state expression

The 1990 report alters one inherited equation in the declaration grammar so that an LR state admits both a direct environment expression and one with an added {nil}.^[1] The resulting expression set has two alternatives.^[1] No choice of partition can make that individual attribute's expression unique; the example fails ECLR under the report's criterion even if every inherited attribute is placed in its own class.^[1]

Structural Tensions

Larger equivalence classes may reduce duplicated inherited storage, but they create more equality obligations across LR states. Singleton classes avoid those cross-attribute obligations while giving up the same sharing opportunity.^[1][2] Both pressures matter when choosing a partition: a merge can save fields only if every newly grouped demand still has the same singleton expression. Diagnostic: If merging two classes creates a state where their demanded expressions differ, keep the classes separate; if all relevant state comparisons remain common singletons, the merge preserves ECLR membership and may permit sharing. The reports illustrate optimization in particular systems; the formal class definition does not promise a fixed speed or memory saving.^[1][2]

Structural–Framed Character

ECLR lies toward the structural end of the structural–framed spectrum: grammar productions, a specified partition, and LR-state expressions determine membership.^[1][2] Its evaluative weight is low; the label does not judge a compiler's quality or promise speed. Human practice chooses the grammar, semantic equations, LR construction, and partition, but the chosen objects must pass the formal comparison. Its institutional origin is compiler research and the Rie generator, rather than a status conferred by an institution; Rie adoption does not define the class.^[1] A new grammar meeting the criterion would be recognized as another instance, whereas calling an unrelated program with grouped values “ECLR-attributed” would be an imported analogy. Its character: a formal, domain-specific, low-evaluation-weight grammar class relative to a partition, with human design choices bounded by statewise proof.

Structural Core vs. Domain Accent

The portable skeleton is “group demands that share one computation.” Whether that pattern survives across genuinely different domains is a possible cross-domain abstraction requiring unlike cases and separate admission review; this entry does not assign it to an accepted Prime. The ECLR identity is more exact: it requires inherited attributes of an L-attributed grammar, an LR-state demand set, and common singleton symbolic expressions.^[1] Removing those typed elements turns the name into a metaphor rather than a literal ECLR instance. The partition is a component, not a reason to place the whole grammar below the Prime Equivalence Relation.

Instantiates / Related Primes

This entry is a kind of L-Attributed Grammar.

The typed parent is L-Attributed Grammar, because L-attributedness is an explicit condition of the ECLR definition and does not itself ensure the statewise expression condition. LR-Attributed Grammar is a close formal neighbor; the singleton partition recovers Sassa's LR criterion, so it is not asserted as a strict superclass of ECLR. Equivalence Relation names the mathematical structure behind a partition, but is not a typed superclass of the 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

Not to Be Confused With

• Any L-attributed grammar: left-to-right dependencies alone do not establish a common singleton expression in LR states.
• An LR-attributed grammar under every published definition: Sassa's singleton case establishes only a relationship within his stated formalism; other LR-attribution constructions use different tests.
• Rie or a yacc-like generator: these are implementation contexts, not membership evidence for a particular input grammar.
• A partition formed from equal sample outputs: the criterion compares symbolic expressions across relevant states, not observations from a few inputs.

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-state uniqueness and counterexample (printed p. 8), ECLR definition and AG1 equivalence class (printed p. 9), and evaluator implementation and Rie description (printed pp. 9–11). 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 ↩33 ↩34 ↩35 ↩36 ↩37 ↩38 ↩39 ↩40 ↩41 ↩42 ↩43 ↩44 ↩45 ↩46 ↩47 ↩48 ↩49 ↩50 ↩51 ↩52 ↩53 ↩54 ↩55 ↩56

[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 state-expression calculations (printed pp. 13–16), and formal ECLR definition (printed p. 16). registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o ↩p ↩q ↩r ↩s ↩t ↩u