Simple precedence grammar

From Wikipedia, the free encyclopedia

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

Examples

$S\to aSSb|c$

precedence table:

	S	a	b	c	$
S	${\dot =}$	$\lessdot$	${\dot =}$	$\lessdot$
a	${\dot =}$	$\lessdot$		$\lessdot$
b		$\gtrdot$		$\gtrdot$	$\gtrdot$
c		$\gtrdot$	$\gtrdot$	$\gtrdot$	$\gtrdot$
$		$\lessdot$		$\lessdot$

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. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.