#### Keywords

Programming languages (Electronic computers) -- Syntax

#### Abstract

The classes of simple and weak precedence grammars are generalized to include e-rules (productions with the empty right parts). The descriptive power of epsilon simple precedence (ESP) grammars increases directly with the number of e-rules permitted; the class of ESP grammars with no e-rules, *ESP*_{0}, is identical to the class of simple precedence grammars; ESP grammars with at most one e-rule, *ESP*_{1}, define a class of languages which properly includes the class of *ESP*_{0} languages, but is itself properly included in the class of deterministic, context-free languages. In general, ESP grammars having at most *i* e-rules, *ESP _{i}*, define a class of languages which is properly included in that defined by

*ESP*

_{i}_{+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

*ESP*for a given

_{i}*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 fefined 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 e-rules which define exactly the deterministic context-free languages.

#### 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

#### Pages

136 p.

#### Language

English

#### Rights

Public Domain

#### Length of Campus-only Access

None

#### Access Status

Doctoral Dissertation (Open Access)

#### Identifier

DP0020312

#### STARS Citation

Milani, Masoud T., "Epsilon precedence grammars and languages" (1986). *Retrospective Theses and Dissertations*. 4904.

https://stars.library.ucf.edu/rtd/4904