2023 question paper

Compiler Design

27 questions

Q1a. Which of the following is the most powerful parser? (i) SLR (ii) LALR (iii) Canonical LR (iv) Operator precedence20232m
Module 2: Syntax Analysis (Parser)
Which of the following is the most powerful parser?
(i) SLR
(ii) LALR
(iii) Canonical LR
(iv) Operator precedence

View this question on its own page →
Search Google Ask AI
Worked Solution
Answer: (iii) Canonical LR

Explanation

Parsers can be ordered by the size of the grammar class they can handle (their power):

Operator-precedence parsing: only works on operator grammars (no $\epsilon$ , no two adjacent nonterminals) — the least general.

SLR(1): uses the LR(0) items but decides reduce actions using the broad $\mathrm{FOLLOW}$ set of the left-hand nonterminal, ignoring the specific context of each item → weaker.

LALR(1): merges LR(1) items that share the same core (same item, different lookahead). More powerful than SLR(1).

Canonical LR / LR(1): keeps every lookahead separate, producing the most states and therefore accepting the largest set of grammars among the given options.

Hence the most powerful parser is:

$\boxed{\text{(iii) Canonical LR (LR(1))}}$

Order of power (weakest → strongest):
Operator-precedence < SLR(1) < LALR(1) < Canonical LR(1)
Q1b. A top down parser generates (i) Rightmost derivation (ii) Rightmost derivation in reverse (iii) Leftmost derivation (iv) Left most derivation in reverse20232m
Module 2: Syntax Analysis (Parser)
A top down parser generates
(i) Rightmost derivation
(ii) Rightmost derivation in reverse
(iii) Leftmost derivation
(iv) Left most derivation in reverse

View this question on its own page →
Search Google Ask AI
Worked Solution
Answer: (iii) Leftmost derivation

Explanation

A top-down parser starts from the start symbol (root) and tries to derive the input string by expanding nonterminals in leftmost order — i.e. it always expands the leftmost nonterminal first.

Leftmost derivation: each step replaces the leftmost nonterminal — this is exactly what a top-down (recursive-descent / predictive / LL) parser constructs.

Rightmost derivation: each step replaces the rightmost nonterminal — not what a top-down parser does.

Rightmost derivation in reverse / handle pruning: that is the basis of bottom-up parsing (LR parsers), not top-down.

Therefore a top-down parser generates a

$\boxed{\text{(iii) Leftmost derivation}}$

Q1c. A shift reduce parser carries out the actions specified within braces immediately after reducing with the corresponding rule of grammar: S \to xxW {print "1"}, S \to y {print "2"}, S \to Sz {print "3"} What is the translation of xxxxyzz using the syntax directed translation scheme described by the above rules? (i) 23131 (ii) 11233 (iii) 11231 (iv) 3321120232m

Module 3: Semantic Analysis, Symbol Table, Run-time environment

A shift reduce parser carries out the actions specified within braces immediately after reducing with the corresponding rule of grammar:
$S \to xxW$ {print "1"}, $S \to y$ {print "2"}, $S \to Sz$ {print "3"}
What is the translation of $xxxxyzz$ using the syntax directed translation scheme described by the above rules?
(i) 23131
(ii) 11233
(iii) 11231
(iv) 33211

View this question on its own page →

Search Google Ask AI

Worked Solution

Answer: (iii) 11231

Reasoning (shift–reduce with actions executed on reduce)

Grammar:
$S \to xxW \ \{\text{print }1\}, \qquad S \to y \ \{\text{print }2\}, \qquad S \to Sz \ \{\text{print }3\}$

Input string: x x x x y z z.

Reducing the string from the input up to $S$ (the actions fire in the order the reductions are performed):

Step	Stack contents (top right)	Action	Printed
1	`x x` collected, `W → … y`	reduce `xxW → S`	1
2	next `x x` + …	reduce `xxW → S`	1
3	`y`	reduce `y → S`	2
4	`S` + `z`	reduce `Sz → S`	3
5	`S` + `z` then top combine	reduce (top-level `xxW`/final)	1

Collecting the prints in the order the reductions happen:

$\boxed{11231}$

Hence the correct choice is (iii).

Q1d. Three-address code involves (i) Exactly 3 address (ii) At most 3 addresses (iii) No unary operator (iv) None20232m
Module 4: Intermediate Code Generation, Code Improvement (optimization)
Three-address code involves
(i) Exactly 3 address
(ii) At most 3 addresses
(iii) No unary operator
(iv) None

View this question on its own page →
Search Google Ask AI
Worked Solution
Answer: (ii) At most 3 addresses

Explanation

A three-address code is an intermediate-code statement of the general form:

$\mathrm{result} = \mathrm{arg}_1\ \text{op}\ \mathrm{arg}_2$

Each statement contains at most three operands/addresses: the destination plus at most two source operands. The name comes from the fact that a single 3-address statement involves at most three addresses.

It is not exactly 3 addresses — a statement like t = a or t = -a has fewer than three addresses.

It can contain a unary operation (e.g. t = -x), so saying "no unary operator" is wrong.

Therefore "Exactly 3 address" (i), "No unary operator" (iii), and "None" (iv) are incorrect.

The correct statement is:

$\boxed{\text{(ii) At most 3 addresses}}$
Q1e. Handle pruning forms the basis of........ (i) Bottom up parsing (ii) Top down parsing (iii) Predictive parsing (iv) Recursive descent parsing20232m
Module 2: Syntax Analysis (Parser)
Handle pruning forms the basis of........
(i) Bottom up parsing
(ii) Top down parsing
(iii) Predictive parsing
(iv) Recursive descent parsing

View this question on its own page →
Search Google Ask AI
Worked Solution
Answer: (i) Bottom-up parsing

Explanation

A handle is a substring of a (right) sentential form that matches the right-hand side of a production, and whose reduction brings us one step closer to the start symbol when reduced.

Handle pruning is the process of repeatedly finding the handles (finding the rightmost such substring during a rightmost reduction) and reducing them — from the input string up to the start symbol.

This is precisely how a bottom-up parser (shift-reduce / LR parser) works: it repeatedly reduces handles until the entire input has been reduced to the start symbol.

Top-down parsing, predictive parsing, and recursive-descent parsing all work top-down (expanding the root) and do not prune handles.

$\boxed{\text{(i) Bottom up parsing}}$
Q1f. Left factoring guarantees (i) Not occurring of backtracking (ii) Cycle free parse tree (iii) Error free target code (iv) Correct LL(1) parsing table20232m
Module 2: Syntax Analysis (Parser)
Left factoring guarantees
(i) Not occurring of backtracking
(ii) Cycle free parse tree
(iii) Error free target code
(iv) Correct LL(1) parsing table

View this question on its own page →
Search Google Ask AI
Worked Solution
Answer: (i) Not occurring of backtracking

Explanation

Left factoring is a grammar transformation that factors out the common prefix of two or more production alternatives.

It is used to remove uncertainty about which alternative to choose when a common prefix could lead to two different nonterminal, which otherwise forces the parser to backtrack while building a predictive (LL) parser.

How it works:
$A \to \alpha\beta_1 \mid \alpha\beta_2 \;\Rightarrow\; A \to \alpha A', \quad A' \to \beta_1 \mid \beta_2$

In an LL(1) (predictive top-down) parser the decision is made by looking at the first token; factoring out a common prefix ensures the choice is deterministic, so backtracking never occurs.

Hence left factoring guarantees:
$\boxed{\text{(i) Not occurring of backtracking}}$
Q1g. Consider a grammar A \to a S_1 | a S_2. The left factored grammar produced from the grammar is (i) A \to a A', A' \to S_1 | S_2 (ii) A' \to a A, A \to a S_1 | a S_2 (iii) A \to a A', A' \to S_1 | S_2, S_1 \to S_1, S_2 (iv) None of these20232m
Module 2: Syntax Analysis (Parser)
Consider a grammar $A \to a S_1 | a S_2$ . The left factored grammar produced from the grammar is
(i) $A \to a A', A' \to S_1 | S_2$
(ii) $A' \to a A, A \to a S_1 | a S_2$
(iii) $A \to a A', A' \to S_1 | S_2, S_1 \to S_1, S_2$
(iv) None of these

View this question on its own page →
Search Google Ask AI
Worked Solution
Answer: (i) $A \to aA',\ A' \to S_1 \mid S_2$

Step 1 — left factoring

Given grammar:
$A \to aS_1 \mid aS_2$

The two alternatives share the common prefix a. We factor it out into a new nonterminal $A'$ :

$A \to aA'$

$A' \to S_1 \mid S_2$

This is the standard left-factored (CFG) form that removes backtracking uncertainty, because after reading a the parser chooses between $S_1$ and $S_2$ by looking at the next input, not by backtracking.

Hence the correct answer is:

$\boxed{\text{(i)}\ A \to aA',\ A' \to S_1 \mid S_2}$
Q1h. Synthesized attributed are calculated (i) From the values of attributes of the children of the node (ii) From the values of attributes of the parent of the node (iii) From the values of attributes of the siblings of the node (iv) None of these20232m
Module 3: Semantic Analysis, Symbol Table, Run-time environment
Synthesized attributed are calculated
(i) From the values of attributes of the children of the node
(ii) From the values of attributes of the parent of the node
(iii) From the values of attributes of the siblings of the node
(iv) None of these

View this question on its own page →
Search Google Ask AI
Worked Solution
Answer: (iii) children of the node (option (i))

Explanation

Attributes in a syntax-directed definition are classified by the direction of their dependency:

Synthesized attribute (S-attribute): computed from the attribute values of the children of a node. Its value at a node is a function of the values at its descendants, so the tree is evaluated bottom-up. A classic example is E.val = E1.val * T.val.

Inherited attribute (I-attribute): computed from the parent and/or siblings — flows top-down or sideways.

Since the question is about synthesized attributes, they are calculated:

$\boxed{\text{from the values of the attributes of the children of the node → option (i)}}$
Q1i. The method which merges the bodies of two loops is (i) Loop rolling (ii) Loop Jamming (iii) Constant folding (iv) None of the above20232m
Module 4: Intermediate Code Generation, Code Improvement (optimization)
The method which merges the bodies of two loops is
(i) Loop rolling
(ii) Loop Jamming
(iii) Constant folding
(iv) None of the above

View this question on its own page →
Search Google Ask AI
Worked Solution
Answer: (ii) Loop Jamming (loop jamming)

Explanation

Loop jamming / loop fusion (jamming) is the compiler optimization that merges the bodies of two adjacent loops that have the same range of traversal, into a single loop, so the loop control overhead runs only once.

Loop rolling is not a standard optimization.

Constant folding folds expressions with only constants at compile time, evaluating them at compile time (e.g. x = 3+4 → x = 7), unrelated to merging loops.

"None of the above" is therefore wrong.

Hence the method which merges the bodies of two loops is:

$\boxed{\text{(ii)Loop jamming (loop fusion)}}$
Q1j. For a grammar G, shift reduce (S-R) conflicts are present in LALR(1) parser, if and only if (i) The LAR (1) parser for G has S.R conflicts (ii) The LR(0) parser for G has S.R conflicts (iii) The SLR(1) parser for G has S.R conflicts (iv) The SLR(0) parser for G has S.R conflicts20232m
Module 2: Syntax Analysis (Parser)
For a grammar G, shift reduce (S-R) conflicts are present in LALR(1) parser, if and only if
(i) The LAR (1) parser for G has S.R conflicts
(ii) The LR(0) parser for G has S.R conflicts
(iii) The SLR(1) parser for G has S.R conflicts
(iv) The SLR(0) parser for G has S.R conflicts

View this question on its own page →
Search Google Ask AI
Worked Solution
Answer: (i) The LR(1) parser for G has S–R conflicts

Explanation — LALR vs LR relationship

LALR(1) parsers are built by merging the states of a canonical LR(1) parser that share the same core (same items, different lookaheads).

Merging states can create a reduce–reduce (R–R) conflict (two different reduce actions that were separated by lookahead now share a cell).

However, state-merging cannot create a new shift–reduce (S–R) conflict. Intuitively, a shift action exists on a terminal $t$ in a state only if $t$ is in that state's core in the LR(1) automaton too. So if the LALR(1) table has an S–R conflict, the same conflict must have already been present in the LR(1) table.

Therefore the correct statement is the one in option (i) — the LR(1) parser for $G$ has S–R conflicts (with LAR(1) in the paper being a typo for LR(1)).

$\boxed{\text{(i) The LR(1) parser for G has S.R conflicts}}$
Budget App•POCKETLY
Pocketly on Android
Log daily food, travel, and hostel expenses instantly. Set monthly spending limits and see where your money goes without complex spreadsheets.
Install Pocketly
Q2a. Explain the working of each phase of compiler in detail with an example.20237m
Module 1: Introduction, Lexical Analysis
Explain the working of each phase of compiler in detail with an example.

View this question on its own page →
Search Google Ask AI
Worked Solution
The six phases of a compiler (with an example)

A compiler translates a high-level program into target (machine) code in several phases. They are divided into the front end (source-language dependent) and back end (machine dependent).

Lexical Analysis (Scanner)

Reads the raw character stream and groups it into meaningful tokens (identifiers, keywords, operators, literals).

Output: a stream of tokens $\langle \text{type, attribute}\rangle$ .

Uses a symbol table to record identifiers.

Example: for position = initial + rate * 60, tokens are: ident(position), =, ident(initial), +, ident(rate), *, num(60).

Syntax Analysis (Parsing)

Groups tokens into a parse tree / syntax tree according to the grammar.

Detects syntactic errors (e.g. x = + * y).

Output: a parse tree (for position = initial + rate*60 we get precedence built in: rate*60 is computed first).

Semantic Analysis

Checks the parse tree for semantic correctness: type checking, name/declaration matching, etc.

For types: if position, initial, rate are float and 10 is int, it may insert implicit conversion int→real.

Output: annotated syntax tree.

Intermediate Code Generation

Produces a machine-independent intermediate representation (e.g. three-address code).

Example for the above assignment:
t1 = int_to_float(10) t2 = rate * t1 t3 = initial + t2 position = t3

Code Optimization

Improves the intermediate code, e.g. reduces t1 = int_to_float(10) because 10 is a constant that can be folded and converted once. After optimization:
t2 = rate * 10.0 position = initial + t2

Code Generation (Target Code Generation)

Maps optimized intermediate code onto target machine's assembly instructions, e.g.:
MOVF R2, #10.0 (or LDF) MULF R2, R1 ADDF R2, R0 MOVF position, R2

Symbol Table is a central data structure maintained throughout all phases, storing names, types, scope, and addresses.

$\boxed{\text{Order: Lexical → Syntax → Semantic → Intermediate Code → Optimization → Code Generation}}$
Q2b. What is an activation record? Explain how they are used to access various local and global variables.20237m
Module 3: Semantic Analysis, Symbol Table, Run-time environment
What is an activation record? Explain how they are used to access various local and global variables.

View this question on its own page →
Search Google Ask AI
Worked Solution
What is an activation record? How are local/global variables accessed?

Activation record (AR) — also called a stack frame — is a block of memory pushed onto the run-time stack for each call of a procedure/function. It holds everything needed to return from the call and to run the callee. When the procedure returns, its record is popped (unless it is kept for certain closures).

Typical layout (higher addresses → lower):

[ actual parameters ] [ return value (if any) ] [ access link / control link (saved frame pointer) ] [ return address (saved PC) ] [ saved machine status ] [ local data (locals, temporaries) ] [ saved top-of-stack pointer ]

Accessing local variables:

While a procedure is active, the runtime keeps a base pointer (frame pointer) that names the bottom of the current AR.

Every local variable is stored at a fixed offset from the start of the AR, an offset chosen at compile time.

So x is accessed as base + offset(x) — no runtime search: just load [base+off].

Accessing global (non-local) variables:

Globals live in a global/static data area (not on the stack in most compilers). Each global has a fixed compile-time address/offset from a global base register/area, so access is again just an absolute/relative memory load.

Some compilers (old Pascal-style) used an access link/display to reach enclosing non-locals: each frame holds a pointer to the frame of the statically enclosing procedure; accessing a nonlocal of depth $d$ follows $d$ links. (Dynamic scoping instead uses a dynamic link up the call chain.)

Example (C):

int g = 10; /* global */ int f(int p) { int l; l = g + p; return l; }

At run time while inside f:

p and l are at FP + offset_p and FP + offset_l (local, in the AR).

g is at its fixed global-area address (single load).

Conclusion

Locals → offsets within the current activation record on the run-time stack (FP + offset).

Globals → fixed addresses in a global data region, known at compile time.

Q3a. What are the advantages of LALR parsing over SLR and CLR methods?20235m

Module 2: Syntax Analysis (Parser)

What are the advantages of LALR parsing over SLR and CLR methods?

View this question on its own page →

Search Google Ask AI

Worked Solution

Advantages of LALR(1) parsing over SLR(1) and canonical LR (CLR)

Method	Number of states	Power	Slots management
SLR(1)	fewest	weakest (uses FOLLOW)	smallest
LALR(1)	same as SLR	between SLR and CLR	larger
Canonical LR (CLR/CLR(1))	the most	strongest	largest

Advantages of LALR over SLR:

LALR(1) accepts a larger grammar class than SLR(1): SLR reduces using $\mathrm{FOLLOW}$ , which may cause spurious reduce–reduce and shift–reduce conflicts, because it ignores which attribute context produced the follow. LALR uses the precise lookahead symbols from the LR(1) items (merged by core), so fewer conflicts arise. Many grammars that are not SLR are LALR.
It is still simple: LALR(1) lookaheads are "compatible" — no shift–reduce conflict is introduced by merging states.

Advantages of LALR over canonical LR (CLR):

Fewer states — In practice LALR(1) has roughly the same number of states as SLR(1), whereas a canonical LR(1) parser can have a very large state space (up to exponential in the grammar size). This makes LALR tables much more compact and memory-efficient.
Faster table construction — merging reduces the number of states to process.
It is the method of choice in practice: LALR(1) is used in tools like YACC / Bison because it is strong enough for almost all practical grammars yet keeps the table small — the "sweet spot" between SLR (too weak) and CLR (too many states).

Trade-off: CLR may parse a slightly larger class, but its cost (huge state) is not justified in most cases. So LALR(1) is the best power/size ratio.

$\boxed{\text{LALR(1) : smaller (SLR-like) state count, near-CLR power → most practical; wins for memory and speed.}}$

Q3b. Write the algorithm to compute FIRST and FOLLOW for a given grammar.20235m
Module 2: Syntax Analysis (Parser)
Write the algorithm to compute FIRST and FOLLOW for a given grammar.

View this question on its own page →
Search Google Ask AI
Worked Solution
Algorithm to compute FIRST and FOLLOW

Notation: $X$ = nonterminal/terminal; $\alpha,\beta$ = strings of grammar symbols; $\epsilon$ = empty string; $ = end marker.

FIRST

Compute $FIRST(X_1\dots X_n))$ = set of terminals that can start any string derivable from $X_1X_2\dots X_n$ (plus $\epsilon$ if the whole can derive $\epsilon$ ).

Rules (for individual symbol):

If $X$ is a terminal, then $\mathrm{FIRST}(X) = \{X\}$ .

If $X$ is $\epsilon$ production i.e. $X\to\epsilon$ , add $\epsilon$ to $\mathrm{FIRST}(X)$ .

If $X$ is a nonterminal and $X\to Y_1Y_2\dots Y_k$ , then:

Put $\mathrm{FIRST}(Y_1)$ \textbackslash}{\epsilon} into $\mathrm{FIRST}(X)$ .

If $Y_1$ derives $\epsilon$ , also put $\mathrm{FIRST}(Y_2)\setminus\{\epsilon\}$ , and so on.

If $Y_1..Y_k$ all can derive $\epsilon$ , then put $\epsilon$ into $\mathrm{FIRST}(X)$ .

Order: For each production, apply until no more additions; repeat the whole loop until no change.

For a string $\alpha = X_1X_2\dots X_n$ :
$\mathrm{FIRST}(\alpha) = \mathrm{FIRST}(X_1) \setminus \{\epsilon\}$ ; if $\epsilon\in \mathrm{FIRST}(X_1)$ , add $\mathrm{FIRST}(X_2)\setminus\{\epsilon\}$ , etc.; if all $X_i$ derive $\epsilon$ , add $\epsilon$ to $\mathrm{FIRST}(\alpha)$ .

2. Compute FOLLOW(X) for every nonterminal X

Rule to find the set of terminals that can appear immediately to the right of $X$ in some sentential form.

If $X$ is the start symbol, place ` $` in$ \mathrm{FOLLOW}(X)$.

For a production $A\to\alpha B\beta$ : everything in $\mathrm{FIRST}(\beta)$ except $\epsilon$ goes into $\mathrm{FOLLOW}(B)$ .

If there is a production $A\to\alpha B$ or $A\to\alpha B\beta$ where $\beta \rightsquigarrow \epsilon$ (i.e. $\beta$ is nullable), then everything in $\mathrm{FOLLOW}(A)$ gets added to $\mathrm{FOLLOW}(B)$ .

Repeat these steps until no further additions occur.

(Terminals/symbol ) that are not nonterminals have no FOLLOW.)

These First/Follow results are then used to build the predictive (LL(1)) parsing table: for $A\to\alpha$ , put the production into M[A][a] for each a in $\mathrm{FIRST}(\alpha)$ ; if $\alpha$ nullable, put it into M[A][b] for each b in $\mathrm{FOLLOW}(A)$ .
Q3c. What is shift-reduce conflict?20234m
Module 2: Syntax Analysis (Parser)
What is shift-reduce conflict?

View this question on its own page →
Search Google Ask AI
Worked Solution
What is a shift–reduce conflict?

A shift–reduce conflict (S–R conflict) is a parsing-table conflict in an LR-family bottom-up parser: in one state (looking at one input symbol), the parser has both a valid shift action and a valid reduce action.

Why it happens: When constructing the parsing table, a single cell $M[\text{state}, \text{terminal}]$ ends up with two entries: one saying "shift a (push onto the stack / go to next state)" and the other saying "reduce using production $A\to\alpha$ ". Since the parser cannot decide deterministically, the grammar is not LR with the given method (and the table entry is ambiguous).

Example grammar with S–R conflict: classic ambiguous grammar
$E\to E+E \mid E*E \mid (E) \mid \text{id}$
produces S–R conflict in LR(0)/SLR(1)/LALR(1) because, e.g. after parsing E + E . with input + or *, the parser doesn't know whether to shift the operator (deferring) or reduce E+E.

Remedies:

Add precedence/associativity (%left, %right, %prec in YACC) — e.g. make * bind tighter than +.

Refactor the grammar to an unambiguous form (e.g. with separate term/factor levels).

Use a more powerful parsing method (canonical LR can resolve conflicts that SLR can't) — but a true ambiguity cannot be removed by switching methods.

Reduction internal form: in LR table notation, a cell with both s and r actions is marked as a conflict, and the grammar is rejected by the parser generator (unless a rule like "shift wins on S–R conflict" is chosen YACC's default: prefer shift).

$\boxed{\text{S–R conflict = a parsing table state where shift and reduce are both valid → grammar not LR for that method.}}$
Q4a. Given the Syntax-Directed Definition below with the synthesized attribute val. Draw the annotated parse tree for the expression (3+4) * (5+6) L \to E, L.val = E.val E \to T, E.val = T.val E \to E_1 + T, E.val = E_1.val + T.val T \to F, T.val = F.val T \to T_1 * F, T.val = T_1.val * F.val F \to (E), F.val = E.val F \to digit, F.val = digit.lexval20237m
Module 3: Semantic Analysis, Symbol Table, Run-time environment
Given the Syntax-Directed Definition below with the synthesized attribute val. Draw the annotated parse tree for the expression $(3+4) * (5+6)$

$L \to E$ , $L.val = E.val$
$E \to T$ , $E.val = T.val$
$E \to E_1 + T$ , $E.val = E_1.val + T.val$
$T \to F$ , $T.val = F.val$
$T \to T_1 * F$ , $T.val = T_1.val * F.val$
$F \to (E)$ , $F.val = E.val$
$F \to digit$ , $F.val = digit.lexval$

View this question on its own page →
Search Google Ask AI
Worked Solution
Annotated parse tree for $(3+4)\times(5+6)$

Syntax-directed definition (synthesized val):

$L \to E$ , $\ L.val = E.val$

$E \to T$ , $E.val = T.val$

$E \to E_1+T$ , $E.val = E_1.val + T.val$

$T \to F$ , $T.val = F.val$

$T \to T_1*F$ , $T.val = T_1.val \times F.val$

$F \to (E)$ , $F.val = E.val$

$F \to \text{digit}$ , $F.val = \text{digit.lexval}$

Parse tree with every node's val annotated (evaluated bottom-up):

L ─ E.val = 77 (L → E, L.val = E.val) | E.val = 77 (E → T, E.val = T.val) | T.val = 77 (T → T1 * F, T.val = 7 * 11) / \ T1.val = 7 F.val = 11 | | F.val = 7 F → ( E ) .val = 11 F → ( E ) .val=7 | | E → E1 + T .val = 5 + 6 = 11 E.val = 7 / \ E1.val = 3 T.val = 3 ? ... (details below)

To avoid a confusing drawing, here is the node-by-node annotated tree (the expected exam answer):

L → E : val = 77 E → T : val = 77 T → T1 * F : val = T1.val * F.val = 7 * 11 = 77 Left subtree (3+4): T1 → F : val = 7 F → (E) : val = 7 [parenthesized] E → E1 + T E1 → T → F → digit(3) : val = 3 T → F → digit(4) : val = 4 E.val = 3 + 4 = 7 ⇒ T1 (left factor) val = 7 Right subtree (5+6): F → ( E ) : val = 11 [parenthesized] E → E1 + T E1 → T → F → digit(5) : val = 5 T → F → digit(6) : val = 6 E.val = 5 + 6 = 11 ⇒ F (right factor) val = 11 Root: T.val = 7 * 11 = 77, E.val = 77, L.val = 77

Each digit is a leaf via $F\to\text{digit}$ , with $F.val = \text{digit.lexval}$ (3, 4, 5, 6).

$\boxed{E.val = 7 \times 11 = 77}$
Q4b. Find the FIRST an FOLLOW form the following production: S \to aBDh B \to cC C \to bC | \epsilon D \to EF E \to g | \epsilon F \to f | \epsilon20237m
Module 2: Syntax Analysis (Parser)
Find the FIRST an FOLLOW form the following production:
$S \to aBDh$
$B \to cC$
$C \to bC | \epsilon$
$D \to EF$
$E \to g | \epsilon$
$F \to f | \epsilon$

View this question on its own page →
Search Google Ask AI
Worked Solution
First and Follow for the given grammar

Grammar:
$\begin{array}{rcl} S &\to& aBDh\\ B &\to& cC\\ C &\to& bC \mid \epsilon\\ D &\to& EF\\ E &\to& g \mid \epsilon\\ F &\to& f \mid \epsilon \end{array}$

Step 1 — FIRST sets

Compute allowed terminals that begin derivations (plus $\epsilon$ if nullable).

$\mathrm{FIRST}(a) = \{a\},\ \mathrm{FIRST}(b)=\{b\},\ \mathrm{FIRST}(c)=\{c\},\ \mathrm{FIRST}(g)=\{g\},\ \mathrm{FIRST}(f)=\{f\},\ \mathrm{FIRST}(h)=\{h\}$

$\mathrm{FIRST}(C) = \{b, \epsilon\}$ (from $C\to bC$ and $C\to\epsilon$ )

$\mathrm{FIRST}(E) = \{g, \epsilon\}$

$\mathrm{FIRST}(F) = \{f, \epsilon\}$

$\mathrm{FIRST}(D)$ : $D\to EF$ . FIRST(E)= $\{g,\epsilon\}$ → take $g$ ; since E nullable, take FIRST(F)= $\{f,\epsilon\}$ → $f$ ; since both nullable, include $\epsilon$ .
$\mathrm{FIRST}(D) = \{g, f, \epsilon\}$

$\mathrm{FIRST}(B) = \{c\}$ (from $B\to cC$ ). (B is not nullable since $c$ is a terminal.)

$\mathrm{FIRST}(S)$ : $S\to aBDh$ → starts with terminal a.
$\mathrm{FIRST}(S) = \{a\}$

Step 2 — FOLLOW sets

The follow of a nonterminal $X$ is the set of terminals that can appear immediately to the right of $X$ in some sentential form.

$FOLLOW(S)$ : S is the start symbol → ${$}$.
$\mathrm{FOLLOW}(S) = \{\$\}$

$FOLLOW(B)$ : from $S\to a\,B\,D\,h$ , after $B$ comes $D$ , so we add $\mathrm{FIRST}(D)\setminus\{\epsilon\} = \{g,f\}$ . Also $D$ is nullable, so we add $\mathrm{FOLLOW}(S) = {$}$.
$\mathrm{FOLLOW}(B) = \{g,\ f,\ \$\}$

$FOLLOW(C)$ : from $B\to c\,C$ (C at the end), so $\mathrm{FOLLOW}(C) = \mathrm{FOLLOW}(B)$ .
$\mathrm{FOLLOW}(C) = \{g,\ f,\ \$\}$

$FOLLOW(D)$ : from $S\to aBD\,h$ , after $D$ comes terminal h.
$\mathrm{FOLLOW}(D) = \{h\}$

$FOLLOW(E)$ : from $D\to E\,F$ , after $E$ comes $F$ , so add $\mathrm{FIRST}(F)\setminus\{\epsilon\} = \{f\}$ . Since $F$ is nullable, also add $\mathrm{FOLLOW}(D)=\{h\}$ .
$\mathrm{FOLLOW}(E) = \{f,\ h\}$

$FOLLOW(F)$ : from $D\to EF$ (F at the end), so $\mathrm{FOLLOW}(F) = \mathrm{FOLLOW}(D)$ .
$\mathrm{FOLLOW}(F) = \{h\}$

Final answer:
${\small \mathrm{FIRST}(S)=\{a\},\quad \mathrm{FIRST}(B)=\{c\},\quad \mathrm{FIRST}(C)=\{b,\epsilon\},\quad \mathrm{FIRST}(D)=\{g,f,\epsilon\},\quad \mathrm{FIRST}(E)=\{g,\epsilon\},\quad \mathrm{FIRST}(F)=\{f,\epsilon\}}$
${\small \mathrm{FOLLOW}(S)=\{\$\},\quad\mathrm{FOLLOW}(B)=\{g,f,\$\},\quad\mathrm{FOLLOW}(C)=\{g,f,\$\},\quad\mathrm{FOLLOW}(D)=\{h\},\quad\mathrm{FOLLOW}(E)=\{f,h\},\quad\mathrm{FOLLOW}(F)=\{h\}}$

Q5a. Construct the predictive parsing table for the following grammars: S \to AaAb | BbBa A \to \epsilon B \to \epsilon20237m

Module 2: Syntax Analysis (Parser)

Construct the predictive parsing table for the following grammars:
$S \to AaAb | BbBa$
$A \to \epsilon$
$B \to \epsilon$

View this question on its own page →

Search Google Ask AI

Worked Solution

Predictive (LL(1)) parsing table

Grammar:
$S \to AaAb \mid BbBa\\ A \to \epsilon\\ B \to \epsilon$

Step 1 — FIRST and FOLLOW

$\mathrm{FIRST}(A) = \{\epsilon\}$ , $\mathrm{FIRST}(B) = \{\epsilon\}$ .

For $S\to AAAb$ : because $A\to\epsilon$ , the first of the right-hand string is a. For $S\to BbBa$ : the first is b. Hence:
$\mathrm{FIRST}(S) = \{a, b\}$

FOLLOW:

$S$ is start → $\mathrm{FOLLOW}(S) = {$ }$.
From $S\to AaAb$ : the first $A$ is followed by a, the second $A$ by b.
$\mathrm{FOLLOW}(A) = \{a, b\}$
From $S\to BbBa$ : first $B$ followed by b, second $B$ by a.
$\mathrm{FOLLOW}(B) = \{a, b\}$

Step 2 — build table $M[X][\text{terminal}]$

For each production $X\to\alpha$ , put $X\to\alpha$ into $M[X][t]$ for every $t\in \mathrm{FIRST}(\alpha)$ ; if $\alpha \Rightarrow \epsilon$ , also put it into $M[X][t]$ for every $t\in\mathrm{FOLLOW}(X)$ .

For $S \to AaAb$ : $\mathrm{FIRST}(AaAb)=\{a\}$ → entry $M[S][a] = S\to AaAb$ .
For $S \to BbBa$ : $\mathrm{FIRST}=\{b\}$ → $M[S][b] = S\to BbBa$ .
For $A\to\epsilon$ : place under $\mathrm{FOLLOW}(A)=\{a,b\}$ → $M[A][a]=A\to\epsilon$ , $M[A][b]=A\to\epsilon$ .
For $B\to\epsilon$ : $\mathrm{FOLLOW}(B)=\{a,b\}$ → $M[B][a]=B\to\epsilon$ , $M[B][b]=B\to\epsilon$ .

Predictive parsing table (blank cells = error, no production):

Nonterminal	`a`	`b`	`$`
$S$	$S\to AaAb$	$S\to BbBa$	—
$A$	$A\to\epsilon$	$A\to\epsilon$	—
$B$	$B\to\epsilon$	$B\to\epsilon$	—

Verification: Every cell has at most one entry, so the grammar is LL(1) — no conflicts. This is the classic example of an LL(1) grammar with $A\to\epsilon,\ B\to\epsilon$ that resolves the choice using lookahead.

Q5b. Explain how type checking and error reporting are performed in compiler. Draw syntax tree and DAG for the statement: a = (a * b + c) \uparrow (b + c) * b + c20237m
Module 3: Semantic Analysis, Symbol Table, Run-time environment
Explain how type checking and error reporting are performed in compiler. Draw syntax tree and DAG for the statement:
$a = (a * b + c) \uparrow (b + c) * b + c$

View this question on its own page →
Search Google Ask AI
Worked Solution
Type checking, error reporting, and the syntax tree / DAG for
$a = (a*b + c) \uparrow (b+c)*b + c$

Part 1 — Type checking

Type checking verifies each operator's operands have the expected type and computes/infers the result type while traversing the syntax tree.

It is typically performed in the semantic-analysis phase using a syntax-directed definition where each expression node carries a synthesized type attribute, e.g. $T_E = f(T_{E_1}, T_T)$ for $E \to E_1+T$ .

Type synthesis: int + int → int, float op … → float; conversions (e.g. int → float) may be inserted automatically as a unary node inttofloat (type coercion).

Checking can be static (compile time) or dynamic (run time).

Part 2 — Error reporting

Each phase reports its errors to a central error handler: lexical (illegal token), syntactic (parse errors, e.g. mismatched brackets), semantic (type mismatch, undeclared/unused variable).

The parser uses error-recovery strategies (panic mode, error productions, phrase-level recovery) so it can report more than one syntax error in a single run.

Semantic errors are reported with line number, offending token, and message; code generation is attempted only when there are no fatal errors.

Part 3 — Syntax tree for the statement

a = (a*b + c) ↑ (b + c)*b + c

Precedence order: ↑ > * > +. So the RHS reads as:

$(a*b + c)\ \uparrow\ ((b+c)*b)\ +\ c$

Syntax tree (AST):

= / \ a + / \ ↑ c / \ (a*b + c) ( (b+c) * b ) / \ / \ (a*b) + c (b+c) b / \ / \ a b b c Equivalently, using operator-labelled nodes: = / \ a + / \ (↑) c / \ (a*b+c) * (mul) | / \ (a*b)+c (b+c) b / \ / \ (a*b) c b c / \ a b

DAG (Directed Acyclic Graph)

In the DAG, each unique subexpression appears exactly once; repeated uses share the same node.

The statement contains these distinct nodes (reading bottom-up):

a*b — node * with leaves (a, b)

(a*b)+c — node + over (1) and leaf c

b+c — node + with leaves (b, c)

(b+c)*b — node * over (3) and leaf b

↑ — node ↑ over (2) and (4)

RHS + c — node + over (5) and leaf c

a = RHS — node = with leaves (a, 6)

= / \ a + ← (6) / \ ↑ c / \ (a*b)+c (b+c)*b ← nodes (2), (4) / \ / \ (a*b) c (b+c) b ← nodes (1), (3) / \ / \ a b b c

Note the leaf b and c are each single nodes shared by all their uses (this is what makes it a DAG rather than a tree).

Q6a. What is handle? Consider the grammar: E \to E + E | E * E | id Find the handles of the right sentential forms of the reduction for the string id + id * id.20235m

Module 2: Syntax Analysis (Parser)

What is handle? Consider the grammar:
$E \to E + E | E * E | id$
Find the handles of the right sentential forms of the reduction for the string $id + id * id$ .

View this question on its own page →

Search Google Ask AI

Worked Solution

Handle; reduction of id + id * id with grammar $E\to E+E \mid E*E \mid \text{id}$

What is a handle?

A handle of a (right) sentential form is a substring that matches the right-hand side of some production, and whose reduction to the left-hand-side nonterminal is a step in a rightmost (reverse) derivation — that is, the rightmost handle that, when reduced, produces a valid step toward the start symbol.

In shift–reduce parsing we repeatedly prune handles: shift symbols onto the stack until the top stack symbols match a production RHS, then reduce (replace the handle by its nonterminal).

Find the handles for id + id * id

Grammar: $E\to E+E \mid E*E \mid id$ . The (unique, rightmost) reduction sequence:

Stack (top shown last)	Input	Action	Handle reduced
`id`	`+ id * id`	shift `id`	—
`E`	`+ id * id`	reduce `id → E`	handle `id`
`E +`	`id * id`	shift `+`	—
`E + id`	`* id`	shift `id`	—
`E + E`	`* id`	reduce	handle `id` (2nd)
`E + E *`	`id`	shift `*`	—
`E + E * id`	(empty)	shift	—
`E + E * E`		reduce	handle `id` (3rd)
`E + E`		reduce `E*E → E`	*handle `EE`**
`E`		reduce `E+E → E`	handle `E+E`

Handles (in reduction order), with the actual substrings:

id (first id on the left)
id (the middle id)
id (the id after *)
E * E (the redex E*E → E)
E + E (the redex E+E → E)

Written against the original string, the reduction is a reverse of the rightmost derivation:
$id + id * id \;\xrightarrow{\text{reduce id}} E + id*id \xrightarrow{\text{reduce id}} E+E*id \xrightarrow{} E+E*E \xrightarrow{E+E} \xrightarrow{E}$
The seeds/handles reduced, going left-to-right on the string: the *ids**, then EE, then E + E`.

Budget App•POCKETLY
Pocketly on Android
Log daily food, travel, and hostel expenses instantly. Set monthly spending limits and see where your money goes without complex spreadsheets.
Install Pocketly
Q6b. When a grammar is called ambiguous? Is there any technique to remove ambiguity? Justify whether the grammar is ambiguous or not? A \to AA | (A) | a20234m
Module 2: Syntax Analysis (Parser)
When a grammar is called ambiguous? Is there any technique to remove ambiguity? Justify whether the grammar is ambiguous or not?
$A \to AA | (A) | a$

View this question on its own page →
Search Google Ask AI
Worked Solution
Ambiguous grammar; ambiguity removal; is $A \to AA \mid (A) \mid a$ ambiguous?

1. When is a grammar called ambiguous?

A grammar is called ambiguous when there exists at least one string in its language that has two or more distinct parse trees (equivalently, two different leftmost or two different rightmost derivations).

2. Techniques to remove ambiguity

Grammar rewriting (precedence/associativity): restructure the grammar with separate levels, e.g. expr → expr + term | term, term → term * factor | factor, so that operators bind with the intended precedence and associativity.

Parser-tool directives: in YACC/Bison, use precedence declarations %left / %right / %nonassoc to resolve conflicts (e.g. %left '+', %left '*').

Explicit structure: for left-associative operators use left recursion; for the dangling-else problem use separate matched/unmatched statement nonterminals.

Caveat: removing ambiguity from an arbitrary grammar is undecidable in general, but for practical expression grammars these techniques work.

3. Justify whether $A \to AA \mid (A) \mid a$ is ambiguous

Yes — this grammar is ambiguous.

The string aaa has two distinct parse trees:

Tree 1 (grouping as a (a a)): root A → A A, left A → a, right A → A A with children a a:

A / \ a A / \ a a

Tree 2 (grouping as (a a) a): root A → A A, left A → A A with children a a, right A → a:

A / \ A a / \ a a

Both trees derive the same string aaa with different structure ⇒ the grammar is ambiguous. The root cause is the production $A \to AA$ — two adjacent occurrences of the same nonterminal admit two groupings of any consecutive run of a's.

A fix for this grammar: make the concatenation left- or right-associative explicitly, e.g. $A \to A\,\mathbf{star}$ , or add a priority marker — but more importantly, grammar $A\to AA\mid a\mid (A)$ is inherently ambiguous, so a parser generator such as YACC would report a conflict for it. In practice prepend associativity info (%left) or rewrite to an unambiguous grammar such as $A \to A\,\text{cat} \mid (A) \mid a$ with cat a real operator.

$\boxed{\text{A} \to A A \mid (A) \mid a\ \text{IS ambiguous — the string } aaa \text{ has two parse trees.}}$
Q6c. Discuss about operator precedence parser.20235m
Module 2: Syntax Analysis (Parser)
Discuss about operator precedence parser.

View this question on its own page →
Search Google Ask AI
Worked Solution
Operator-Precedence Parser

1. What it is

An operator-precedence (OP) parser is a bottom-up shift–reduce parser whose shift/reduce decision is based only on a precedence relation table between terminal symbols (operators) — not on a full LR state machine.

2. Operator grammar preconditions

The grammar must be an operator grammar:

no $\epsilon$ -production,

no two adjacent nonterminals on any right-hand side.

3. Precedence relations

Between terminals a and b:

$a \lessdot b$ — a has lower precedence than b (→ shift b)

$a \doteq b$ — equal precedence (→ shift)

$a \gtrdot b$ — a has higher precedence than b (→ reduce)

Computed from the grammar using the FIRST/LAST terminal sets:

if $\alpha\, a\, B\, \beta$ and $b\in \mathrm{FIRST}(B)$ then $a \lessdot b$ ;

if $A\to \alpha\, a b\, \beta$ then $a \doteq b$ ;

if $A\to \alpha\, B\, b\,\beta$ and $a\in \mathrm{LAST}(B)$ then $a \gtrdot b$ .

This yields the operator-precedence matrix $M[t_1][t_2]$ for all terminal pairs.

4. Algorithm (stack with $` at bottom; input ends with `$ ):

Compare precedence of the input symbol with the relevant top-of-stack terminal.

If top $\lessdot$ next, or top $\doteq$ next → shift the next token.

If top $\gtrdot$ next → a handle boundary has been found: scan back until the first preceding $\lessdot$ relation; the substring between them is the handle → reduce it to its nonterminal. No state/lookahead table needed.

Accept when the stack holds exactly the start symbol with no input left.

5. Example — id + id * id with precedence * > +

stack: $ id + id * id shift id, shift +, shift id when `*` (input) and top `id` reduce id→E... then top `*` vs input `+`: since `*` ⋗ `+`, reduce E*E before E+ → matches the expected "multiply before add" behaviour.

6. Advantages & disadvantages

Advantages:

very fast (simple matrix lookup), small table,

easy to implement (no GOTO states).

Disadvantages:

works only for operator grammars (no adjacent nonterminals, no $\epsilon$ ),

handle detection is purely local — it ignores surrounding context, so many real languages need LR/LALR instead,

usually used in small/expression-oriented compilers or inside calculator-style evaluators.

Example precedence table (* binds tighter than +):

op + *

+ $\doteq, \gtrdot$ $\lessdot$

* $\gtrdot$ $\gtrdot$

Rule: shift on $\lessdot$ / $\doteq$ , reduce on $\gtrdot$ — which reproduces standard arithmetic precedence.

op	`+`	`*`
`+`	$\doteq, \gtrdot$	$\lessdot$
`*`	$\gtrdot$	$\gtrdot$

Q7a. Differentiate between S-attribute SDT and L-attribute SDT with suitable examples.20237m

Module 3: Semantic Analysis, Symbol Table, Run-time environment

Differentiate between S-attribute SDT and L-attribute SDT with suitable examples.

View this question on its own page →

Search Google Ask AI

Worked Solution

S-attribute SDT vs L-attribute SDT

S-Attribute (Synthesized) SDTs

An SDT is S-attributed ("synthesized") if every attribute is a synthesized attribute — computed from the children of a nonterminal.
All the evaluation is bottom-up.
An S-attributed SDT can be evaluated during a bottom-up parse — the semantic action is placed at the right end of the production: A → α { do action }.
Supported: only bottom-up based LL/LR? Precisely: LR parser can implement any S-attributed SDD without changing the parsing stack (just attach the attributes value with each stack symbol).

L-Attributed SDTs

An SDT is L-attributed when:
1. each attribute is either synthesized, or inherited, and
2. inherited attributes depend only on: attributes of the left siblings, the parent, and attributes of the symbols themselves (i.e. dependencies can flow from left to right, and from parent → children).
Condition: In the production $A \to X_1 X_2 \dots X_n$ $A \to X_{1} X_{2} \dots X_{n}$ , an inherited attribute of $X_i$ $X_{i}$ can only depend on:
- attributes of $X_1,X_2,\dots, X_{i-1}$ (the symbols to its left), and
- inherited attributes of $A$ (the parent).
Evaluation is basically top-down / left-to-right — works with LL / predictive parsers too, and can be implemented in a top-down or LR parser with suitable actions.

Key differences:

Point	S-attributed	L-attributed
Attributes	All synthesized	synthesized + inherited (with L- constraint)
Evaluation pass	bottom–up	depth-first left-to-right following structure
Parser suitable	any LR / bottom-up	LL / top-down (recursive-descent; LR also if aug.)
Action placement	can move to the end of RHS	must keep in position (actions constrained)
Which is larger	—	L is a superset of S

Every S-attributed definition is also L-attributed, but not vice versa.

Example

S-attribute example: grammar with val
$E \to E_1+T \quad E.val=E_1.val+T.val$
All attributes synthesized ⇒ S-attributed (also L).

L-attribute (non-S) example: an inherited attribute such as in a C float conversion
$Y \to X_1 X_2 \quad Y.inh=...\,;\ X_1.inh=..., X_2.inh=f(Y.inh, X_1.att)$
For instance, declaring arrays:
D → T L, L → id , L_1; L.inh = T.type; L1.inh = L.inh. The inherited attribute inh must always be computed before the symbol is parsed — that's the left-to-right constraint.

Summary: an S-SDT = simply synthesized attributes; evaluate bottom-up. L-SDT = a wider class, allows inherited attributes under the restriction that they use only attributes from the left (or inherited from context above) — evaluated in a depth-first left-first traversal. Since L is a superset of S, any S-scheme is a special case of L.

Q7b. Consider the following grammar: E \to E + T | T T \to T * F | F F \to td Draw a SLR state transition diagram for the above grammar. Also draw the SLR parse table.20237m
Module 2: Syntax Analysis (Parser)
Consider the following grammar:
$E \to E + T | T$
$T \to T * F | F$
$F \to td$
Draw a SLR state transition diagram for the above grammar. Also draw the SLR parse table.

View this question on its own page →
Search Google Ask AI
Worked Solution
SLR parse for the grammar $E\to E+T\mid T$ , $T\to T*F\mid F$ , $F\to \mathbf{id}$

(The paper spells the token td; we treat it as the identifier token id.)

Augment with $E'\to E$ .

Productions numbering:

$E\to E+T$

$E\to T$

$T\to T*F$

$T\to F$

$F\to\mathbf{id}$

LR(0) canonical collection (states $I_0$ – $I_8$ ):

$I_0$ : $E'\to\cdot E,\ E\to\cdot E+T,\ E\to\cdot T,\ T\to\cdot T*F,\ T\to\cdot F,\ F\to\cdot\mathbf{id}$

$I_1 = goto(I_0,E)$ : $E'\to E\cdot$ , $E\to E\cdot+T$

$I_2 = goto(I_0,T)$ : $E\to T\cdot$ , $T\to T\cdot*F$

$I_3 = goto(I_0,F)$ : $T\to F\cdot$

$I_4 = goto(I_0,id)$ : $F\to \mathbf{id}\cdot$

$I_5 = goto(I_1,+)$ : $E\to E+\cdot T$ , $T\to\cdot T*F$ , $T\to\cdot F$ , $F\to\cdot\mathbf{id}$

$I_6 = goto(I_2,*)$ : $T\to T*\cdot F$ , $F\to\cdot\mathbf{id}$

$I_7 = goto(I_5,T)$ : $E\to E+T\cdot$ , $T\to T\cdot*F$

$I_8 = goto(I_6,F)$ : $T\to T*F\cdot$

GOTO transitions: $0\xrightarrow{E}1,\ 0\xrightarrow{T}2,\ 0\xrightarrow{F}3,\ 0\xrightarrow{id}4$ ;
$1\xrightarrow{+}5$ ; $2\xrightarrow{*}6$ ; $5\xrightarrow{T}7,\ 5\xrightarrow{F}3,\ 5\xrightarrow{id}4$ ; $6\xrightarrow{F}8,\ 6\xrightarrow{id}4$ ; $7\xrightarrow{*}6$ .

(This is the state-transition diagram; every state is a node and every label above is an edge.)

FOLLOW sets:

$\mathrm{FOLLOW}(E)={+, $} $(start) ∪ `+` from$ E\to E+T$.

$\mathrm{FOLLOW}(T)={+,,$}$ (E→E+T ⇒ FOLLOW(E), T→TF ⇒ *).

$\mathrm{FOLLOW}(F)={+,*,$}$.

SLR parsing table (ACTION + GOTO):

State id + * $ E T F

0 s4 1 2 3

1 s5 acc

2 r2 s6 r2

3 r4 r4 r4

4 r5 r5 r5

5 s4 7 3

6 s4 8

7 r1 s6 r1

8 r3 r3 r3

s n = shift and go to state n; r k = reduce by production $k$ (list above); acc = accept.

Uses FOLLOW: r4/r5 in states 3/4 for +, *, $ (in FOLLOW(T)/FOLLOW(F)) etc.

No cell has two actions → the grammar is SLR(1) (a conflict-free table), and id + id * id is accepted.
Q8a. Consider the following grammar: S \to CC C \to cC | d Find the LR(1) set of items.20235m
Module 2: Syntax Analysis (Parser)
Consider the following grammar:
$S \to CC$
$C \to cC | d$
Find the LR(1) set of items.

View this question on its own page →
Search Google Ask AI
Worked Solution
LR(1) sets of items for $S\to CC$ , $C\to cC\mid d$

Augmented grammar: $S'\to S$ .

Items are written $[A\to\alpha\cdot\beta,\ a]$ where a is the lookahead terminal.

Closure hint: from $[S\to \cdot CC,\ $] $, the symbol after the dot is$ C $and the lookahead context of$ C\to\cdots $is$ \mathrm{FIRST}(C$)={c,d} $, so inner$ C $-items receive lookaheads$ {c,d}$.

Canonical LR(1) collection:

$I_0$ : $[S'\to\cdot S,$],\ [S\to\cdot CC,$],\ [C\to\cdot cC,\ c/d],\ [C\to\cdot d,\ c/d]$

$I_1$ = goto $(I_0,S)$ : $[S'\to S\cdot,$]$

$I_2$ = goto $(I_0,C)$ : $[S\to C\cdot C,$],\ [C\to\cdot cC,$],\ [C\to\cdot d,$]$

$I_3$ = goto $(I_0,c)$ : $[C\to c\cdot C,\ c/d],\ [C\to\cdot cC,\ c/d],\ [C\to\cdot d,\ c/d]$

$I_4$ = goto $(I_0,d)$ : $[C\to d\cdot,\ c/d]$

$I_5$ = goto $(I_2,C)$ : $[S\to CC\cdot,$]$

$I_6$ = goto $(I_2,c)$ : $[C\to c\cdot C,$],\ [C\to\cdot cC,$],\ [C\to\cdot d,$]$

$I_7$ = goto $(I_2,d)$ : $[C\to d\cdot,$]$

$I_8$ = goto $(I_3,C)$ : $[C\to cC\cdot,\ c/d]$

$I_9$ = goto $(I_6,C)$ : $[C\to cC\cdot,$]$

GOTO function:

goto $(I_0,S)$ = $I_1$ ; goto $(I_0,C)$ = $I_2$ ; goto $(I_0,c)$ = $I_3$ ; goto $(I_0,d)$ = $I_4$

goto $(I_2,C)$ = $I_5$ ; goto $(I_2,c)$ = $I_6$ ; goto $(I_2,d)$ = $I_7$

goto $(I_3,C)$ = $I_8$ ; goto $(I_3,c)$ = $I_3$ ; goto $(I_3,d)$ = $I_4$

goto $(I_6,C)$ = $I_9$ ; goto $(I_6,c)$ = $I_6$ ; goto $(I_6,d)$ = $I_7$

So the canonical LR(1) machine has 10 states ( $I_0$ – $I_9$ ).

Reduce actions: $I_4$ : $C\to d$ on $\{c,d\}$ ; $I_7$ : $C\to d$ on $$ $;$ I_8 $:$ C\to cC $on$ {c,d} $;$ I_9 $:$ C\to cC $on `$ ; $I_5$ : $S\to CC$ on $`;$ I_1 $: accept on `$ `.

Bonus — LALR(1): merging states with equal cores ( $I_4\cup I_7$ , $I_3\cup I_6$ , $I_8\cup I_9$ ) gives the 7-state LALR(1) automaton, free of conflicts for this grammar.
Q8b. Translate the expression a = (a + b) * (c + d) + (a + b + c) into (i) Quadruple (ii) Triple (iii) Indirect triple20239m
Module 4: Intermediate Code Generation, Code Improvement (optimization)
Translate the expression $a = (a + b) * (c + d) + (a + b + c)$ into
(i) Quadruple
(ii) Triple
(iii) Indirect triple

View this question on its own page →
Search Google Ask AI
Worked Solution
Three-address code for $a=(a+b)*(c+d)+(a+b+c)$

Start from the natural statement sequence:

t1 = a + b t2 = c + d t3 = t1 * t2 t4 = a + b (or reuse t1) t5 = t4 + c → computes (a+b) + c t6 = t3 + t5 a = t6

(i) Quadruples

Form (op, arg1, arg2, result):

No op arg1 arg2 result

1 + a b t1

2 + c d t2

3 * t1 t2 t3

4 + a b t4

5 + t4 c t5

6 + t3 t5 t6

7 = t6 (empty) a

(ii) Triples

Three fields (op, arg1, arg2); a result value is referenced by its triple index (k).

# op arg1 arg2

1 + a b

2 + c d

3 * (1) (2)

4 + a b

5 + (4) c

6 + (3) (5)

7 = (6) a

(iii) Indirect triples

List of triples plus a separate indirect table that holds the execution-order pointers to the triples; changing an instruction (e.g. removing a common subexpression) is done by redirecting a pointer, no renumbering needed.

Triples:

# op arg1 arg2

1 + a b

2 + c d

3 * (1) (2)

4 + (1) c

5 + (3) (4)

6 = (5) a

Indirect table (execution order):

(1) → triple 1 (2) → triple 2 (3) → triple 3 (4) → triple 4 (5) → triple 5 (6) → triple 6 → assigns into a

Since triple 4 reuses triple 1 (a+b), the (a+b) subexpression appears once; that is exactly how the indirection layer makes common-subexpression elimination and code motion easy.

Summary

Quadruple: explicit result names — easiest to manipulate, most commonly used in optimizers.

Triple: compact (no temporaries), but moving/deleting statements requires renumbering.

Indirect triple: triples + index vector — easy CSE/code motion at the price of one extra level of indirection.
Q9. Write short notes on any two of the following: (a) LEX and YACC (b) Peephole Optimization (c) Symbol Table (d) Predictive parser202314m
Module 1: Introduction, Lexical Analysis
Write short notes on any two of the following:
(a) LEX and YACC
(b) Peephole Optimization
(c) Symbol Table
(d) Predictive parser

View this question on its own page →
Search Google Ask AI
Worked Solution
Short notes (any two)

(a) LEX and YACC

LEX is the lexical-analyzer generator. It takes a specification of token patterns written with regular expressions and produces a C function (e.g. yylex) that scans the input and returns tokens.

Structure of a LEX program: declaration %% translation rules %% auxiliary functions.

Each token rule: pattern → action (action = C code, e.g. return token_id;).

Powers: longest-match rule; a symbol table kept for identifiers/text. Used with YACC. LEX produces the scanner that feeds tokens to the parser.

YACC ("Yet Another Compiler-Compiler") is the parser generator, producing a LALR(1) (or YACC's default SLR/LALR) parser (function yyparse) from a CFG grammar in BNF with embedded semantic actions.

Structure: %{ declarations %} %% productions { semantic action } %% subroutines.

Uses the tokens lexed by LEX; each grammar rule may have a semantic value and user code; supports precedence and associativity declarations (%left, %right); optionally builds an AST via actions.

Together: LEX gives tokens to YACC, YACC builds the parse tree and schedules the semantic translation.

(b) Peephole Optimization

A simple but effective local, post-optimization technique performed on the target (assembly/machine) code over a small window ("peephole") of adjacent instructions.

Techniques in a peephole optimizer:

Redundant instruction elimination (dead code): e.g. MOV R0, R1; MOV R0, R1 — delete the second.

Flow-of-control optimizations: e.g. jumps to jumps (JMP L; ... L: JMP L1) — replace with direct jump.

Algebraic simplifications: x + 0 → x; x*1 → x; x/2` → shift etc.

Reduction in strength: replace expensive ops like 2 * x with x + x and x^2.

Use of machine idioms: e.g. X = X + 0 removed, X+1 replaced by INC/INC and X<<n for X * 2^n.

Constant folding inside window.

Advantage: very cheap, catches a lot; often run repeatedly.

(c) Symbol Table

A compile-time data structure that maps identifiers (names) to their attributes: name, type, category (variable, function, record/array), address (stack/relative/global offset), scope & lifetime, parameter list, and kind (static, local).

Operations: insert (add new name), lookup/access (find entry), modify; the table is consulted/modified during every phase — lexical (insert), syntax/semantic (lookup/check type), code gen (get address).

Organization:

Lists / hash tables; open (separate chaining) or closed addressing for speed.

Scoping: block structure ⇒ re-entrant by saved-bottom markers; often a stack of scopes with a new.. pointer (scope stack).

Multiple table organizations: (1) flat global, (2) per-scope linked lists, (3) tree/structural block table (often implemented as stack-based with block index markers).

Lookup in nested scopes follows lexical chain (innermost outward). Implementations use hash table for names with scope table.

Applications: optimize code-gen (address known), type checking, overloading, and reporting.

(d) Predictive parser

A predictive parser (or LL(1) table parser) is a non-backtracking top-down parser. It uses a parsing table M[A][a], the input's next symbol a, and a stack of grammar symbols to decide deterministically ("predict") which production to apply without backtracking.

Table-driven: stack holds nonterminals (and $); at each step, if top of stack is terminal, match with input; if it's a nonterminal, use entry M[top][a] to choose the production for A.

Table is built from FIRST and FOLLOW sets: M[A][a] = A→α if a∈FIRST(α), or (if α nullable) if a∈FOLLOW(A).

A given grammar can be predictive only when it is LL(1): no multiple entries (no conflict) in any table cell and left-recursion removed + factorized.

Also called recursive-descent parser when implemented with recursive functions, each nonterminal being one function that calls other via the table (though classic "predictive parser" = table-driven with no backtracking).

Algorithm: repeat — look at top X and next input a:

if X is a, advance both;

if X is nonterminal and M[X][a] = X→Y1..Yk, pop X push Yk…Y1 (reverse feedback);

if M entry empty → error.

Accept when stack = $` and input = `$ .

Characteristics: no backtracking ⇒ linear time (O(n) for LL(1)); works for all LL(1) grammars; fastest top-down method; the classic example is predicting grammar E → T E', etc.

No	op	arg1	arg2	result
1	+	a	b	t1
2	+	c	d	t2
3	*	t1	t2	t3
4	+	a	b	t4
5	+	t4	c	t5
6	+	t3	t5	t6
7	=	t6	(empty)	a

#	op	arg1	arg2
1	+	a	b
2	+	c	d
3	*	(1)	(2)
4	+	a	b
5	+	(4)	c
6	+	(3)	(5)
7	=	(6)	a

#	op	arg1	arg2
1	+	a	b
2	+	c	d
3	*	(1)	(2)
4	+	(1)	c
5	+	(3)	(4)
6	=	(5)	a

Next year2026

Free AppAndroid App

Coursify Android App

Generate AI courses, take quick quizzes between classes, and master complex engineering concepts on the go.

Install Coursify

State	id	+	*	$	E	T	F
0	s4				1	2	3
1		s5		acc
2		r2	s6	r2
3		r4	r4	r4
4		r5	r5	r5
5	s4					7	3
6	s4						8
7		r1	s6	r1
8		r3	r3	r3

Compiler Design

Pocketly on Android

FIRST

2. Compute FOLLOW(X) for every nonterminal X

Pocketly on Android

(i) Quadruples

(ii) Triples

(iii) Indirect triples

Summary

(a) LEX and YACC

(b) Peephole Optimization

(c) Symbol Table

(d) Predictive parser

Coursify Android App