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:

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.

Parsing algorithms

{{Compu-lang-stub