Samiksha Jaiswal (Editor)

Simple precedence grammar

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

A simple precedence grammar is a context-free formal grammar that can be parsed with a simple precedence parser. The concept was first developed by Niklaus Wirth and Helmut Weber from the ideas of Robert Floyd in their paper, EULER: a generalization of ALGOL, and its formal definition, in the Communications of the ACM in 1966.

Contents

Formal definition

G = (N, Σ, P, S) is a simple precedence grammar if all the production rules in P comply with the following constraints:

  • There are no erasing rules (ε-productions)
  • There are no useless rules (unreachable symbols or unproductive rules)
  • For each pair of symbols X, Y (X, Y ∈ (N ∪ Σ)) there is only one Wirth–Weber precedence relation.
  • G is uniquely inversible

    • Examples

    S → a S S b | c

    precedence table:

    References

    Simple precedence grammar Wikipedia
    (Text) CC BY-SA