Abstract
Disambiguation methods for context-free grammars enable concise specification of programming languages by ambiguous grammars. A disambiguation filter is a function that selects a subset from a set of parse trees the possible parse trees for an ambiguous sentence. The framework of filters provides a declarative description of disambiguation methods independent of parsing. Although filters can be implemented straightforwardly as functions that prune the parse forest produced by some generalized parser, this can be too inefficient for practical applications. In this paper the optimization of parsing schemata, a framework for high-level description of parsing algorithms, by disambiguation filters is considered in order to find efficient parsing algorithms for declaratively specified disambiguation methods. As a case study the optimization of the parsing schema of Earley’s parsing algorithm by two filters is investigated. The main result is a technique for generation of efficient LR-like parsers for ambiguous grammars disambiguated by means of priorities.- Anthology ID:
- 1997.iwpt-1.24
- Volume:
- Proceedings of the Fifth International Workshop on Parsing Technologies
- Month:
- September 17-20
- Year:
- 1997
- Address:
- Boston/Cambridge, Massachusetts, USA
- Editors:
- Anton Nijholt, Robert C. Berwick, Harry C. Bunt, Bob Carpenter, Eva Hajicova, Mark Johnson, Aravind Joshi, Ronald Kaplan, Martin Kay, Bernard Lang, Alon Lavie, Makoto Nagao, Mark Steedman, Masaru Tomita, K. Vijay-Shanker, David Weir, Kent Wittenburg, Mats Wiren
- Venue:
- IWPT
- SIG:
- SIGPARSE
- Publisher:
- Association for Computational Linguistics
- Note:
- Pages:
- 210–224
- Language:
- URL:
- https://aclanthology.org/1997.iwpt-1.24
- DOI:
- Cite (ACL):
- Eelco Visser. 1997. A Case Study in Optimizing Parsing Schemata by Disambiguation Filters. In Proceedings of the Fifth International Workshop on Parsing Technologies, pages 210–224, Boston/Cambridge, Massachusetts, USA. Association for Computational Linguistics.
- Cite (Informal):
- A Case Study in Optimizing Parsing Schemata by Disambiguation Filters (Visser, IWPT 1997)
- PDF:
- https://preview.aclanthology.org/revert-3132-ingestion-checklist/1997.iwpt-1.24.pdf