Multiple choice question for engineering
Set 1
1. Which of the following identity is true?
a) Ɛ +RR* = R* = ɛ + R*R
b) (R1R2)*R1 = R1 (R2R1)*
c) R*R* = R*
d) All of the mentioned
Answer
Answer: d [Reason:] The former Re can be produced from the latter one.
2. The set of all strings over ∑ = {a,b} in which all strings having bbbb as substring is
a) (a+b)* bbbb (a+b)*
b) (a+b)* bb (a+b)*bb
c) bbb(a+b)*
d) bb (a+b)*
Answer
Answer: a [Reason:] Out of all RE mentioned only the first string certainly has bbbb as substring. Rest all just have a possibility of having it.
3. The set of all strings over ∑ ={a,b} in which a single a is followed by any number of b’s a single b followed by any number of a’s is
a) ab* + ba*
b) ab*ba*
c) a*b + b*a
d) None of the mentioned
Answer
Answer: a [Reason:] ab*+ba* is the expression in which which a single a is followed by any number of b’s a single b followed by any number of a’s.
4. Regular expressions are used to represent which language
a) Recursive language
b) Context free language
c) Regular language
d) All of the mentioned
Answer
Answer: c [Reason:] Regular expression is represented by regular language.
5. The set of all strings over ∑ = {a,b} in which strings consisting a’s and b’s and ending with in bb is
a) ab
b) a*bbb
c) (a+b)* bb
d) All of the mentioned
Answer
Answer: c [Reason:] Only this expression ends with bb only.
6. If P, Q, R are three regular expressions and if P does not contain a then the equation R = R + RP has a unique solution given by
a) R = QP*
b) R = P*Q
c) R = RP
d) None of the mentioned
Answer
Answer: a [Reason:] It is an important law primarily used in conversion.
7. If L1 and L2 are regular languages is/are also regular language(s).
a) L1 + L2
b) L1L2
c) L1
d) All of the mentioned
Answer
Answer: d [Reason:] All these expression give us a regular grammar when L1 and L2 are regular.
8. Regular expression a/b denotes the set
a) {a}
b) {ab}
c) {a,b}
d) None of the mentioned
Answer
Answer: c [Reason:] Because it would give either a or b.
9. Which of the following regular expression denotes zero or more instances of an a or b?
a) a/b
b) (a/b)*
c) (ab)*
d) a*Ib
Answer
Answer: b [Reason:] This expression gives o or more instances of a or b.
10. The string (a)|((b)*(c)) is equivalent to
a) Empty
b) abcabc
c) b*c|a
d) None of the mentioned
Answer
Answer: c [Reason:] Either b or a can lead followed by c this expression can be achieved by C as well.
Set 2
1. Which languages necessarily need heap allocation in the runtime environment?
a) Those that support recursion
b) Those that use dynamic scoping
c) Allow dynamic data structure
d) Those that use global variables
Answer
Answer: c [Reason:] E.g.: Heap .
2. Given the language L-{ab, aa, baa}, which of the following strings are in LG?
1) abaabaaabaa
2) aaaabaaaa
3) baaaaabaaaab
4) baaaaabaa
a) 1,2 and 3
b) 2,3 and 4
c) 1,2 and 4
d) 1,3 and 4
Answer
Answer: c [Reason:] generates strings like aaaabaaaa
baaaaabaa
3. A simple two-pass assembler does which of the following in the first pass
a) Space for the literals
b) Total length of the program
c) It builds the symbol table for the symbols and their values.
d) All of the mentioned
Answer
Answer: d [Reason:] the two pass assembler allocates space for literals as well as calculates table length and also builds the symbol table
4. _________ or scanning is the process where the stream of characters making up the source program is read from left to right and grouped into tokens.
a) Lexical
b) Diversion
c) Modelling
d) None of the mentioned
Answer
Answer: a [Reason:] Takes input strings and gives tokens as output
5. Which of the following is used for grouping of characters into tokens?
a) Parser
b) Code optimization
c) Code generator
d) Lexical analyzer
Answer
Answer: d [Reason:] Gives tokens as output
6. The lexical analyzer takes _________as input and produces a stream of _______as output.
a) Source program, tokens
b) Token, source program
c) Either A and B
d) None of the mentioned
Answer
Answer: a [Reason:] Lexical analyser takes source program as input and token as output
7. The action of parsing the source program into proper syntactic classes is called
a) Syntax analysis
b) Lexical analysis
c) Interpretation analysis
d) General syntax analysis
Answer
Answer: b [Reason:] checks for correct syntax
8. Task of the lexical analysis
a) None of the mentioned
b) To build a literal and identifier table
c) To build a uniform symbol table
d) Both
Answer
Answer: d [Reason:] It is the task performed
9. The output of lexical analyzer is A
a) Set of regular expressions
b) Syntax tree
c) Set of tokens
d) Strings of character
Answer
Answer: c [Reason:] Tokens is the output of a lexical analyser
10. The output of a lexical analyzer is
a) Machine code
b) Intermediate code
c) Stream of tokens
d) Parse tree
Answer
Answer: c [Reason:] Set of tokens is given as an output
Set 3
1. In a two pass assembler, adding literals to literal table and address resolution of local symbols are done using
a) First pass and second respectively
b) Both second pass
c) Second pass and first respectively
d) Both first pass
Answer
Answer: d [Reason:] A two pass assembler does two passes over the source file ( the second pass can be over a file generated in the first pass ).
2. In Two pass assembler the object code generation is done during the
a) Second pass
b) First pass
c) Zeroth pass
d) Not done by assembler
Answer
Answer :a [Reason:] On the second pass, the assembler:.
• source statements into machine code
• error messages, if error has occurred.
3. Pick the machine independent phase of the compiler
a) Syntax analysis
b) Code generation
c) Lexical analysis
d) A, C and D
Answer
Answer: d [Reason:] Machine independent phases are Lexical analysis, Syntax analysis, Semantic analysis, Intermediate code generation and sometime code optimization.
4. A system program that combines the separately compiled modules of a program into a form suitable for execution
a) Assembler
b) Linking loader
c) Cross compiler
d) Load and Go
Answer
Answer: b [Reason:] Combines the modules which have been compiled separately
5. Which of the following type of software should be used if you need to create, edit and print document?
a) Word processing
b) Spreadsheet
c) Desktop publishing
d) UNIX
Answer
Answer: an [Reason:] Application software such as word processors.
6. Output file of the Lex is _________ is the input file is Sam.
a) sam
b) sam.yy.c
c) sam.lex
d) sam.obj
Answer
Answer: b [Reason:] This Produce the file “sam.yy.c”, which we can then compile with g++
7. Type checking is normally done during
a) Lexical analysis
b) Syntax analysis
c) Syntax directed translation
d) Code generation
Answer
Answer: c [Reason:] It enables the compiler to do type checking
8. Yacc is available as a command on the
a) MINIX
b) UNIX
c) DOS
d) None of the mentioned
Answer
Answer: b [Reason:] Unix provides with a YACC command
9.Loading process can be divided into two programs. The first is binder the other is
a) Linkage editor
b) Module Loader
c) Relocate
d) None of the mentioned
Answer
Answer: b [Reason:] A module loader is the answer.
10. In Lex, a class is complemented by first placing
a) ^
b) OR
c) –
d) NOT
Answer
Answer: a [Reason:] ^ =complement.
Set 4
1. Which of the following derivations does a top-down parser use while parsing an input string?
a) Leftmost derivation
b) Leftmost derivation in reverse
c) Rightmost derivation
d) Rightmost derivation in reverse
Answer
Answer: a [Reason:] In top down parser takes input from Left to right constructing leftmost derivation of the sentence.
2. The process of assigning load addresses to the various parts of the program and adjusting the code and data in the program to reflect the assigned addresses is called
a) Assembly
b) Parsing
c) Relocation
d) Symbol resolute
Answer
Answer: c [Reason:] Relocation is the process of replacing symbolic references or names of libraries with actual usable addresses in memory before running a program. Linker performs it during compilation.
3. Which of the following statements is false?
a) Left as well as right most derivations can be in Unambiguous grammar
b) An LL (1) parser is a top-down parser
c) LALR is more powerful than SLR
d) Ambiguous grammar can’t be LR (k)
Answer
Answer: a [Reason:] If a grammar has more than one leftmost (or rightmost) derivation the grammar is ambiguous. Sometimes in unambiguous grammar the rightmost derivation and leftmost derivations may differ.
4. Which of the following grammar rules violate the requirements of an operator grammar?
(i) P -> QR
(ii) P -> QsR
(iii) P -> ε
(iV) P -> QtRr
a) (i) only
b) (i) and (iii) only
c) (ii) and (iii) only
d) (iii) and (iv) only
Answer
Answer: b [Reason:]
An operator precedence parser is a bottom-up parser that interprets an operator-precedence grammar.
Consider the grammar with the following translation rules and E as the start symbol.
A -> A1 #B {A.value = A1.value * B.value}
| B {A.value = B.value}
B-> B1 & F {B.value = B1.value + C.value}
|C {B.value= C.value }
C -> num {C.value = num.value}.
5. Compute E.value for the root of the parse tree for the expression:2 # 3 & 5 # 6 &4.
a) 200
b) 180
c) 160
d) 40
Answer
Answer: c [Reason:] higher precedence operator will never produce an expression with operator with lower precedence.&># in terms of precedence order.
6. 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 *
Answer
Answer: b [Reason:] Precedence is that a higher precedence operator will never produce an expression with operator with lower precedence.
In the given grammar MINUS has higher precedence than ASTERIX.
7. Consider a program P that consists of two source modules M1(contains reference to a function defined in M2) and M2 contained in two different files.
a) Edit time
b) Compile time
c) Link time
d) Load time
Answer
Answer : c [Reason:]
Compiler transforms source code into the machine language which is in binary .
Kinds of object codes:
defined symbols, which allow it to be called by other modules,
ii undefined symbols, which call the other modules where these symbols are defined, and
iii symbols which are used internally within object file for relocation.
8. Which of the following suffices to convert an arbitrary CFG to an LL(1) grammar?
a) Removing left recursion only
b) Factoring the grammar alone
c) Factoring & left recursion removal
d) None of the mentioned
Answer
Answer: d [Reason:]
Factoring as well as left recursion removal do not suffice to convert an arbitrary CFG to LL(1) grammar.
9. Assume that the SLR parser for a grammar G has n1 states and the LALR parser for G has n2 states.
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 mentioned
Answer
Answer: b [Reason:] SLR parser has less range of context free languages than LALR but still both n1 & n2 are same for SLR & LALR respectively.
10. Match the following.
P. Regular expression 1. Syntax analysis Q. Pushdown automata 2. Code generation R. Dataflow analysis 3. Lexical analysis S. Register allocation 4. Code optimization
a) P-4. Q-1, R-2, S-3
b) P-3, Q-1, R-4, S-2
c) P-3, Q-4, R-1, S-2
d) P-2, Q-1, R-4, S-3
Answer
Answer: b [Reason:]
Syntax analysis has Regular expressions . The code optimization goes hand in hand with data flow analysis. Whereas CFG is related to PDA which is related to syntax analysis Register allocation is used in reference with code generation.
Set 5
1. Find the TRUE statement?
I. There exist parsing algorithms for some programming languages which has O(3) complexity.
II. A programming language which allows recursion can be implemented
with static storage allocation.
III. No L-attributed definition can be evaluated in The framework
of bottom-up parsing.
IV. Code improving transformations can be performed at both intermediate code level and source
Language.
a) I and II
b) I and IV
c) III and IV
d) I III and IV
Answer
Answer: b [Reason:] In recursion, space used but recursive call can’t be calculated by the compiler.
2. Which of the following describes a handle (as applicable to LR-parsing) appropriately?
a) Position where next reduce or shift operation will occur
b) The next step has use of Non-terminal for reduction
c) used for reduction in a coming-up step along with a position in the sentential form where the next shift or reduce operation will occur
d) used in the next step for reduction along with a position in the sentential form where the right hand side of the production may be found
Answer
Answer: d [Reason:] the next step in LR parsing shall have Reduction .
3. Which one of the following is a top-down parser?
a) Recursive descent parser
b) Operator precedence parser
c) An LR(k) parser
d) An LALR(k) parser
Answer
Answer: a [Reason:] Recursive Descent also known as top down parsing also known to be LL(1).
Consider the following two statements:
P: Every regular grammar is LL(1)
Q:Regular is LR(1) grammar.
4. Which of the following is TRUE?
a) Both P and Q are true
b) P is true and Q is false
c) P is false and Q is true
d) Both P and Q are false
Answer
Answer: c [Reason:] Ambiguity can be seen in regular grammar
S → aA/a
A → aA/ε
In above grammar, string ‘a’ has two leftmost
derivations.
S → aA
S → a
S->a (using A->ε).
5. Consider the grammar defined by the following production rules
S –> T * P
T –> U | T * U
P –> Q + P | Q
Q –> Id
U –> Id
Which one of the following is TRUE?
a) + is left associative, while ∗ is right associative
b) + is right associative, while ∗ is left associative
c) Both + and ∗ are right associative
d) Both + and ∗ are left associative
Answer
Answer: b [Reason:]
It is associative we can see and tell.
Second productions latter part shows left recursion and is left associative.
6. The grammar A → AA | (A) | e is not suitable for predictive-parsing because the grammar is
a) Ambiguous
b) Left recursive
c) Right recursive
d) An operator grammar
Answer
Answer: b [Reason:]
A ::= A a
| b is the left recursive language.
7. Consider the grammar
E → E + n | E × n | n
For a sentence n + n × n, the handles in the right-sentential form of the reduction are
a) n, E + n and E + n × n
b) n, E + n and E + n × n
c) n, n + n and n + n × n
d) n, E + n and E × n
Answer
Answer: d [Reason:] E → E + n {Applying E → E + n }
→ E + E * n {Applying E → E * n }
→ E + n * n {Applying E → n }
→ n + n * n {Applying E → n } .
8. Which grammar rules violate the requirements of an operator grammar ?
1. P → Q R
2. P → Q s R
3. P → ε
4. P → Q t R r
a) 1 only
b) 1 and 3 only
c) 2 and 3 only
d) 3 and 4 only
Answer
Answer:b [Reason:] Top down parsin: We begin with the start symbol and compare the right side of the different productions against the first piece of input to see which of the productions should be used.
9. Which of the following suffices to convert an arbitrary CFG to an LL(1) grammar?
a) Removing left Recursive alone
b) Factoring the grammar alone
c) Along with removing left recursion we also perform the factoring of the grammar
d) None of the mentioned
Answer
Answer: d [Reason:] Removing left recursion and factoring the grammar do not suffice to convert an arbitrary CFG to LL(1) grammar.
10. In a bottom-up evaluation of a syntax directed definition its inherited attributes can do which of the following?
a) Always evaluated
b) Can be evaluated if the definition is L attributed
c) Can be evaluated if the definition has synthesized attributes
d) Never be evaluated
Answer
Answer: b [Reason:] A Syntax Directed Definition (SDD) is called S Attributed if it has only synthesized attributes. Also the
L-Attributed Definitions contain both synthesized and inherited attributes but do not need to build a dependency graph to evaluate them.
Total Views: 21
