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

    Research output: Contribution to journalArticleAcademicpeer-review

    62 Downloads (Pure)

    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.
    Original languageEnglish
    Pages (from-to)387-406
    Number of pages20
    JournalRAIRO Informatique Théorique
    Volume16
    Publication statusPublished - 1982

    Keywords

    • IR-66955
    • EWI-9293

    Fingerprint Dive into the research topics of 'From LL-regular to LL(1) grammars: Transformations, covers and parsing'. Together they form a unique fingerprint.

    Cite this