simple precedence grammar

A simple precedence grammar is a context-free formal grammar that can be parsed with a simple precedence parser.

The Theory of Parsing, Translation, and Compiling: Compiling, Alfred V. Aho, Jeffrey D. Ullman, Prentice–Hall, 1972. The concept was first created in 1964 by Claude Pair,{{cite journal|author=Claude Pair |title = Arbres, piles et compilation|year=1964|journal=Revue française de traitement de l'information}}, in English Trees, stacks and compiling 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.{{citation |title=Machines, Languages, and Computation |publisher=Prentice–Hall |year=1978 |isbn=9780135422588 |quote=Wirth and Weber [1966] generalized Floyd's precedence grammars, obtaining the simple precedence grammars. |url-access=registration |url=https://archive.org/details/machineslanguage00denn }}

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}{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

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

[http://www.cs.clemson.edu/course/cpsc827/material/Simple%20Precedence/Relations.pdf "Simple Precedence Relations"] at Clemson University

Category:Formal languages