Paper 2 CS · UNIT 08 · MOCK TEST

Mock 7 – Lexical & Syntax Analysis (Parsing)

Unit 8: Theory of Computation and Compilers · 26 questions · about 31 minutes. Press End Mock any time to see your score and the correct answers.

All 10 topic-wise mocks in this unit

0 / 26 answered 00:00

Consider the following Context Free Grammar (G):

S → A B
B → + A B | ε
A → C D
D → * C D | ε
C → [ S ] | x

Variable = { S, A, B, C, D }

Terminals = { +, *, [, ], x }

Q1. In the LL(1) Parsing table of the given CFG, how many valid non-blank entries will be there in the rows for variables 'B' and 'D'?

AB = 3 entries; D = 4 entries BB = 6 entries; D = 5 entries CB = 2 entries; D = 3 entries DB = 1 entry; D = 2 entries

Q2. Arrange the following parsers in increasing order of their power of handling grammars, i.e. from the least powerful parser to the most powerful parser.
A. LR(0)
B. LR(1)
C. LALR(1)
D. LL(0)
E. SLR
Choose the correct answer from the options given below:

ALL(0) → LR(0) → SLR → LR(1) → LALR(1) BSLR → LR(0) → LL(0) → LR(1) → LALR(1) CLL(0) → LR(0) → SLR → LALR(1) → LR(1) DLR(0) → LL(0) → SLR → LR(1) → LALR(1)

Q3. yacc is which of the following parsers?

APredictive Parser BSLR Parser CCLR Parser DLALR Parser

Q4. Consider the grammar E → E + n | E × n | n. For the sentence n + n × n, the handles in the right-sentential forms of the reduction are:

An, E + n and E + n × n Bn, E + n and E + E × n Cn, n + n and n + n × n Dn, E + n and E × n

Q5. Match List I with List II according to the input to the compiler phase that processes it:

List I	List II
(a) Syntax tree	(I) Code generator
(b) Intermediate representation	(II) Semantic analyzer
(c) Token stream	(III) Lexical analyzer
(d) Character stream	(IV) Syntax analyzer

A(a)-(IV), (b)-(III), (c)-(I), (d)-(II) B(a)-(II), (b)-(I), (c)-(IV), (d)-(III) C(a)-(II), (b)-(IV), (c)-(I), (d)-(III) D(a)-(IV), (b)-(I), (c)-(II), (d)-(III)

Q6. Which of the following parsers is the most powerful?

AOperator precedence BSLR CCanonical LR DLALR

Q7. Shift-reduce conflicts are resolved by:

ALeft recursion BLeft factoring CAmbiguity DAssociativity and precedence

Q8. Match List I with List II

List I	List II
A. A → aB \| a (a ∈ T; A, B ∈ V)	I. Recursive Descent Parser
B. A → BC \| a (a ∈ T; A, B, C ∈ V)	II. Turing Machine
C. LL(1) grammar	III. Chomsky Normal Form
D. Halting problem	IV. Finite Automata

AA-IV, B-III, C-I, D-II BA-III, B-I, C-II, D-IV CA-II, B-IV, C-III, D-I DA-IV, B-III, C-II, D-I

Q9. Which of the following is a function of the semantic analysis phase of compilation?

AType conversion BTokenization CLoop optimization DData flow analysis

Q10. Match List I with List II

List I	List II
A. Back Tracking	I. Automata
B. Infinite languages with matching numbers	II. Undecidable Problem
C. Canonical LR Parser	III. Predictive Parser
D. Post Correspondence Problem	IV. Large number of states

AA-I, B-II, C-III, D-IV BA-II, B-III, C-I, D-III CA-IV, B-III, C-II, D-I DA-III, B-I, C-IV, D-II

Q11. The number of tokens in the line ' for i in range (begin; end ; step) : ' is:

A4 B7 C8 D12

Q12. While processing a string, an LR parser reads the input

AFrom right to left BFrom left to right CEither from left to right or right to left DFrom the centre of the string

Q13. Match List I with List II (stack and input configurations)

List I	List II
A. Initial configuration of stack and input in LL parsing	I. $ \| w$
B. Final configuration of stack and input in LL parsing	II. $ \| $
C. Initial configuration of stack and input in LR parsing	III. $S \| w$
D. Final configuration of stack and input in LR parsing	IV. $S \| $

AA-III, B-IV, C-I, D-II BA-III, B-II, C-I, D-IV CA-II, B-III, C-IV, D-I DA-II, B-IV, C-I, D-III

Q14. Consider the following statements:
Statement I: An LALR parser is more powerful than a canonical LR parser.
Statement II: An SLR parser is more powerful than LALR.
Which of the following is correct?

AStatement I true and Statement II false BStatement I false and Statement II true CBoth Statement I and Statement II false DBoth Statement I and Statement II true

Q15.

Arrange the following parsers in increasing order of their power of handling grammars i.e. from the least powerful parser to the most powerful parser.

A. LR (0)

B. LR (1)

C. LALR(1)

D. LL (0)

E. SLR

ALL(0) → LR(0) → SLR → LR(1) → LALR(1) BSLR → LR(0) → LL(0) → LR(1) → LALR(1) CLL(0) → LR(0) → SLR → LALR(1) → LR(1) DLR(0) → LL(0) → SLR → LR(1) → LALR(1)

Q16.

Match List I with List II. List I: A. A → aB | a (a ∈ T; A, B ∈ V), B. A → BC | a (a ∈ T; A, B, C ∈ V), C. LL(1) grammar, D. Halting problem. List II: I. Recursive descent parser, II. Turing machine, III. Chomsky Normal Form, IV. Finite automata.

AA-IV, B-III, C-I, D-II BA-III, B-I, C-II, D-IV CA-II, B-IV, C-III, D-I DA-IV, B-III, C-II, D-I

Q17.

Match List-I with List-II :

AA-I, B-II, C-III, D-IV BA-II, B-III, C-I, D-III CA-IV, B-III, C-II, D-I DA-III, B-I, C-IV, D-Il

Q18.

Match List - I with List - II according to input to the compiler phase that process it :

A(a)-(IV), (b)-(III), (c)-(I), (d)-(II) B(a)-(II), (b)-(I), (c)-(IV), (d)-(III) C(a)-(II), (b)-(IV), (c)-(I), (d)-(III) D(a)-(IV), (b)-(I), (c)-(II), (d)-(III)

Q19.

Which of the following parser is most powerful parser?

AOperator precedence BSLR CCanonical LR DLALR

Q20.

While processing a string by an LR parser, the reading of the given string by the parser is-

AFrom right to left BFrom left to right CCan be either from left to right or right to left DFrom the centre of the given string

Q21.

Match the following based on the language accepted by using brute force method of parsing.

Aa-IV, b-III , c-I, d-II Ba-II, b-IV, c-I, d-III Ca-I, b- IV, c-III, d-II Da-II, b-III, c-I, d-IV

Directions (Q96–100): A Turing machine for L = {aⁿbᵐcⁿdᵐ | n ≥ 1, m ≥ 1} is designed as M = ({q0, …, q7, qf}, {a, b, c, d}, {a, b, c, d, X1, X2, Y1, Y2, B}, δ, q0, B, {qf}). X1 and X2 mark matched a's and c's; Y1 and Y2 mark matched b's and d's. Part of δ is given in the transition table (shown with each question); cells M1–M5 are to be filled.

Q22.

What is the Move in the cell with number 'M4' of the resultant Table?

A(q5, Y1, L) B(q3, Y1, R) C(q4, Y1, L) DError entry

Q23.

Statement I: The LALR parser is more powerful than the canonical LR parser. Statement II: The SLR parser is more powerful than LALR. Which is correct?

AStatement I true and Statement II false BStatement I false and Statement II true CBoth Statements I and II false DBoth Statements I and II true

Q24.

Given below are two statements

Statement I: LL(1) and LR are examples of Bottom‐up parsers.

Statement II: Recursive descent parser and SLR are examples of Top‐down parsers In light of the above statements, choose the correct answer from the options given below

ABoth Statement I and Statement II are true BBoth Statement I and Statement II are false CStatement I is true but Statement II is false DStatement I is false but Statement II is true

Q25.

Shift-reduce parser consists of

(a) input buffer

(b) stack

A(a) and (b) only B(a) and (c) only C(c) only D(a), (b) and (c)

Q26.

A bottom-up parser generates :

ALeft-most derivation in reverse BRight-most derivation in reverse CLeft-most derivation DRight-most derivation

Next: Mock 8 – Semantic Analysis, Code Generation & Optimisation (Part 1) →