Lexical and Syntax Analysis - Compiler Design - Computer Science & Information Technology Previous Year Questions

1

2013 · Computer Science & Information Technology · Compiler Design · Lexical and Syntax Analysis

Computer Science & Information Technology (CS) 2013 [Session 1]

What is the maximum number of reduce moves that can be taken by a bottom-up parser for a grammar with no epsilon- and unit-production (i.e., of type \(A \rightarrow \epsilon\) and \(A \rightarrow a\)) to parse a string with \(n\) tokens?

A

\(n/2\)

B

\(n-1\)

C

\(2n-1\)

D

\(2^n\)

Open complete paper

2

2013 · Computer Science & Information Technology · Compiler Design · Lexical and Syntax Analysis

Computer Science & Information Technology (CS) 2013 [Session 1]

Consider the following two sets of LR(1) items of an LR(1) grammar.
X -> c.X, c/d
X -> .cX, c/d
X -> .d, c/d
X -> c.X, $ X -> .cX, $ X -> .d, $ Which of the following statements related to merging of the two sets in the corresponding LALR parser is/are FALSE?
1. Cannot be merged since look aheads are different.
2. Can be merged but will result in S-R conflict.
3. Can be merged but will result in R-R conflict.
4. Cannot be merged since goto on c will lead to two different sets.

A

1 only

B

2 only

C

1 and 4 only

D

1, 2, 3 and 4

Open complete paper

3

2013 · Computer Science & Information Technology · Compiler Design · Lexical and Syntax Analysis

Computer Science & Information Technology (CS) 2013 [Session 3]

What is the maximum number of reduce moves that can be taken by a bottom-up parser for a grammar with no epsilon- and unit-production (i.e., of type A → ε and A → a) to parse a string with n tokens?

A

n/2

B

n-1

C

2n-1

D

2^n

Open complete paper

4

2013 · Computer Science & Information Technology · Compiler Design · Lexical and Syntax Analysis

Computer Science & Information Technology (CS) 2013 [Session 3]

Consider the following two sets of LR(1) items of an LR(1) grammar.
X → c.X, c/d     X → c.X, $
X → .cX, c/d     X → .cX, $
X → .d, c/d     X → .d, $
Which of the following statements related to merging of the two sets in the corresponding LALR parser is/are FALSE?
1. Cannot be merged since look aheads are different.
2. Cannot be merged but will result in S-R conflict.
3. Can be merged but will result in R-R conflict.
4. Cannot be merged since goto on c will lead to two different sets.

A

1 only

B

2 only

C

1 and 4 only

D

1, 2, 3 and 4

Open complete paper

5

2013 · Computer Science & Information Technology · Compiler Design · Lexical and Syntax Analysis

Computer Science & Information Technology (CS) 2013 [Session 4]

Consider the following two sets of LR(1) items of an LR(1) grammar.
X -> c.X, c/d
X -> .cX, c/d
X -> .d, c/d

X -> c.X, $
X -> .cX, $
X -> .d, $
Which of the following statements related to merging of the two sets in the corresponding LALR parser is/are FALSE?
1. Cannot be merged since look aheads are different.
2. Can be merged but will result in S-R conflict.
3. Can be merged but will result in R-R conflict.
4. Cannot be merged since goto on c will lead to two different sets.

A

1 only

B

2 only

C

1 and 4 only

D

1, 2, 3 and 4

Open complete paper

6

2014 · Computer Science & Information Technology · Compiler Design · Lexical and Syntax Analysis

Computer Science & Information Technology (CS) 2014 [Session 1]

A canonical set of items is given below
\(S \to L . > R\)
\(Q \to R .\)
On input symbol < the set has

A

a shift-reduce conflict and a reduce-reduce conflict.

B

a shift-reduce conflict but not a reduce-reduce conflict.

C

a reduce-reduce conflict but not a shift-reduce conflict.

D

neither a shift-reduce nor a reduce-reduce conflict.

Open complete paper

7

2014 · Computer Science & Information Technology · Compiler Design · Lexical and Syntax Analysis

Computer Science & Information Technology (CS) 2014 [Session 2]

Consider the grammar defined by the following production rules, with two operators * and +

\[ S \to T * P \]
\[ T \to U | T * U \]
\[ P \to Q + P | Q \]
\[ Q \to Id \]
\[ U \to 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

Open complete paper

8

2017 · Computer Science & Information Technology · Compiler Design · Lexical and Syntax Analysis

Computer Science & Information Technology (CS) 2017 [Session 2]

Match the following according to input (from the left column) to the compiler phase (in the right column) that processes it:

A

Input	Compiler Phase
(P) Syntax tree	(i) Code generator
(Q) Character stream	(ii) Syntax analyzer
(R) Intermediate representation	(iii) Semantic analyzer
(S) Token stream	(iv) Lexical analyzer

Open complete paper

9

2017 · Computer Science & Information Technology · Compiler Design · Lexical and Syntax Analysis

Computer Science & Information Technology (CS) 2017 [Session 2]

Which of the following statements about parser is/are CORRECT?
I. Canonical LR is more powerful than SLR.
II. SLR is more powerful than LALR.
III. SLR is more powerful than Canonical LR.

A

I only

B

II only

C

III only

D

II and III only

Open complete paper

10

2017 · Computer Science & Information Technology · Compiler Design · Lexical and Syntax Analysis

Computer Science & Information Technology (CS) 2017 [Session 2]

Consider the following expression grammar \(G\): \(E \rightarrow E - T \mid T\), \(T \rightarrow T + F \mid F\), \(F \rightarrow (E) \mid id\). Which of the following grammars is not left recursive, but is equivalent to \(G\)?

A

\(E \rightarrow E - T \mid T\), \(T \rightarrow T + F \mid F\), \(F \rightarrow (E) \mid id\)

B

\(E \rightarrow TE'\), \(E' \rightarrow -TE' \mid \epsilon\), \(T \rightarrow T + F \mid F\), \(F \rightarrow (E) \mid id\)

C

\(E \rightarrow TX\), \(X \rightarrow -TX \mid \epsilon\), \(T \rightarrow FY\), \(Y \rightarrow +FY \mid \epsilon\), \(F \rightarrow (E) \mid id\)

D

\(E \rightarrow TX \mid (TX)\), \(X \rightarrow -TX \mid +TX \mid \epsilon\), \(T \rightarrow id\)

Open complete paper

11

2018 · Computer Science & Information Technology · Compiler Design · Lexical and Syntax Analysis

Computer Science & Information Technology (CS) 2018 [Session 2]

Which one of the following statements is FALSE?

A

Context-free grammar can be used to specify both lexical and syntax rules.

B

Type checking is done before parsing.

C

High-level language programs can be translated to different Intermediate Representations.

D

Arguments to a function can be passed using the program stack.

Open complete paper

12

2018 · Computer Science & Information Technology · Compiler Design · Lexical and Syntax Analysis

Computer Science & Information Technology (CS) 2018 [Session 2]

A lexical analyzer uses the following patterns to recognize three tokens \(T_1, T_2\), and \(T_3\) over the alphabet \(\{a,b,c\}\).
\[ \begin{aligned} T_1 &: a?(b|c)^*a \\ T_2 &: b?(a|c)^*b \\ T_3 &: c?(b|a)^*c \end{aligned} \]
Note that 'x?' means 0 or 1 occurrence of the symbol \(x\). Note also that the analyzer outputs the token that matches the longest possible prefix.
If the string \(bbaacabc\) is processed by the analyzer, which one of the following is the sequence of tokens it outputs?

A

\(T_1T_2T_3\)

B

\(T_1T_1T_3\)

C

\(T_2T_1T_3\)

D

\(T_3T_3\)

Open complete paper

13

2019 · Computer Science & Information Technology · Compiler Design · Lexical and Syntax Analysis

Computer Science & Information Technology (CS) 2019 [Session 2]

Which one of the following kinds of derivation is used by LR parsers?

A

Leftmost

B

Leftmost in reverse

C

Rightmost

D

Rightmost in reverse

Open complete paper

14

2019 · Computer Science & Information Technology · Compiler Design · Lexical and Syntax Analysis

Computer Science & Information Technology (CS) 2019 [Session 2]

Consider the grammar given below:
\( S \to Aa \)
\( A \to BD \)
\( B \to b \mid \epsilon \)
\( D \to d \mid \epsilon \)
Let \( a, b, d \), and \( \$ \) be indexed as follows:

a	b	d	$
3	2	1	0

Compute the FOLLOW set of the non-terminal B and write the index values for the symbols in the FOLLOW set in the descending order. (For example, if the FOLLOW set is {a, b, d, $}, then the answer should be 3210)
Answer: __________.

Check answer

Open complete paper

15

2019 · Computer Science & Information Technology · Compiler Design · Lexical and Syntax Analysis

Computer Science & Information Technology (CS) 2019 [Session 2]

Consider the augmented grammar given below:
S' → S
S → (L) | id
L → L, S | S
Let I₀ = CLOSURE ({[S' → •S]}). The number of items in the set GOTO(I₀, ( ) is: ______.

Check answer

Open complete paper

16

2020 · Computer Science & Information Technology · Compiler Design · Lexical and Syntax Analysis

Computer Science & Information Technology (CS) 2020 [Session 2]

Consider the following grammar.
\(S \rightarrow aSB \mid d\)
\(B \rightarrow b\)
The number of reduction steps taken by a bottom-up parser while accepting the string \(aaadbbh\) is ______.

Check answer

Open complete paper

17

2020 · Computer Science & Information Technology · Compiler Design · Lexical and Syntax Analysis

Computer Science & Information Technology (CS) 2020 [Session 2]

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

Both Rule 1 and Rule 2 are L-attributed.

B

Only Rule 1 is L-attributed.

C

Only Rule 2 is L-attributed.

D

Neither Rule 1 nor Rule 2 is L-attributed.

Open complete paper

18

2021 · Computer Science & Information Technology · Compiler Design · Lexical and Syntax Analysis

Computer Science & Information Technology (CS) 2021 [Session 1]

Consider the following context-free grammar where the set of terminals is {a, b, c, d, f}. S → d a T | R f T → a S | b a T | ε R → c a T R | ε The following is a partially-filled LL(1) parsing table. | | a | b | c | d | f | $ | |---|---|---|---|---|---|---| | S | | | ① | S → d a T | ② | | | T | T → a S | T → b a T | ③ | | T → ε | ④ | | R | | | R → c a TR | | R → ε | | 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)?

Check answer

Open complete paper

19

2021 · Computer Science & Information Technology · Compiler Design · Lexical and Syntax Analysis

Computer Science & Information Technology (CS) 2021 [Session 1]

Consider the following statements.

\( S_1 \) : Every SLR(1) grammar is unambiguous but there are certain unambiguous grammars that are not SLR(1).
\( S_2 \) : For any context-free grammar, there is a parser that takes at most \( O(n^3) \) time to parse a string of length \( n \).

Which one of the following options is correct?

A

\(S_1 \) is true and \(S_2 \) is false

B

\(S_1 \) is false and \(S_2 \) is true

C

\(S_1 \) is true and \(S_2 \) is true

D

\(S_1 \) is false and \(S_2 \) is false

Open complete paper

20

2021 · Computer Science & Information Technology · Compiler Design · Lexical and Syntax Analysis

Computer Science & Information Technology (CS) 2021 [Session 2]

Consider the following augmented grammar with {#, @, <, >, a, b, c} as the set of terminals.

S' → S
S → S # c S
S → S S
S → S @
S → < S >
S → a
S → b
S → c

Let I₀ = CLOSURE({S' → •S}). The number of items in the set GOTO(GOTO(I₀, <), <) is __________

Check answer

Open complete paper