Bottom-up parser
The term bottom-up parser or upward parser describes an analysis tool for natural and formal languages .
As a rule, a parser is used as part of a translation program from one language to another. In programming languages , such a translation program is also called a compiler . A parser also checks the conformity or adherence to the rules of a language: It issues warnings and error messages if the input text does not conform to the rules.
A bottom-up parser works on the basis of the smallest unit found (“bottom”) in the direction of the larger context (“up”).
The bottom-up parser implements the strategy of bottom-up parsing (data-guided parsing). With this, starting from the tokens (words) of the input sentence, an attempt is made to gradually build up larger syntactic structures until one finally arrives at the start symbol of the grammar .
Important subclasses are
- Shift-Reduce-Parsing like 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 parser's stack is initially empty. The steps of a shift-reduce parser look like this:
| input | stack | action | Applied rules |
|---|---|---|---|
| Daisy loves Donald | begin | ||
| loves donald | Daisy | Put the word "Daisy" on the stack | |
| loves donald | NP | Reduce "Daisy" to NP with rule 4. | 4th |
| Donald | NP loves | Put the word "love" on the pile | 4th |
| Donald | NP V | Reduce "loves" to V with rule 5. | 4 5 |
| NP V Donald | Put word "Donald" on the stack | 4 5 | |
| NP V NP | Reduce "Donald" to NP with rule 3. | 4 5 3 | |
| NP VP | Reduce the sequence V NP on the stack to VP with rule 2. | 4 5 3 2 | |
| S. | Reduce the sequence NP VP on the stack to S with rule 1. | 4 5 3 2 1 |
There are no more words in the input sentence, the start symbol is on the stack , the sentence was therefore accepted by the parser with the output of the rule sequence 4 5 3 2 1 .