Question

Which of the following is/are Bottom-Up Parser(s)?

• A. Shift-reduce Parser
• B. Predictive Parser
• C. LL(1) Parser
• D. LR Parser

Hint:

Bottom-up parsers construct the parse tree starting from the input string (leaves) and work their way toward the start symbol (root). Examples include Shift-reduce Parser and LR Parser.

Answer 1

The Correct Option is A

Step 1: Understand parsing techniques. Parsing techniques are broadly categorized as:
Top-Down Parsing: Constructs the parse tree starting from the root (start symbol) and moves toward the leaves.
Bottom-Up Parsing: Constructs the parse tree starting from the leaves (input string) and moves toward the root. Step 2: Analyze the given parsers.
1. Shift-reduce Parser: This is a bottom-up parsing technique. It uses shift and reduce operations to construct the parse tree. Thus, it is a Bottom-Up Parser.
2. Predictive Parser: This is a top-down parsing technique. It uses lookahead symbols to predict which production to apply. It is NOT a Bottom-Up Parser.
3. LL(1) Parser: This is a top-down parsing technique based on leftmost derivations with one symbol of lookahead. It is NOT a Bottom-Up Parser.
4. LR Parser: This is a bottom-up parsing technique that uses left-to-right scanning and rightmost derivation in reverse. It is a Bottom-Up Parser. Step 3: Conclude the correct parsers.
From the analysis, Shift-reduce Parser and LR Parser are Bottom-Up Parsers. Final Answer: \[ \boxed{\text{(1) Shift-reduce Parser, (4) LR Parser}} \]