How unit 2 is examined
This unit covers parsing (top-down, then bottom-up) and syntax directed translation; the SLR table for the LR(0) grammar carries the most marks (14), then recursive descent and top-down parsing types, then L-attributed definitions.
Syntax analysis: CFGs, top down parsing, brute force, recursive descent
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>
Definition. <mark>Parsing (syntax analysis) is the phase that checks whether the token string produced by the lexical analyser can be derived from the start symbol of a context-free grammar, and builds a parse tree if it can.</mark> A CFG has four parts: terminals, non-terminals, productions $A \to \alpha$ and a start symbol. Top-down parsing builds the parse tree from the root (start symbol) towards the leaves, using a leftmost derivation.
Key points.
- Top-down parsing starts with the start symbol and repeatedly expands the leftmost non-terminal until the input string is matched.
- Brute force (backtracking) parsing tries the alternatives of a production in order and, if a choice fails to match the input, undoes it and tries the next one.
- Recursive descent parsing writes one procedure per non-terminal; each procedure matches terminals of its production body and calls the procedures of the non-terminals in it.
- Predictive parsing (LL(1)) needs no backtracking: it chooses the production from one lookahead symbol using a table built with FIRST and FOLLOW sets.
- Left recursion makes a top-down parser loop forever, and common prefixes force backtracking, so the grammar must be transformed first.
- Backtracking is slow (possibly exponential) and delays error reports, which is why it is a limitation.
Example. Grammar $E \to T + E \mid T$, $T \to id$; input id + id.
void E() { T(); if (tok == '+') { match('+'); E(); } } // E -> T + E | T
void T() { if (tok == ID) match(ID); else error(); } // T -> id
Trace: E calls T (matches id), sees +, matches it, calls E, which calls T (matches id), no more +, returns. Input is accepted when tok == $ at the end.
Answer frame. For the 6-mark question, open with the definition of parsing, draw the root-to-leaf tree idea, then explain backtracking, recursive descent and predictive LL(1) (FIRST/FOLLOW) in that order; close by noting the LL(1) needs an unambiguous, non-left-recursive grammar. For recursive descent, open with "one procedure per non-terminal", write the code above, show the call trace and the parse tree, and close with backtracking and left recursion as limitations.
Pitfall: Writing recursive descent for a left-recursive rule such as $E \to E + T$ gives infinite recursion; remove the left recursion first.
Asked: [6 marks] (May 2024) Define parsing. Explain types of Top down parsing. Asked: [8 marks] (May 2024) Explain Recursive Descent parsing method with example.
Grammar transformation, predictive parsing, bottom up parsing
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>
Definition. Grammar transformation rewrites a grammar into an equivalent one that a top-down parser can use, by removing left recursion and left factoring.
Key points.
- Left recursion $A \to A\alpha \mid \beta$ is removed as $A \to \beta A'$, $A' \to \alpha A' \mid \epsilon$.
- Left factoring rewrites $A \to \alpha\beta_1 \mid \alpha\beta_2$ as $A \to \alpha A'$, $A' \to \beta_1 \mid \beta_2$, so the parser need not guess.
- A predictive parser uses a stack and a table $M[A, a]$ filled from FIRST and FOLLOW; the grammar must be LL(1).
- Bottom-up parsing builds the tree from the leaves to the root by shift and reduce actions, tracing a rightmost derivation in reverse.
Operator precedence, LR parsers (SLR, LALR, LR), parser generation
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>
Definition. <mark>An LR(k) parser scans the input left to right, produces a rightmost derivation in reverse, and uses k lookahead symbols; it is a shift-reduce parser driven by a DFA of LR(0) items.</mark> An LR(0) item is a production with a dot marking how much of the body has been seen, for example $L \to *\cdot R$.
Key points.
- Augment the grammar with $S' \to S$ so that acceptance is signalled when $S' \to S\cdot$ is reached.
- $closure(I)$ adds $B \to \cdot\gamma$ for every item $A \to \alpha \cdot B\beta$ in $I$; $goto(I, X)$ moves the dot over X and takes the closure.
- In SLR, reduce $A \to \alpha$ in state i only on symbols in FOLLOW(A); shift on terminals after the dot; goto for non-terminals.
- LALR merges LR(1) states that have the same core, so it has SLR-sized tables but is more powerful; canonical LR(1) is the most powerful and has the biggest tables.
- Operator precedence parsing works on operator grammars (no $\epsilon$, no two adjacent non-terminals) using precedence relations $\lessdot$, $\doteq$, $\gtrdot$ between terminals.
- Parser generators such as YACC/Bison build LALR tables from a grammar automatically.
Example (May 2024). Grammar: (1) $S \to L=R$, (2) $S \to R$, (3) $L \to *R$, (4) $L \to id$, (5) $R \to L$; augmented with (0) $S' \to S$.
| State | Items | Transitions |
|---|---|---|
| I0 | $S'\to\cdot S$, $S\to\cdot L=R$, $S\to\cdot R$, $L\to\cdot *R$, $L\to\cdot id$, $R\to\cdot L$ | S:I1, L:I2, R:I3, *:I4, id:I5 |
| I1 | $S'\to S\cdot$ | accept |
| I2 | $S\to L\cdot =R$, $R\to L\cdot$ | =:I6 |
| I3 | $S\to R\cdot$ | |
| I4 | $L\to *\cdot R$, $R\to\cdot L$, $L\to\cdot *R$, $L\to\cdot id$ | R:I8, L:I7, *:I4, id:I5 |
| I5 | $L\to id\cdot$ | |
| I6 | $S\to L=\cdot R$, $R\to\cdot L$, $L\to\cdot *R$, $L\to\cdot id$ | R:I9, L:I7, *:I4, id:I5 |
| I7 | $R\to L\cdot$ | |
| I8 | $L\to *R\cdot$ | |
| I9 | $S\to L=R\cdot$ |
<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u2-01" viewBox="0 0 467 424" width="467" height="424" role="img" aria-label="LR(0) DFA. I0 also goes on id to I5; I4 and I6 go on * back to I4 and on id to I5."><style>#dsfig-u2-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u2-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u2-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u2-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u2-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u2-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u2-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u2-01 .t{fill:#16181D;font-weight:500}#dsfig-u2-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u2-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u2-01 .dot{fill:#16181D}#dsfig-u2-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u2-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u2-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u2-01 .ah{fill:#454C5A}#dsfig-u2-01 .ah.hi{fill:#2340B8}#dsfig-u2-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u2-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u2-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u2-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u2-01 .e{stroke:#B1B7C3}html.dark #dsfig-u2-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u2-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u2-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u2-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u2-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u2-01 .t{fill:#E6E8ED}html.dark #dsfig-u2-01 .t.inv{fill:#0F1115}html.dark #dsfig-u2-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u2-01 .dot{fill:#E6E8ED}html.dark #dsfig-u2-01 .ann{fill:#8FA3FF}html.dark #dsfig-u2-01 .lbl{fill:#858D9C}html.dark #dsfig-u2-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u2-01 .ah{fill:#B1B7C3}html.dark #dsfig-u2-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u2-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u2-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u2-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah4" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh4" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M51.4,196.8 L156.4,56.8" marker-end="url(#ah4)"/><path class="e" d="M57.2,204 L150,160.7" marker-end="url(#ah4)"/><path class="e" d="M57.6,219.1 L149.5,255.8" marker-end="url(#ah4)"/><path class="e" d="M51.4,227.2 L156.4,367.2" marker-end="url(#ah4)"/><path class="e" d="M188,151.8 L277,151.8" marker-end="url(#ah4)"/><path class="e" d="M188,384 L277,384" marker-end="url(#ah4)"/><path class="e" d="M186.2,376 L408,272.5" marker-end="url(#ah4)"/><path class="e" d="M188,384 L406,384" marker-end="url(#ah4)"/><path class="e" d="M312.4,139.4 L411.1,53.8" marker-end="url(#ah4)"/><path class="e" d="M312.4,164.2 L411.1,249.8" marker-end="url(#ah4)"/><g class="wl"><rect x="94.9" y="117" width="19.2" height="18" rx="9"/><text class="t" x="104.5" y="126" dy=".35em" text-anchor="middle">S</text></g><g class="wl"><rect x="94.9" y="172.9" width="19.2" height="18" rx="9"/><text class="t" x="104.5" y="181.9" dy=".35em" text-anchor="middle">L</text></g><g class="wl"><rect x="94.9" y="228.8" width="19.2" height="18" rx="9"/><text class="t" x="104.5" y="237.8" dy=".35em" text-anchor="middle">R</text></g><g class="wl"><rect x="94.9" y="289" width="19.2" height="18" rx="9"/><text class="t" x="104.5" y="298" dy=".35em" text-anchor="middle">*</text></g><g class="wl"><rect x="223.9" y="142.8" width="19.2" height="18" rx="9"/><text class="t" x="233.5" y="151.8" dy=".35em" text-anchor="middle">=</text></g><g class="wl"><rect x="220.3" y="375" width="26.4" height="18" rx="9"/><text class="t" x="233.5" y="384" dy=".35em" text-anchor="middle">id</text></g><g class="wl"><rect x="288.4" y="314.8" width="19.2" height="18" rx="9"/><text class="t" x="298" y="323.8" dy=".35em" text-anchor="middle">L</text></g><g class="wl"><rect x="288.4" y="375" width="19.2" height="18" rx="9"/><text class="t" x="298" y="384" dy=".35em" text-anchor="middle">R</text></g><g class="wl"><rect x="352.9" y="86.9" width="19.2" height="18" rx="9"/><text class="t" x="362.5" y="95.9" dy=".35em" text-anchor="middle">R</text></g><g class="wl"><rect x="352.9" y="198.7" width="19.2" height="18" rx="9"/><text class="t" x="362.5" y="207.7" dy=".35em" text-anchor="middle">L</text></g><circle class="n" cx="40" cy="212" r="18"/><text class="t" x="40" y="212" dy=".35em" text-anchor="middle">I0</text><circle class="n" cx="169" cy="40" r="18"/><text class="t" x="169" y="40" dy=".35em" text-anchor="middle">I1</text><circle class="n" cx="169" cy="151.8" r="18"/><text class="t" x="169" y="151.8" dy=".35em" text-anchor="middle">I2</text><circle class="n" cx="169" cy="263.6" r="18"/><text class="t" x="169" y="263.6" dy=".35em" text-anchor="middle">I3</text><circle class="n" cx="169" cy="384" r="18"/><text class="t" x="169" y="384" dy=".35em" text-anchor="middle">I4</text><circle class="n" cx="298" cy="384" r="18"/><text class="t" x="298" y="384" dy=".35em" text-anchor="middle">I5</text><circle class="n" cx="298" cy="151.8" r="18"/><text class="t" x="298" y="151.8" dy=".35em" text-anchor="middle">I6</text><circle class="n" cx="427" cy="263.6" r="18"/><text class="t" x="427" y="263.6" dy=".35em" text-anchor="middle">I7</text><circle class="n" cx="427" cy="384" r="18"/><text class="t" x="427" y="384" dy=".35em" text-anchor="middle">I8</text><circle class="n" cx="427" cy="40" r="18"/><text class="t" x="427" y="40" dy=".35em" text-anchor="middle">I9</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">LR(0) DFA. I0 also goes on id to I5; I4 and I6 go on * back to I4 and on id to I5.</figcaption></figure>
FOLLOW: $FOLLOW(S)=\{\$}$, $FOLLOW(L)=\{=,\$}$, $FOLLOW(R)=\{=,\$}$ (from $S \to L=R$ and $R \to L$).
| State | id | * | = | $ | S | L | R |
|---|---|---|---|---|---|---|---|
| 0 | s5 | s4 | 1 | 2 | 3 | ||
| 1 | acc | ||||||
| 2 | s6 / r5 | r5 | |||||
| 3 | r2 | ||||||
| 4 | s5 | s4 | 7 | 8 | |||
| 5 | r4 | r4 | |||||
| 6 | s5 | s4 | 7 | 9 | |||
| 7 | r5 | r5 | |||||
| 8 | r3 | r3 | |||||
| 9 | r1 |
The grammar is not SLR(1): state 2 has a shift-reduce conflict on =, since $=\in FOLLOW(R)$ allows reduce $R \to L$ while $S \to L\cdot =R$ shifts. It is LR(1)/LALR(1), where the reduce lookahead is only $\$$.
Answer frame. Open with the augmented grammar and numbered productions; compute closure and goto to list I0 to I9; draw the DFA; write the FOLLOW sets; fill the table with shifts, gotos and reduces by FOLLOW; close by stating the s/r conflict in I2 on =, so the grammar is not SLR(1).
Pitfall: Reducing on every terminal instead of only FOLLOW(A) hides the conflict and gives a wrong table.
Asked: [14 marks] (May 2024) Compute LR(0) items for the grammar $S \to L=R \mid R$, $L \to *R \mid id$, $R \to L$ and construct the SLR parser table.
Syntax directed definitions: syntax trees, S-attributed, L-attributed
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>
Definition. <mark>A syntax directed definition (SDD) attaches attributes to grammar symbols and semantic rules to productions; an L-attributed definition is one whose inherited attributes depend only on the parent and on siblings to the left.</mark> Synthesized attributes are computed from children; inherited ones from parent and left siblings.
Key points.
- An S-attributed definition uses only synthesized attributes, so it is evaluated bottom-up during LR parsing, when a reduction happens.
- In an L-attributed definition, for $A \to X_1X_2\dots X_n$ the inherited attribute of $X_i$ may use only the inherited attributes of A and any attributes of $X_1 \dots X_{i-1}$, never those to its right, so evaluation is a left-to-right depth-first walk.
- Every S-attributed definition is also L-attributed, and dependency graphs of L-attributed rules have no cycles.
- Syntax trees are built with node-making functions such as
mknode(op, left, right)andmkleaf(id, entry).
Example. Declaration $D \to T\,L$, $T \to int$, $L \to L_1, id \mid id$:
| Production | Semantic rule |
|---|---|
| $D \to T\,L$ | $L.in = T.type$ |
| $T \to int$ | $T.type = integer$ |
| $L \to L_1, id$ | $L_1.in = L.in$; addtype(id.entry, L.in) |
Here $T.type$ is synthesized, $L.in$ is inherited from the left sibling T; evaluation order is T first, then L, left to right.
Answer frame. Open with the L-attributed definition; explain synthesized versus inherited; give the table above; draw the dependency arrow T.type to L.in to L1.in; close with the left-to-right rule.
Asked: [8 marks] (May 2024) Explain L-attribute definition with suitable example.
Top down translation, bottom up evaluation of inherited attributes, recursive evaluation, analysis of syntax directed definition
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>
Definition. Top-down translation embeds semantic actions inside productions and executes them while a recursive descent or predictive parser walks the input.
Key points.
- For L-attributed definitions, inherited attributes become parameters and synthesized attributes become return values of the parsing procedures.
- After left-recursion removal the translation scheme places actions so that an attribute is computed before it is used.
- Bottom-up evaluation of inherited attributes uses marker non-terminals $M \to \epsilon$ whose action copies the value from a known stack position.
- Recursive evaluation visits the parse tree depth-first, evaluating children before the attributes that depend on them, following the dependency graph.
Last-minute revision
- Parsing checks that tokens derive from the start symbol of a CFG and builds a parse tree.
- Top-down: leftmost derivation from the root; bottom-up: rightmost derivation in reverse.
- Recursive descent has one procedure per non-terminal; it fails on left recursion.
- Remove left recursion: $A \to \beta A'$, $A' \to \alpha A' \mid \epsilon$.
- LR item is a production with a dot; closure adds items, goto moves the dot.
- SLR reduces $A \to \alpha$ only on FOLLOW(A).
- For the May 2024 grammar there are 10 states (I0 to I9) and I2 has a shift-reduce conflict on
=. - FOLLOW(S)={$}, FOLLOW(L)=FOLLOW(R)={=, $}.
- Power: SLR < LALR < canonical LR(1).
- S-attributed uses only synthesized attributes; L-attributed allows inherited from the parent and left siblings.
Memory hooks
- LR: "Left-to-right scan, Rightmost derivation reversed".
- SLR is Simple: FOLLOW sets only; LALR merges same cores.
- Dot moves right: shift moves it over a terminal, reduce is dot at the end.
- Synthesized goes up, inherited comes down or across from the left.
Coverage checklist
- Syntax analysis: CFGs, Top down parsing, Brute force approach, recursive descent parsing: covers [6 marks] Define parsing, types of top-down parsing; [8 marks] Recursive descent with example.
- transformation on the grammars, predictive parsing, bottom up parsing: no past questions.
- operator precedence parsing, LR parsers (SLR, LALR, LR), Parser generation: covers [14 marks] LR(0) items and SLR table.
- Syntax directed definitions: Construction of Syntax trees, Bottom up evaluation of S-attributed definition, L-attribute definition: covers [8 marks] L-attribute definition with example.
- Top down translation, Bottom Up evaluation of inherited attributes Recursive Evaluation, Analysis of Syntax directed definition: no past questions.