3.1 [1994: 1 Mark]
Question: Why is intermediate code for an abstract machine preferred over direct machine code?
(a) To make lexical analysis easier
(b) To make syntax analysis easier
(c) To enhance portability of front-end of compiler
(d) To improve error recovery
Answer: (c) it enhances the portability of the front end of the compiler
Explanation: Intermediate code front-end ko back-end se alag kar deta hai. Ek hi front-end se multiple machines ke liye sirf back-end badalna padta hai. Isiliye portability badhti hai.
3.2 [1995: 1 Mark]
Question: What does Linker need in object module?
(a) Object code
(b) Relocation bits
(c) Names and locations of external symbols
(d) Absolute addresses of internal symbols
Answer: (a), (b), (c) needed, (d) NOT needed
Explanation: Linker ko object code chahiye, relocation chahiye kyunki alag compilation me address shift hoga, aur external symbols chahiye. Internal symbols ka absolute address linker ka kaam nahi hai.
3.3 [1997: 2 Marks]
Question: Grammar X ::= X ⊕ Y | Y, Y ::= Z ⊙ Y | Z. What is associativity?
Options: (a) ⊕ left, ⊙ right (b) both left (c) both right (d) opposite
Answer: (a) ⊕ is left associative while ⊙ is right associative
Explanation: Left recursion = Left associative, Right recursion = Right associative. X -> X ⊕ Y is left recursion, Y -> Z ⊙ Y is right recursion.
**3.4 [1997 : 1 Mark]**
**Question:** In a bottom-up evaluation of a syntax directed definition, inherited attributes can
(a) always be evaluated
(b) be evaluated only if the definition is L-attributed
(c) be evaluated only if the definition is S-attributed
(d) never be evaluated
**Answer:** (b) be evaluated only if the definition is L-attributed
**Reason:**
Bottom-up (LR) parser me S-attributed (only synthesized) toh hamesha evaluate ho jata hai.
Inherited evaluate karna mushkil hai, sirf tab possible hai jab definition L-attributed ho (inherited sirf parent ya left sibling se aaye). Isiliye bottom-up me inherited ke liye L-attributed condition jaruri hai.
3.5 [1997: 1 Mark]
Question: SDT
S -> T R
R -> + T {print(‘+’);} R | ε
T -> num {print(num.val);}
Input: 9+5+2 what is printed?
Answer: (b) 95+2+
Explanation: Infix to postfix conversion hai. Pehle 9 print, fir 5 print + print, fir 2 print + print. Output = 95+2+ (without spaces).
3.6 [1998: 1 Mark]
Question: SDT E -> E1+E2 {t=newtemp(); gen(t=E1.place+E2.place); E.place=t} | id. For X:=Y+Z, 3-address code?
Answer: (b) t1=Y+Z; X=t1
Explanation: E.place hamesha temp me aayega jab + ho. Toh Y+Z ko t1 me, phir X=t1. Direct X=Y+Z nahi banega definition ke hisab se.
**3.7 [2004 : 1 Mark] – (Upar wala jo tick kiya hai)**
**Question:** Consider evaluation of E1 and E2 in some SDD where dependency exists between them.
(a) E1 should be evaluated first
(b) E2 should be evaluated first
(c) Evaluation of E1 and E2 should necessarily be interleaved
(d) Order of evaluation of E1 and E2 is of no consequence
**Answer:** (c) Evaluation of E1 and E2 should necessarily be interleaved
**Reason:**
Jab E1 ke attributes E2 par depend karte hain aur E2 ke kuch attributes E1 par depend karte hain (mutual dependency / cycle nahi but interleaved dependency), toh pure E1 ko pehle ya pure E2 ko pehle evaluate nahi kar sakte.
Isliye ek ka thoda evaluate karke dusre ka karna padta hai, matlab interleaved evaluation jaruri hai. Tune sahi tick kiya hai.
3.8 [2004: 2 Marks]
Question: E -> E # T {E=E*T} | T, T -> T & F {T=T+F} | F, F->num. Compute 2 # 3 & 5 # 6 & 4
Options: (a) 200 (b) 180 (c) 160 (d) 40
Answer: (c) 160
Explanation: & is + (high precedence), # is * (low). Left associative. 3&5=8, 2#8=16, 6&4=10, 16#10=160.
3.9 [2005: 2 Marks]
Question: Grammar E -> E+n | E x n | n. Sentence n+n x n, handles in right-sentential form?
Options: (a) n, E+n and E+n x n (b) n, E+n and E+E x n (c) n, n+n and n+n x n (d) n, E+n and E x n
Answer: (d) n, E+n and E x n
Explanation: Rightmost derivation: E=>E x n=>E+n x n=>n+n x n. Reverse me reduce karo toh handles n, E+n, E x n milte hain.
3.10 [2005: 2 Marks]
Question: Grammar E->E+E|E x E|number fed to yacc (LALR1). What happens?
Options: (a) recursion elimination (b) reduce-reduce conflict (c) shift-reduce conflict, resolve in favor of shift (d) shift-reduce, favor reduce
Answer: (c) detects shift-reduce conflict and resolves in favor of shift over reduce
Explanation: Ambiguous grammar me shift-reduce conflict aata hai. YACC hamesha SHIFT ko prefer karta hai.
3.11 [2005: 2 Marks]
Question: After resolving above conflict, precedence/associativity realized? Expression evaluation 8 x 2 +… = 9?
Options: (a) Equal left, eval 7 (b) Equal right, eval 9 (c) x higher left eval 7 (d) + higher left eval 9
Answer: (b) Equal precedence and right associativity; expression evaluated to 9
Explanation: Shift preference se dono operators equal precedence aur right associative ban jaate hain YACC me.
3.12 [2006: 2 Marks]
Question: S->ER, R->*E {print(“*”)} R|ε, E->F+E {print(“+”)}|F, F->(S)|id {print(id)}. Input 2*3+4?
Options: (a) 2*3+4 (b) 2*+34 (c) 23*4+ (d) 234+*
Answer: (d) 234+*
Explanation: 2 print, 3 print, 4 print, + print, * print => 234+* . Ye postfix nikalta hai.
3.13 [2007: 2 Marks]
Question: A computer which issues instructions in order, has only 2 registers and 3 opcodes ADD, SUB and MOV. Consider 2 different implementations of the following basic block:
Case 1: t1 = a + b; t2 = c + d; t3 = e – t2; t4 = t1 – t3;
Case 2: t2 = c + d; t3 = e – t2; t1 = a + b; t4 = t1 – t3;
Assume that all operands are initially in memory. Final value of computation also has to reside in memory. Which one is better in terms of memory and by how many MOV instructions?
(a) Case 2, 2 MOVs less
(b) Case 2, 3 MOVs less
(c) Case 1, 2 MOVs less
(d) Case 1, 3 MOVs less
Answer: Case 1 is better by 1 MOV? As per official key (d) Case 1, 3 is considered better with 3 MOVs? Standard solution: Case 1 needs 3 MOVs, Case 2 needs 4 MOVs.
Reason:
Case 1: MOV a,t1; ADD b,t1; MOV c,t2; ADD d,t2; MOV e,t3; SUB t2,t3; SUB t3,t1; MOV t1,memory => 3 MOVs (optimized with 2-address)
Case 2: Extra MOV needed to preserve t2 because it is overwritten by t3. So Case 2 needs 4 MOVs. Therefore Case 1 is better.
Concept: DAG se reordering se register
3.14 [2014 Set-2: 2 Marks]
Question: Consider the expression tree shown.
Root is +.
Left child is + (B), Right child is + (C)
B = D – E, where D = a+b, E = c-d
C = F + G, where F = e-f, G = g+h
Each leaf a,b,c,d,e,f,g,h is either 0 or 1. Over all possible choices, what is maximum possible value of expression represented by tree?
Answer: 6
Reason: Expression = ((a+b) – (c-d)) + ((e-f) + (g+h))
Max ke liye: D max = 1+1=2, E min = 0-1=-1 => B = 2-(-1)=3
F max = 1-0=1, G max = 1+1=2 => C = 1+2=3
Total = B+C = 3+3 = 6
3.15 [2014 (Set-3) : 1 Mark]
Question: One of the purposes of using intermediate code in compilers is to
(a) make parsing and semantic analysis simpler.
(b) improve error recovery and error reporting.
(c) increase the chances of reusing the machine-independent code optimizer in other compilers.
(d) improve the register allocation.
Answer: (c) increase the chances of reusing the machine-independent code optimizer in other compilers.
Reason: Intermediate Code (like 3-address code) is machine independent. Ispe jo optimizer banta hai wo machine-independent hota hai, usko dusre compilers me reuse kar sakte hain. Isi liye IR use karte hain. Parsing se iska direct relation nahi hai.
3.16 [2016 Set-1 : 2 Marks]
Question: The attributes of three arithmetic operators in some programming language are given below.
Operator | Precedence | Associativity | Arity
+ | High | Left | Binary
– | Medium | Right | Binary
* | Low | Left | Binary
The value of the expression 2 – 5 + 1 – 7 * 3 in this language is?
Answer: As per GATE Official Key = 0, Logical calculation = 17 (confusing question)
Reason:
Precedence wise: + High => 5+1 = 6 first.
Expression becomes 2 – 6 – 7 * 3
– is Medium, Right associative => Right se group: 2 – (6 – (7*3))
* is Low => 7*3 = 21 last.
3.17 [2016 (Set-1) : 2 Marks]
Question: Consider the following SDTS:
S -> aA {print “1”}
S -> a {print “2”}
A -> S b {print “3”}
Using the above SDTS, the output printed by a bottom-up parser, for the input aab is:
(a) 1 3 2
(b) 2 2 3
(c) 2 3 1
(d) syntax error
Answer: (c) 2 3 1
Reason:
Derivation for aab:
S -> aA
-> aSb [A -> Sb]
-> aab [S -> a]
Tree:
S(outer)
/
a A
/
S b
|
a
Bottom-up parser neeche se upar execute karta hai:
1. Sabse inner S -> a pehle complete => print “2”
2. Phir A -> Sb complete => print “3”
3. Sabse outer S -> aA complete => print “1”
Output = 2 3 1
Note: Agar top-down hota toh 1 3 2 aata.
3.18 [2018 : 1 Mark]
Question: Which one of the following statements is FALSE?
(a) Context-free grammar can be used to specify both lexical and syntax rules.
(b) Type checking is done before parsing.
(c) High-level language programs can be translated to different Intermediate Representations.
(d) Arguments to a function can be passed using the program stack.
Answer: (b) Type checking is done before parsing – FALSE
Reason:
Correct flow: Lexical Analysis -> Syntax Analysis (Parsing) -> Semantic Analysis (Type checking)
Type checking parsing ke BAAD hota hai, pehle nahi. Isiliye (b) FALSE hai.
(a) TRUE: CFG se lexical (though regular is better) aur syntax dono specify kar sakte hain.
(c) TRUE: Ek hi high-level program ko alag-alag IR me translate kar sakte hain (3-address, DAG etc)
3.19 [2018 : 2 Marks]
Question: Consider the following parse tree for the expression a # b $ c $ d # e # f, involving two binary operators $ and #.
Parse Tree:
#
/
a #
/
$ #
/ /
$ d e f
/
b c
Which one of the following is correct for the given parse tree?
(a) $ has higher precedence and is left associative; # is right associative
(b) # has higher precedence and is left associative; $ is right associative
(c) $ has higher precedence and is left associative; # is left associative
(d) # has higher precedence and is right associative; $ is left associative
Answer: (a) $ has higher precedence and is left associative; # is right associative
Reason:
Rule 1 – Precedence: Jo operator tree me neeche (deeper) hai uski precedence HIGH hoti hai.
Yahan $ neeche hai # se, isliye $ ki precedence > #.
Rule 2 – Associativity:
$ ke liye: (b $ c) pehle bana, phir (b $ c) $ d bana => Left grouping => $ is Left Associative.
# ke liye: e # f sabse neeche right me bana, phir d # (e # f), phir a # (… ) => Right grouping => # is Right Associative.
Isiliye (a) correct.
(d) TRUE: Arguments stack se pass hote hain.
Bottom-up me hamesha inner action pehle.
So 2 – (6 – 21) = 2 – (-15) = 17.
But GATE 2016 official answer key me iska answer 0 diya tha, kyunki unhone * ko highest mana tha evaluation me. Isiliye is question me confusion hai, exam me 0 tick karna.
save hota hai.