A fast general parser for automatic code generation

Wuu Yang*

*Corresponding author for this work

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    1 Scopus citations

    Abstract

    The code generator in a compiler attempts to match a subject tree against a collection of tree-shaped patterns for generating instructions. Tree-pattern matching may be considered as a generalization of string parsing. We propose a new generalized LR (GLR) parser, which extends the LR parser stack with a parser cactus. GLR explores all plausible parsing steps to find the least-cost matching. GLR is fast due to two properties: (1) duplicate parsing steps are eliminated and (2) partial parse trees that will not lead to a least-cost matching are discarded as early as possible.

    Original languageEnglish
    Title of host publicationMethods and Tools of Parallel Programming Multicomputers - Second Russia-Taiwan Symposium, MTPP 2010, Revised Selected Papers
    Pages30-39
    Number of pages10
    DOIs
    StatePublished - 13 Dec 2010
    Event2nd Russia-Taiwan Symposium on Methods and Tools of Parallel Programming Multicomputers, MTPP 2010 - Vladivostok, Russian Federation
    Duration: 16 May 201019 May 2010

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume6083 LNCS
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Conference

    Conference2nd Russia-Taiwan Symposium on Methods and Tools of Parallel Programming Multicomputers, MTPP 2010
    Country/TerritoryRussian Federation
    CityVladivostok
    Period16/05/1019/05/10

    Keywords

    • ambiguous grammar
    • code generator
    • compiler
    • context-free grammar
    • general parsing
    • parsing
    • pattern matching
    • tree pattern
    • tree-pattern matching

    Fingerprint

    Dive into the research topics of 'A fast general parser for automatic code generation'. Together they form a unique fingerprint.

    Cite this