Generalized LR Parsing

1. Front Matter

   Pages i-xiii

   PDF

2. The Generalized LR Parsing Algorithm

   • Masaru Tomita, See-Kiong Ng

   Pages 1-16

3. Experiments with GLR and Chart Parsing

   • Patrick Shann

   Pages 17-34

4. The Computational Complexity of GLR Parsing

   • Mark Johnson

   Pages 35-42

5. GLR Parsing in Time O(n ³)

   • James R. Kipps

   Pages 43-59

6. GLR Parsing for ε-Grammers

   • Rahman Nozohoor-Farshi

   Pages 61-75

7. Parallel GLR Parsing Based on Logic Programming

   • Hozumi Tanaka, Hiroaki Numazaki

   Pages 77-91

8. GLR Parsing with Scoring

   • Keh-Yih Su, Jong-Nae Wang, Mei-Hui Su, Jing-Shin Chang

   Pages 93-112

9. GLR Parsing With Probability

   • J. H. Wright, E. N. Wrigley

   Pages 113-128

10. GLR Parsing for Erroneous Input

    • Stuart Malone, Sue Felshin

    Pages 129-139

11. GLR Parsing for Noisy Input

    • Hiroaki Saito, Masaru Tomita

    Pages 141-151

12. GLR Parsing in Hidden Markov Model

    • Kenji Kita, Takeshi Kawabata, Hiroaki Saito

    Pages 153-164

13. Back Matter

    Pages 165-166

    PDF

The Generalized LR parsing algorithm (some call it "Tomita's algorithm") was originally developed in 1985 as a part of my Ph.D thesis at Carnegie Mellon University. When I was a graduate student at CMU, I tried to build a couple of natural language systems based on existing parsing methods. Their parsing speed, however, always bothered me. I sometimes wondered whether it was ever possible to build a natural language parser that could parse reasonably long sentences in a reasonable time without help from large mainframe machines. At the same time, I was always amazed by the speed of programming language compilers, because they can parse very long sentences (i.e., programs) very quickly even on workstations. There are two reasons. First, programming languages are considerably simpler than natural languages. And secondly, they have very efficient parsing methods, most notably LR. The LR parsing algorithm first precompiles a grammar into an LR parsing table, and at the actual parsing time, it performs shift-reduce parsing guided deterministically by the parsing table. So, the key to the LR efficiency is the grammar precompilation; something that had never been tried for natural languages in 1985. Of course, there was a good reason why LR had never been applied for natural languages; it was simply impossible. If your context-free grammar is sufficiently more complex than programming languages, its LR parsing table will have multiple actions, and deterministic parsing will be no longer possible.

• Parsing
• algorithms
• complexity
• grammar
• hidden markov model
• logic programming
• natural language
• programming
• programming language

• Carnegie Mellon University, USA

  Masaru Tomita

Policies and ethics