Regular extensions of some classes of grammars

Research output: Book/ReportReportOther research output

Abstract

Culik and Cohen introduced the class of LR-regular grammars, an extension of the LR(k) grammars. In this report we consider the analogous extension of the LL(k) grammers, called the LL-regular grammars. The relations of this class of grammars to other classes of grammars are shown. Every LL-regular grammar can be transformed to an equivalent LL-regular grammar in Greibach Normal Form. LL-regular grammars can be parsed with a very simple two-scan parsing algorithm. Algorithms and some proofs of correctness are given. In this report extensions of some other classes of grammars are also considered.
Original languageUndefined
Place of PublicationEnschede
PublisherUniversity of Twente, Department of Applied Mathematics
Number of pages51
Publication statusPublished - Sep 1975

Keywords

  • HMI-SLT: Speech and Language Technology
  • EWI-9553

Cite this

Nijholt, A. (1975). Regular extensions of some classes of grammars. Enschede: University of Twente, Department of Applied Mathematics.
Nijholt, Anton. / Regular extensions of some classes of grammars. Enschede : University of Twente, Department of Applied Mathematics, 1975. 51 p.
@book{f177500954c343439b06f860dc2a1dfe,
title = "Regular extensions of some classes of grammars",
abstract = "Culik and Cohen introduced the class of LR-regular grammars, an extension of the LR(k) grammars. In this report we consider the analogous extension of the LL(k) grammers, called the LL-regular grammars. The relations of this class of grammars to other classes of grammars are shown. Every LL-regular grammar can be transformed to an equivalent LL-regular grammar in Greibach Normal Form. LL-regular grammars can be parsed with a very simple two-scan parsing algorithm. Algorithms and some proofs of correctness are given. In this report extensions of some other classes of grammars are also considered.",
keywords = "HMI-SLT: Speech and Language Technology, EWI-9553",
author = "Anton Nijholt",
year = "1975",
month = "9",
language = "Undefined",
publisher = "University of Twente, Department of Applied Mathematics",

}

Nijholt, A 1975, Regular extensions of some classes of grammars. University of Twente, Department of Applied Mathematics, Enschede.

Regular extensions of some classes of grammars. / Nijholt, Anton.

Enschede : University of Twente, Department of Applied Mathematics, 1975. 51 p.

Research output: Book/ReportReportOther research output

TY - BOOK

T1 - Regular extensions of some classes of grammars

AU - Nijholt, Anton

PY - 1975/9

Y1 - 1975/9

N2 - Culik and Cohen introduced the class of LR-regular grammars, an extension of the LR(k) grammars. In this report we consider the analogous extension of the LL(k) grammers, called the LL-regular grammars. The relations of this class of grammars to other classes of grammars are shown. Every LL-regular grammar can be transformed to an equivalent LL-regular grammar in Greibach Normal Form. LL-regular grammars can be parsed with a very simple two-scan parsing algorithm. Algorithms and some proofs of correctness are given. In this report extensions of some other classes of grammars are also considered.

AB - Culik and Cohen introduced the class of LR-regular grammars, an extension of the LR(k) grammars. In this report we consider the analogous extension of the LL(k) grammers, called the LL-regular grammars. The relations of this class of grammars to other classes of grammars are shown. Every LL-regular grammar can be transformed to an equivalent LL-regular grammar in Greibach Normal Form. LL-regular grammars can be parsed with a very simple two-scan parsing algorithm. Algorithms and some proofs of correctness are given. In this report extensions of some other classes of grammars are also considered.

KW - HMI-SLT: Speech and Language Technology

KW - EWI-9553

M3 - Report

BT - Regular extensions of some classes of grammars

PB - University of Twente, Department of Applied Mathematics

CY - Enschede

ER -

Nijholt A. Regular extensions of some classes of grammars. Enschede: University of Twente, Department of Applied Mathematics, 1975. 51 p.