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:

Examples

S \to aSSb | c

precedence table:

Sabc$
S\dot = \lessdot \dot = \lessdot
a\dot =\lessdot \lessdot
b \gtrdot \gtrdot\gtrdot
c \gtrdot\gtrdot\gtrdot\gtrdot
$ \lessdot \lessdot

Notes

  1. The Theory of Parsing, Translation, and Compiling: Compiling, Alfred V. Aho, Jeffrey D. Ullman, Prentice–Hall, 1972.
  2. Machines, Languages, and Computation, Prentice–Hall, 1978, ISBN 9780135422588, Wirth and Weber [1966] generalized Floyd's precedence grammars, obtaining the simple precedence grammars.

References

External links


This article is issued from Wikipedia - version of the Sunday, March 16, 2014. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.