An imperial comparison of generalized LR tables

Marc Lankhorst

    Research output: Chapter in Book/Report/Conference proceedingConference contributionProfessional

    29 Downloads (Pure)

    Abstract

    In this study, table sizes and parsing efficiency of Tomita's algorithm with LR(0), SLR(1), LALR(1) and LR(1) parsing tables are compared on the basis of empirical data. From this comparison, it can be con­cluded that LALR(1) tables are the best choice regar­ding parsing time. These tables are about the same size as SLR(1) and noticeably smaller than LR(1) tables. If the size of the tables or the ease of construction is a determining factor, it can be advisable to use LR(0) tables.
    As is known from the theory of 'standard' LR parsing, the useofLR(1) tables is expected to result in the best parsing efficiency compared to the other three types. However, this is not the case in Generalized LR par­sing. LR(1) turns out to be significantly slower than the other types presented. We give an elegant explana­tion for this unexpected phenomenon.
    Original languageEnglish
    Title of host publicationTomita's Algorithm - Extensions and Applications
    Subtitle of host publicationProceedings of the first Twente Workshop on Language Technology
    EditorsRob Heemels, Anton Nijholt, Klaas Sikkel
    Place of PublicationEnschede
    PublisherUniversiteit Twente
    Pages87-94
    Number of pages8
    Publication statusPublished - 1991
    Event1st Twente Workshop on Language Technology, TWLT 1: Tomita's Algorithm: Extensions and Applications - Enschede, Netherlands
    Duration: 22 Mar 199122 Mar 1991
    Conference number: 1

    Publication series

    NameMemoranda informatica
    PublisherUniversity of Twente
    Number91-68
    ISSN (Print)0924-3755

    Workshop

    Workshop1st Twente Workshop on Language Technology, TWLT 1
    Abbreviated titleTWLT
    CountryNetherlands
    CityEnschede
    Period22/03/9122/03/91

    Fingerprint Dive into the research topics of 'An imperial comparison of generalized LR tables'. Together they form a unique fingerprint.

    Cite this