A fast general parser for automatic code generation

Wuu Yang

doi:10.1007/978-3-642-14822-4_4

A fast general parser for automatic code generation

Wuu Yang^*

^*Corresponding author for this work

Department of Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-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 language	English
Title of host publication	Methods and Tools of Parallel Programming Multicomputers - Second Russia-Taiwan Symposium, MTPP 2010, Revised Selected Papers
Pages	30-39
Number of pages	10
DOIs	https://doi.org/10.1007/978-3-642-14822-4_4
State	Published - 2010
Event	2nd Russia-Taiwan Symposium on Methods and Tools of Parallel Programming Multicomputers, MTPP 2010 - Vladivostok, Russian Federation Duration: 16 May 2010 → 19 May 2010

Publication series

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

Conference

Conference	2nd Russia-Taiwan Symposium on Methods and Tools of Parallel Programming Multicomputers, MTPP 2010
Country/Territory	Russian Federation
City	Vladivostok
Period	16/05/10 → 19/05/10

Keywords

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

Access to Document

10.1007/978-3-642-14822-4_4

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

@inproceedings{7e805ca72e6246f2a4804ec1b316d7eb,

title = "A fast general parser for automatic code generation",

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.",

keywords = "ambiguous grammar, code generator, compiler, context-free grammar, general parsing, parsing, pattern matching, tree pattern, tree-pattern matching",

author = "Wuu Yang",

year = "2010",

doi = "10.1007/978-3-642-14822-4_4",

language = "English",

isbn = "3642148212",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "30--39",

booktitle = "Methods and Tools of Parallel Programming Multicomputers - Second Russia-Taiwan Symposium, MTPP 2010, Revised Selected Papers",

note = "2nd Russia-Taiwan Symposium on Methods and Tools of Parallel Programming Multicomputers, MTPP 2010 ; Conference date: 16-05-2010 Through 19-05-2010",

}

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. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6083 LNCS, pp. 30-39, 2nd Russia-Taiwan Symposium on Methods and Tools of Parallel Programming Multicomputers, MTPP 2010, Vladivostok, Russian Federation, 16/05/10. https://doi.org/10.1007/978-3-642-14822-4_4

A fast general parser for automatic code generation. / Yang, Wuu.
Methods and Tools of Parallel Programming Multicomputers - Second Russia-Taiwan Symposium, MTPP 2010, Revised Selected Papers. 2010. p. 30-39 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6083 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - A fast general parser for automatic code generation

AU - Yang, Wuu

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

KW - ambiguous grammar

KW - code generator

KW - compiler

KW - context-free grammar

KW - general parsing

KW - parsing

KW - pattern matching

KW - tree pattern

KW - tree-pattern matching

UR - http://www.scopus.com/inward/record.url?scp=78649856765&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-14822-4_4

DO - 10.1007/978-3-642-14822-4_4

M3 - Conference contribution

AN - SCOPUS:78649856765

SN - 3642148212

SN - 9783642148217

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 30

EP - 39

BT - Methods and Tools of Parallel Programming Multicomputers - Second Russia-Taiwan Symposium, MTPP 2010, Revised Selected Papers

T2 - 2nd Russia-Taiwan Symposium on Methods and Tools of Parallel Programming Multicomputers, MTPP 2010

Y2 - 16 May 2010 through 19 May 2010

ER -

Yang W. 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. 2010. p. 30-39. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-14822-4_4

A fast general parser for automatic code generation

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this