A bottom-up parser generates :

Answer: A bottom-up parser generates the rightmost derivation in reverse.

Reason: Bottom-up parsing starts from the input tokens and repeatedly replaces the right-hand side of productions by their left-hand side (a reduce operation). Each reduction corresponds to undoing a production application from a rightmost derivation, so the parser reconstructs the rightmost derivation steps in reverse order.

• Operation style: Bottom-up parsers perform shift and reduce operations, reducing substrings of the already-read input to nonterminals.

• Derivation correspondence: Each reduce corresponds to one production used in a rightmost derivation, but applied backwards, so the overall derivation built is the rightmost derivation in reverse.

• Examples: Shift-reduce parsers and the LR family (SLR, LALR, CLR) are common bottom-up parsers.

Contrast: Top-down parsers construct a leftmost derivation directly (for example, LL parsers).