Syntax Analysis and Parsing Questions and Answers

Q: Arrange these grammar transformations in the order they are normally applied when preparing a grammar for predictive parsing.1. perform left factoring2. remove ambiguity from the grammar3. compute the FIRST and FOLLOW sets4. eliminate left recursion

Correct answer: 2 - 4 - 1 - 3Remove ambiguity first, since neither of the other transformations helps with it and the grammar must be unambiguous before either is worth doing. Then eliminate left recursion, which a top-down parser cannot tolerate at all. Then left factor, which removes the remaining need for lookahead beyond one token. Only then compute FIRST and FOLLOW, on the grammar that will actually be used.

Q: Consider the following statements about FIRST and FOLLOW.1. Epsilon may belong to a FIRST set.2. The end of input marker may belong to a FOLLOW set.3. Epsilon may belong to a FOLLOW set.

Correct answer: 1 and 2 onlyStatements 1 and 2 are correct: epsilon belongs to the FIRST set of anything that can derive the empty string, and the end of input marker belongs to the FOLLOW set of the start symbol. Statement 3 is wrong - a FOLLOW set contains terminals and the end marker, and epsilon is not something that can follow a symbol.

21.

Arrange these grammar transformations in the order they are normally applied when preparing a grammar for predictive parsing.
1. perform left factoring
2. remove ambiguity from the grammar
3. compute the FIRST and FOLLOW sets
4. eliminate left recursion

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

Answer: A

Correct answer: 2 - 4 - 1 - 3

Remove ambiguity first, since neither of the other transformations helps with it and the grammar must be unambiguous before either is worth doing. Then eliminate left recursion, which a top-down parser cannot tolerate at all. Then left factor, which removes the remaining need for lookahead beyond one token. Only then compute FIRST and FOLLOW, on the grammar that will actually be used.

Discuss in Forum

22.

FIRST of a string of grammar symbols is

A.the first production listed for the leading nonterminal
B.the set of terminals that can begin a string derived from it
C.the set of terminals that can immediately follow it in a derivation
D.the set of nonterminals appearing anywhere within the string

Answer: B

Correct answer: the set of terminals that can begin a string derived from it

FIRST tells the parser what it may expect to see if it chooses a given production, so comparing the FIRST sets of the alternatives is how the choice is made. Epsilon is included when the string can derive nothing at all, and it is that case which brings FOLLOW into the calculation.

Discuss in Forum

23.

FOLLOW of a nonterminal A is

A.the set of productions in which A appears on the right side
B.the set of nonterminals that can derive the same strings as A
C.the set of terminals that can appear immediately after A
D.the set of terminals that can begin any string derived from A

Answer: C

FOLLOW is needed to decide when to apply an epsilon production, since the parser must then look at what comes after A. The end marker is in FOLLOW of the start symbol by definition. Computing the sets is an iterative process repeated until nothing more changes.

Discuss in Forum

24.

Consider the following statements about FIRST and FOLLOW.
1. Epsilon may belong to a FIRST set.
2. The end of input marker may belong to a FOLLOW set.
3. Epsilon may belong to a FOLLOW set.

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

Answer: D

Correct answer: 1 and 2 only

Statements 1 and 2 are correct: epsilon belongs to the FIRST set of anything that can derive the empty string, and the end of input marker belongs to the FOLLOW set of the start symbol. Statement 3 is wrong - a FOLLOW set contains terminals and the end marker, and epsilon is not something that can follow a symbol.

Discuss in Forum

25.

A grammar is LL(1) if

A.one token of lookahead suffices to choose the correct production
B.it has at most one production for each of its nonterminals
C.it can be parsed by some bottom-up parser without conflicts
D.every one of its productions has exactly one symbol on the right

Answer: A

Correct answer: one token of lookahead suffices to choose the correct production

The two Ls mean scanning left to right and producing a leftmost derivation, and the 1 is the tokens of lookahead. The condition is that for each nonterminal the FIRST sets of its alternatives are disjoint, and where an alternative can be empty, that its FIRST set is disjoint from the nonterminal’s FOLLOW set.

Discuss in Forum

26.

An ambiguous grammar can never be

A.written down using only context free productions
B.LL(1) or LR(1), since both require a unique parsing action
C.used to describe any real programming language construct
D.converted into a finite automaton for scanning purposes

Answer: B

Correct answer: LL(1) or LR(1), since both require a unique parsing action

Both methods build a table with one entry per state and lookahead, and ambiguity means two different actions are needed in one place, which appears as a conflict. The grammar may still be written down and may describe a real construct perfectly well - it simply cannot be parsed deterministically without being rewritten or a conflict resolution rule supplied.

Discuss in Forum

27.

A grammar with left recursion can never be

A.unambiguous, because recursion always creates two parse trees
B.used with a parser generator of any kind whatsoever
C.LL(1), since the predictive parser would not terminate
D.LR(1), because bottom-up parsing cannot handle recursion

Answer: C

Correct answer: LL(1), since the predictive parser would not terminate

A predictive parser expanding a left recursive nonterminal would call itself without consuming a token and never return. Left recursion is therefore fatal to LL parsing and must be eliminated first; LR parsing handles it without difficulty, and in fact prefers it. Nothing about left recursion makes a grammar ambiguous.

Discuss in Forum

28.

Match each grammar defect with the transformation that addresses it.
List I
A. left recursion
B. common prefix in alternatives
C. two parse trees for one sentence
D. nonterminal deriving no terminal string
List II
1. rewriting to remove ambiguity
2. recursion elimination
3. removal of useless symbols
4. left factoring

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

Answer: D

Each defect blocks a different aspect of parsing. Recognising which transformation applies is the routine first step in preparing any grammar for a parser generator. Most generators report the defect precisely enough to identify the offending rule.

Discuss in Forum

29.

A useless nonterminal in a grammar is one that

A.derives no terminal string or is unreachable from the start symbol
B.appears on the right hand side of exactly one production only
C.has more alternatives than any other nonterminal present
D.derives only the empty string and nothing else besides

Answer: A

Correct answer: derives no terminal string or is unreachable from the start symbol

Either fault makes the nonterminal contribute nothing to the language: one that derives no terminal string can never complete a derivation, and one unreachable from the start symbol can never begin one. Both are removed before parsing, since they only complicate the tables and can mask genuine errors in the grammar.

Discuss in Forum

30.

The two broad families of parsing methods are

A.single pass parsing and multipass parsing of the source
B.top-down parsing and bottom-up parsing
C.recursive parsing and iterative parsing of the token stream
D.deterministic parsing and probabilistic parsing of the input

Answer: B

Top-down builds the tree from the root toward the leaves, bottom-up from the leaves toward the root. Every practical parsing algorithm belongs to one family or the other. The choice determines both the grammars accepted and the shape of the code written.

Discuss in Forum

Loading…

Topics

Other Subjects

Tags: Syntax Analysis and Parsing Questions and Answers || Syntax Analysis and Parsing MCQ Questions and Answers || Syntax Analysis and Parsing GK Questions and Answers || Syntax Analysis and Parsing GK MCQ Questions || Syntax Analysis and Parsing Multiple Choice Questions and Answers || Syntax Analysis and Parsing GK || GK on Syntax Analysis and Parsing || Compiler Design Questions and Answers || Compiler Design MCQ Questions and Answers || Compiler Design GK Questions and Answers || GK on Compiler Design

Syntax Analysis and Parsing Questions and Answers

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications