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.
| Identifer | oai:union.ndltd.org:ucf.edu/oai:stars.library.ucf.edu:rtd-5903 |
| Date | 01 January 1986 |
| Creators | Milani, Masoud T. |
| Publisher | University of Central Florida |
| Source Sets | University of Central Florida |
| Language | English |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | Retrospective Theses and Dissertations |
| Rights | Public Domain |
Page generated in 0.2133 seconds