Back to search

University of Victoria (Canada)

Faster Tomita parsing

Abstract

dc:description.abstract

Tomita'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

Chain of custody

source
Harvested from
University of Victoria (Canada)
Base URL
dspace.library.uvic.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Aycock, John Daniel. Faster Tomita parsing. Master of Science M.Sc. thesis, 1998. https://hdl.handle.net/1828/17005