Loading AI tools
From Wikipedia, the free encyclopedia
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.
This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. (March 2023) |
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.
SearchProductionToReduce (Stack)
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
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.