Paper: LR Recursive Transition Networks For Earley And Tomita Parsing

ACL ID P91-1013
Title LR Recursive Transition Networks For Earley And Tomita Parsing
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 1991
Authors
  • Mark Perlin (Carnegie Mellon University, Pittsburgh PA)

Efficient syntactic and semantic parsing for ambiguous context-free languages are generally characterized as complex, specialized, highly formal algorithms. In fact, they are readily constructed from straightforward recursive Iransition networks (RTNs). In this paper, we introduce LR-RTNs, and then computationally motivate a uniform progression from basic LR parsing, to Earley's (chart) parsing, concluding with Tomita's parser. These apparently disparate algorithms are unified into a single implementation, which was used to automatically generate all the figures in this paper.