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 developed by Niklaus Wirth and Helmut Weber from the ideas of Robert Floyd in their paper, EULER: a generalization of ALGOL, and its formal definition, in the Communications of the ACM in 1966.[2]
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.
- G is uniquely inversible
Examples
precedence table:
| S | a | b | c | $ | |
| S | |||||
| a | |||||
| b | |||||
| c | |||||
| $ |
Notes
- ↑ The Theory of Parsing, Translation, and Compiling: Compiling, Alfred V. Aho, Jeffrey D. Ullman, Prentice–Hall, 1972.
- ↑ 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
This article is issued from Wikipedia - version of the 3/16/2014. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.