Generalized LR Parsing

Editors: Tomita, Masaru (Ed.)

Buy this book

eBook $129.00
price for USA (gross)
  • ISBN 978-1-4615-4034-2
  • Digitally watermarked, DRM-free
  • Included format: PDF
  • ebooks can be used on all reading devices
  • Immediate eBook download after purchase
Hardcover $166.00
price for USA
  • ISBN 978-0-7923-9201-9
  • Free shipping for individuals worldwide
  • Usually dispatched within 3 to 5 business days.
Softcover $166.00
price for USA
  • ISBN 978-1-4613-6804-5
  • Free shipping for individuals worldwide
  • Usually dispatched within 3 to 5 business days.
About this book

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.

Table of contents (11 chapters)

  • The Generalized LR Parsing Algorithm

    Tomita, Masaru (et al.)

    Pages 1-16

  • Experiments with GLR and Chart Parsing

    Shann, Patrick

    Pages 17-34

  • The Computational Complexity of GLR Parsing

    Johnson, Mark

    Pages 35-42

  • GLR Parsing in Time O(n 3 )

    Kipps, James R.

    Pages 43-59

  • GLR Parsing for ε-Grammers

    Nozohoor-Farshi, Rahman

    Pages 61-75

Buy this book

eBook $129.00
price for USA (gross)
  • ISBN 978-1-4615-4034-2
  • Digitally watermarked, DRM-free
  • Included format: PDF
  • ebooks can be used on all reading devices
  • Immediate eBook download after purchase
Hardcover $166.00
price for USA
  • ISBN 978-0-7923-9201-9
  • Free shipping for individuals worldwide
  • Usually dispatched within 3 to 5 business days.
Softcover $166.00
price for USA
  • ISBN 978-1-4613-6804-5
  • Free shipping for individuals worldwide
  • Usually dispatched within 3 to 5 business days.
Loading...

Recommended for you

Loading...

Bibliographic Information

Bibliographic Information
Book Title
Generalized LR Parsing
Editors
  • Masaru Tomita
Copyright
1991
Publisher
Springer US
Copyright Holder
Springer Science+Business Media New York
eBook ISBN
978-1-4615-4034-2
DOI
10.1007/978-1-4615-4034-2
Hardcover ISBN
978-0-7923-9201-9
Softcover ISBN
978-1-4613-6804-5
Edition Number
1
Number of Pages
XIII, 166
Topics