Compiler-Design

Question 1
 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 1 Explanation: 
Question 2
 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 2 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 3
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 3 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 4
 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 5

Suppose we have a computer with a single register and only three instructions given below:

 LOAD addren     ; load register
                 ; from addren
 STORE addren    ; store register
                 ; at addren
 ADD addren      ; add register to
                 ; contents of addren
                 ; and place the result
                 ; in the register 

Consider the following grammar:

   A → id :=E       E → E + T|T        T → (E)|id 

Write a syntax directed translation to generate code using this grammar for the computer described above.

A
Theory Explanation.
Question 6

Match the following items

A
(i) - (d), (ii) - (a), (iii) - (b), (iv) - (c)
Question 6 Explanation: 
Backus Normal Form (BNF) is a notation technique for context free grammars, often used to describe the syntax of languages used in computing.
Yacc (Yet Another Compiler- Compiler) is a computer program for the UNIX operating system. It is a LALR parser generator, generating a parser, the part of a compiler that tries to make syntactic sense of the source code, specially a LALR parser, based on an analytic grammar. Yacc is written in portable C.
Question 7

Generation of intermediate code based on an abstract machine model is useful in compilers because

A
it makes implementation of lexical analysis and syntax analysis easier
B
syntax-directed translations can be written for intermediate code generation
C
it enhances the portability of the front end of the compiler
D
it is not possible to generate code for real machines directly from high level language programs
Question 7 Explanation: 
In Intermediate code optimizations can also enhances the probability of optimizer.
Question 8

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 9

(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 10

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 10 Explanation: 

⇒ 23131
Note SR is bottom up parser.
Question 11

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 11 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 12

Consider evaluating the following expression tree on a machine with load-store architecture in which memory can be accessed only through load and store instructions. The variables a, b, c, d and e initially stored in memory. The binary operators used in this expression tree can be evaluate by the machine only when the operands are in registers. The instructions produce results only in a register. If no intermediate results can be stored in memory, what is the minimum number of registers needed to evaluate this expression?

A
2
B
9
C
5
D
3
Question 12 Explanation: 
Load R1, a ; R1 ← M[a]
Load R2, b ; R2 ← M[b]
Sub R1, R2 ; R1 ← R1 – R2
Load R2, c ; R2 ← M[c]
Load R3, d ; R3 ← M[d]
Add R2, R3 ; R2 ← R2 + R3
Load R3, e ; R3 ← M[e]
Sub R3, 3 ; R3 ← R3 – R2
Add R1, R3 ; R1 ← R1 + R3
Total 3 Registers are required minimum.
Question 13

Consider two binary operators ‘↑’ and ‘↓’ with the precedence of operator ↓ being lower than that of the operator ↑. Operator ↑ is right associative while operator ↓, is left associative. Which one of the following represents the parse tree for expression (7↓3↑4↑3↓2)?

A
B
C
D
Question 13 Explanation: 
7 ↓ 3 ↑ 4 ↑ 3 ↓ 2
⇒ 7 ↓ (3 ↑ (4 ↑ 3)) ↓ 2
⇒ 7 ↓ (3 ↑ (4 ↑ 3))) ↓ 2 as ↓ is left associative
Question 14

In a compiler, keywords of a language are recognized during

A
parsing of the program
B
the code generation
C
the lexical analysis of the program
D
dataflow analysis
Question 14 Explanation: 
Any identifier is also a token so it is recognized in lexical Analysis.
Question 15

The lexical analysis for a modern computer language such as Java needs the power of which one of the following machine models in a necessary and sufficient sense?

A
Finite state automata
B
Deterministic pushdown automata
C
Non-Deterministic pushdown automata
D
Turing machine
Question 15 Explanation: 
Lexical Analysis is implemented by finite automata.
Question 16

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 16 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 17

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 17 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 18

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 18 Explanation: 

7 reductions total.
Question 19

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 20

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 21

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 21 Explanation: 
If M2 macro is called with X=0, then it will go into an infinite loop.
Question 22

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 22 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 23

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 23 Explanation: 
Compiler is use dynamic memory allocation then the memory will be allocated to an array at runtime.
Question 24

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 24 Explanation: 
Macro is expanded during the process of Macro expansion.
Question 25

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 25 Explanation: 
Heap allocation is required for languages that support dynamic data structures.
Question 26

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 26 Explanation: 

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

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 28

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 28 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 29

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 29 Explanation: 
LR > LALR > SLR
Canonical LR parser is more powerful than LALR parser.
Question 30

Type checking is normally done during

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

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 32

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 32 Explanation: 
DO → 1
10 → 2
I → 3
= → 4
1.25 → 5
Question 33

Which of the following is the most powerful parsing method?

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

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 35

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 35 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 36

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 36 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 37

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 37 Explanation: 
Top-down parser - Leftmost derivation
Bottom-Up parser - Reverse of rightmost derivation
Question 38

(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 39

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 40

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 41

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 41 Explanation: 
Relocation can change the assigned address of data and code in the program.
Question 42

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 42 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 43

(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 44

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 44 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 45

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 45 Explanation: 
Question 46

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 46 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 47

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 47 Explanation: 

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

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 48 Explanation: 

Hence, it is LL(1).
Question 49

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 49 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 50

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 50 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.
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