A fast general parser for automatic code generation

Wuu Yang*

*Corresponding author for this work

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

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
CountryRussian 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

    Yang, W. (2010). A fast general parser for automatic code generation. In Methods and Tools of Parallel Programming Multicomputers - Second Russia-Taiwan Symposium, MTPP 2010, Revised Selected Papers (pp. 30-39). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6083 LNCS). https://doi.org/10.1007/978-3-642-14822-4_4