Simple precedence grammar

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.[3]

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 ${\displaystyle \in }$ (N ∪ Σ)) there is only one Wirth–Weber precedence relation.
• G is uniquely inversible

Examples

${\displaystyle S\to aSSb|c}$

precedence table

${\displaystyle {\begin{array}{c|ccccc}&S&a&b&c&\$\\\hline S&{\dot {=}}&\lessdot &{\dot {=}}&\lessdot &\\a&{\dot {=}}&\lessdot &&\lessdot &\\b&&\gtrdot &&\gtrdot &\gtrdot \\c&&\gtrdot &\gtrdot &\gtrdot &\gtrdot \\\$&&\lessdot &&\lessdot &\end{array}}}$

Notes

1. The Theory of Parsing, Translation, and Compiling: Compiling, Alfred V. Aho, Jeffrey D. Ullman, Prentice–Hall, 1972.
2. Claude Pair (1964). "Arbres, piles et compilation". Revue française de traitement de l'information., in English Trees, stacks and compiling
3. Machines, Languages, and Computation, Prentice–Hall, 1978, ISBN 9780135422588, Wirth and Weber [1966] generalized Floyd's precedence grammars, obtaining the simple precedence grammars.

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