Syntax Analysis and Parsing Questions and Answers

31.

A top-down parser constructs the parse tree

A.from the middle outward, starting at the deepest nesting
B.in an arbitrary order determined by the input token stream
C.from the root downward, expanding nonterminals as it goes
D.from the leaves upward, combining symbols into larger units

Answer: C

Correct answer: from the root downward, expanding nonterminals as it goes

A top-down parser starts with the start symbol and works towards the input, choosing a production for each nonterminal and expanding it, so the tree is built from the root. A bottom-up parser does the reverse, combining tokens into larger structures until it reaches the start symbol.

Discuss in Forum

32.

A bottom-up parser constructs the parse tree

A.from the root downward, predicting which production applies
B.by first building every possible subtree and then selecting one
C.without building a tree at all, since none is ever required
D.from the leaves upward, reducing right sides to their left sides

Answer: D

Reductions replace a matched right side by its nonterminal, building the tree upward. The sequence of reductions traced backward gives a rightmost derivation of the input string. This correspondence is what justifies calling the method a rightmost parse.

Discuss in Forum

33.

Recursive descent parsing implements

A.one procedure per nonterminal, called as the grammar dictates
B.a table driven automaton indexed by state and lookahead token
C.a stack of grammar symbols manipulated by shift and reduce actions
D.a finite automaton constructed from the token patterns

Answer: A

Correct answer: one procedure per nonterminal, called as the grammar dictates

Recursive descent turns the grammar directly into code: each nonterminal becomes a procedure whose body follows its productions, calling the procedures for the nonterminals on the right side and matching the terminals. The call stack does the work a parse stack would otherwise do, which is what makes such parsers so readable.

Discuss in Forum

34.

Predictive parsing is recursive descent

A.restricted to grammars containing no recursion at all
B.without backtracking, the production chosen by lookahead alone
C.with unlimited backtracking over all of the possible productions
D.implemented bottom-up rather than top-down as usual

Answer: B

Correct answer: without backtracking, the production chosen by lookahead alone

Predictive parsing is recursive descent with the guarantee that the lookahead always determines which production to use, so no alternative ever has to be abandoned and retried. The grammar must be LL(1) for that guarantee to hold, which is why left recursion is eliminated and left factoring applied first.

Discuss in Forum

35.

Backtracking in a top-down parser is undesirable chiefly because

A.it stops the parser from ever announcing a fault in the input
B.the grammar has to be ambiguous before backtracking becomes possible
C.it can take exponential time and undoes semantic actions already run
D.it requires more memory than any machine is able to provide

Answer: C

Correct answer: it can take exponential time and undoes semantic actions already run

Backtracking may explore many alternatives before finding the right one, and the cost can grow exponentially with the input. Worse for a practical compiler, any semantic action already executed - a symbol table entry, a line of output - must be undone, which is difficult to do correctly and is why predictive parsing is preferred.

Discuss in Forum

36.

A table driven predictive parser uses a stack containing

A.the states belonging to a deterministic machine
B.the tokens read so far from the input stream
C.the semantic values of the expressions parsed so far
D.grammar symbols still to be matched or expanded

Answer: D

Correct answer: grammar symbols still to be matched or expanded

The stack of a predictive parser holds what the parser still expects to see. A terminal on top is matched against the input and popped; a nonterminal is replaced by the right side of the production the table selects. It is a direct simulation of the recursive descent call stack without the recursion.

Discuss in Forum

37.

An entry M[A, a] of an LL(1) parsing table holds

A.the production to apply when A is on top and a is the next token
B.the state to move to when the automaton next reads the token a
C.the semantic action associated with the nonterminal A
D.the set of terminals that may follow the nonterminal A

Answer: A

The table is indexed by nonterminal and lookahead terminal. Two productions in one cell is exactly the LL(1) conflict that makes the grammar unsuitable for predictive parsing. Such a conflict usually points at a common prefix or at left recursion.

Discuss in Forum

38.

A grammar has 6 nonterminals and 9 terminals. How many cells does its LL(1) parsing table have, counting the end marker as a terminal?

A.90
B.60
C.54
D.15

Answer: B

The table is indexed by nonterminal and by terminal including the end marker, giving 6 times 10 which is 60 cells. Most cells are error entries and only a few hold productions. Sparse representations therefore save a great deal of space in practice.

Discuss in Forum

39.

A shift-reduce parser performs a shift when

A.it detects that the input contains a syntax error
B.it reaches the end of the input token stream
C.it pushes the next input token onto the stack
D.it replaces a right side on the stack by its left side

Answer: C

Shifting moves a token from the input to the stack. Reduction is the complementary action, replacing the symbols of a matched right side by the nonterminal on its left. Shifting and reducing are the only two actions a bottom-up parser ever performs.

Discuss in Forum

40.

The handle in bottom-up parsing is

A.whichever symbol happens to be sitting on top of the parser stack
B.the next input token that the parser is about to shift
C.the start symbol of the grammar being used by the parser
D.the substring matching a right side whose reduction is the correct step

Answer: D

Correct answer: the substring matching a right side whose reduction is the correct step

A handle is not merely something that matches a right side but one whose reduction leads towards a successful parse, so identifying handles correctly is the whole problem of bottom-up parsing. LR parsing solves it by tracking, in its state, every production of which a prefix has been seen.

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