Please provide compiler design lab viva voce questions and answers

Compiler Design questions and answers


(1) For the C program given below the statement that does not hold true is

for (i = 0; ifor(j = 0; jif (i%c)
{
x += (4*j+5*i);
y+=(7+4*j);
}
}
}

A) There is a scope strength reduction
B) There is a scope of dead code elimination
C) There is a scope of common sub-expression elimination
D) None of the above

View Answer / Hide Answer


(2) In compilers generation of intermediate code based on an abstract machine model is useful because

(A) Syntax-directed translations can be written for intermediate code generation
(B) To generate code for real machines directly from high-level language programs is not possible
© Portability of the front end of the compiler is enhanced
(D) Implementation of lexical and syntax analysis is easier

View Answer / Hide Answer


(3) Consider the grammar where P, Q, R are not terminals and r, s, t are terminals

a. P->Q R
b. P->Q s R
c. P->ε
d. P->Q t R r

The grammar rules that violate the requirements of an operator grammar is

(A) a and c only
(B) b and c only
© a and d only
(D) a only

View Answer / Hide Answer


(4) Which one of the following statement is false for the SLR (1) and LALR (1) parsing tables for a context free grammar?

(A) The reduce entries in both the tables may be different
(B) The error entries in both the tables may be different
© The go to part of both tables may be different
(D) The shift entries in both the tables may be identical

View Answer / Hide Answer


(5) We have a grammar with not epsilon and unit production (i.e. of type A->ε and
A ->a) to parse a string, with n tokens. What is the maximum number of reduces moves that can be taken by a bottom-up parser for this grammar?

(A) 2n - 1
(B) 2n
© n-1
(D) n/2

View Answer / Hide Answer


For questions 6 and 7 refer to the data given below:

The processor allows only register operands in its instructions and the given code segment is executed in that processor. For each instruction almost two source operands and one destination

operand is available. Assume that all the variables are dead after this code segment.

z = x + y;
p = z * x;
q = c + x;
j = z * z;

If (j > x)
{
M = x*x;
}
else
{
p = p*p;
q = q*q;
}

(6) Only two registers are available in the instruction set architecture of the processor. The code motion moves the statements from one place to another while preserving correctness. The only allowed complier optimization is code motion. In the compiled code, the minimum number of spills to memory is

(A) 0
(B) 1
© 2
(D) 3

View Answer / Hide Answer


(7) Assume that no other optimization other than optimizing register allocation is applied. To compile this code segment without any spill to memory the minimum number of registers needed in the instruction set architecture of the processor is

(A) 3
(B) 6
© 4
(D) 5

View Answer / Hide Answer


(8) We have the grammar E->E + n I E x n I n. The handles in the right-sentential form of the reduction for a sentence n + n x n are

(A) n, n + n and n + n x n
(B) n, E + n and E x n
© n, E + n and E + E x n
(D) n, E + n and E + n x n

View Answer / Hide Answer


(9) The languages that need heap allocation in the runtime environment are

(A) Those that use global variables
(B) Those that use dynamic scoping
© Those that support recursion
(D) Those that allow dynamic data structure

View Answer / Hide Answer


(10) When is the type checking usually done?

(A) During syntax directed translation
(B) During lexical analysis
© During code optimization
(D) During syntax analysis

View Answer / Hide Answer


(11) What information need to be included in an object module, if a linker is given object modules for a set of programs that were compiled separately?

(A) Names and locations of all external symbols defined in the object module
(B) Object code
© Absolute addresses of internal symbols
(D) Relocation bits

View Answer / Hide Answer


(12) We have two sets of LR (1) items of LR (1) grammar described below.

X->c.X, c/d X->c.X, $
X->.cX, c/d X->.cX, $
X->.d, c/d X->.d, $

Related to the merging of two sets in the corresponding parser, the statement that does not hold true is

(A) Cannot be merged since look aheads are different.
(B) Cannot be merged but will result in R-R conflict
© Cannot be merged but will result in S-R conflict
(D) All of the above

View Answer / Hide Answer


(13)
a. Begin
b. Program
c. <>

While compiling a Pascal program, without looking at the next input character the string that can be definitely said to be token is

(A) b
(B) c
© a
(D) All of the above

View Answer / Hide Answer


(14)
S->xx W {print”1”}
S->y {print”2”}
W->Sz {print”3”}

A shift reduce parser carries out the actions specified within braces immediately after reducing with the corresponding rule of grammar. Using the syntax directed translation scheme described

by the above rule, the translation of xxxxyzz is

(A) 11231
(B) 11233
© 23131
(D) 33211

View Answer / Hide Answer


(15) In some programming language, L denotes the set of letters and D denotes the set of digits. An identifier is permitted to be a letter followed by any number of letters or digits. The expression that defines an identifier is

(A) (L.D)*
(B) (L + D)*
© L (L.D)
(D) L (L + D)*

View Answer / Hide Answer


(16) Which one of the following statement is true?

(A) Canonical LR parser is more powerful than LALR parser
(B) SLR parser is more powerful than LALR
© LALR parser is more powerful than canonical LR parser
(D) SLR parser, canonical LR parser and LALR parser all have the same power

View Answer / Hide Answer


(17) The activities are listed below. What is the pass numbers of each of the activities respectively?

a. Object code generation
b. Literals added to the literal table
c. Listing printed
d. Address resolution of local symbols that occur in a two pass assembler

(A) 1, 2, 2, 2
(B) 2, 1, 1, 1
© 1, 2, 1, 2
(D) 2, 1, 2, 1

View Answer / Hide Answer


(18) In a compiler _______________ checks every character of the source text.

(A) The lexical analyzer
(B) The syntax analyzer
© The code generator
(D) The code optimizer

View Answer / Hide Answer


For questions 19 and 20 refer to the data given below:

The programming language given below is written in the programming language that does not allow nested declarations of functions and allows global variables.
global int j = 100, k = 5;
void M(n)
{
int j = 10;
print (n + 10);
j = 200;
k = 20;
print (n);
}
main()
{
M(j + k);
}

(19) What is the output of the above program if the programming language uses static scoping and call by need parameter passing mechanism?

(A) 25, 220
(B) 115, 105
© 220, 115
(D) 105, 220

View Answer / Hide Answer


(20) What is the output of the above program if the programming language uses dynamic scoping and call by name parameter passing mechanism?

(A) 105, 25
(B) 105, 115
© 220, 25
(D) 115, 220

View Answer / Hide Answer


(21) ______________ is not an advantage of using shared, dynamically linked libraries as opposed to using statically linked libraries.

(A) Lesser overall page fault rate in the system
(B) Faster program startup
© Existing programs need not be relinked to take advantage of newer versions
(D) Smaller sizes of executable files

View Answer / Hide Answer


(22) The instructions of a simplified computer, which has only two registers, are given below:
OP Rj, Rk - Performs Rj OP Rk and stores the result in register Rk.
OP m, Rj - Performs the content of memory location m OP Rj and stores the result in Rj
MOV m, Rk - Moves the content of memory location m to register Rk.
MOV Rk, m - Moves the content of register Rk to memory location m.
OP is either ADD or SUB.

We have the following basic block:

T1 = a + b
T2 = c + d
T3 = e - T2
T4 = T1 - T3

Assuming that all operands are initially in memory and the final value of the computation in memory, the minimum number of MOV instructions in the code generated for this basic block is

(A) 3
(B) 2
© 6
(D) 4

View Answer / Hide Answer


For questions 23 and 24 refer to the data given below:

Consider the language L = {ai bi I i ? j}?

(23) The grammar that generates this language is

(A) S->aS\Sb\a\b
(B) S->AC\CB
C->aC b\a\b
A->aA\ ∈
B->Bb\ ∈
© S->AC\CB
C->aCb\∈
A->aA\a
B->bB\b
(D) S->AC\CB
C->aC b\∈
A->aA\ ∈
B->Bb\ ∈

View Answer / Hide Answer


(24) In the correct grammar from question 23 to generate the string al bm with l ≠ m, the length of the derivation (number of steps starting from s) is

(A) max (l, m) + 3
(B) max (l, m) + 2
© l + m + 2
(D) l + m + 3

View Answer / Hide Answer


(25) Consider the following C program:

int min (){ /*line 1*/
int I, N; /*line 2*/
fro (I=0, I
While creating the object module, the compiler’s response about line no. 3 is

(A) Only syntax error
(B) No compilation error
© Only lexical error
(D) Both lexical and syntax error

View Answer / Hide Answer


(26) We have the translation scheme given below:

S->FR
R->*E{print(‘*’);R\ε
E->F + E{print (‘+’);\F
F->(S)\id {print (id.value);}

In the above translation scheme id represents the token in integer form and id value represents the corresponding integer value. What will be printed by this translation scheme when an input

is ‘2 * 3 + 4’?

(A) 2 3 * 4 +
(B) 2 3 4 + *
© 2 * + 3 4
(D) 2 * 3 + 4

View Answer / Hide Answer


(27) We have the grammar with the translation rules:

E->E1 # T {E.value = E1.value * T.value}
I T {E.value = T.value}
T->T1 & F {T.value = T1.value F.value}
I F {T.value = F.value}
F->num {F.value = num.value}

In the above grammar E is the start symbol. What will be the value of E for the root parser tree for the expression 2 # 3 & 5 # 6 & 4?

(A) 50
(B) 100
© 200
(D) 160

View Answer / Hide Answer


(28) For the expression grammar

E->E*F I F+E I F
F->F – I id

The statement, which holds true, is

(A) + and – have same precedence
(B) Precedence of * is higher +
© Precedence of - is higher *
(D) Precedence of + is higher *

View Answer / Hide Answer


(29) Which one of the following statement holds true for a bottom-up evaluation of syntax directed definition?

(A) Inherited attributes can always be evaluated
(B) Inherited attributes can never be evaluated
© Inherited attributes can be evaluated only if the definition is L-attributed
(D) Inherited attributes can be evaluated only if the definition has synthesized attributes

For questions 30 and 31 refer to the data given below:

{S, A, B} is the non-terminal alphabet and {a, b} is the terminal alphabet of the CFG. S is the start symbol. The set of production rules are given below,
S->aB S->bA
B->b A->a
B->bS A->aS
B->aBB A->bAA

View Answer / Hide Answer


(30) The string that is generated by the grammar is

(A) aabbbb
(B) abbbba
© aabbab
(D) aaaabb

View Answer / Hide Answer


(31) The number of derivation trees for the correct answer strings to question 30 is

(A) 4
(B) 1
© 3
(D) 2

View Answer / Hide Answer


(32) For a grammar G, Shift reduce (S-R) conflicts is present in LALR (1) parser, if and only if

(A) The LR (1) parser for G has S-R conflicts
(B) The LR (0) parser for G has S-R conflicts
© The SLR (1) parser for G has S-R conflicts
(D) The SLR (0) parser for G has S-R conflicts

View Answer / Hide Answer


(33) For arithmetic expression the grammar rule is E->E1-E2. A CPU has a single user register and the code generated is target to the CPU. The first operand should be in the register for the subtraction operation. E1 and E2 do not have any common sub-expression. Which one of the following is true in order to get the shortest possible code?

(A) Order of evaluation of E1 and E2 has no consequence
(B) E1 and E2 evaluation should be interleaved
© E2 should be evaluated first
(D) E1 should be evaluated first

View Answer / Hide Answer


(34) Consider the grammar G whose SLR parser has n1 states and LALR parser has n2 states. What is the relation between n1 and n2?

(A) n1 = n2
(B) n1 < n2
© n1 > n2
(D) None of the above

View Answer / Hide Answer


(35) A program P has M1 and M2, the two source modules contained in two different files. When is the reference resolved if M1 contains reference to a function defined in M2?

(A) Edit time
(B) Load time
© Compile time
(D) Link time

View Answer / Hide Answer


(36) For predictive parsing the grammar A->AA I (A) I ε is not suitable because

(A) The grammar is right recursive
(B) The grammar is left recursive
© The grammar is ambiguous
(D) The grammar is an operator grammar

View Answer / Hide Answer


(37) How many tokens are there in the following C statement?

printf (“j=%d, &j=%x”, j&j)

(A) 4
(B) 5
© 9
(D) 10

View Answer / Hide Answer


(38) Assuming that the input is scanned in left to right order, while parsing an input string the top-down parser use

(A) Rightmost derivation
(B) Leftmost derivation
© Rightmost derivation that is traced out in reverse
(D) Leftmost derivation that is traced out in reverse

View Answer / Hide Answer


(39) To convert an arbitrary CFG to an LL (1) grammar

(A) Factor the grammar alone
(B) Remove left recursion alone
© Remove left recursion and factor the grammar
(D) None of the above

View Answer / Hide Answer


(40) S->S*E
S->E
E->F+E
E->F
F->Id
Corresponding to the above grammar, we have following LR (0) items.

a. S->S*E
b. E->F.+E
c. E->F+.E

The two items that will appear in the same set in the canonical sets-of-items for the grammar is

(A) a and c
(B) a and b
© b and c
(D) a, b and c

View Answer / Hide Answer


(41) __________________ is a top-down parser

(A) Operator precedence parser
(B) An LALR (k) parser
© An LR (k) parser
(D) Recursive descent parser

View Answer / Hide Answer


(42) Why is the code optimizations are carried out on the intermediate code?

(A) Because for optimization information from the front end cannot be used
(B) Because program is more accurately analyzed on intermediate code than on machine code.
© Because for optimization information from data flow analysis cannot be used
(D) Because they enhance the portability of the compiler to the other target processor.

View Answer / Hide Answer


(43) In a compiler, when is the keyboards of a language are recognized?

(A) During the lexical analysis of a program
(B) During parsing of the program
© During the code generation
(D) During the data flow analysis

View Answer / Hide Answer


(44) In a compiler, the data structure responsible for the management of information about variables and their attributes is

(A) Semantic stack
(B) Parser table
© Symbol table
(D) Abstract syntax-tree

View Answer / Hide Answer


(45) The lexical analysis for Java needs _____________ in a necessary and sufficient sense.

(A) Turing machine
(B) Non-deterministic push down automata
© Deterministic push down automata
(D) Finite state automata

corresponding machine language equivalent with the help of OPTAB. Then theSYMTAB is searched for the numeric equivalent of register and that value isinserted into the operand field.Eg: 125 1036 RDREC CLEAR X B410B4-macine equivalent of the opcode CLEAR 10-numeric equivalent of the register X.20. What is meant by external references?Assembler program can be divided into many sections known as control sectionsand each control section can be loaded and relocated independently of the others. If the instruction in one control section need to refer instruction or data in another control section .the assembler is unable to process these references in normal way.Such references between control are called external references.21. Define control section.A control section is a part of the program that maintains its identity after assembly; each control section can be loaded and relocated independently of theothers. Control sections are most often used for subroutines. The major benefit of using control sections is to increase flexibility.22. What is the difference between the assembler directiveEXTREF and EXTDEF.EXTDEF names external symbols that are defined in a particular controlSection and may be used in other sections.EXTREF names external symbols that are referred in a particular controlsection and defined in another control section.23. Give the general format of define record.This record gives information about external symbols that are defined in a particular control section. The format isCol 1 DCol 2-7 name of external symbol defined in this control sectionCol 8-13 relative address of the symbol with in this control sectionCol 14-73 name and relative address for other external symbols.24. Give the use of assembler directive CSECT and USECSECT - used to divide the program into many control sectionsUSE – used to divide the program in to many blocks called program blocks25. What is the use of the assembler directive START?


The assembler directive START gives the name and starting address of the program. The format is PN START 1000HerePN – Name of the program1000 - Starting address of the program.
LOADERS AND LINKERS
1. What are the basic functions of loaders?

Loading – brings the object program into memory for execution

Relocation – modifies the object program so that it can be loaded at anaddress different from the location originally specified

Linking – combines two or more separate object programs and alsosupplies the information needed to reference them.2. Define absolute loader.The loader, which is used only for loading, is known as absolute loader.e.g. Bootstrap loader 3. What is meant by bootstrap loader?This is a special type of absolute loader which loads the first program to be run bythe computer. (usually an operating system)4. What are relative (relocative) loaders?Loaders that allow for program relocation are called relocating (relocative) loaders.5. What is the use of modification record?Modification record is used for program relocation. Each modification recordspecifies the starting address and the length of the field whose value is to be alteredand alsodescribes the modification to be performed.6. What are the 2 different techniques used for relocation?Modification record method and relocation bit method.7. Define Relocation bit method.If the relocation bit corresponding to a word of object code is set to 1, the program’s starting address is to be added to this word when the program isrelocated. Bit value 0 indicates no modification is required.8. Define bit mask.


The relocation bits are gathered together following the length indicator in each textrecord and which is called as bit mask. For e.g. the bit mask FFC(111111111100)specifies that the first 10 words of object code are to be modified during relocation.9. What is the need of ESTAB?It is used to store the name and address of the each external symbol. It alsoindicatesin which control section the symbol is defined.10. What is the use of the variable PROGADDR?It gives the beginning address in memory where the linked program is to be loaded. The starting address is obtained from the operating system.11. Write the two passes of a linking loader.Pass1: assigns address to all external symbolsPass2: it performs actual loading, relocation and linking.12. Define automatic library search.In many linking loaders the subroutines called by the program being loaded areautomatically fetched from the library, linked with the main program and loaded.This feature is referred to as automatic library search.13. List the loader options INCLUDE &DELETE.The general format of INCLUDE is INCLUDE program_name (library name) Thiscommand direct the loader to read the designated object program from a libraryand treat it as the primary loader input. The general format of DELETE commandis DELETE Csect-name It instructs the loader to delete the named control sectionsfrom the sets of programs loaded.14. Give the functions of the linking loader.The linking loader performs the process of linking and relocation. It includes theoperation of automatic library search and the linked programs are directly loadedinto the memory.15. Give the difference between linking loader and linkage editors.Linking loader Linkage editor 1.The relocation and linking is performed each time the program is loaded
1.
It produces a linked version of a program and which is written in a file for later execution Here the loading can be accomplished in a single pass Two passes are required.