Shift-Reduce parsers perform the following :
2014
Shift-Reduce parsers perform the following :
- A.
Shift step that advances in the input stream by K(K > 1) symbols and Reduce step that applies a completed grammar rule to some recent parse trees, joining them together as one tree with a new root symbol.
- B.
Shift step that advances in the input stream by one symbol and Reduce step that applies a completed grammar rule to some recent parse trees, joining them together as one tree with a new root symbol.
- C.
Shift step that advances in the input stream by K(K = 2) symbols and Reduce step that applies a completed grammar rule to form a single tree.
- D.
Shift step that does not advance in the input stream and Reduce step that applies a completed grammar rule to form a single tree.
Attempted by 90 students.
Show answer & explanation
Correct answer: B
Answer: In shift-reduce parsing, the shift step advances the input by one symbol and the reduce step applies a grammar production to recent stack elements or partial parse trees, replacing the matched right-hand side with the production's left-hand side and forming a single subtree.
Key points:
Shift: move exactly one input symbol (token) from the input to the top of the parser stack; advance the input pointer by one.
Reduce: when the top of the stack matches the right-hand side of a grammar production, pop those symbols, push the production's left-hand side, and combine the popped elements into a single parse subtree.
Simple example (grammar and parsing actions):
Grammar: S → A B, A → a, B → b. Input: a b $ (where $ is end marker).
Shift 'a' onto the stack (advance input by one).
Reduce using A → a: replace 'a' with A (form subtree A).
Shift 'b' onto the stack.
Reduce using B → b: replace 'b' with B (form subtree B).
Reduce using S → A B: replace A B with S (form the complete parse tree).
This explanation corrects ambiguous or incorrect statements about shifting multiple symbols or not advancing the input, and clearly shows the incremental nature of shift-reduce parsing.