Compiler-Design

Question 1
 Consider the following C code segment:
a = b + c;
e = a + 1;
d = b + c;
f = d + 1;
g = e + f;
In a compiler, this code segment is represented internally as a directed acyclic graph (DAG). The number of nodes in the DAG is _______
A
6
Question 2
Consider the following statements.
S1:Every SLR(1) grammar is unambiguous but there are certain unambiguous grammars that  are not SLR(1).
S2: For any context-free grammar, there is a parser that takes at most O(n3 )
Which one of the following options is correct?
A
S1is true and S2is true
B
S1is true and S2is false
C
S1is false and S2is true
D
S1is false and S2is false
Question 2 Explanation: 

Every unambiguous grammar need not be SLR(1). As we know some unambiguous grammar which is CLR(1)  but not SLR(1).  So S1 is true.


Any CFG (which is in CNF form) can be parsed by CYK algorithm in O(n3) where n is length of string. Although it is not given that CFG is in CNF form but since we can convert any CFG in CNF form so S2 is true

Question 3
 Consider the following grammar (that admits a series of declarations, followed by expressions) and the associated syntax directed translation (SDT) actions, given as pseudo-code:
P ⟶ D* E*
D ⟶ int ID {record that ID.lexeme is of type int}
D ⟶ bool ID {record that ID.lexeme is of type bool}
E ⟶ E1 + E2 {check that E1.type = E2.type = int; set E.type := int}
E ⟶ !E1 {check that E1.type = bool; set E.type := bool}
E ⟶ ID {set E.type := int}
With respect to the above grammar, which one of the following choices is correct?
A
The actions can be used to type-check syntactically correct integer variable declarations and integer expressions.
B
The actions will lead to an infinite loop.
C
The actions can be used to type-check syntactically correct boolean variable declarations and boolean expressions.
D
The actions can be used to correctly type-check any syntactically correct program.
Question 3 Explanation: 
This SDT will never lead to infinite loop so option 2 is false. This SDT is type checking for bool as well as integer variables, hence this SDT can be used to correctly type-check any syntactically correct program involving boolean and integer variables.
Question 4
 Consider the following context-free grammar where the set of terminals is {a, b, c, d, f}

Which one of the following choices represents the correct combination for the numbered cells in the parsing table (“blank” denotes that the corresponding cell is empty)? 
A
① S ⟶ Rf ② S ⟶ Rf ③ T ⟶ ∊ ④ T ⟶ ∊
B
① blank ② S ⟶ Rf ③ T ⟶ ∊ ④ T ⟶ ∊
C
① S ⟶ Rf ② blank ③ blank ④ T ⟶ ∊
D
① blank ② S ⟶ Rf ③ blank ④ blank
Question 4 Explanation: 
Question 5

A linker is given object modules for a set of programs that were compiled separately. What information need to be included in an object module?

A
Object code
B
Relocation bits
C
Names and locations of all external symbols defined in the object module
D
Absolute addresses of internal symbols
Question 5 Explanation: 
In object module it includes names and locations of all external symbols defined in the object module.
To link to external symbols it must know the location of external symbols.
Question 6

A shift reduce parser carries out the actions specified within braces immediately after reducing with the corresponding rule of grammar

S → xxW {print "1"}
S → y {print "2"}
W → Sz {print "3"} 

What is the translation of xxxxyzz using the syntax directed translation scheme described by the above rules?

A
23131
B
11233
C
11231
D
33211
Question 6 Explanation: 

⇒ 23131
Note SR is bottom up parser.
Question 7

Construct the LL(1) table for the following grammar.

 1. Expr → _Expr
 2. Expr → (Expr)
 3. Expr → Var Expr Tail
 4. ExprTail → _Expr
 5. ExprTail → λ
 6. Var → Id Var Tail
 7. VarTail → (Expr)
 8. VarTail → λ
 9. Goal → Expr$ 
A
Theory Explanation.
Question 8

(a) Translate the arithmetic expression a*-(b+c) into syntax tree.
(b) A grammar is said to have cycles if it is the case that
A ⇒ +A
Show that no grammar that has cycles can be LL(I).

A
Theory Explanation.
Question 9

Consider the following grammar.

     S → aSB|d
     B → b 

The number of reduction steps taken by a bottom-up parser while accepting the string aaadbbb is _______.

A
7
Question 9 Explanation: 

7 reductions total.
Question 10

Consider the following statements.

    I. Symbol table is accessed only during lexical analysis and syntax analysis.
    II. Compilers for programming languages that support recursion necessarily need heap storage for memory allocation in the run-time environment.
    III. Errors violating the condition ‘any variable must be declared before its use’ are detected during syntax analysis.

Which of the above statements is/are TRUE?

A
II only
B
I only
C
I and III only
D
None of I, II and III
Question 10 Explanation: 
I is wrong as Symbol table is also accessed during semantic analysis phase.
II is wrong as compilers which supports recursion require stack memory in run time environment.
III is wrong “any variable must be declared before its use” is a semantic error and not syntax error.
Question 11

Consider the productions A⟶PQ and A⟶XY. Each of the five non-terminals A, P, Q, X, and Y has two attributes: s is a synthesized attribute, and i is an inherited attribute. Consider the following rules.

    Rule 1: P.i = A.i + 2, Q.i = P.i + A.i, and A.s = P.s + Q.s
    Rule 2: X.i = A.i + Y.s and Y.i = X.s + A.i 

Which one of the following is TRUE?

A
Only Rule 2 is L-attributed.
B
Neither Rule 1 nor Rule 2 is L-attributed.
C
Both Rule 1 and Rule 2 are L-attributed.
D
Only Rule 1 is L-attributed.
Question 11 Explanation: 
In rule 2 for production A -> XY the attribute “i” is calculated from the right sibling Y in X.i = A.i + Y.s which is violating the L attribute definition, as in L attribute calculating attribute vale from RHS sibling is not allowed.
Question 12

The pass number for each of the following activities

    1. Object code generation
    2. Literals added to literal table
    3. Listing printed
    4. Address resolution of local symbols

That occur in a two pass assembler respectively are

A
1, 2, 1, 2
B
2, 1, 2, 1
C
2, 1, 1, 2
D
1, 2, 2, 2
Question 12 Explanation: 
The functionalities from pass 1 and pass 2 are:
Pass 1:
1) Assign addresses to all statements in the program.
2) Save the values assigned to all labels for use in pass 2.
3) Perform some processing of assembler directives.
Pass 2:
1) Assemble instructions.
2) Generate data values defined by BYTE, WORD etc.
3) Perform processing of assembler directives not done during pass 1.
4) Write the program and assembling listing.
Question 13

Which of the following macros can put a micro assembler into an infinite loop?

(i)  .MACRO M1 X
     .IF EQ, X      ;if X=0 then
      M1 X + 1
     .ENDC
     .IF NE X       ;IF X≠0 then
     .WORD X        ;address (X) is stored here
     .ENDC
     .ENDM
(ii) .MACRO M2 X
     .IF EQ X
      M2 X
     .ENDC
     .IF NE, X
     .WORD X+1
     .ENDC
     .ENDM 
A
(ii) only
B
(i) only
C
both (i) and (ii)
D
None of the above
Question 13 Explanation: 
If M2 macro is called with X=0, then it will go into an infinite loop.
Question 14

Given below are the transition diagrams for two finite state machine M1 and M2 recognizing languages L1 and L2 respectively.
(a) Display the transition diagram for a machine that recognizes L1.L2, obtained from transition diagrams for M1 and M2 by adding only ε transitions and no new states.
(b) Modify the transition diagram obtained in part(a) obtain a transition diagram for a machine that recognizes (L1.L2)∗ by adding only ε transitions and no new states. (Final states are enclosed in double circles).

A
Theory Explanation.
Question 15

Consider the syntax-directed translation schema (SDTS) shown below:

    E → E + E  {print “+”}
    E → E ∗ E  {print “.”}
    E → id     {print id.name}
    E → (E) 

An LR-parser executes the actions associated with the productions immediately after a reduction by the corresponding production. Draw the parse tree and write the translation for the sentence.

(a+b)∗(c+d), using the SDTS given above. 
A
Theory Explanation.
Question 16

In the following grammar

         X ::= X ⊕ Y/Y
         Y ::= Z * Y/Z
         Z ::= id  

Which of the following is true?

A
‘⊕’ is left associative while ‘*’ is right associative
B
Both ‘⊕’ and ‘*’ is left associative
C
‘⊕’ is right associative while ‘*’ is left associative
D
None of the above
Question 16 Explanation: 

⊕ is left associative.
* is right associative.
Question 17

A language L allows declaration of arrays whose sizes are not known during compilation. It is required to make efficient use of memory. Which of the following is true?

A
A compiler using static memory allocation can be written for L
B
A compiler cannot be written for L; an interpreter must be used
C
A compiler using dynamic memory allocation can be written for L
D
None of the above
Question 17 Explanation: 
Compiler is use dynamic memory allocation then the memory will be allocated to an array at runtime.
Question 18

The conditional expansion facility of macro processor is provided to

A
test a condition during the execution of the expanded program
B
to expand certain model statements depending upon the value of a condition during the execution of the expanded program
C
to implement recursion
D
to expand certain model statements depending upon the value of a condition during the process of macro expansion
Question 18 Explanation: 
Macro is expanded during the process of Macro expansion.
Question 19

Heap allocation is required for languages

A
that support recursion
B
that support dynamic data structures
C
that use dynamic scope rules
D
None of the above
Question 19 Explanation: 
Heap allocation is required for languages that support dynamic data structures.
Question 20

Match the pairs in the following questions:

(a) Pointer data type       (p) Type conversion
(b) Activation record       (q) Dynamic data structure
(c) Repeat-until            (r) Recursion
(d) Coercion                (s) Non-deterministic loop
A
(a) - (q), (b) - (r), (c) - (s), (d) - (p)
Question 20 Explanation: 
Pointer data type - Dynamic data structure
Activation record - Recursion
Repeat until - Non-deterministic loop
Coercion - Type conversion
Question 21

Match the pairs in the following questions:

(a) Lexical analysis         (p) DAG's
(b) Code optimization        (q) Syntax trees
(c) Code generation          (r) Push down automaton
(d) Abelian groups           (s) Finite automaton
A
(a) - (s), (b) - (p), (c) - (q), (d) - (r)
Question 21 Explanation: 
Lexical analysis - Finite automaton
Code optimization - DAG
Code generation - Syntax tree
Abelian groups - Push down automaton
Question 22

In a resident – OS computer, which of the following systems must reside in the main memory under all situations?

A
Assembler
B
Linker
C
Loader
D
Compiler
Question 22 Explanation: 
In many operating system loader is permanently resident in memory.
Some OS may allow virtual memory may allow the loader to be located in a region of memory that is in page table.
Question 23

Which of the following statements is true?

A
SLR parser is more powerful than LALR
B
LALR parser is more powerful than Canonical LR parser
C
Canonical LR parser is more powerful than LALR parser
D
The parsers SLR, Canonical CR, and LALR have the same power
Question 23 Explanation: 
LR > LALR > SLR
Canonical LR parser is more powerful than LALR parser.
Question 24

Type checking is normally done during

A
lexical analysis
B
syntax analysis
C
syntax directed translation
D
code optimization
Question 24 Explanation: 
Type checking is normally done during syntax directed translation.
Question 25

Let the attribute 'val' give the value of a binary number generated by S in the following grammar:

S → L.L | L 
L→ LB | B 
B → 0 | 1 

For example, an input 101.101 gives S.val = 5.625

Construct a syntax directed translation scheme using only synthesized attributes, to determine S.val.

A
Theory Explanation.
Question 26

Which of the following is the most powerful parsing method?

A
LL (1)
B
Canonical LR
C
SLR
D
LALR
Question 26 Explanation: 
Canonical LR is most powerful.
LR > LALR > SLR
Question 27

The number of tokens in the Fortran statement DO 10 I = 1.25 is

A
3
B
4
C
5
D
None of the above
Question 27 Explanation: 
DO → 1
10 → 2
I → 3
= → 4
1.25 → 5
Question 28

Let synthesized attribute val give the value of the binary number generated by S in the following grammar. For example, on output 101.101, S.val = 5.625.

   S → LL|L 
   L → LB|B 
   B → 0|1 

Write S-attributed values corresponding to each of the productions to find S.val.

A
Theory Explanation.
Question 29

The number of tokens in the following C statement.

printf("i = %d, &i = %x", i, &i); 

is

A
3
B
26
C
10
D
21
Question 29 Explanation: 
We have six different types of tokens are available
(i) Keyword
(ii) Identifier
(iii) Constant
(iv) Variable
(v) String
(vi) Operator
Print = Token 1
( = Token 2
"i=%d%x" = Token 3 [Anything inside " " is one Token]
, = Token 4
i = Token 5
, = Token 6
& = Token 7
i = Token 8
) = Token 9
; = Token 10
Here, totally 10 Tokens are present in the equation.
Question 30

Which of the following derivations does a top-down parser use while parsing an input string? The input is assumed to be scanned in left to right order.

A
Leftmost derivation
B
Leftmost derivation traced out in reverse
C
Rightmost derivation
D
Rightmost derivation traced out in reverse
Question 30 Explanation: 
Top-down parser - Leftmost derivation
Bottom-Up parser - Reverse of rightmost derivation
Question 31

Given the following expression grammar:

    E → E * F | F + E | F
    F → F - F | id  

which of the following is true?

A
* has higher precedence than +
B
- has higher precedence than *
C
+ and – have same precedence
D
+ has higher precedence than *
Question 31 Explanation: 
The operator which is in low level that can have high preference.
Order of precedence is *, +, -.
Here * and + have equal preference, '-' can have higher precedence than + and *.
Question 32

Consider the syntax directed translation scheme (SDTS) given in the following.
Assume attribute evaluation with bottom-up parsing, i.e., attributes are evaluated immediately after a reduction.

 E → E1 * T {E.val = E1.val * T.val}
 E → T {E.val = T.val}
 T → F – T1{T.val = F.val – T1.val}
 T → F {T.val = F.val}
 F → 2 {F.val = 2}
 F → 4 {F.val = 4} 

(a) Using this SDTS, construct a parse tree for the expression
4 – 2 – 4 * 2
and also compute its E.val.

(b) It is required to compute the total number of reductions performed to parse a given input. Using synthesized attributes only, modify the SDTS given, without changing the grammar, to find E.red, the number of reductions performed while reducing an input to E.

A
Theory Explanation is given below.
Question 33

The process of assigning load addresses to the various parts of the program and adjusting the code and date in the program to reflect the assigned addresses is called

A
Assembly
B
Parsing
C
Relocation
D
Symbol resolution
Question 33 Explanation: 
Relocation can change the assigned address of data and code in the program.
Question 34

Which of the following statements is false?

A
An unambiguous grammar has same leftmost and rightmost derivation
B
An LL(1) parser is a top-down parser
C
LALR is more powerful than SLR
D
An ambiguous grammar can never be LR(k) for any k
Question 34 Explanation: 
Option B: LL parser is a top-down parser for a subset of context-free languages. It parses the input from Left to right, performing Left most derivation of the sentence.
Option C: LALR is more powerful than SLR.
Option D: An ambiguous grammar can never be LR (k) for any k, because LR(k) algorithm aren’t designed to handle ambiguous grammars. It would get stuck into undecidability problem, if employed upon an ambiguous grammar, no matter how large the constant k is.
Question 35

Consider the following grammar with terminal alphabet ∑{a,(,),+,*} and start symbol E. The production rules of the grammar are:

              E → aA
              E → (E)
              A → +E
              A → *E
              A → ε 

(a) Compute the FIRST and FOLLOW sets for E and A.
(b) Complete the LL(1) parse table for the grammar.

A
Theory Explanation is given below.
Question 36

The syntax of the repeat-until statement is given by the gollowing grammar

   S → repeat S1 until E  

Where E stands for expressions, S and S1 stand for statement. The non-terminals S and S1 have an attribute code that represents generated code. The nonterminal E has two attributes. The attribute code represents generated code to evaluate the expression and store its truth value in a distinct variable, and the attribute varName contains the name of the variable in which the truth value is stored? The truth-value stored in the variable is 1 if E is true, 0 if E is false.

Give a syntax-directed definition to generate three-address code for the repeatuntil statement. Assume that you can call a function newlabel( ) that returns a distinct label for a statement. Use the operator ‘\\’ to concatenate two strings and the function gen(s) to generate a line containing the string s.

A
Theory Explanation is given below.
Question 37

(a) Remove left-recursion from the following grammar:

    S → Sa| Sb | a | b 

(b) Consider the following grammar:

    S → aSbS| bSaS |ε  

Construct all possible parse trees for the string abab. Is the grammar ambiguous?

A
Theory Explanation is given below.
Question 38

(a) Construct all the parse trees corresponding to i + j * k for the grammar

      E → E+E
      E → E*E
      E → id  
    (b) In this grammar, what is the precedence of the two operators * and +?
    (c) If only one parse tree is desired for any string in the same language, what changes are to be made so that the resulting LALR(1) grammar is non-ambiguous?
A
Theory Explanation is given below.
Question 39

Which of the following suffices to convert an arbitrary CFG to an LL(1) grammar?

A
Removing left recursion alone
B
Factoring the grammar alone
C
Removing left recursion and factoring the grammar
D
None of the above
Question 39 Explanation: 
Left recursion removing (or) factoring the given grammar are not sufficient to convert an arbitrary CFG to an LL(1) grammar.
To convert an arbitrary CFG to an LL(1) grammar we need to remove the left recursion and as well as left factoring without that we cannot convert.
Question 40

Assume that the SLR parser for a grammar G has n1 states and the LALR parser for G has n2 states. The relationship between n1 and n2 is:

A
n1 is necessarily less than n2
B
n1 is necessarily equal to n2
C
n1 is necessarily greater than n2
D
None of the above
Question 40 Explanation: 
No. of states in SLR and LALR are equal and no. of states in SLR and LALR are less than or equal to LR(1).
Question 41

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 has synthesized attributes
D
never be evaluated
Question 41 Explanation: 
L-Attributed grammar can able to inherits either inherited attributes (or) synthesized attributes.
L-Attributed definitions are a class of syntax directed definitions whose attributes can be evaluated by a single traversal of the parse-tree.
Question 42

Which of the following statements is FALSE?

A
In statically typed languages, each variable in a program has a fixed type
B
In un-typed languages, values do not have any types
C
In dynamically typed languages, variables have no types
D
In all statically typed languages, each variable in a program is associated with values of only a single type during the execution of the program
Question 42 Explanation: 
Dynamic typed languages are those languages in which variable must necessarily be defined before they are used. Then dynamic typed languages have types.
Question 43

Consider the grammar shown below

S → i E t S S' | a
S' → e S | ε
E → b 

In the predictive parse table. M, of this grammar, the entries M[S', e] and M[S', $] respectively are

A
{S'→e S} and {S'→ε}
B
{S'→e S} and { }
C
{S'→ε} and {S'→ε}
D
{S'→e S, S'→ε} and {S'→ε}
Question 43 Explanation: 
First(S) = {1,a}
First(S') = {e,ε}
First(E) = {b}
Follow(S') = {e,$}
Only when 'First' contains ε, we need to consider FOLLOW for getting the parse table entry.

Hence, option (D) is correct.
Question 44

Consider the grammar shown below.

S → C C
C → c C | d

The grammar is

A
LL(1)
B
SLR(1) but not LL(1)
C
LALR(1) but not SLR(1)
D
LR(1) but not LALR(1)
Question 44 Explanation: 

Hence, it is LL(1).
Question 45

Consider the translation scheme shown below.

S → T R
R → + T {print ('+');} R|ε
T → num {print(num.val);}

Here num is a token that represents an integer and num.val represents the corresponding integer value. For an input string '9 + 5 + 2', this translation scheme will print

A
9 + 5 + 2
B
9 5 + 2 +
C
9 5 2 + +
D
+ + 9 5 2
Question 45 Explanation: 

Now traverse the tree and whatever comes first to print, just print it.
Answer will be 9 5 + 2 +.
Question 46

Consider the syntax directed definition shown below.

S → id := E           {gen (id.place = E.place;);}
E → E1 + E2           {t = newtemp ( ); 
                      gen(t = E1.place + E2.place;); 
                      E.place = t}
E → id                {E.place = id.place;}

Here, gen is a function that generates the output code, and newtemp is a function that returns the name of a new temporary variable on every call. Assume that ti's are the temporary variable names generated by newtemp. For the statement 'X: = Y + Z', the 3-address code sequence generated by this definition is

A
X = Y + Z
B
t1 = Y + Z; X = t1
C
t1= Y; t2 = t1 + Z; X = t2
D
t1 = Y; t2 = Z; t3 = t1 + t2; X = t3
Question 46 Explanation: 
Question 47

Which of the following is NOT an advantage of using shared, dynamically linked libraries as opposed to using statically linked libraries?

A
Smaller sizes of executable files
B
Lesser overall page fault rate in the system
C
Faster program startup
D
Existing programs need not be re-linked to take advantage of newer versions of libraries
Question 47 Explanation: 
Dynamic link libraries takes more time in program setup (in loading and linking phase to set up the global offset table and load and link the required libraries).
Question 48

Which of the following grammar rules violate the requirements of an operator grammar? P,Q,R are nonterminals, and r,s,t are terminals.

    (i) P → Q R
    (ii) P → Q s R
    (iii) P → ε
    (iv) P → Q t R r
A
(i) only
B
(i) and (iii) only
C
(ii) and (iii) only
D
(iii) and (iv) only
Question 48 Explanation: 
Operator values doesn't contains nullable values and two adjacent non-terminals on RHS production.
i) On RHS it contains two adjacent non-terminals.
ii) Have nullable values.
Question 49

Consider a program P that consists of two source modules M1 and M2 contained in two different files. If M1 contains a reference to a function defined in M2, the reference will be resolved at

A
Edit time
B
Compile time
C
Link time
D
Load time
Question 49 Explanation: 
The link time can gives the reference to the executable file when the functions are present in the other modules.
Question 50

Consider the grammar rule E → E1 - E2 for arithmetic expressions. The code generated is targeted to a CPU having a single user register. The subtraction operation requires the first operand to be in the register. If E1 and E2 do not have any common sub expression, in order to get the shortest possible code

A
E1 should be evaluated first
B
E2 should be evaluated first
C
Evaluation of E1 and E2 should necessarily be interleaved
D
Order to evaluation of E1 and E2 is of no consequence
Question 50 Explanation: 
After evaluating E2 first and then E1, we will have E2 in the register and then we can simply do SUB operation with E2 which will be in memory. And if we do E1 first and then E2, then we must move E2 to memory and again bring back E1 to the register before doing SUB operation, which will increase load.
There are 50 questions to complete.

Access subject wise (1000+) question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content

Register Now