1. Which of the following identity is wrong?
a) R + R = R
b) (R*)* = R*
c) ƐR = Rɛ = R
d) ØR = RØ = RR*
Explanation: Regular grammar combined with empty does not give R* instead gives empty.
2. Grammars that can be translated to DFAs is __________
a) Left linear grammar
b) Right linear grammar
c) Generic grammar
d) All of the mentioned
Explanation: Right Linear grammar can be translate to DFA.
3. A language is regular if and only if it is accepted by finite automata.
a) The given statement statement is true
b) Given statement is false
c) Statement is partially true
d) None of the mentioned
Explanation: Regular Language is accepted by Finite Automata. Every regular language is Context free.
4. A Push Down Automata is if there is at most one transition applicable to each configuration?
a) Deterministic
b) Non deterministic
c) Finite
d) Non finite
Explanation: In every situation, only one transition is available as continuation then the result is deterministic push down automata.
5. 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
Explanation: In recursion, space used but recursive call can’t be calculated by the compiler.
6. 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
Explanation: the next step in LR parsing shall have a Reduction.
7. 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
Explanation: 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.
8. 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
Explanation: 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->ε).
9. 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
Explanation: It is associative we can see and tell.
Second productions latter part shows left recursion and is left associative.
10. 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
Explanation:
A ::= A a
| b is the left recursive language.