Simple precedence grammar

From HandWiki

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 [math]\displaystyle{ \in }[/math] (N ∪ Σ)) there is only one Wirth–Weber precedence relation.
  • G is uniquely inversible

Examples

[math]\displaystyle{ S \to aSSb | c }[/math]
precedence table
[math]\displaystyle{ \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} }[/math]

Notes

  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, https://archive.org/details/machineslanguage00denn, "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