Elamur Research⌕
☰
home / papers / 1993 / Generalized Probabilistic LR Parsing of Natural Language (Corpora) with Unification-Based Grammars

Generalized Probabilistic LR Parsing of Natural Language (Corpora) with Unification-Based Grammars

Paper · 1993 · Ted Briscoe and John Carroll

Summary

Grammars with broad coverage of English typically license many analyses for a single sentence, sometimes thousands. Briscoe and Carroll address how to pick out the plausible analysis and how to adapt a general grammar to a particular sublanguage. They describe an automatic way to compile the unification-based ANLT grammar into an LALR(1) parse table. Two parsers use this table. The first is an interactive parser in which a human selects the correct derivation, which yields disambiguated training data with little manual effort. The second is a breadth-first probabilistic parser that attaches probabilities directly to LR table actions. Because these probabilities depend on parse state, the model can tell apart derivations that a probabilistic CFG would score identically. An optimized version of Tomita's generalized LR algorithm ran faster in practice than a well-indexed chart parser, even though its worst-case complexity is exponential. A pilot study on noun definitions from LDOCE produced encouraging results: rule-frequency statistics tracked the most plausible analysis usefully, though not perfectly. This makes statistical ranking available within a linguistically adequate grammar formalism.

Key points

  • The grammar is ANLT, with a lexicon of about 40,000 lexemes and roughly 700 phrase structure rules. Earlier work found that a previous version correctly analyzed 96.8% of 10,000 corpus noun phrases.
  • Probabilities are assigned to LR parse-table actions rather than to CFG rules or lexical tags. This makes the language model sensitive to parse context.
  • An interactive LR parser supports supervised training. A human chooses the correct analyses and adds grammar rules where coverage is missing.
  • Generalized LR parsing based on Tomita (1987) was compared empirically with an optimized chart parser and was the more efficient of the two for ANLT.
  • The pilot study trained on 150 LDOCE noun definitions and was retested on those plus 55 new ones. Definitions use a vocabulary of about 2,000 morphemes and average roughly 10 words, with a maximum of about 30.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓University of CambridgeCambridge · United Kingdom256 works · 123,373 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksArtificial Intelligence · 17,965 worksArts and Humanities · 17,450 worksLanguage and Linguistics · 17,296 works

Cite

Cite as Ted Briscoe and John Carroll. 1993. Generalized Probabilistic LR Parsing of Natural Language (Corpora) with Unification-Based Grammars. Computational Linguistics.

The paper itself, not this page. BibTeX from the library's record of the work.

@article{briscoe1993generalized,
  title = {{Generalized Probabilistic LR Parsing of Natural Language (Corpora) with Unification-Based Grammars}},
  author = {Ted Briscoe and John Carroll},
  journal = {Computational Linguistics},
  year = {1993},
  url = {https://aclanthology.org/J93-1002/}
}

References

76 references, 7 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Aho, A.; Sethi, R.; and Ullman, J. (1986). Compilers: Principles, Techniques and Tools. Addison-Wesley. find
  2. Alshawi, H., ed. (1992). The Core Language Engine. MIT Press. find
  3. Baker, J. (1982). "Trainable grammars for speech recognition." Speech Communication Papers for the 97th Meeting of the Acoustical Society of America, 547-550. find
  4. Baum, L. (1972). "An inequality and associated maximization technique in statistical estimation for probabilistic functions of Markov processes." Inequalities, III, 1-8. find
  5. Bermudez, M. (1991). "A unifying model for lookahead LR parsing." Computer Languages, 16(2), 167-178. find
  6. Boguraev, B.; Carroll, J.; Briscoe, E.; and Grover, C. (1988). "Software support for practical grammar development." In Proceedings, 12th International Conference on Computational Linguistics, Budapest, Hungary, 54-58. find
  7. Brent, M. (1991). "Automatic acquisition of subcategorization frames from untagged text." In Proceedings, 29th Annual Meeting of the Association for Computational Linguistics, Berkeley, CA, 209-214. find
  8. Briscoe, E. (1987). Modelling Human Speech Comprehension: A Computational Approach. Ellis Horwood and Wiley. find
  9. Briscoe, E.; Grover, C.; Boguraev, B.; and Carroll, J. (1987). "A formalism and environment for the development of a large grammar of English. In Proceedings, l Oth International Joint Conference on Artificial Intelligence, Milan, Italy, 703-708. find
  10. Briscoe, E., and Carroll, J. (1991). "Generalized probabilistic LR parsing of natural language (corpora) with unification-based grammars." Technical Report 224, Computer Laboratory, Cambridge University. find
  11. Briscoe, E., and Waegner, N. (1992). "Robust stochastic parsing using the inside-outside algorithm." In Proceedings, AAAI Workshop on Statistically-based NLP Techniques, San Jose, CA. find
  12. Carroll, J., and Grover, C. (1989). "The derivation of a large computational lexicon for English." In Computational Lexicography for Natural Language Processing, edited by B. Boguraev and E. Briscoe, 117-134. Longman. find
  13. Carroll, J.; Boguraev, B.; Grover, C.; and Briscoe, E. (1988). "The grammar development environment: a user guide." Technical Report 127, Computer Laboratory, Cambridge University. find
  14. Carroll, J., and Briscoe, E. (1992). "Probabilistic normalisation and unpacking of packed parse forests for unification-based grammars." In Proceedings, AAAI Fall Symposium on Probabilistic Approaches to Natural Language, Cambridge, MA, 33-38. find
  15. Chapman, N. (1987). LR Parsing: Theory and Practice. Cambridge University Press. find
  16. Church, K., and Hanks, P. (1989). "Word association norms, mutual information, and lexicography." In Proceedings, 27th Annual Meeting of the Association for Computational Linguistics, Vancouver, British Columbia, 76-83.
  17. Church, K., and Patil, R. (1982). "Coping with syntactic ambiguity or how to put the block in the box on the table." Computational Linguistics, 8, 139-149. find
  18. Copestake, A. (1990). "An approach to building the hierarchical element of a lexical knowledge base from a machine-readable dictionary." In Proceedings, Workshop on Inheritance in Natural Language Processing, Tilburg, 19-29. find
  19. Copestake, A. (1992). "Defaults in lexical representation." In Default Inheritance in Unification-based Approaches to the Lexicon, edited by E. Briscoe, A. Copestake, and V. de Paiva. Cambridge University Press. find
  20. Culic, K. II, and Cohen, R. (1973). "LR-regular grammars — an extension of LR(k) grammars." Journal of Computer and System Sciences, 7, 66-96. find
  21. Cutting, D.; Kupiec, J.; Pedersen, J.; and Sibun, P. (1992). "A practical part-of-speech tagger." 3rd Applied ACL, Trento, Italy, 133-140.
  22. DeRemer, E, and Pennello, T. (1982). "Efficient computation of LALR(1) look-ahead sets." ACM Transactions on Programming Languages and Systems, 4(4), 615-649. de Rose, S. (1988). "Grammatical category disambiguation by statistical optimization." Computational Linguistics, 14(1), 31-39.
  23. Earley, J. (1970). "An efficient context-free parsing algorithm." Communications of the ACM, 13(2), 94-102. find
  24. Frazier, L. (1988). "Grammar and language processing." In Linguistics: The Cambridge Survey, Volume 2, edited by F. Newmeyer, 14-45. Cambridge University Press. find
  25. Fujisaki, T.; Jelinek, E; Cocke, J.; Black E.; and Nishino, T. (1989). "A probabilistic method for sentence disambiguation." In Proceedings, 1st International Workshop on Parsing Technologies, Carnegie-Mellon University, Pittsburgh, PA, 105-114. find
  26. Gale, W., and Church, K. (1990). "Poor estimates of context are worse than none." DARPA Speech and Natural Language Workshop, Hidden Valley, PA, 283-287. find
  27. Garside, R.; Leech, G.; and Sampson, G. (1987). The Computational Analysis of English: A Corpus-Based Approach. find
  28. Gazdar, G.; Klein, E.; Pullum, G.; and Sag, I. (1985). Generalized Phrase Structure Grammar. Blackwell. find
  29. Gazdar, G., and Mellish, C. (1989). Natural Language Processing in Lisp. find
  30. Grosch, J. (1990). "Lalr — A generator for efficient parsers." Software — Practice and Experience, 20(11), 1115-1135. find
  31. Grover, C.; Briscoe, E.; Carroll, J.; and Boguraev, B. (1989). "The Alvey natural language tools grammar (second release)." Technical Report 162, Computer Laboratory, Cambridge University. find
  32. Hektoen, E. (1991). "LAR processing for natural language grammars." Masters dissertation, Computer Laboratory, Cambridge University, Cambridge, U.K. find
  33. Hindle, D., and Rooth, M. (1991). "Structural ambiguity and lexical relations." In Proceedings, 29th Annual Meeting of the Association for Computational Linguistics, Berkeley, CA, 229-236.
  34. Holmes, J. (1988). Speech Synthesis and Recognition. Van Nostrand Reinhold. find
  35. Jensen, K.; Heidorn, G.; Miller, L.; and Ravin, Y. (1983), "Parse fitting and prose fixing: getting a hold on ill-formedness." Computational Linguistics, 9, 147-153.
  36. Johnson, M. (1989). "The computational complexity of Tomita's algorithm." In Proceedings, Ist International Workshop on Parsing Technologies, Carnegie-Mellon University, Pittsburgh, PA, 203-208. find
  37. Kimball, J. (1973). "Seven principles of surface structure parsing in natural language." Cognition, 2, 15-47. find
  38. Kipps, J. (1989). "Analysis of Tomita's algorithm for general context-free parsing." In Proceedings, 1st International Workshop on Parsing Technologies, Carnegie-Mellon University, Pittsburgh, PA, 193-202. find
  39. Klein, E., and Martin, M. (1989). "The parser generating system PGSU." Software — Practice and Experience, 19(11), 1015-1028. find
  40. Kristensen, B., and Madsen, O. (1981). "Methods for computing LALR(k) lookahead." ACM Transactions on Programming Languages and Systems, 3(1), 60-82. find
  41. Kupiec, J. (1991). "A trellis-based algorithm for estimating the parameters of a hidden stochastic context-free grammar," DARPA Speech and Natural Language Workshop, Asilomar, CA. find
  42. Lari, K., and Young, S. (1990). "The estimation of stochastic context-free grammars using the Inside-Outside algorithm." Computer Speech and Language Processing, 4, 35-56. find
  43. Leech, G., and Garside, R. (1991). "Running a grammar factory: the production of syntactically analysed corpora or 'treebanks'." In English Computer Corpora: Selected Papers and Bibliography, edited by S. Johansson and A. Strenstrom. Mouton de Gruyter. find
  44. Magerman, D., and Marcus, M. (1991). "Pearl: A probabilistic chart parser." In Proceedings, 2nd International Workshop on Parsing Technologies, Cancun, Mexico, 193-199. find
  45. Meteer, M.; Schwartz, R.; and Weischedel, R. (1991). "POST: Using probabilities in language processing." In Proceedings, 12th International Joint Conference on Artificial Intelligence, Sydney, Australia, 960-965. find
  46. Nakazawa, T. (1991). "An extended LR parsing algorithm for grammars using feature-based syntactic categories." In Proceedings, 5th European Conference of the Association for Computational Linguistics, Berlin, Germany, 69-74. find
  47. Ng, S.-K., and Tomita, M. (1991). "Probabilistic parsing for general context-free grammars." In Proceedings, 2nd International Workshop on Parsing Technologies, Cancun, Mexico, 154-163. find
  48. Osborne, M. (1990). "Corpus parsing." Masters dissertation, University of Cambridge, Cambridge, U.K. find
  49. Pereira, E, and Shieber, S. (1987). Prolog and Natural Language Analysis. University of Chicago Press. find
  50. Pereira, F., and Warren, D. (1980). "Definite clause grammars for language analysis — a survey of the formalism and a comparison with augmented transition networks." Artificial Intelligence, 13(3), 231-278. find
  51. Pereira, E, and Schabes, Y. (1992). "Inside-outside re-estimation for partially bracketed corpora." In Proceedings, 30th Annual Meeting of the Association for Computational Linguistics, Newark, DE, 128-135. find
  52. Pollack, M., and Pereira, E (1988). "An integrated framework for semantic and pragmatic interpretation." In Proceedings, 26th Annual Conference of the Association for Computational Linguistics, Buffalo, NY, 75-86.
  53. Pollard, C., and Sag, I. (1987). find
  54. Information~Based Syntax and Semantics: Volume 1 — Fundamentals. Chicago University Press. find
  55. Procter, P., ed. (1978). The Longman Dictionary of Contemporary English. Longman. find
  56. Ritchie, G.; Pulman, S.; Russell, G.; and Black, A. (1987). "A computational framework for lexical description." Computational Linguistics, 13, 290-307. find
  57. Sampson, G. (1987). "The grammatical database and parsing scheme." In The Computational Analysis of English: A Corpus-Based Approach, edited by R. Garside; G. Leech; and G. Sampson, 82-96. Longman. find
  58. Sampson, G.; Haigh, R.; and Atwell, E. (1989). "Natural language analysis by stochastic optimization: a progress report on Project APRIL." Journal of Experimental and Theoretical Artificial Intelligence, 1, 271-287. find
  59. Santorini, B. (1990). "Penn treebank tagging and parsing manual." University of Pennsylvania, CIS Dept. Unpublished manuscript. find
  60. Schabes, Y. (1991a). "Polynomial time and space shift-reduce parsing of arbitrary contexbfree grammars." In Proceedings, 29th Annual Meeting of the Association for Computational Linguistics, Berkeley, CA, 106-113. find
  61. Schabes, Y. (1991b). "The valid prefix property and left to right parsing of tree-adjoining grammar." In Proceedings, 2nd International Workshop on Parsing Technologies, Cancun, Mexico, 21-30. find
  62. Sharman, R. (1989). "Probabilistic ID/LP grammars for English." Report 217, IBM UK Scientific Centre, Winchester, England. find
  63. Sharman, R. (1991). "An introduction to language modelling." Unpublished manuscript, IBM UK Scientific Centre, Winchester, England. find
  64. Sharman, R.; Jelinek, F.; and Mercer, R. (1990). "Generating a grammar for statistical training." DARPA Speech and Natural Language Workshop, Hidden Valley, PA, 267-274. find
  65. Shieber, S. (1983). "Disambiguation by a shift-reduce parsing technique." In Proceedings, 21st Annual Meeting of the Association for Computational Linguistics, MIT, Cambridge, MA, 113-118. find
  66. Shieber, S. (1984). "The design of a computer language for linguistic information." In Proceedings, l Oth International Conference on Computational Linguistics, Stanford, CA, 362-366. find
  67. Shieber, S. (1985). "Using restriction to extend parsing algorithms for complex feature-based formalisms." In Proceedings, 23rd Annual Meeting of the Association for Computational Linguistics, Chicago, IL, 145-152. find
  68. Spector, D. (1983). "Lexing and parsing modula-2." SIGPLANNotices, 18(10), 25-32. find
  69. Taylor, L.; Grover, C.; and Briscoe, E. (1989). "The syntactic regularity of English noun phrases." In Proceedings, 4th European Meeting of the Association for Computational Linguistics, UMIST, Manchester, U.K., 256-263.
  70. Tomita, M. (1984). "Parsers for natural languages." In Proceedings, lOth International Conference on Computational Linguistics, Stanford, CA, 354-357. find
  71. Tomita, M. (1987). "An efficient augmented context-free parsing algorithm." Computational Linguistics, 13(1), 31–46. find
  72. Viterbi, A. (1967). "Error bounds for convolutional codes and an asymptotically optimum decoding algorithm." IEEE Trans. Information Theory, IT-13, 260-269. find
  73. Wright, J. (1990). "LR parsing of probabilistic grammars with input uncertainty for speech recognition." Computer Speech and Language, 4, 297-323. find
  74. Wright, J., and Wrigley, E. (1989). "Probabilistic LR parsing for speech recognition." In Proceedings, 1st International Workshop on Parsing Technologies, Carnegie-Mellon University, Pittsburgh, PA, 193-202. find
  75. Wright, J.; Wrigley, E.; and Sharman, R. (1991). "Adaptive probabilistic generalized LR parsing." In Proceedings, 2nd International Workshop on Parsing Technologies, Cancun, Mexico, 154-163. find
  76. Zeevat, H.; Calder, J.; and Klein, E. (1987). Unification categorial grammar. In Edinburgh Working Papers in Cognitive Science, 1: Categorial Grammar, Unification Grammar, and Parsing, edited by N. Haddock, E. Klein, and G. Morrill, Centre for Cognitive Science, Edinburgh University, U.K., 195-222. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/briscoe-1993-generalized-probabilistic-lr-parsing-natural/