# 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:

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

## References

- Alfred V. Aho, Jeffrey D. Ullman (1977).
*Principles of Compiler Design*. 1st Edition. Addison–Wesley. - William A. Barrett, John D. Couch (1979).
*Compiler construction: Theory and Practice*. Science Research Associate. - Jean-Paul Tremblay, P. G. Sorenson (1985).
*The Theory and Practice of Compiler Writing*. McGraw–Hill.

- v
- t
- e

- LL
- Recursive descent
- Tail recursive

- Precedence
- Simple
- Operator
- Shunting-yard

- LR
- Simple
- Look-ahead
- Canonical
- Generalized

- CYK
- Recursive ascent
- Shift-reduce

This computer science article is a stub. You can help Wikipedia by expanding it. |

- v
- t
- e

This programming-language-related article is a stub. You can help Wikipedia by expanding it. |

- v
- t
- e