Lexical Analysis, Parsing & Syntax-Directed Translation

The compiler front end turns a stream of characters into a structured representation, and it does so in stages because each stage produces something the next can consume more cheaply.

The lexer uses a regular language and the parser uses a context-free one, and that split is not arbitrary. Recognising an identifier needs no nesting, so a finite automaton suffices and runs in linear time with a tiny constant. Recognising nested expressions needs a stack, which is more expensive, so it is worth handling the easy part first.

Every parsing method is characterised by two choices: how much lookahead it consults, and whether it builds the parse tree from the root down or from the leaves up.

The grammar classes — LL(1), SLR(1), LALR(1), CLR(1) — are not properties of languages. They are exactly the sets of grammars each method can handle without conflict. A language may have an LL(1) grammar and a non-LL(1) grammar simultaneously, and questions exploit that constantly.

So the diagnostic question is: what does this method need to decide, and does the grammar give it enough information at that point? A conflict means the answer is no.

1. The Front End Pipeline

Six phases are named, and the first four are the front end.

Which phase catches which error is examined directly. A missing semicolon is syntax. A misspelled keyword is usually lexical only if it produces an illegal character; otherwise it becomes an identifier token and fails at syntax or semantics. Adding an integer to a string is semantic, because the grammar permits the shape and only the types forbid it.

The symbol table spans all phases rather than belonging to one. The lexer creates entries, the parser and semantic analyser annotate them with types and scopes, and code generation reads addresses from them.

2. Lexical Analysis

The lexer groups characters into tokens. A token is a category, a lexeme is the actual text, and a pattern is the rule describing the category.

For the input count, the token is identifier, the lexeme is count, and the pattern is the regular expression for identifiers.

Token patterns are regular languages, so the lexer is built by converting regular expressions to an NFA, then to a DFA, then minimising. That pipeline is exactly the automata theory chapter applied.

Two rules resolve ambiguity when several patterns match.

Longest match wins: given elsewhere, the lexer produces one identifier rather than the keyword else followed by where.

Among equal-length matches, the earlier-listed pattern wins, which is why keyword patterns are listed before the identifier pattern. Otherwise every keyword would be lexed as an identifier.

Lexical analysis cannot detect most errors, because almost any character sequence forms some valid token. Its errors are confined to characters that begin no legal token at all.

3. Top-Down Parsing

A top-down parser builds the parse tree from the root, expanding a variable at each step and matching terminals as it goes. It produces a leftmost derivation.

Two grammar features make top-down parsing impossible and must be removed first.

Left recursion causes infinite descent: a rule $A\to A\alpha$ expands $A$ into something beginning with $A$, forever. It is removed by rewriting as $A\to \beta A^{\prime }$ with $A^{\prime }\to \alpha A^{\prime }\mid ϵ$, which converts left recursion into right recursion.

Common prefixes prevent a decision with one lookahead symbol. Rules $A\to \alpha \beta$ and $A\to \alpha \gamma$ look identical until $\alpha$ has been consumed. Left factoring rewrites them as $A\to \alpha A^{\prime }$ with $A^{\prime }\to \beta \mid \gamma$, deferring the choice until the distinguishing symbol is visible.

Neither transformation changes the language, only the grammar, which is the practical face of grammar classes being about grammars rather than languages.

4. FIRST, FOLLOW and LL(1)

The parsing table is built from two sets.

FIRST of a string is the set of terminals that can begin a string derived from it, plus $ϵ$ if it can derive the empty string.

FOLLOW of a variable is the set of terminals that can appear immediately after it in some sentential form, plus the end marker if it can appear at the end.

Computing them follows fixed rules. For FIRST, take the first symbol; if it is a terminal, that is the answer, and if it is a variable that can vanish, continue to the next symbol.

For FOLLOW, whatever follows a variable in a production body contributes, and if the remainder can vanish, the FOLLOW of the left-hand side contributes too.

The FOLLOW of the start symbol always contains the end marker.

The parsing table places production $A\to \alpha$ in the cell for row $A$ and each terminal in FIRST($\alpha$). If $\alpha$ can derive $ϵ$, the production also goes in every cell for FOLLOW($A$), since seeing something that can follow $A$ means $A$ should vanish.

A grammar is LL(1) exactly when no cell holds two productions. Two productions in one cell means the parser cannot choose with one symbol of lookahead.

Left recursion always causes a conflict, and so does an unfactored common prefix, which is why both must be removed. An ambiguous grammar is never LL(1), since ambiguity guarantees a cell collision.

5. Bottom-Up Parsing

A bottom-up parser builds the tree from the leaves, repeatedly recognising a right-hand side and replacing it with the left-hand side. It produces a rightmost derivation in reverse.

The mechanism is shift-reduce. Shift pushes the next input symbol onto a stack; reduce pops a right-hand side and pushes the corresponding variable. The parser accepts when the stack holds only the start symbol and the input is exhausted.

A handle is the substring that should be reduced next, and the entire difficulty of bottom-up parsing is identifying handles. The LR family solves it by tracking, in the parser state, which productions are partially matched.

An LR(0) item is a production with a dot marking how much has been seen. The item $A\to \alpha \cdot \beta$ means $\alpha$ is on the stack and $\beta$ is still expected.

The canonical collection of item sets is built by closure and goto. Closure adds, for a dot before a variable, every production of that variable with the dot at the start. Goto moves the dot past a symbol and takes the closure again.

Two conflicts can arise.

A shift-reduce conflict occurs when a state contains both a completed item, suggesting reduce, and an item with the dot before a terminal, suggesting shift.

A reduce-reduce conflict occurs when a state contains two different completed items.

6. The LR Family

Four methods differ in how much information they use to decide when to reduce.

The containment is strict at every step: every LR(0) grammar is SLR(1), every SLR(1) grammar is LALR(1), and every LALR(1) grammar is CLR(1).

SLR uses FOLLOW, which is a global approximation. It asks what could follow the variable anywhere in the grammar, which is sometimes more than what could follow it in this particular state. That over-approximation is what makes SLR weaker than it might be.

CLR carries an exact lookahead with each item, computed for the specific context, so it never reduces when it should not. The cost is many more states, since items differing only in lookahead are kept separate.

LALR merges CLR states having the same core — the same items ignoring lookaheads — and unions their lookahead sets. The table shrinks to LR(0) size while retaining most of CLR's power.

Merging can introduce a reduce-reduce conflict but never a shift-reduce conflict, and that asymmetry is examined constantly. A shift decision depends only on the core, which merging preserves; a reduce decision depends on the lookahead sets, which merging enlarges and can therefore make overlap.

Every LL(1) grammar is LR(1), but not conversely. Bottom-up parsing sees the whole right-hand side before deciding, while top-down must commit at the start, so bottom-up is strictly more informed.

7. Syntax-Directed Translation

A syntax-directed definition attaches attributes to grammar symbols and rules for computing them.

A synthesised attribute is computed from the children, flowing up the tree. An inherited attribute is computed from the parent or siblings, flowing down or across.

An S-attributed definition uses only synthesised attributes. It can always be evaluated bottom-up during a shift-reduce parse, computing each value at the moment of reduction, which makes it the natural fit for LR parsing.

An L-attributed definition allows inherited attributes, but each may depend only on the parent and on siblings to its left. That restriction guarantees a single left-to-right depth-first pass suffices.

Every S-attributed definition is L-attributed, since having no inherited attributes satisfies the restriction vacuously.

The classic use of an inherited attribute is propagating a declared type down a list of identifiers, where the type appears once at the left and must reach every name to its right.

A definition that is not L-attributed may need multiple passes or an explicit dependency graph, and if the graph has a cycle no evaluation order exists at all.

8. Worked Examples

Example 1. Compute FIRST and FOLLOW for the grammar $S\to ABc$, $A\to a\mid ϵ$, $B\to b\mid ϵ$.

Start with FIRST.

FIRST($A$) is $\{a,ϵ\}$, directly from its two productions.

FIRST($B$) is $\{b,ϵ\}$, likewise.

FIRST($S$) begins with FIRST($A$) minus $ϵ$, giving $\{a\}$. Since $A$ can vanish, continue to $B$, adding $\{b\}$. Since $B$ can also vanish, continue to $c$, adding $\{c\}$. As the whole body cannot vanish — $c$ is a terminal — $ϵ$ is not included.

FIRST($S$) = $\{a,b,c\}$.

Now FOLLOW.

FOLLOW($S$) = \{\}$, the end marker, as always for the start symbol.

For FOLLOW($A$): in $S\to ABc$, what follows $A$ is $Bc$. FIRST($Bc$) is $\{b\}$ plus, since $B$ can vanish, $\{c\}$.

FOLLOW($A$) = $\{b,c\}$.

For FOLLOW($B$): in $S\to ABc$, what follows $B$ is $c$.

FOLLOW($B$) = $\{c\}$.

Note that FOLLOW($A$) picked up $c$ only because $B$ is nullable. Had $B$ been unable to vanish, $c$ would not appear there, and this nullable-propagation step is the one most often skipped.

Example 2. Remove left recursion and left factor: $E\to E+T\mid T$ and $A\to ab\mid ac\mid d$.

For the left recursion in $E$, identify the recursive alternative $E+T$ and the non-recursive one $T$.

The standard transformation gives $E\to T{E}^{\prime }$ and $E^{\prime }\to +T{E}^{\prime }\mid ϵ$.

The new grammar generates the same strings, but the recursion is now on the right, so a top-down parser descends into $E^{\prime }$ only after consuming a $+$, and terminates.

Note that the transformation loses left associativity in the grammar's structure, which is why a translation scheme must reintroduce it through attributes rather than relying on the tree shape.

For the common prefix in $A$, the alternatives $ab$ and $ac$ share the prefix $a$.

Factor it out: $A\to a{A}^{\prime }\mid d$ with $A^{\prime }\to b\mid c$.

Now a parser seeing $a$ commits to the first alternative and defers the $b$-versus-$c$ decision until the next symbol, which is exactly one lookahead away.

Both transformations change the grammar and not the language, which is why a language can be LL(1) even when a particular grammar for it is not.

Example 3. Is the grammar $S\to iEtS\mid iEtSeS\mid a$, $E\to b$ LL(1)?

This is the dangling-else grammar, with $i$ for "if", $t$ for "then", $e$ for "else".

Two productions for $S$ begin with $i$, so there is an unfactored common prefix. That alone means the grammar is not LL(1), since the parser cannot choose between them on seeing $i$.

Left factor: $S\to iEtS{S}^{\prime }\mid a$ with $S^{\prime }\to eS\mid ϵ$.

Now check the table cell for $S^{\prime }$ and the terminal $e$.

$S^{\prime }\to eS$ goes there, since FIRST($eS$) contains $e$.

$S^{\prime }\to ϵ$ goes into every cell for FOLLOW($S^{\prime }$), and FOLLOW($S^{\prime }$) contains $e$ — because in $S\to iEtS{S}^{\prime }$, the $S$ before $S^{\prime }$ can itself be an if-then-else whose $e$ follows.

Both productions land in the cell for $(S^{\prime },e)$, so the grammar is still not LL(1) even after factoring.

The conflict is genuine ambiguity: an else can attach to either of two open ifs. Real parsers resolve it by a rule rather than by the grammar, preferring to shift, which attaches the else to the nearest if.

Example 4. Explain why LALR merging can create a reduce-reduce conflict but never a shift-reduce conflict.

LALR builds the CLR item sets and then merges any two states whose cores are identical, where the core is the set of items ignoring their lookahead components. The merged state's lookahead set for each item is the union of the originals.

Consider a shift-reduce conflict. A shift action arises from an item with the dot before a terminal, which is part of the core. A reduce action arises from a completed item with a lookahead.

If the merged state has a shift on terminal $t$, then the core contained an item with the dot before $t$, so both original states had that same shift.

For a conflict, some completed item must have $t$ in its merged lookahead set, meaning $t$ was in one of the originals. But that original state had both the shift on $t$ and the reduce on $t$ — so it already had the conflict before merging.

Merging therefore cannot create a shift-reduce conflict; it can only expose one that CLR already had.

Now consider reduce-reduce. Suppose state 1 has completed items $A\to \alpha \cdot$ with lookahead $\{x\}$ and $B\to \beta \cdot$ with lookahead $\{y\}$, and state 2 has the same items with lookaheads $\{y\}$ and $\{x\}$ respectively.

Neither state conflicts, since in each the two lookahead sets are disjoint.

After merging, the first item has lookahead $\{x,y\}$ and so does the second. Now both reduce on $x$ and both reduce on $y$ — a genuine new conflict created by the merge.

That is why a grammar can be CLR(1) and not LALR(1), and why the containment is strict.

Example 5. Classify these attributes as synthesised or inherited, and state whether the definition is S-attributed or L-attributed: computing the value of an arithmetic expression; propagating a declared type to a list of identifiers.

Expression evaluation is synthesised. The value of $E\to E_1+T$ is computed as the sum of the values of $E_1$ and $T$, both children. Information flows strictly upward from leaves to root.

The definition is S-attributed, using only synthesised attributes, and can therefore be evaluated during a bottom-up parse by computing each value at the moment its production is reduced. No separate tree traversal is needed.

Type propagation is inherited. In a declaration such as int a, b, c, the type appears once, at the far left, and must reach every identifier to its right.

With a grammar $D\to TL$ and $L\to L_1,\text{id}\mid \text{id}$, the attribute L.type is set from T.type by the parent, then passed down to L1.type. Information flows downward and leftward-to-rightward, which is the definition of inherited.

The definition is L-attributed, because L.type depends only on the parent's attribute and on siblings to its left — namely $T$, which precedes $L$ in the body.

It is not S-attributed, so it cannot be evaluated by a pure bottom-up pass without extra machinery. It can be evaluated in one left-to-right depth-first traversal, which is what L-attributed guarantees.

Example 6. A grammar has 3 shift-reduce conflicts under SLR(1) but none under LALR(1). What does this tell you?

SLR decides to reduce a production $A\to \alpha$ whenever the lookahead is in FOLLOW($A$), where FOLLOW is computed globally over the entire grammar.

That is an over-approximation. FOLLOW($A$) collects every terminal that can follow $A$ anywhere in any derivation, but in a particular parser state, only some of those are actually possible.

If a terminal $t$ is in FOLLOW($A$) globally but cannot follow $A$ in the context this state represents, SLR still schedules a reduce on $t$. If the state also shifts on $t$, a spurious conflict appears.

LALR carries lookaheads computed per item set rather than per variable, so its lookahead for that reduce action is a subset of FOLLOW($A$) — precisely the terminals that can follow $A$ in this context.

If $t$ is excluded, the conflict vanishes, and the grammar parses cleanly.

So the observation tells us the grammar is LALR(1) but not SLR(1), and that all three conflicts were artefacts of FOLLOW's global approximation rather than genuine ambiguities in the grammar.

This is the usual reason SLR fails, and it is why practical parser generators use LALR: it achieves nearly CLR's power at LR(0)'s table size.

Summary

The front end splits into a regular part and a context-free part because recognising tokens needs no nesting and recognising structure does.

A token is a category, a lexeme is the text, and a pattern is the rule. Longest match wins, and among ties the earlier-listed pattern wins, which is why keywords precede identifiers.

Top-down parsing produces a leftmost derivation and requires left recursion removed and common prefixes factored. Neither transformation changes the language.

FIRST collects the terminals that can begin a string; FOLLOW collects those that can follow a variable, and the start symbol's FOLLOW always contains the end marker. A nullable symbol propagates the next symbol's FIRST into the earlier one's FOLLOW.

A grammar is LL(1) exactly when no parsing-table cell holds two productions. Ambiguous grammars and left-recursive grammars never are.

Bottom-up parsing produces a rightmost derivation in reverse by shifting and reducing, and the difficulty is identifying handles. LR items with a dot track partial matches.

LR(0) is contained in SLR(1), contained in LALR(1), contained in CLR(1), all strictly. SLR uses global FOLLOW and is weakened by that approximation; CLR uses exact per-state lookaheads and pays in table size; LALR merges same-core states to get most of CLR's power at LR(0)'s size.

Merging can create a reduce-reduce conflict but never a shift-reduce conflict, because shift actions depend only on the core.

Every LL(1) grammar is LR(1) and not conversely, since bottom-up sees the whole right-hand side before committing.

S-attributed definitions use only synthesised attributes and evaluate during a bottom-up parse. L-attributed definitions allow inherited attributes depending only on the parent and left siblings, and evaluate in one left-to-right pass.