simple precedence parser

• 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.

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:

class="wikitable" ! |	E	E'	T	T'	F	+	*	(	)	num	$
E | || || || || ||≐|| || ||⋗ || ||
E' | || || || || || || || ||≐|| ||
T | || || || || ||⋗||≐|| ||⋗|| ||⋗
T' | || || || || ||⋗|| || ||⋗|| ||⋗
F | || || || || ||⋗||⋗|| ||⋗|| ||⋗
+ | || ||⋖||≐||⋖|| || ||⋖|| ||⋖ ||
* | || || || ||≐|| || ||⋖|| ||⋖ ||
( |⋖||≐||⋖||⋖||⋖|| || ||⋖|| ||⋖ ||
) | || || || || ||⋗||⋗|| ||⋗|| ||⋗
num | || || || || ||⋗||⋗||||⋗|| ||⋗
$ |⋖|| ||⋖||⋖||⋖|| || ||⋖|| ||⋖ ||

{{aligned table|cols=4|row1header=Y|class=wikitable|style=font-family:monospace|col3align=right

| 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

}}

• 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.

{{Parsers}}

{{DEFAULTSORT:Simple Precedence Parser}}

Category:Parsing algorithms

{{comp-sci-stub}}

{{Compu-lang-stub}}