Article

Free access

Interleaving syntax and semantics in an efficient bottom-up parser

Authors:

John Dowding,

Robert Moore,

Frančois Andry,

Douglas MoranAuthors Info & Claims

ACL '94: Proceedings of the 32nd annual meeting on Association for Computational Linguistics

Pages 110 - 116

https://doi.org/10.3115/981732.981748

Published: 27 June 1994 Publication History

PDF eReader

Abstract

We describe an efficient bottom-up parser that interleaves syntactic and semantic structure building. Two techniques are presented for reducing search by reducing local ambiguity: Limited left context constraints are used to reduce local syntactic ambiguity, and deferred sortal-constraint application is used to reduce local semantic ambiguity. We experimentally evaluate these techniques, and show dramatic reductions in both number of chart edges and total parsing time. The robust processing capabilities of the parser are demonstrated in its use in improving the accuracy of a speech recognizer.

References

[1]

Alshawi, H. (ed.). 1992. The Core Language Engine. MIT Press, Cambridge, Massachusetts.

Google Scholar

[2]

Dowding, J., Garwon, J., Appelt, D., Bear, J., Cherny, L., Moore, R., and Moran, D. 1993. GEMINI: A Natural Language Understanding System for Spoken-Language Understanding, in 31st Annual Meeting of the Association for Computational Linguistics, Columbus, Ohio (June), pp. 54--61.

Digital Library

Google Scholar

[3]

Earley, J. 1970. An Efficient Context-Free Parsing Algorithm, Communications of the ACM, 31, 2 (Feb.), pp. 94--102.

Digital Library

Google Scholar

[4]

Graham, S., Harrison, M., and Ruzzo, W. 1980. An Improved Context-Free Recognizer, ACM Transactions on Programming Languages and Systems, 2, 3 (July), pp. 415--462.

Digital Library

Google Scholar

[5]

Hopcroft, J. and Ullman, J. 1980. Introduction to Automata Theory, Languages, and Computation, Addison-Wesley Publishing, Reading, Massachusetts.

Digital Library

Google Scholar

[6]

Kasami, T. 1965. An Efficient Recognition and Syntax. Algorithm for Context-Free Languages, Scientific Report AFCRL-65-758, Air Force Cambridge Research Laboratory, Bedford, Massachusetts.

Google Scholar

[7]

MADCOW 1992. Multi-site Data Collection for a Spoken Language Corpus, in Proceedings of the DARPA Speech and Natural Language Workshop, February 23--26, pp. 7--14.

Digital Library

Google Scholar

[8]

Moore, R., and Dowding, J. 1991. Efficient Bottom-Up Parsing, in Proceedings of the DARPA Speech and Natural Language Workshop, February 19--22, pp. 200--203.

Digital Library

Google Scholar

[9]

Murveit, H., Butzberger, J., Digalakis, V. and Weintraub, M. 1993. Large-Vocabulary Dictation Using SRI's DECIPHERTM Speech Recognition System: Progressive-Search Techniques, in Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing, Minneapolis, Minnesota (April), pp. II-319-II-322.

Google Scholar

[10]

Pallet, D. et al. 1994. 1993 Benchmark Tests for the ARPA Spoken Language Program, in Proceedings of the ARPA Workshop on Human Language Technology, March 8--11.

Digital Library

Google Scholar

[11]

Shieber, S. 1985. Using Restriction to Extend Parsing Algorithms for Complex-Feature-Based Formalisms, in 23rd Annual Meeting of the Association for Computational Linguistics, Chicago, Illinois (July), pp. 145--152.

Digital Library

Google Scholar

[12]

Younger, D. 1967. Recognition and Parsing of Context-Free Languages in Time n3, Information and Control, 10, 2, pp. 189--208.

Crossref

Google Scholar

Cited By

View all

Korkontzelos IManandhar SKaplan R(2010)Can recognising multiword expressions improve shallow parsing?Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics10.5555/1857999.1858088(636-644)Online publication date: 2-Jun-2010
https://dl.acm.org/doi/10.5555/1857999.1858088
Chollet GAmehraye ARazik JZouari LKhemiri HMokbel C(2009)Spoken dialogue in virtual worldsProceedings of the Second international conference on Development of Multimodal Interfaces: active Listening and Synchrony10.1007/978-3-642-12397-9_36(423-443)Online publication date: 23-Mar-2009
https://dl.acm.org/doi/10.1007/978-3-642-12397-9_36
Zhou DHe YScott DUszkoreit H(2008)A hybrid generative/discriminative framework to train a semantic parser from an un-annotated corpusProceedings of the 22nd International Conference on Computational Linguistics - Volume 110.5555/1599081.1599221(1113-1120)Online publication date: 18-Aug-2008
https://dl.acm.org/doi/10.5555/1599081.1599221
Show More Cited By

Interleaving syntax and semantics in an efficient bottom-up parser

Recommendations

On the interaction of syntax and semantics in a syntactically guided caseframe parser
COLING '88: Proceedings of the 12th conference on Computational linguistics - Volume 2

In this paper we describe a parser for German based on semantic caseframe instantiation guided by a syntactic analyzer. Pure caseframe parsers lack the ability to capture syntactic regularities, which leads to redundancy in the lexicon and/or poor ...
Bottom-up context-sensitive algorithms for Bengali parser in natural language processing

This paper embodies the design of parsing algorithms tangibly for a Bengali parser. To design parsing algorithms a detailed study on linguistics and grammar has been performed. A detailed study also has been made on the various techniques and algorithms ...
Syntax-Based Post-Ordering for Efficient Japanese-to-English Translation

This article proposes a novel reordering method for efficient two-step Japanese-to-English statistical machine translation (SMT) that isolates reordering from SMT and solves it after lexical translation. This reordering problem, called post-ordering, is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ACL '94: Proceedings of the 32nd annual meeting on Association for Computational Linguistics

June 1994

353 pages

Program Chair:
James Pustejovsky
Brandeis University

Publisher

Association for Computational Linguistics

United States

Publication History

Published: 27 June 1994

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 85 of 443 submissions, 19%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
373
Total Downloads

Downloads (Last 12 months)40
Downloads (Last 6 weeks)8

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Korkontzelos IManandhar SKaplan R(2010)Can recognising multiword expressions improve shallow parsing?Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics10.5555/1857999.1858088(636-644)Online publication date: 2-Jun-2010
https://dl.acm.org/doi/10.5555/1857999.1858088
Chollet GAmehraye ARazik JZouari LKhemiri HMokbel C(2009)Spoken dialogue in virtual worldsProceedings of the Second international conference on Development of Multimodal Interfaces: active Listening and Synchrony10.1007/978-3-642-12397-9_36(423-443)Online publication date: 23-Mar-2009
https://dl.acm.org/doi/10.1007/978-3-642-12397-9_36
Zhou DHe YScott DUszkoreit H(2008)A hybrid generative/discriminative framework to train a semantic parser from an un-annotated corpusProceedings of the 22nd International Conference on Computational Linguistics - Volume 110.5555/1599081.1599221(1113-1120)Online publication date: 18-Aug-2008
https://dl.acm.org/doi/10.5555/1599081.1599221
Stoness STetreault JAllen J(2004)Incremental parsing with reference interactionProceedings of the Workshop on Incremental Parsing: Bringing Engineering and Cognition Together10.5555/1613148.1613152(18-25)Online publication date: 25-Jul-2004
https://dl.acm.org/doi/10.5555/1613148.1613152
Schuler WHinrichs ERoth D(2003)Using model-theoretic semantic interpretation to guide statistical parsing and word recognition in a spoken language interfaceProceedings of the 41st Annual Meeting on Association for Computational Linguistics - Volume 110.3115/1075096.1075163(529-536)Online publication date: 7-Jul-2003
https://dl.acm.org/doi/10.3115/1075096.1075163
Schuler W(2002)Interleaved semantic interpretation in environment-based parsingProceedings of the 19th international conference on Computational linguistics - Volume 110.3115/1072228.1072252(1-7)Online publication date: 24-Aug-2002
https://dl.acm.org/doi/10.3115/1072228.1072252
Stent ADowding JGawron JBratt EMoore RDale RChurch K(1999)The CommandTalk spoken dialogue systemProceedings of the 37th annual meeting of the Association for Computational Linguistics on Computational Linguistics10.3115/1034678.1034713(183-190)Online publication date: 20-Jun-1999
https://dl.acm.org/doi/10.3115/1034678.1034713
Roussel DHalber AHirschberg JKamm CWalker M(1997)Filtering errors and repairing linguistic anomalies for spoken dialogue systemsInteractive Spoken Dialog Systems on Bringing Speech and NLP Together in Real Applications10.5555/1641462.1641477(74-81)Online publication date: 11-Jul-1997
https://dl.acm.org/doi/10.5555/1641462.1641477
Moore RDowding JBratt HGawron JGorfu YCheyer AGrishman R(1997)CommandTalkProceedings of the fifth conference on Applied natural language processing10.3115/974557.974558(1-7)Online publication date: 31-Mar-1997
https://dl.acm.org/doi/10.3115/974557.974558
Moran DCheyer AJulia LMartin DPark S(1997)Multimodal user interfaces in the Open Agent ArchitectureProceedings of the 2nd international conference on Intelligent user interfaces10.1145/238218.238290(61-68)Online publication date: 6-Jan-1997
https://dl.acm.org/doi/10.1145/238218.238290
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Recommendations

On the interaction of syntax and semantics in a syntactically guided caseframe parser

Bottom-up context-sensitive algorithms for Bengali parser in natural language processing

Syntax-Based Post-Ordering for Efficient Japanese-to-English Translation

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations