BottomupParser

Bottom-up parsing is a method of syntactic analysis in compilers that constructs a parse tree for a sequence of tokens by starting with the tokens and merging them into higher-level constructs until the start symbol is reached. It contrasts with top-down parsers that build the tree from the start symbol downward. The approach is well suited to deterministic parsing of many programming language grammars.

The most common form is shift-reduce parsing, implemented as LR parsing. The parser uses a stack to hold symbols and an input buffer of remaining tokens. It repeatedly shifts the next input token onto the stack or reduces a recognized right-hand side of a production to its left-hand side, according to a parse table.

Parse tables are divided into action and goto components. The action table tells whether to shift, reduce, accept, or report an error for a given state and lookahead token. The goto table indicates the destination state after a reduction. A successful parse ends in the start symbol.

LR parsing belongs to the family of bottom-up parsers, including canonical LR(1), SLR(1), and LALR(1). Canonical LR(1) is complete but uses large tables; SLR and LALR reduce table sizes at the cost of potentially requiring grammar refinement to avoid conflicts.

Bottom-up parsers are widely used in real-world compilers because of their efficiency and ability to handle a large class of grammars. Tools such as yacc and Bison implement LR-based parsers. Ambiguities or conflicts in a grammar are resolved by grammar design, operator precedence, or by rewriting the grammar.