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.

* v
* t
* e

Parsing algorithms

Top-down|

* LL
* Recursive descent
* Tail recursive
* Pratt parser

Bottom-up|

* Precedence
* Simple
* Operator
* Shunting-yard
* Bounded-context
* LR
* Simple
* Look-ahead
* Canonical
* Generalized
* CYK
* Recursive ascent
* Shift-reduce

Mixed, other|

* Combinator
* Chart
* Earley

Related topics|

* PEG
* Definite clause grammar
* Dynamic programming
* Memoization
* Parser generator
* LALR
* Metacompiler
* Parse tree
* AST
* Scannerless parsing
* History of compiler construction
* Comparison of parser generators

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Simple precedence parser. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Simple_precedence_parser&oldid=285641"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template