A simple precedence grammar is a
context-free formal grammar
In formal language theory, a grammar (when the context is not given, often called a formal grammar for clarity) describes how to form strings from a language's alphabet that are valid according to the language's syntax. A grammar does not describe ...
that can be parsed with a
simple precedence parser In computer science, a simple precedence parser is a type of bottom-up parser for context-free grammars that can be used only by simple precedence grammars.
The implementation of the parser is quite similar to the generic bottom-up parser. A stack ...
. The concept was first created in 1964 by
Claude Pair, and was later rediscovered, from ideas due to
Robert Floyd, by
Niklaus Wirth
Niklaus Emil Wirth (born 15 February 1934) is a Swiss computer scientist. He has designed several programming languages, including Pascal (programming language), Pascal, and pioneered several classic topics in software engineering. In 1984, he w ...
and
Helmut Weber Helmut is a German name. Variants include Hellmut, Helmuth, and Hellmuth.
From old German, the first element deriving from either ''heil'' ("healthy") or ''hiltja'' ("battle"), and the second from ''muot'' ("spirit, mind, mood").
Helmut may refer ...
who published a paper, entitled ''EULER: a generalization of ALGOL, and its formal definition'', published in 1966 in the
Communications of the ACM
''Communications of the ACM'' is the monthly journal of the Association for Computing Machinery (ACM). It was established in 1958, with Saul Rosen as its first managing editor. It is sent to all ACM members.
Articles are intended for readers with ...
.
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
In formal language theory, a context-free grammar (CFG) is a formal grammar whose Production (computer science), production rules are of the form
:A\ \to\ \alpha
with A a ''single'' nonterminal symbol, and \alpha a string of Terminal and nonter ...
(unreachable symbols or unproductive rules)
* For each pair of symbols ''X'', ''Y'' (''X'', ''Y''
(''N'' ∪ Σ)) there is only one
Wirth–Weber precedence relation.
* G is
uniquely inversible
Examples
:
;precedence table:
Notes
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
Formal languages
{{Compu-lang-stub