Compiler Design GATE previous year questions with answer

Given:
Three statements about parsing power:
I. Canonical LR is more powerful than SLR.
II. SLR is more powerful than LALR.
III. SLR is more powerful than canonical LR.
To find:
Which of the statements is/are correct.
Solution:
Let me recall the hierarchy of power for bottom-up LR parsers.
The parsing power increases as follows:
LR(0) < SLR(1) < LALR(1) < CLR(1)<br>This means every SLR(1) grammar is an LALR(1) grammar, and every LALR(1) grammar is a CLR(1) grammar.
So CLR(1) is the most powerful among them, followed by LALR(1), then SLR(1), and LR(0) is the least powerful.
Now let's check statement I:
"Canonical LR is more powerful than SLR."
Since CLR(1) > SLR(1), this statement is correct.
Now checking statement II:
"SLR is more powerful than LALR."
Since LALR(1) is actually more powerful than SLR(1), this statement is false.
Now checking statement III:
"SLR is more powerful than canonical LR."
CLR(1) is more powerful than SLR(1), so this statement is also false.
Therefore, only statement I is correct.
Answer: (A) I only

Let me recall the standard order of phases in a compiler and their respective inputs.
First, the Lexical analyser takes the source code as a stream of characters and produces tokens.
So, Character Stream is the input to the Lexical analyser, which gives Q → (iv).
Next, the Syntax analyser takes the stream of tokens generated by the lexical analyser and builds a parse tree or syntax tree.
So, Token stream is the input to the Syntax analyser, which gives S → (ii).
Next, the Semantic analyser takes the syntax tree to check for semantic consistency and type checking.
So, Syntax Tree is the input to the Semantic analyser, which gives P → (iii).
Finally, the Code generator takes the intermediate representation (IR) to generate target machine code.
So, Intermediate representation is the input to the Code generator, which gives R → (i).
Combining all the pairs, I get:
P → (iii), Q → (iv), R → (i), S → (ii).
Looking at the options, this directly matches Option C.
Answer:
(C) P -> (iii), Q -> (iv), R -> (i), S -> (ii)

To match the concepts related to compiler design and runtime environments, let us analyze each item individually.
Analyze each matching pair:
• (P) Lexical analysis: This is the first phase of a compiler where the input source code is broken down into a stream of tokens. The patterns for these tokens (like keywords, identifiers, operators) are typically defined using regular expressions. Finite automata, derived from regular expressions, are used to implement lexical analyzers (scanners).     Therefore, (P) Lexical analysis matches with (iii) Regular expressions.

• (Q) Top down parsing: Top-down parsing is a parsing strategy that starts from the start symbol of the grammar and tries to derive the input string by applying production rules. This process corresponds to constructing a parse tree from the root downwards. A key characteristic of top-down parsers is that they typically produce a leftmost derivation of the input string.     Therefore, (Q) Top down parsing matches with (i) Leftmost derivation.

• (R) Semantic analysis: This phase of the compiler checks for the semantic correctness of the program, ensuring that the code adheres to the language's rules beyond just syntax. A primary task of semantic analysis is type checking, which verifies that operations are applied to compatible data types (e.g., ensuring an integer is not added to a string without proper conversion).     Therefore, (R) Semantic analysis matches with (ii) Type checking.

• (S) Runtime environments: A runtime environment refers to the state of a program during its execution, including memory organization, variable storage, and function call management. Activation records (also known as stack frames) are data structures used to manage information for each active function call. They are pushed onto the call stack when a function is invoked and contain local variables, parameters, return addresses, etc.     Therefore, (S) Runtime environments matches with (iv) Activation records.

Consolidate the matches:
• P ↔ iii
• Q ↔ i
• R ↔ ii
• S ↔ iv

Comparing these matches with the given options, option B aligns perfectly with our findings.

Given:
SDTS rules:
S → aA { print 1 }
S → a { print 2 }
A → Sb { print 3 }
Input string: aab
To find:
The output printed by a bottom-up parser.
Solution:
First, let me write down the parse tree that derives the string "aab":
S → a A
A → S b
S → a
Let me trace the shift-reduce steps of the bottom-up parser live on the input "aab$":
Start with an empty stack.
Shift the first 'a'. Stack = [a], Remaining input = ab$
If I reduce this first 'a' to S, the stack becomes [S], but no production rule starts with "S a", so the parser won't reduce here.
Shift the second 'a'. Stack = [a, a], Remaining input = b$
Now, the handle at the top of the stack is the second 'a', which reduces using S → a.
So, reduction 1: S → a. Stack becomes [a, S].
This executes the semantic action: print 2.
Now shifting the next symbol 'b'.
Stack = [a, S, b], Remaining input = $
The handle "Sb" matches the production rule A → Sb.
So, reduction 2: A → Sb. Stack becomes [a, A].
This executes the semantic action: print 3.
Now the handle "aA" matches the production rule S → aA.
So, reduction 3: S → aA. Stack becomes [S].
This executes the semantic action: print 1.
The start symbol S is reached and input is fully consumed, so the parser accepts.
Writing the outputs in sequence: 2 3 1.
Answer: (C) 2 3 1

Given Grammar:
The grammar G is:
S → F  |  H
F → p  |  c
H → d  |  c
Where S, F, H are non-terminals, and p, d, c are terminals.
Check for LL(1) Property (Statement S1):
A grammar is LL(1) if, for every non-terminal A with productions A → α₁ | α₂ | ... | α_k, the following conditions hold:
• For any two distinct productions A → α_i and A → α_j, the sets FIRST(α_i) and FIRST(α_j) must be disjoint (i.e., FIRST(α_i) ∩ FIRST(α_j) = ∅).
• If ε ∈ FIRST(α_i), then FIRST(α_j) ∩ FOLLOW(A) = ∅ for all j ≠ i.

Let's compute the FIRST sets for the productions:
• FIRST(p) = {p}
• FIRST(c) = {c}
• FIRST(d) = {d}

• For non-terminal F:
    F → p     → FIRST(p) = {p}
    F → c     → FIRST(c) = {c}
    So, FIRST(F) = {p, c}

• For non-terminal H:
    H → d     → FIRST(d) = {d}
    H → c     → FIRST(c) = {c}
    So, FIRST(H) = {d, c}

• For non-terminal S:
    S → F     → FIRST(F) = {p, c}
    S → H     → FIRST(H) = {d, c}

Now, let's check the LL(1) condition for S:
• We have productions S → F and S → H.
• We need to check if FIRST(F) ∩ FIRST(H) is empty.
• FIRST(F) = {p, c}
• FIRST(H) = {d, c}
• FIRST(F) ∩ FIRST(H) = {c}

Since the intersection {c} is not empty, the grammar fails the LL(1) condition for non-terminal S. An LL(1) parser would not know whether to choose the production S → F or S → H when the next input symbol is 'c'.
Therefore, statement S1 is incorrect.
Check for LR(1) Property (Statement S2):
A grammar is LR(1) if its LR(1) parsing table has no shift/reduce or reduce/reduce conflicts. A key characteristic that often leads to LR conflicts is ambiguity. If a grammar is ambiguous, it cannot be LR(k) for any k.
Let's consider the string "c".
• One derivation for "c" is: S ⇒ F ⇒ c
• Another derivation for "c" is: S ⇒ H ⇒ c

Since the string "c" has two distinct leftmost derivations (or parse trees), the grammar is ambiguous.

An ambiguous grammar cannot be LR(1). During LR parsing, when the parser has processed 'c' and is about to reduce, it would be in a state with items like `F → c.` (reduce by F → c) and `H → c.` (reduce by H → c). If the lookahead symbol (which would be '$' for the entire string "c") is common to the lookahead sets of both reduce items, a reduce/reduce conflict occurs. In this case, both reductions would have '$' as a lookahead, leading to a conflict.

Therefore, statement S2 is incorrect.
Final Conclusion:
Since both S1 and S2 are incorrect, the correct option is Neither S1 and S2.

PROCESSED

PROCESSED