Programming languages, Syntax
The classes of simple and weak precedence grammars are generalized to include ε-rules (productions with the empty right parts). The descriptive power of epsilon simple precedence (ESP) grammars increases directly with the number of ε-rules permitted; the class of ESP grammars with no ε-rules, ESP0, is identical to the class of simple precedence grammars; ESP grammars with at most one ε-rule, ESP1, define a class of languages which properly includes the class of ESP0 languages, but is itself properly included in the class of deterministic, context-free languages. In general, ESP grammars having at most i ε-rules, ESPi, define a class of languages which is properly included in that defined by ESPi+1 grammars. This hierarchy of languages exhausts the deterministic context-free languages. The hierarchy of ESP languages is established using an iteration theorem which may be used to show that a given language is not ESPi for a given i.
An algorithm to convert arbitrary LR(1) grammars to equivalent epsilon weak precedence (EWP) grammars is developed.
The class of Viable Prefix EWP grammars is defined and it is shown that the EWP parser for every Viable Prefix EWP grammar detects syntactic errors at the earliest possible time. Also, it is established that every deterministic context-free language is defined by some Viable Prefix EWP grammar.
Finally, it is shown that the class of EWP grammars, while properly containing the class of Viable Prefix EWP grammars, is itself properly included in the well-known classes of context-free grammars with the ε-rules which define exactly the deterministic context-free languages.
Workman, David A.
Doctor of Philosophy (Ph.D.)
College of Arts and Sciences
Length of Campus-only Access
Doctoral Dissertation (Open Access)
Milani, Masoud T., "Epsilon Precedence Grammars and Languages" (1986). Retrospective Theses and Dissertations. 4904.