Simple precedence grammar


In computer science, a simple precedence grammar is a context-free formal grammar that can be parsed with a simple precedence parser. The concept was first created in 1964 by Claude Pair, and was later rediscovered, from ideas due to Robert Floyd, by Niklaus Wirth and Helmut Weber who published a paper, entitled EULER: a generalization of ALGOL, and its formal definition, published in 1966 in the Communications of the ACM.

Formal definition

G = is a simple precedence grammar if all the production rules in P comply with the following constraints:

Examples

;precedence table:

Simple precedence parser

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.
  • Until Stack equals "$ S" and Input equals "$"
  • * Search the table for the relationship between Top and NextToken
  • * if the relationship is ⋖ or ≐
  • ** Shift:
  • ** Push
  • ** Push
  • ** RemoveNextToken
  • * if the relationship is ⋗
  • ** Reduce:
  • ** SearchProductionToReduce
  • ** Remove the Pivot from the Stack
  • ** Search the table for the relationship between the nonterminal from the production and first symbol in the stack
  • ** Push
  • ** Push
SearchProductionToReduce
  • 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 --> | 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:
EE'TT'F+*num$
E≐⋗
E'≐
T⋗≐⋗⋗
T'⋗⋗⋗
F⋗⋗⋗⋗
+⋖≐⋖⋖⋖
*≐⋖⋖
⋗⋗⋗⋗
num⋗⋗⋗⋗
$⋖⋖⋖⋖⋖⋖

Wirth–Weber precedence relationship

In computer science, a Wirth–Weber relationship between a pair of symbols is necessary to determine if a formal grammar is a simple precedence grammar. In such a case, the simple precedence parser can be used. The relationship is named after computer scientists Niklaus Wirth and Helmut Weber.
The goal is to identify when the viable prefixes have the pivot and must be reduced. A means that the pivot is found, a means that a potential pivot is starting, and a means that a relationship remains in the same pivot.

Precedence relations computing algorithm

We will define three sets for a symbol:
The pseudocode for computing relations is:
  • RelationTable := ∅
  • For each production
  • * For each two adjacent symbols in
  • ** add
  • ** add
  • ** add
  • add where is the initial non terminal of the grammar, and $ is a limit marker
  • add where is the initial non terminal of the grammar, and $ is a limit marker

Example 1

  • Head = ∅
  • Head =
  • Head = ∅
  • Head = ∅
  • Tail = ∅
  • Tail =
  • Tail = ∅
  • Tail = ∅
  • Head = a
  • Head =
  • Head = b
  • Head = c
  • * a Next to S
  • **
  • **
  • ***
  • ***
  • * S Next to S
  • **
  • **
  • ***
  • ***
  • **
  • ***
  • ***
  • ***
  • ***
  • * S Next to b
  • **
  • **
  • ***
  • ***
  • * there is only one symbol, so no relation is added.
;precedence table:

Example 2

  • Head =
  • Head = ∅
  • Head =
  • Head = ∅
  • Head = ∅
  • Head = ∅
  • Tail =
  • Tail = ∅
  • Tail =
  • Tail = ∅
  • Tail = ∅
  • Tail = ∅
  • Head =
  • Head = a
  • Head =
  • Head = '
  • Head = b
  • * a Next to T
  • **
  • **
  • ***
  • * '
  • **
  • **
  • ***
  • ***
  • ***
  • ***
  • * b Next to T
  • **
  • **
  • ***
;precedence table: