On the covering of parsable grammars

Research output: Book/ReportReportOther research output

Abstract

We introduce the notion of a parsable grammer, i.e. a grammar which can be parsed using a deterministic pushdown transducer. This class of grammars includes the LR(k)-grammars. The notion of covering is generalized and brought into a form making it possible to consider more than only left or righmost derivations. With this new definition of covering we prove that every parsable grammar can be covered by a strict deterministic grammar. A practical consequence is that every parsable grammar can be parsed using a strict deterministic parsing method. Some extensions of the definition of parsable grammars are considered.
Original languageUndefined
Place of PublicationEnschede
PublisherUniversity of Twente, Department of Applied Mathematics
Number of pages56
Publication statusPublished - Sep 1975

Keywords

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

Cite this

Nijholt, A. (1975). On the covering of parsable grammars. Enschede: University of Twente, Department of Applied Mathematics.
Nijholt, Anton. / On the covering of parsable grammars. Enschede : University of Twente, Department of Applied Mathematics, 1975. 56 p.
@book{5b26829ad5474a23b289b258bef78036,
title = "On the covering of parsable grammars",
abstract = "We introduce the notion of a parsable grammer, i.e. a grammar which can be parsed using a deterministic pushdown transducer. This class of grammars includes the LR(k)-grammars. The notion of covering is generalized and brought into a form making it possible to consider more than only left or righmost derivations. With this new definition of covering we prove that every parsable grammar can be covered by a strict deterministic grammar. A practical consequence is that every parsable grammar can be parsed using a strict deterministic parsing method. Some extensions of the definition of parsable grammars are considered.",
keywords = "EWI-9552, HMI-SLT: Speech and Language Technology",
author = "Anton Nijholt",
year = "1975",
month = "9",
language = "Undefined",
publisher = "University of Twente, Department of Applied Mathematics",

}

Nijholt, A 1975, On the covering of parsable grammars. University of Twente, Department of Applied Mathematics, Enschede.

On the covering of parsable grammars. / Nijholt, Anton.

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

Research output: Book/ReportReportOther research output

TY - BOOK

T1 - On the covering of parsable grammars

AU - Nijholt, Anton

PY - 1975/9

Y1 - 1975/9

N2 - We introduce the notion of a parsable grammer, i.e. a grammar which can be parsed using a deterministic pushdown transducer. This class of grammars includes the LR(k)-grammars. The notion of covering is generalized and brought into a form making it possible to consider more than only left or righmost derivations. With this new definition of covering we prove that every parsable grammar can be covered by a strict deterministic grammar. A practical consequence is that every parsable grammar can be parsed using a strict deterministic parsing method. Some extensions of the definition of parsable grammars are considered.

AB - We introduce the notion of a parsable grammer, i.e. a grammar which can be parsed using a deterministic pushdown transducer. This class of grammars includes the LR(k)-grammars. The notion of covering is generalized and brought into a form making it possible to consider more than only left or righmost derivations. With this new definition of covering we prove that every parsable grammar can be covered by a strict deterministic grammar. A practical consequence is that every parsable grammar can be parsed using a strict deterministic parsing method. Some extensions of the definition of parsable grammars are considered.

KW - EWI-9552

KW - HMI-SLT: Speech and Language Technology

M3 - Report

BT - On the covering of parsable grammars

PB - University of Twente, Department of Applied Mathematics

CY - Enschede

ER -

Nijholt A. On the covering of parsable grammars. Enschede: University of Twente, Department of Applied Mathematics, 1975. 56 p.