SYLLABUS
Lexical analysis, parsing, syntax-directed translation. Runtime environments. Intermediate code generation. Local optimisation, Data flow analyses: constant propagation, liveness analysis, common subexpression elimination.
Q1 – Which of the following is/are Bottom-Up Parser(s)?
(A) Shift-reduce Parser
(B) Predictive Parser
(C) LL(1) Parser
(D) LR Parser
Ans – (A, D)
Explanation – Option (A) – The Shift-Reduce Parser can be classified as a Bottom-Up Parser. The parser initiates at the input symbols and attempts to reduce it to the start symbol of the grammar. The parser will use operations of “shift” and “reduce”.
Option (B) The Predictive Parser can be classified as a Top-Down Parser. The parser predicts what rules to apply in accordance with the current input, and it works from the start symbol of the grammar to the input string itself.
Option (C) – The LL(1) Parser can be classified as a Top-Down Parser. The first “L” indicates that the parser processes the input from Left-to-right, and the second “L” indicates that the parser generates a Leftmost derivation. To make decisions, it requires 1 lookahead symbol.
Option (D) – The LR Parser can be classified as a Bottom-Up Parser. The parser processes the input Left-to-right, while producing a Rightmost derivation (in reverse). It is considered a very powerful, and popular type of a bottom-up parser.
Q2 – Consider the following syntax-directed definition (SDD).
𝑆→𝐷𝐻𝑇𝑈 | { 𝑆.𝑣𝑎𝑙 = 𝐷.𝑣𝑎𝑙 + 𝐻.𝑣𝑎𝑙 + 𝑇.𝑣𝑎𝑙 + 𝑈.𝑣𝑎𝑙; } |
𝐷→”M”𝐷1 | { 𝐷.𝑣𝑎𝑙 = 5 + 𝐷1.𝑣𝑎𝑙; } |
𝐷→𝜖 | { 𝐷.𝑣𝑎𝑙 = −5; } |
𝐻→”L”𝐻1 | { 𝐻.𝑣𝑎𝑙 = 5∗10 + 𝐻1.𝑣𝑎𝑙; } |
𝐻→𝜖 | { 𝐻.𝑣𝑎𝑙 = −10; } |
𝑇→”C”𝑇1 | { 𝑇.𝑣𝑎𝑙 = 5∗100 + 𝑇1.𝑣𝑎𝑙; } |
𝑇→𝜖 | { 𝑇.𝑣𝑎𝑙 = −5; } |
𝑈→”K” | { 𝑈.𝑣𝑎𝑙 = 5; } |
Given “MMLK” as the input, which one of the following options is the CORRECT value computed by the SDD (in the attribute 𝑆.𝑣𝑎𝑙)?
(A) 45
(B) 50
(C) 55
(D) 65
Ans – (A)
Explanation – This question wants you to calculate a value computed by the SDD. Input “MMLK” is given and the gramma is given.
To determine S, we need to separate “MMLK” into 4 parts.
D – something beginning with M
D -> “M” D1 -> Adds 5 each time
D -> 𝜖 -> -5 from the value
Input has 2 times M. So, +5 +5 -5 = 5
H – something beginning with L
H -> “L” H1 -> Adds 5*10 each time
H -> 𝜖 -> -10 from the value
Input has next alphabet L. So, 5*10 – 10 = 40.
T – something beginning with C
T -> “C” T1 -> Adds 5*100 each time
T -> 𝜖 -> -5 from the value
There is no C in the input. So, -5 because of no C.
U – the final letter K
U -> “K” -> Adds 5 each time
Input has next alphabet K. So, 5 because of 1 K.
Total value = 𝑆.𝑣𝑎𝑙 = 𝐷.𝑣𝑎𝑙 + 𝐻.𝑣𝑎𝑙 + 𝑇.𝑣𝑎𝑙 + 𝑈.𝑣𝑎𝑙;
Total value = 𝑆.𝑣𝑎𝑙 = 5 + 40 – 5 + 5 = 45.
Hence, option (A) is the answer.
Q3 – Consider the following grammar 𝐺, with 𝑆 as the start symbol. The grammar 𝐺 has three incomplete productions denoted by (1), (2), and (3).
𝑆 → 𝑑𝑎𝑇 | (1)
𝑇 → 𝑎𝑆 | 𝑏𝑇 | (2)
𝑅 → (3) | 𝜖
The set of terminals is {𝑎, 𝑏, 𝑐, 𝑑, 𝑓}. The FIRST and FOLLOW sets of the different non-terminals are as follows.
FIRST(𝑆) = {𝑐, 𝑑, 𝑓}, FIRST(𝑇) = {𝑎, 𝑏, 𝜖}, FIRST(𝑅) = {𝑐, 𝜖}
FOLLOW(𝑆) = FOLLOW(𝑇) = {𝑐, 𝑓, $}, FOLLOW(𝑅) = {𝑓}
Which one of the following options CORRECTLY fills in the incomplete productions?
(A) (1) 𝑆→𝑅𝑓 (2) 𝑇→𝜖 (3) 𝑅→𝑐𝑇𝑅
(B) (1) 𝑆→𝑓𝑅 (2) 𝑇→𝜖 (3) 𝑅→𝑐𝑇𝑅
(C) (1) 𝑆→𝑓𝑅 (2) 𝑇→𝑐𝑇 (3) 𝑅→𝑐𝑅
(D) (1) 𝑆→𝑅𝑓 (2) 𝑇→𝑐𝑇 (3) 𝑅→𝑐𝑅
Ans – (A)
Explanation –
Terminals: {a, b, c, d, f}
FIRST(S) = {c, d, f}
FIRST(T) = {a, b, ε}
FIRST(R) = {c, ε}
FOLLOW(S) = FOLLOW(T) = {c, f, $}
FOLLOW(R) = {f}
S → daT | (1)
T → aS | bT | (2)
R → (3) | ε
In Option A and D, S → Rf
If R → cTR | ε, then FIRST(R) = {c, ε}
So FIRST(S) = {c, d, f}
In Option B and C, S → fR
Then FIRST(S) starts with f, but now how will c be in FIRST(S)?
So, our assumption is correct. The answer is option (A) or (D).
In Option A, 𝑇 → 𝜖
If T → aS | bT | ε, then FIRST(T) = {a, b, ε}
In Option D, 𝑇 → 𝑐𝑇
If T → aS | bT | 𝑐𝑇, then FIRST(T) = {a, b, c} which is wrong.
So, our assumption is correct. The answer is option (A).