This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. Please help improve this article by introducing more precise citations. (March 2023) (Learn how and when to remove this message)

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**.

- 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.

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

E --> E + T' | T' T' --> T T --> T * F | F F --> ( E' ) | num E' --> E

**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 | ⋗ | ⋗ | ⋗ | ⋗ | |||||||

$ | ⋖ | ⋖ | ⋖ | ⋖ | ⋖ | ⋖ |

STACK PRECEDENCE INPUT ACTION $ ⋖ 2 * ( 1 + 3 )$ SHIFT $ ⋖ 2 ⋗ * ( 1 + 3 )$ REDUCE (F -> num) $ ⋖ F ⋗ * ( 1 + 3 )$ REDUCE (T -> F) $ ⋖ T ≐ * ( 1 + 3 )$ SHIFT $ ⋖ T ≐ * ⋖ ( 1 + 3 )$ SHIFT $ ⋖ T ≐ * ⋖ ( ⋖ 1 + 3 )$ SHIFT $ ⋖ T ≐ * ⋖ ( ⋖ 1 ⋗ + 3 )$ REDUCE 4× (F -> num) (T -> F) (T' -> T) (E ->T ') $ ⋖ T ≐ * ⋖ ( ⋖ E ≐ + 3 )$ SHIFT $ ⋖ T ≐ * ⋖ ( ⋖ E ≐ + ⋖ 3 )$ SHIFT $ ⋖ T ≐ * ⋖ ( ⋖ E ≐ + < 3 ⋗ )$ REDUCE 3× (F -> num) (T -> F) (T' -> T) $ ⋖ T ≐ * ⋖ ( ⋖ E ≐ + ≐ T ⋗ )$ REDUCE 2× (E -> E + T) (E' -> E) $ ⋖ T ≐ * ⋖ ( ≐ E' ≐ )$ SHIFT $ ⋖ T ≐ * ⋖ ( ≐ E' ≐ ) ⋗ $ REDUCE (F -> ( E' )) $ ⋖ T ≐ * ≐ F ⋗ $ REDUCE (T -> T * F) $ ⋖ T ⋗ $ REDUCE 2× (T' -> T) (E -> T') $ ⋖ E $ ACCEPT