Short Notes on Two Topics in Compiler Design: SLR(1) Parser and Attribute Grammar

This section provides two concise, exam-ready short notes—(a) SLR(1) parser and (d) Attribute grammar—and also includes the key ideas, construction steps, and common pitfalls.

In compiler design, parsers determine whether an input string conforms to a grammar, while syntax-directed definitions / attribute grammars attach semantic meaning (e.g., types, values) to parse-tree nodes.

Key terms

• LR(0) items
• FOLLOW sets
• ACTION/GOTO tables
• Synthesized attributes
• Inherited attributes

Note: Because your question asks for “any two of the following” items, the course focuses on (a) SLR(1) parser and (d) Attribute grammar.

(a) SLR(1) Parser — Short Note

Idea

An SLR(1) parser is an LR-family shift–reduce parser that uses:

1. LR(0) items to build the LR automaton states, and
2. FOLLOW sets to decide when to reduce.

It is called “Simple LR(1)” because it approximates LR(1) lookaheads using FOLLOW sets instead of exact context-sensitive lookaheads.

Core construction (what appears in the parsing tables)

• For each state $i$:
  • If an item has a dot before a terminal $a$, then ACTION[i,a] = shift j.
  • If an item corresponds to a production completed with dot at the end (e.g., $A \to \alpha \cdot$), then ACTION[i,a] = reduce $A \to \alpha$ for all terminals $a$ in FOLLOW(A).
  • For completed start production (augmented grammar), ACTION[i,$$$] = accept.
• GOTO transitions come from nonterminal moves.

Why FOLLOW-based reduction works (intuitively)

FOLLOW(A) captures the terminals that can legally follow $A$ in some sentential form. Since SLR(1) uses that as the lookahead set, it often reduces correctly—but may introduce conflicts that would be avoided by full LR(1).

What conflicts mean

If the parsing table construction yields:

• Shift/Reduce conflict: the parser cannot decide between shifting and reducing.
• Reduce/Reduce conflict: two different reductions are possible for the same lookahead.

These conflicts indicate that the grammar is not SLR(1) (though it might still be LR(1) or LALR(1)).

Mini-example sketch (typical exam framing)

• Build LR(0) item sets (states).
• For a state containing $A \to \alpha \cdot$:
  • Reduce $A \to \alpha$ on lookaheads in FOLLOW(A).
• Put accept on $$$ when the augmented start production is complete.

Mermaid: shift/reduce in one view

(d) Attribute Grammar — Short Note

What it is

An attribute grammar extends a context-free grammar by assigning:

• attributes to each grammar symbol occurrence in a parse tree, and
• semantic rules to compute attribute values.

These rules are evaluated during or after parsing to compute program properties such as:

• types,
• constant values,
• intermediate code generation information, etc.

Attribute types

• Synthesized attributes: typically evaluated bottom-up.
• Inherited attributes: require top-down or multi-pass evaluation.

Semantic rules and dependencies

A production like:

$$A \to X_1 X_2 \dots X_n$$

has semantic rules that specify how to compute attributes of $A$ and/or of $X_i$’s based on other attributes.

Evaluation must respect dependency order: if attribute $b$ depends on $c$, then $c$ must be computed first.

Example shape (exam-friendly)

• Suppose $E \to E_1 + T$.
• A synthesized attribute like $\text{val}(E)$ may be computed as:
  • $\text{val}(E) = \text{val}(E_1) + \text{val}(T)$

For inherited attributes, you might pass a context (e.g., expected type) from parent to child:

• $\text{type}(T) = \text{type}(E)$ (pattern depends on language specification)

Relation to syntax-directed definition (SDD)

An attribute grammar is a general framework; SDD is essentially a practical form where semantic rules are attached to grammar productions using attributes.

Visualizing Attribute Dependencies

A dependency graph helps confirm evaluation order.

• For synthesized attributes, dependencies usually point upward (children → parent).
• For inherited attributes, dependencies can point downward (parent → child).