Bottom-up parsing

The term bottom-up parser or Aufwärtsparser called an analysis tool for natural and formal languages.

As a rule, a parser is used as part of a transmission program of one language to another. In computer languages ​​such translation program called compilers. A parser also checks the conformity or the maintenance of the rules of a language: It issues warnings and error messages, if the input text is not in compliance.

A bottom-up parser works, starting from the smallest unit encountered ( " Bottom" ) towards the larger context ( "Up" ).

The bottom-up parser implements the strategy of bottom-up parsing ( parsing data -led ). In this by the tokens ( words ) of the input sentence, starting trying to build gradually larger syntactic structures, until you finally reached the start symbol of the grammar.

Important subclasses are

• Shift-reduce parsing as LR ( k) parsing
• Operator Precedence parsing

Example

Given a context-free grammar with the following production rules:

The start symbol is S.

The sentence to be analyzed by the bottom-up parser, is " Daisy loves Donald ". The stack of the parser is initially empty. The steps of a shift-reduce parser look like this:

There are no other words in the input sentence more, on the stack is the start symbol, the sentence was therefore accepted by the parser output usually Episode 4 5 3 2 1.

• Computational Linguistics
• Compiler