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

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.