Name
Abstract | ||
|---|---|---|
Tomita devised a method of generalized LR (GLR) parsing to parse ambiguous grammars efficiently. A GLR parser uses linear-time LR parsing techniques as long as possible, falling back an more expensive general techniques when necessary.Much research has addressed speeding up LR parsers. However, we argue that this previous work is not transferable to GLR parsers. Instead, we speed up LR parsers by building larger pushdown automata, trading space for time. A variant of the GLR algorithm then incorporates our faster LR parsers.Our timings show that our new method for GLR parsing can parse highly ambiguous grammars significantly faster than a standard GLR parser. |
Year | DOI | Venue |
|---|---|---|
1999 | 10.1007/b72146 | CC |
Keywords | Field | DocType |
pushdown automata,linear time | Top-down parsing,Programming language,LR parser,Computer science,Simple LR parser,Algorithm,GLR parser,Parsing expression grammar,Parsing,Parser combinator,Canonical LR parser | Conference |
Volume | ISSN | ISBN |
1575 | 0302-9743 | 3-540-65717-7 |
Citations | PageRank | References |
24 | 1.75 | 14 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| John Aycock | 1 | 351 | 33.03 |
| R. Nigel Horspool | 2 | 643 | 115.14 |