GATE-2024-CS1(Forenoon)

Bottom-Up parsers construct parse trees for input strings starting from the leaves (tokens) and working up to the root of the parse tree. Let’s analyze each option:

(A) Shift-reduce Parser: Shift-reduce parsing is a type of bottom-up parsing. It starts with the input string and tries to reduce it to the start symbol of the grammar by repeatedly applying grammar rules or shifting tokens onto the parsing stack until a reduction is possible. Therefore, this is a bottom-up parser.

(B) Predictive Parser: Predictive parsing is a type of top-down parsing where the parser predicts which production rule to apply based on the current input symbol and a look-ahead symbol. Therefore, this is not a bottom-up parser.

(C) LL(1) Parser: LL(1) parsing is a type of top-down parsing. It uses a left-to-right scan of the input, a leftmost derivation, and one-symbol lookahead. Therefore, this is not a bottom-up parser.

(D) LR Parser: LR parsing is a type of bottom-up parsing. It constructs a rightmost derivation in reverse, starting from the leaves (tokens) and working up to the start symbol of the grammar. Therefore, this is a bottom-up parser.

So, the bottom-up parser(s) among the given options are:
Shift-reduce Parser and LR Parser