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. Simbols ${\displaystyle {\dot {<}}}$, ${\displaystyle {\dot {=}}}$ and ${\displaystyle {\dot {>}}}$ are used to identify the pivot, and to know when to Shift or when to Reduce.

Implementation

• Compute the Wirth-Weber precedence relationship table.
• Start with a stack with only the starting marker $.
• Start with the string beeing parsed (Input) ended with an ending marker $.
• While not (Stack equals to $S and Input equals to $) (S = Initial simbol of the grammar)
  • Search in the table the relationship between Top(stack) and NextToken(Input)
  • if the relationship is ${\displaystyle {\dot {=}}}$  or ${\displaystyle {\dot {<}}}$ 
    • Shift:
    • Push(Stack, relationship)
    • Push(Stack, NextToken(Input))
    • RemoveNextToken(Input)
  • if the relationship is ${\displaystyle {\dot {>}}}$ 
    • Reduce:
    • SearchProductionToReduce(Stack)
    • RemovePivot(Stack)
    • Search in the table the relationship between the Non terminal from the production and NextToken(Input)
    • Push(Stack, relationship)
    • Push(Stack, Non terminal)

SearchProductionToReduce (Stack)

• search the Pivot in the stack the nearest ${\displaystyle {\dot {<}}}$  from the top
• search in the productions of the grammar wich one have the same right side than the Pivot

Given the language:
E  --> E + T  | T'
T' --> T
T  --> T * F  | F
F --> ( E ) | [0..9]

and the Parsing table:

STACK                 PRECEDENCE    INPUT            ACTION

$                          <        2 * ( 1 + 3 )$   SHIFT
$ < 2                      >        * ( 1 + 3 )$     REDUCE (F -> 2)
$ < F                      >        * ( 1 + 3 )$     REDUCE (T -> F)
$ < T                      =        * ( 1 + 3 )$     SHIFT
$ < T = *                  <        ( 1 + 3 )$       SHIFT
$ < T = * < (              <        1 + 3 )$         SHIFT
$ < T = * < ( < 1          >        + 3 )$           REDUCE 4 times (F -> 1) (T -> F) (T' -> T) (E -> T')
$ < T = * < ( < E          =        + 3 )$           SHIFT
$ < T = * < ( < E = +      <        3 )$             SHIFT
$ < T = * < ( < E = + < 3  >        )$               REDUCE 3 times (F -> 3) (T -> F) (T' -> T) 
$ < T = * < ( < E = + = T  >        )$               REDUCE (E -> E + T)
$ < T = * < ( < E          =        )$               SHIFT
$ < T = * < ( = E = )      >        $                REDUCE (F -> ( E ))
$ < T = * = F              >        $                REDUCE (T -> T * F)
$ < T                      >        $                REDUCE 2 times (T' -> T) (E -> T')
$ < E                      >        $                ACCEPT