Bottom-up parsing - Definition and Overview

Bottom-up parsing is a technique that can be used in compilers that translate human-readable computer languages to assembly language or pseudocode. The name refers to a parsing approach that starts from individual symbols and builds up lexemes (such as identifiers or keywords), then builds up larger units from there.

Different computer languages require different parsing techniques, although it is not uncommon to use a parsing technique that is more powerful than what is actually required.

Typically, a bottom-up parser is written as a general parsing engine, with the parsing rules of any specific computer language described in a specialized parser language.

The four common classes of bottom-up parsing are:

• LR(0) - No lookahead symbol
• SLR(1) - Simple with one lookahead symbol
• LALR(1) - Lookahead bottom up, not as powerful as full LR(1) but simpler to implement. YACC uses this language.
• LR(1) - Most general language, but most complex to implement.

Hand-coding for any of these parser-language classes is very complex, so typically one uses rules-based parser generators.

The Parser performs one of two actions (beside accept). These are "Shift" and "Reduce".