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