On Covers and Left-Corner Parses

Rieks op den Akker

    Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

    5 Downloads (Pure)

    Abstract

    A transformation is defined which is a modification of a classic transformation on context-free grammars. By means of this transformation, a proof is presented of the fact that any cycle-free context-free grammar can be left-to-left-corner covered by a non-left-recursive grammar. The proof method is based on the idea to transform the characteristic grammar associated with the simple syntax-directed translation scheme which defines the left-corner parse of the strings generated by the input grammar of the scheme. It is shown that the transformation yields an LL(k) grammar if and only if it is applied to an LC(k) grammar. Finally, some ideas are presented to extend the theory of covers to the semantical covering of attribute grammars.
    Original languageEnglish
    Title of host publicationEssays on concepts, formalisms, and tools
    Subtitle of host publicationA collection of papers dedicated to Leo A.M. Verbeek
    EditorsP.R.J. Asveld, A. Nijholt
    Place of PublicationAmsterdam
    PublisherCentre for Mathematics and Computer Science
    Pages107-127
    Number of pages21
    ISBN (Print)90-6196-326-5
    Publication statusPublished - 1987

    Publication series

    NameCWI Tract
    PublisherStichting Mathematisch Centrum
    Number42

    Keywords

    • HMI-SLT: Speech and Language Technology

    Fingerprint Dive into the research topics of 'On Covers and Left-Corner Parses'. Together they form a unique fingerprint.

  • Cite this

    op den Akker, R. (1987). On Covers and Left-Corner Parses. In P. R. J. Asveld, & A. Nijholt (Eds.), Essays on concepts, formalisms, and tools: A collection of papers dedicated to Leo A.M. Verbeek (pp. 107-127). (CWI Tract; No. 42). Amsterdam: Centre for Mathematics and Computer Science.