From LL-regular to LL(1) grammars: Transformations, covers and parsing

Research output: Contribution to journalArticle

Abstract

In this paper it is shown that it is possible to transform any LL-regular grammar G into an LL(1) grammar G' in such a way that parsing G' is as good as parsing G. That is, a parse of a sentence of grammar G can be obtained with a simple string homomorphism from the parse of a corresponding sentence of G'. Since any LL(k) grammar is an LL-regular grammar the results that are obtained are valid for LL(k) grammars as well. The relation between LL-regular grammars is expressed by means of a generalized version of the well-known cover relation between two grammars.
LanguageUndefined
Pages387-406
Number of pages20
JournalRAIRO Informatique Théorique
Volume16
StatePublished - 1982

Keywords

  • IR-66955
  • EWI-9293

Cite this

@article{0e9334cb98fb445a9f81b02f30206199,
title = "From LL-regular to LL(1) grammars: Transformations, covers and parsing",
abstract = "In this paper it is shown that it is possible to transform any LL-regular grammar G into an LL(1) grammar G' in such a way that parsing G' is as good as parsing G. That is, a parse of a sentence of grammar G can be obtained with a simple string homomorphism from the parse of a corresponding sentence of G'. Since any LL(k) grammar is an LL-regular grammar the results that are obtained are valid for LL(k) grammars as well. The relation between LL-regular grammars is expressed by means of a generalized version of the well-known cover relation between two grammars.",
keywords = "IR-66955, EWI-9293",
author = "Antinus Nijholt",
year = "1982",
language = "Undefined",
volume = "16",
pages = "387--406",
journal = "RAIRO Informatique th{\'e}orique et applications",
issn = "0988-3754",
publisher = "EDP Sciences",

}

From LL-regular to LL(1) grammars: Transformations, covers and parsing. / Nijholt, Antinus.

In: RAIRO Informatique Théorique, Vol. 16, 1982, p. 387-406.

Research output: Contribution to journalArticle

TY - JOUR

T1 - From LL-regular to LL(1) grammars: Transformations, covers and parsing

AU - Nijholt,Antinus

PY - 1982

Y1 - 1982

N2 - In this paper it is shown that it is possible to transform any LL-regular grammar G into an LL(1) grammar G' in such a way that parsing G' is as good as parsing G. That is, a parse of a sentence of grammar G can be obtained with a simple string homomorphism from the parse of a corresponding sentence of G'. Since any LL(k) grammar is an LL-regular grammar the results that are obtained are valid for LL(k) grammars as well. The relation between LL-regular grammars is expressed by means of a generalized version of the well-known cover relation between two grammars.

AB - In this paper it is shown that it is possible to transform any LL-regular grammar G into an LL(1) grammar G' in such a way that parsing G' is as good as parsing G. That is, a parse of a sentence of grammar G can be obtained with a simple string homomorphism from the parse of a corresponding sentence of G'. Since any LL(k) grammar is an LL-regular grammar the results that are obtained are valid for LL(k) grammars as well. The relation between LL-regular grammars is expressed by means of a generalized version of the well-known cover relation between two grammars.

KW - IR-66955

KW - EWI-9293

M3 - Article

VL - 16

SP - 387

EP - 406

JO - RAIRO Informatique théorique et applications

T2 - RAIRO Informatique théorique et applications

JF - RAIRO Informatique théorique et applications

SN - 0988-3754

ER -