Keywords

Programming languages, Syntax

Abstract

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.

Notes

If this is your thesis or dissertation, and want to learn how to access it or for more information about readership statistics, contact us at STARS@ucf.edu

Graduation Date

1986

Semester

Spring

Advisor

Workman, David A.

Degree

Doctor of Philosophy (Ph.D.)

College

College of Arts and Sciences

Department

Computer Science

Format

PDF

Pages

136 p.

Language

English

Rights

Public Domain

Length of Campus-only Access

None

Access Status

Doctoral Dissertation (Open Access)

Identifier

DP0020312

Accessibility Status

Searchable text

Download

Share

COinS