View source for Simple precedence parser

{{multiple issues|
{{No footnotes|date=March 2023}}
{{Technical|date=May 2025}}
}}
{{Merge to|Simple precedence grammar|date=May 2025}}

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 grammar]]s.

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:
<pre>
E  --> E + T' | T'
T' --> T
T  --> T * F  | F
F  --> ( E' ) | num
E' --> E
</pre>

'''num''' is a terminal, and the [[lexer (computer science)|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
}}

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

{{Parsers}}

{{DEFAULTSORT:Simple Precedence Parser}}
[[Category:Parsing algorithms]]


{{comp-sci-stub}}
{{Compu-lang-stub}}