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 $lessdot$, $dot\; =$ and $gtrdot$ 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 being 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 $dot\; =$ or $lessdot$
*** Shift:
*** Push(Stack, relationship)
*** Push(Stack, NextToken(Input))
*** RemoveNextToken(Input)
** if the relationship is $gtrdot$
*** Reduce:
*** SearchProductionToReduce(Stack)
*** RemovePivot(Stack)
*** Search in the table the relationship between the Non terminal from the production and first symbol in the stack (Starting from top)
*** Push(Stack, relationship)
*** Push(Stack, Non terminal)

SearchProductionToReduce (Stack)
* search the Pivot in the stack the nearest $lessdot$ from the top
* search in the productions of the grammar which one have the same right side than the Pivot

= Example =

Given the language:E --> E + T' | T'T' --> TT --> T * F | FF --> ( E' ) | numE' --> E

num is a terminal, and the lexer parse any integer as num.

and the Parsing table:

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 times (F -> num) (T -> F) (T' -> T) (E ->T ') $ < T = * < ( < E = + 3 )$ SHIFT$ < T = * < ( < E = + < 3 )$ SHIFT$ < T = * < ( < E = + < 3 > )$ REDUCE 3 times (F -> num) (T -> F) (T' -> T) $ < T = * < ( < E = + = T > )$ REDUCE 2 times (E -> E + T) (E' -> E)$ < T = * < ( < E' = )$ SHIFT$ < T = * < ( = E' = ) > $ REDUCE (F -> ( E' ))$ < T = * = F > $ REDUCE (T -> T * F)$ < T > $ REDUCE 2 times (T' -> T) (E -> T')$ < E > $ ACCEPT