Bottom Up Parsing Questions and Answers

51.

The chief practical disadvantage of LR parsing is that

A.the method requires exponential time on some inputs
B.no tool exists that can generate an LR parser automatically
C.the tables are opaque and conflicts can be hard to diagnose
D.the parser cannot handle recursive constructs of any kind

Answer: C

Correct answer: the tables are opaque and conflicts can be hard to diagnose

LR parsing is linear in the input and handles a wide class of grammars, so the objection is not to its power. It is that a conflict is reported against a state number and an item set rather than against the language construct the author was thinking about, which makes tracing the cause a skilled exercise.

Discuss in Forum

52.

Left recursion in a grammar is

A.fatal to an LR parser exactly as it is to a top down parser
B.quite impossible to express in a context free grammar at all
C.automatically removed by the parser generator before use
D.welcome in an LR parser, as it keeps the parsing stack shallow

Answer: D

An iterative construct written left recursively is reduced item by item, so the stack stays short. Written right recursively the whole list must be stacked before any reduction occurs. A long initialiser list makes the difference plainly visible.

Discuss in Forum

53.

Assertion (A): LR grammars are usually written with left recursion for list constructs.
Reason (R): A right recursive list forces the entire list onto the stack before the first reduction can take place.

A.Both A and R are true, and R is the correct explanation of A
B.Both A and R are true, but R is not the correct explanation of A
C.A is true but R is false
D.A is false but R is true

Answer: A

Both are true and the reason gives the mechanism, and the difference is measurable on long lists. Left recursion reduces after each element and keeps the stack at constant depth, which matters for generated initialiser lists and similar input.

Discuss in Forum

54.

A parser generator reporting no conflicts guarantees that

A.the generated parser will produce good error messages
B.the grammar is in the class the generator handles
C.the language described is the one the author intended
D.the semantic actions attached are free of errors

Answer: B

Absence of conflicts is a statement about the grammar, not about whether it describes the intended language. Testing remains necessary for everything the generator cannot check. A conflict free grammar can still accept a language nobody intended.

Discuss in Forum

55.

Reading a conflict report is easier when the generator prints

A.the FIRST and FOLLOW sets of all the nonterminals
B.the number of states in the automaton that was constructed
C.the items of the offending state with the dot positions shown
D.the complete action table for every state in the grammar

Answer: C

The items show what the parser had seen and what it expected, which usually identifies the pair of productions in conflict. Most generators produce such a report on request. Learning to read one is among the more useful practical skills in this area.

Discuss in Forum

56.

Generalised LR parsing handles a conflict by

A.reporting the conflict and then refusing to parse the input at all
B.always preferring the shift over the reduce action
C.backtracking to the previous state and trying again
D.forking the parse and pursuing both alternatives in parallel

Answer: D

Branches that fail are discarded and surviving branches may be merged. The method accepts ambiguous grammars at the cost of the linear time guarantee. Where the grammar happens to be unambiguous the extra cost is negligible.

Discuss in Forum

57.

A graph structured stack in a GLR parser exists to

A.share the common parts of several simultaneous parses
B.store the semantic values computed during the parse
C.record the sequence of states visited for error reporting
D.hold the tokens that the scanner has produced in advance

Answer: A

Correct answer: share the common parts of several simultaneous parses

GLR pursues every viable parse at once, and a naive implementation would need a separate stack for each. The graph structured stack merges the parts the parses have in common and branches only where they differ, which keeps the work proportional to the genuine ambiguity rather than exponential in the input.

Discuss in Forum

58.

Operator precedence parsing is a bottom up method restricted to grammars in which

A.no nonterminal appears on the right side of any production
B.no rule places two nonterminals next to one another on its right
C.every rule carries at most two symbols to the right of the arrow
D.all operators in the language share a single precedence level

Answer: B

Because the parse is driven entirely by relations tabulated between pairs of terminals, a pair of nonterminals standing side by side offers the table nothing to look up. Arithmetic expression grammars happen to obey the restriction, which is what made the method attractive before generators were widely available.

Discuss in Forum

59.

The three precedence relations used in operator precedence parsing are

A.left associative, right associative and non associative
B.less than, equal to and greater than as applied to the state numbers
C.yields precedence to, has the same precedence as, and takes precedence over
D.shift, reduce and accept as in an ordinary LR parser

Answer: C

The relations hold between pairs of terminals and determine where the handle begins and ends. They are not symmetric, so both orderings of a pair must be tabulated. The table is therefore quadratic in the number of terminal symbols.

Discuss in Forum

60.

The following are all bottom up parsing methods EXCEPT

A.SLR parsing built from the LR(0) item sets
B.LALR parsing as generated by Yacc and Bison
C.a table of precedence relations between the operators
D.predictive parsing driven by an LL table

Answer: D

The first three all build the tree from the leaves upward. Predictive parsing expands nonterminals from the start symbol and belongs to the top down family instead. The direction of tree construction is the defining difference.

Discuss in Forum

Loading…

Topics

Other Subjects

Tags: Bottom Up Parsing Questions and Answers || Bottom Up Parsing MCQ Questions and Answers || Bottom Up Parsing GK Questions and Answers || Bottom Up Parsing GK MCQ Questions || Bottom Up Parsing Multiple Choice Questions and Answers || Bottom Up Parsing GK || GK on Bottom Up Parsing || Compiler Design Questions and Answers || Compiler Design MCQ Questions and Answers || Compiler Design GK Questions and Answers || GK on Compiler Design

Bottom Up Parsing Questions and Answers

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications