Abstract
dc:description.abstractTomita's parsing method, or generalized LR parsing, was designed to parse ambiguous grammars efficiently. Tomita uses specific linear-time LR parsing techniques as long as possible, falling back on more expensive general techniques when necessary. Much research has addressed speeding up LR parsers, in this thesis, we argue that this previous work is not transferable to Tomita parsers. To speed up LR parsers, we reduce LR parsing overhead two ways: grammar transformations unroll recursion, and larger finite automata in the parser trade space for time. We have devised a variant of Tomita's algorithm which incorporates our low overhead LR parsers. Our timings show that our Tomita variant gives an order of magnitude improvement for the worst case ambiguous grammar on most inputs, several orders of magnitude improvement are seen on larger grammars.
Degree
thesis:*- Level thesis:degree_level
- Master of Science M.Sc.
- Department thesis:degree_department
- Department of Computer Science
- Year dc:date.issued
- 1998
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Aycock, John Daniel
Rights
dc:rights- Statement dc:rights
-
- Available to the World Wide Web
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/1828/17005