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. 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.
- Start with a stack with only the starting marker $.
- Start with the string being parsed ended with an ending marker $.
- While not
- * Search in the table the relationship between Top and NextToken
- * if the relationship is or
- ** Shift:
- ** Push
- ** Push
- ** RemoveNextToken
- * if the relationship is
- ** Reduce:
- ** SearchProductionToReduce
- ** RemovePivot
- ** Search in the table the relationship between the Non terminal from the production and first symbol in the stack
- ** Push
- ** Push
SearchProductionToReduce
- search the Pivot in the stack the nearest 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' --> T
T --> T * F | F
F --> | num
E' --> E
num is a terminal, and the lexer parse any integer as num.
and the Parsing table:
| E | E' | T | T' | F | + | * | | num | $ |
| E | | | | | | | | | | | |
| E' | | | | | | | | | | | |
| T | | | | | | | | | | | |
| T' | | | | | | | | | | | |
| F | | | | | | | | | | | |
| + | | | | | | | | | | | |
| * | | | | | | | | | | | |
| | | | | | | | | | | |
| num | | | | | | | | | | | |
| $ | | | | | | | | | | | - |
STACK PRECEDENCE INPUT ACTION
$ < 2 * $ SHIFT
$ < 2 > * $ REDUCE
$ < F > * $ REDUCE
$ < T = * $ SHIFT
$ < T = * < $ SHIFT
$ < T = * < $ SHIFT
$ < T = * < $ REDUCE 4 times
$ < T = * < $ SHIFT
$ < T = * < $ SHIFT
$ < T = * < $ REDUCE 3 times
$ < T = * < $ REDUCE 2 times
$ < T = * < $ SHIFT
$ < T = * < > $ REDUCE
$ < T = * = F > $ REDUCE
$ < T > $ REDUCE 2 times
$ < E > $ ACCEPT
