"Lexical Analysis, Parsing & Syntax-Directed Translation" — Practice

Question 1

Which phase detects that a variable is used without being declared?

Accepted Answer

C

Question 2

Which statement is correct?

Accepted Answer

B

Question 3

Merging CLR states to form an LALR table can introduce which conflict?

Accepted Answer

B

Question 4

For the grammar S goes to AB, A goes to a or epsilon, B goes to b or epsilon, compute FIRST and FOLLOW for all three variables and state whether the grammar is LL(1).

Accepted Answer

FIRST(A) is the set containing a and epsilon, directly from its two productions.

FIRST(B) is the set containing b and epsilon, likewise.

FIRST(S): start with FIRST(A) minus epsilon, giving a. Since A is nullable, continue to B and add b. Since B is also nullable, the entire body can vanish, so epsilon is included as well. FIRST(S) is a, b and epsilon.

FOLLOW(S) is the end marker, as always for the start symbol.

FOLLOW(A): in S goes to AB, what follows A is B. FIRST(B) minus epsilon gives b. Since B is nullable, FOLLOW(S) is added too, contributing the end marker. FOLLOW(A) is b and the end marker.

FOLLOW(B): in S goes to AB, nothing follows B, so FOLLOW(S) is added. FOLLOW(B) is the end marker.

Now build the table. For row A: the production A goes to a occupies the cell under a. The production A goes to epsilon occupies every cell in FOLLOW(A), namely under b and under the end marker. No cell has two entries.

For row B: B goes to b occupies the cell under b, and B goes to epsilon occupies the cell under the end marker. No collision.

For row S: S goes to AB occupies cells under FIRST(AB), which is a, b and the end marker since the body is nullable. One entry each.

No cell holds two productions, so the grammar is LL(1).

Question 5

Transform the grammar E goes to E plus T or E minus T or T, and T goes to T times F or F, and F goes to id or open-paren E close-paren, into an LL(1)-suitable form.

Accepted Answer

Both E and T are left recursive, so a top-down parser would descend infinitely. Apply the standard transformation to each.

For E, the recursive alternatives are E plus T and E minus T, and the non-recursive alternative is T.

E goes to T E-prime.
E-prime goes to plus T E-prime, or minus T E-prime, or epsilon.

For T, the recursive alternative is T times F and the non-recursive one is F.

T goes to F T-prime.
T-prime goes to times F T-prime, or epsilon.

F has no left recursion and no common prefix, since id and the open parenthesis are distinct terminals, so it is unchanged.

The full transformed grammar is: E goes to T E-prime; E-prime goes to plus T E-prime or minus T E-prime or epsilon; T goes to F T-prime; T-prime goes to times F T-prime or epsilon; F goes to id or parenthesised E.

Check LL(1) informally. In row E-prime, the three alternatives begin with plus, minus and epsilon respectively. The epsilon production goes into FOLLOW(E-prime), which contains the close parenthesis and the end marker — neither of which is plus or minus. No collision.

In row T-prime, the alternatives begin with times and epsilon, and FOLLOW(T-prime) contains plus, minus, close parenthesis and the end marker. Times is not among them, so no collision.

The grammar is now LL(1). One cost is worth noting: the transformation makes the recursion right-leaning, so left associativity of subtraction must be restored through attribute rules rather than the tree shape.

Question 6

Classify the attribute definitions for a declaration grammar D goes to T L, T goes to int or float, L goes to L comma id or id, and state which evaluation strategies apply.

Accepted Answer

The purpose is to record the declared type against every identifier in the list.

T.type is synthesised: it is computed from T's own production, taking the value int or float depending on which terminal was matched. Information flows up from the leaf to T.

L.type is inherited: the list has no way to know the type from its own subtree, since the type symbol T is its sibling, not its descendant. The parent rule D goes to T L must assign L.type from T.type.

Within the list, L1.type in the production L goes to L1 comma id is also inherited, copied down from L.type so that every identifier in the chain receives it.

The action at each identifier is to write the inherited type into the symbol table entry for that name.

The definition is not S-attributed, because it uses inherited attributes. It therefore cannot be evaluated during a pure bottom-up parse: at the moment L is reduced, the parent rule that would supply L.type has not yet been applied.

The definition is L-attributed. L.type depends on T.type, and T precedes L in the body of D goes to T L, so the dependency runs from a left sibling. Similarly L1.type depends on its parent L.type. Both satisfy the L-attributed restriction.

The consequence is that a single left-to-right depth-first traversal suffices to evaluate everything, which is exactly what recursive-descent parsers do naturally, and why L-attributed definitions pair with top-down parsing while S-attributed ones pair with bottom-up.

Question 7

A grammar produces an SLR(1) table with a shift-reduce conflict but a conflict-free LALR(1) table. Explain how this is possible and what it reveals.

Accepted Answer

SLR decides to reduce a production A goes to alpha whenever the current lookahead lies in FOLLOW(A), and FOLLOW is computed once over the whole grammar.

That computation is context-blind. It collects every terminal that can follow A in any derivation anywhere, without regard to which parser state is currently active.

In a particular state, only some of those terminals can genuinely occur next. If a terminal t is in FOLLOW(A) globally but cannot follow A in the context this state represents, SLR nevertheless schedules a reduce action on t.

If that same state also has an item with the dot immediately before t, it schedules a shift on t as well, and the table records a shift-reduce conflict that corresponds to no real ambiguity in the grammar.

LALR computes lookaheads per item rather than per variable. Each completed item carries the set of terminals that can actually follow it in the specific contexts leading to that state, which is a subset of FOLLOW(A).

If t is excluded from that narrower set, no reduce action on t is generated and the conflict disappears.

What this reveals is twofold. First, the grammar is LALR(1) but not SLR(1), which places it strictly between the two classes and confirms that the containment is proper. Second, the conflicts were artefacts of an approximation rather than genuine ambiguities, so no grammar rewriting is needed — merely a more precise parser generator.

This situation is common enough that it is the standard reason practical tools use LALR rather than SLR: LALR achieves close to CLR's power while keeping the LR(0) table size, and it eliminates precisely this class of spurious conflict.

Question 8

The dangling-else grammar S goes to if E then S, or if E then S else S, or other, is ambiguous. Show why left factoring does not fix it and how real parsers cope.

Accepted Answer

First, the grammar is not LL(1) for an obvious reason: two productions for S begin with the same terminal if, so one symbol of lookahead cannot distinguish them.

Left factoring addresses that surface problem. Extract the common prefix to get S goes to if E then S S-prime, or other, with S-prime goes to else S, or epsilon.

Now examine the parsing table cell for row S-prime and the terminal else.

The production S-prime goes to else S belongs there, since FIRST of its body contains else.

The production S-prime goes to epsilon belongs in every cell of FOLLOW(S-prime). And FOLLOW(S-prime) contains else, because in the body if E then S S-prime, the inner S can itself be a complete if-then-else construct, so an else can legitimately follow the position where S-prime sits.

Both productions therefore occupy the cell for S-prime and else, and the grammar remains non-LL(1) after factoring.

The reason factoring failed is that the difficulty was never a surface prefix. It is genuine ambiguity: in a nested construct such as if A then if B then X else Y, the else can attach to either if, and both parse trees are legal derivations of the same string. No grammar transformation removes an ambiguity that the language specification itself leaves open.

Real parsers resolve it outside the grammar. A bottom-up parser encounters a shift-reduce conflict at exactly this point and applies a default rule preferring shift, which attaches the else to the nearest unmatched if. A recursive-descent parser achieves the same by consuming an else greedily as soon as it appears.

That convention matches the semantics every mainstream language specifies, so the ambiguity is resolved by policy rather than by grammar.

Question 9

A compiler team must choose between recursive descent with LL(1) and a generated LALR(1) parser. Compare them on grammar restrictions, error handling and maintenance.

Accepted Answer

On grammar restrictions, LALR is markedly more permissive. LL(1) requires the grammar to be free of left recursion and free of common prefixes, and both must be removed by hand. Left-recursion removal in particular converts a naturally left-associative rule into a right-recursive one, so associativity must then be restored through attribute actions rather than the tree shape.

LALR accepts left recursion directly, which means the natural grammar for arithmetic expressions can be used unchanged and the parse tree already has the correct associativity. Every LL(1) grammar is also LR(1), so nothing is lost by choosing the bottom-up route on expressiveness grounds.

On error handling, recursive descent is substantially better. Each nonterminal is a hand-written function, so a parse failure occurs at a point where the compiler knows exactly what construct it was attempting and can emit a message naming it. Error recovery can be tailored per construct, skipping to a synchronising token chosen for that context.

A generated LALR parser fails in a state number, and mapping that state back to a human-meaningful description requires extra machinery. Recovery is typically generic, based on error productions or panic-mode token skipping, and the messages are correspondingly vaguer.

On maintenance, the trade reverses again. A generated parser is regenerated from the grammar, so a language change is a grammar edit and the tool reports any new conflict immediately. A recursive-descent parser must be edited by hand, and there is no automatic check that the implementation still matches the intended grammar.

The practical resolution most production compilers reach is recursive descent, accepting the grammar restrictions and manual maintenance in exchange for error messages good enough to show users.

Practice — "Lexical Analysis, Parsing & Syntax-Directed Translation"

Sign in to save attempts to your dashboard and track your accuracy over time

Find a verified tutor

Join a live course

Browse coaching centres

About

Categories

Support

Documentation

Get Study Tips & Updates

Download Our App

Download for iOS

Download for Android

Popular Cities