Simple precedence grammar explained

A simple precedence grammar is a context-free formal grammar that can be parsed with a simple precedence parser.[1] The concept was first created in 1964 by Claude Pair,[2] 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 = (N, Σ, P, S) is a simple precedence grammar if all the production rules in P comply with the following constraints:

\in

(N ∪ Σ)) there is only one Wirth–Weber precedence relation.

Examples

S\toaSSb|c

precedence table:

\begin{array}{c|ccccc} &S&a&b&c&\$ \\ \hline S&

=&

\lessdot&

=

&\lessdot&\\ a&

=&

\lessdot&&\lessdot&\\ b&&\gtrdot&&\gtrdot&\gtrdot \\ c&&\gtrdot&\gtrdot&\gtrdot&\gtrdot \\ \$&&\lessdot&&\lessdot&\end{array}

References

External links

Notes and References

  1. The Theory of Parsing, Translation, and Compiling: Compiling, Alfred V. Aho, Jeffrey D. Ullman, Prentice–Hall, 1972.
  2. Claude Pair . Arbres, piles et compilation. 1964. Revue française de traitement de l'information., in English Trees, stacks and compiling