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 $\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

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

gollark: I would start by establishing a numbering/encoding system by sending Fibonacci or whatever, then defining (through examples, probably) arithmetic operations, and then... it might be hard to relate physical information actually, hm.

gollark: It's pictographic, except bad.

gollark: I would probably *not* do it this way, but it's a start.

gollark: Presumably, an entire civilization working on it might come up with some sensible interpretations.

gollark: https://en.wikipedia.org/wiki/Arecibo_message

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. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

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