Simple precedence parser
# Simple precedence parser

In computer science, a simple precedence parser is a type of bottom-up parser for context-free grammars that can be used only by simple precedence grammars.

The implementation of the parser is quite similar to the generic bottom-up parser. A stack is used to store a viable prefix of a sentential form from a rightmost derivation. The symbols ⋖, ≐ and ⋗ are used to identify the pivot, and to know when to Shift or when to Reduce.

## Implementation

* Compute the Wirth–Weber precedence relationship table for a grammar with initial symbol S.
* Initialize a stack with the starting marker $.
* Append an ending marker $ to the string being parsed (Input).
* Until Stack equals "$ S" and Input equals "$"
   * Search the table for the relationship between Top(stack) and NextToken(Input)
   * if the relationship is ⋖ or ≐
      * Shift:
      * Push(Stack, relationship)
      * Push(Stack, NextToken(Input))
      * RemoveNextToken(Input)
   * if the relationship is ⋗
      * Reduce:
      * SearchProductionToReduce(Stack)
      * Remove the Pivot from the Stack
      * Search the table for the relationship between the nonterminal from the production and first symbol in the stack (Starting from top)
      * Push(Stack, relationship)
      * Push(Stack, Non terminal)

SearchProductionToReduce (Stack)

* Find the topmost ⋖ in the stack; this and all the symbols above it are the Pivot.
* Find the production of the grammar which has the Pivot as its right side.

## Example

Given following language, which can parse arithmetic expressions with the multiplication and addition operations:

num is a terminal, and the lexer parse any integer as num; E represents an arithmetic expression, T is a term and F is a factor.

and the Parsing table:

| | E | E' | T | T' | F | + | * | ( | ) | num | $ |
| - | - | - | - | - | - | - | - | - | - | - | - |
| E | | | | | | ≐ | | | ⋗ | | |
| E' | | | | | | | | | ≐ | | |
| T | | | | | | ⋗ | ≐ | | ⋗ | | ⋗ |
| T' | | | | | | ⋗ | | | ⋗ | | ⋗ |
| F | | | | | | ⋗ | ⋗ | | ⋗ | | ⋗ |
| num | | | | | | ⋗ | ⋗ | | ⋗ | | ⋗ |
