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:
- 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.
Examples
- 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
- 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
Notes and References
- The Theory of Parsing, Translation, and Compiling: Compiling, Alfred V. Aho, Jeffrey D. Ullman, Prentice–Hall, 1972.
- Claude Pair . Arbres, piles et compilation. 1964. Revue française de traitement de l'information., in English Trees, stacks and compiling