Abstract
To combine the advantages of probabilistic grammars and generalized LR parsing, an algorithm for constructing a probabilistic LR parser given a probabilistic context-free grammar is needed. In this paper, implementation issues in adapting Tomita’s generalized LR parser with graph-structured stack to perform probabilistic parsing are discussed. Wright and Wrigley (1989) has proposed a probabilistic LR-table construction algorithm for non-left-recursive context-free grammars. To account for left recursions, a method for computing item probabilities using the generation of systems of linear equations is presented. The notion of deferred probabilities is proposed as a means for dealing with similar item sets with differing probability assignments.- Anthology ID:
- 1991.iwpt-1.18
- Volume:
- Proceedings of the Second International Workshop on Parsing Technologies
- Month:
- February 13-25
- Year:
- 1991
- Address:
- Cancun, Mexico
- Editors:
- Masaru Tomita, Martin Kay, Robert Berwick, Eva Hajicova, Aravind Joshi, Ronald Kaplan, Makoto Nagao, Yorick Wilks
- Venue:
- IWPT
- SIG:
- SIGPARSE
- Publisher:
- Association for Computational Linguistics
- Note:
- Pages:
- 154–163
- Language:
- URL:
- https://aclanthology.org/1991.iwpt-1.18
- DOI:
- Cite (ACL):
- See-Kiong Ng and Masaru Tomita. 1991. Probabilistic LR Parsing for General Context-Free Grammars. In Proceedings of the Second International Workshop on Parsing Technologies, pages 154–163, Cancun, Mexico. Association for Computational Linguistics.
- Cite (Informal):
- Probabilistic LR Parsing for General Context-Free Grammars (Ng & Tomita, IWPT 1991)
- PDF:
- https://preview.aclanthology.org/revert-3132-ingestion-checklist/1991.iwpt-1.18.pdf