Only two notes are required; all four are given here (7 marks each).

---

(a) SLR(1) parser

SLR(1) (Simple LR with 1 lookahead symbol) is a bottom-up LR parser whose states are the sets of LR(0) items, and which uses the FOLLOW sets to decide when to reduce.

Construction steps

1. Augment the grammar with $S' \to S$.
2. Build the canonical collection of LR(0) item sets using closure and goto.
3. Fill the ACTION/GOTO table:
   • $A \to \alpha \cdot a\beta$ in $I_i$ and $\mathrm{goto}(I_i, a) = I_j$ gives shift $j$ on terminal $a$.
   • $A \to \alpha \cdot$ in $I_i$ gives reduce $A \to \alpha$ for every terminal in $\mathrm{FOLLOW}(A)$ (this is the SLR rule).
   • $S' \to S \cdot$ gives accept on $.
   • $\mathrm{goto}(I_i, A) = I_j$ gives GOTO entry $j$ for non-terminal $A$.

The grammar is SLR(1) if the table has no conflicts.

Power: SLR(1) is stronger than LR(0) but weaker than LALR(1) and canonical LR(1), because FOLLOW(A) is a coarse lookahead that ignores the context of the item and can cause spurious shift-reduce conflicts. It has the same small number of states as LR(0) and LALR(1).

---

(b) Syntax Directed Definition (SDD)

An SDD is a context-free grammar in which each grammar symbol has attributes and each production has semantic rules that compute the attributes. It specifies the translation (evaluation of expressions, type checking, code generation) tied to the syntax.

Production	Semantic rule
$E \to E_1 + T$	$E.val = E_1.val + T.val$
$T \to F$	$T.val = F.val$
$F \to \text{digit}$	$F.val = \text{digit}.lexval$

• Synthesized attribute: computed from the attributes of the node's children (bottom-up).
• Inherited attribute: computed from the parent and/or siblings (top-down or sideways).
• S-attributed SDD: uses only synthesized attributes (suits bottom-up parsing). L-attributed SDD: each inherited attribute depends only on the parent and the siblings to its left (suits one left-to-right pass).
• The rules are evaluated on the annotated parse tree; the order must respect the dependency graph. An SDD may contain rules with side effects (for example printing or updating the symbol table); an SDD whose rules have no side effects is an attribute grammar. Unlike a syntax-directed translation scheme, an SDD does not fix where actions run; it only states the rules.

---

(c) Peephole optimization

A peephole optimizer examines a small sliding window of target (or intermediate) instructions, the peephole (typically 2-5 instructions), and replaces patterns by shorter or faster equivalents. It may be applied repeatedly because one change can create new opportunities.

Technique	Before	After
Redundant load/store elimination	ST a, R1<br>LD R1, a	ST a, R1
Constant folding	x = 3 + 4	x = 7
Algebraic simplification	x = x + 0, x = x * 1	removed
Strength reduction	x = x * 2	x = x << 1
Use of machine idioms	ADD R1, R1, #1	INC R1
Unreachable code removal	goto L2 followed by instructions with no label	instructions removed
Control-flow optimization	goto L1 ... L1: goto L2	goto L2

Advantages: simple, local, machine-specific gains; limitation: it cannot see beyond the window, so it complements global optimization.

---

(d) Attribute grammar

An attribute grammar is a context-free grammar extended with attributes attached to grammar symbols and semantic (attribute evaluation) rules attached to productions. Formally, it is a CFG together with a set of attributes (partitioned into synthesized and inherited) and rules that define each attribute purely as a function of other attributes, with no side effects. An attribute grammar is thus an SDD without side effects, used to define the static semantics of a language.

Example (type declaration, uses an inherited attribute):

Production	Semantic rule
$D \to T\,L$	$L.in = T.type$
$T \to \text{int}$	$T.type = integer$
$T \to \text{float}$	$T.type = float$
$L \to L_1 , \text{id}$	$L_1.in = L.in;\; \text{addtype}(\text{id}.entry, L.in)$
$L \to \text{id}$	$\text{addtype}(\text{id}.entry, L.in)$

Here $T.type$ is synthesized and $L.in$ is inherited: the type flows from $T$ to every identifier in the list.

Evaluation: build the dependency graph of attribute instances on the parse tree; if it has no cycle, evaluate the attributes in a topological order. Attribute grammars are used for type checking, symbol-table construction and intermediate code generation.