Simple precedence grammar

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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[edit]

G = (N, Σ, P, S) is a simple precedence grammar if all the production rules in P comply with the following constraints:

Examples[edit]

precedence table:

S a b c $
S
a
b
c
$

Notes[edit]

  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[edit]

  • 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[edit]