Top Down Parsing Questions and Answers

Q: Consider the following conditions for a grammar to be LL(1).1. No two alternatives of a nonterminal have overlapping FIRST sets.2. If an alternative derives epsilon, the others avoid FOLLOW of that nonterminal.3. The grammar contains no productions with more than two symbols.

Correct answer: 1 and 2 onlyStatements 1 and 2 are precisely the LL(1) conditions: the alternatives must be distinguishable on one token of lookahead, and where one derives epsilon the others must avoid whatever may follow the nonterminal. Statement 3 confuses this with a normal form - the length of a right side has nothing to do with whether the grammar is LL(1).

Q: Arrange the steps of building a predictive parsing table in the order performed.1. compute FIRST and FOLLOW for every nonterminal2. remove left recursion from the grammar3. fill each table cell from the FIRST and FOLLOW sets4. left factor the remaining common prefixes

Correct answer: 2 - 4 - 1 - 3The transformations must come before the analysis, since they change the grammar the sets are computed from. Left recursion is removed first, then common prefixes are factored out, then FIRST and FOLLOW are computed on the resulting grammar, and only then can the table be filled from those sets.

Q: The end of input marker is placed in the FOLLOW set of

Correct answer: the start symbol of the grammarThe end of input marker can follow the start symbol and nothing else at the outermost level, so it is placed in FOLLOW of the start symbol and propagates from there to whatever can appear at the end of a sentence. It is not added to every nonterminal, though many will acquire it through propagation.

Q: A grammar has 5 nonterminals and 7 terminals. Including the end of input marker, how many cells does the LL(1) parsing table contain?

Correct answer: 40The rows are the nonterminals and the columns the terminals together with the end of input marker: \[ 5 \times (7 + 1) = 40. \] Forgetting the marker gives 35, which is the trap here - the column for the end of input is what allows the parser to accept, and to reduce by an epsilon production at the end of the input.

21.

Consider the following conditions for a grammar to be LL(1).
1. No two alternatives of a nonterminal have overlapping FIRST sets.
2. If an alternative derives epsilon, the others avoid FOLLOW of that nonterminal.
3. The grammar contains no productions with more than two symbols.

A.1 and 2 only
B.3 only
C.1 only
D.All of them

Answer: A

Correct answer: 1 and 2 only

Statements 1 and 2 are precisely the LL(1) conditions: the alternatives must be distinguishable on one token of lookahead, and where one derives epsilon the others must avoid whatever may follow the nonterminal. Statement 3 confuses this with a normal form - the length of a right side has nothing to do with whether the grammar is LL(1).

Discuss in Forum

22.

The following all prevent a grammar from being LL(1) EXCEPT

A.ambiguity in the grammar as written
B.right recursion in one of the productions
C.a rule that recurses upon itself at its leftmost position
D.two alternatives sharing a common prefix

Answer: B

Left recursion, common prefixes and ambiguity each create a table conflict. Right recursion is perfectly acceptable and is in fact what left recursion elimination produces. Bottom up parsers by contrast prefer left recursion for exactly the opposite reason.

Discuss in Forum

23.

Arrange the steps of building a predictive parsing table in the order performed.
1. compute FIRST and FOLLOW for every nonterminal
2. remove left recursion from the grammar
3. fill each table cell from the FIRST and FOLLOW sets
4. left factor the remaining common prefixes

A.4 - 2 - 1 - 3
B.2 - 1 - 4 - 3
C.2 - 4 - 1 - 3
D.3 - 1 - 4 - 2

Answer: C

Correct answer: 2 - 4 - 1 - 3

The transformations must come before the analysis, since they change the grammar the sets are computed from. Left recursion is removed first, then common prefixes are factored out, then FIRST and FOLLOW are computed on the resulting grammar, and only then can the table be filled from those sets.

Discuss in Forum

24.

Epsilon appears in FIRST(X) exactly when

A.X happens to be a terminal that no scanner would ever emit
B.X heads more than one of the rules written in the grammar
C.X occurs nowhere at all on the right hand side of any production
D.X is capable of deriving the empty string

Answer: D

The marker records that the symbol may vanish entirely, which is what forces the parser to look at FOLLOW instead. Whether epsilon propagates through a whole right side depends on every symbol in it being able to vanish, and tracking that is the part most often got wrong when the sets are computed by hand.

Discuss in Forum

25.

A nonterminal appearing at the very end of a right side inherits into its FOLLOW set

A.the whole FOLLOW set of the nonterminal on the left of that production
B.the entire FIRST set of the nonterminal on the left of the production
C.nothing whatever
D.only the end of input marker and no other terminal symbol besides

Answer: A

Whatever can follow the left side can equally follow the last symbol of any of its right sides, so the whole set is copied across. The same rule applies to a symbol whose successors can all derive the empty string, which is where the computation most often goes astray when it is worked through by hand.

Discuss in Forum

26.

The end of input marker is placed in the FOLLOW set of

A.no nonterminal
B.the start symbol of the grammar
C.every nonterminal in the grammar without exception
D.only those nonterminals that can derive epsilon

Answer: B

Correct answer: the start symbol of the grammar

The end of input marker can follow the start symbol and nothing else at the outermost level, so it is placed in FOLLOW of the start symbol and propagates from there to whatever can appear at the end of a sentence. It is not added to every nonterminal, though many will acquire it through propagation.

Discuss in Forum

27.

Given productions S goes to aAb and A goes to c or epsilon, FOLLOW(A) is

A.the set containing c alone
B.the set containing both a and b
C.the set containing b alone
D.the set containing a alone

Answer: C

A appears in the right side aAb followed immediately by the terminal b, so FIRST of what follows A is simply b. Nothing else can follow A anywhere in this grammar. Small grammars like this one are worth working through by hand until the rule is automatic.

Discuss in Forum

28.

Given productions S goes to AB, A goes to a or epsilon and B goes to b, FIRST(S) is

A.the set containing a alone
B.the set containing b alone
C.the set containing a, b and epsilon
D.the set containing a and b

Answer: D

S begins with A, which contributes a. Because A can also derive epsilon, FIRST of B contributes b as well. Epsilon is not included since S itself cannot derive the empty string. Tracking when epsilon propagates is the part most often got wrong by hand.

Discuss in Forum

29.

A grammar has 5 nonterminals and 7 terminals. Including the end of input marker, how many cells does the LL(1) parsing table contain?

A.40
B.35
C.12
D.70

Answer: A

Correct answer: 40

The rows are the nonterminals and the columns the terminals together with the end of input marker: \[ 5 \times (7 + 1) = 40. \] Forgetting the marker gives 35, which is the trap here - the column for the end of input is what allows the parser to accept, and to reduce by an epsilon production at the end of the input.

Discuss in Forum

30.

An entry M[A, a] in a predictive parsing table contains

A.a list of every terminal permitted to come after A in a sentence
B.whichever rule fits when A heads the stack and a is in hand
C.the state that the parser should move to on reading the token a
D.whichever action is to be run when A has been recognised

Answer: B

Correct answer: whichever rule fits when A heads the stack and a is in hand

The cell holds the production to apply when the nonterminal A is on top of the stack and the lookahead is the terminal a. An empty cell means no production applies and the parser reports an error. A cell with two entries means the grammar is not LL(1).

Discuss in Forum

Loading…

Topics

Other Subjects

Tags: Top Down Parsing Questions and Answers || Top Down Parsing MCQ Questions and Answers || Top Down Parsing GK Questions and Answers || Top Down Parsing GK MCQ Questions || Top Down Parsing Multiple Choice Questions and Answers || Top Down Parsing GK || GK on Top Down Parsing || Compiler Design Questions and Answers || Compiler Design MCQ Questions and Answers || Compiler Design GK Questions and Answers || GK on Compiler Design

Top Down Parsing Questions and Answers

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications