Simple precedence grammar

Template:Short description Template:Technical 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 = (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 $\in$ (N ∪ Σ)) there is only one Wirth–Weber precedence relation.
• G is uniquely inversible

Examples

$S\to aSSb|c$

precedence table

$\begin{array}{cccccc}& S& a& b& c& \mathrm{\$}\\ S& \dot{=}& ⋖& \dot{=}& ⋖& \\ a& \dot{=}& ⋖& & ⋖& \\ b& & ⋗& & ⋗& ⋗\\ c& & ⋗& ⋗& ⋗& ⋗\\ \mathrm{\$}& & ⋖& & ⋖& \end{array}$

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.

External links

• "Simple Precedence Relations" at Clemson University

Template:Comp-sci-stub Template:Compu-lang-stub