Abstract
Ambiguity packing is a well known technique for enhancing the efficiency of context-free parsers. However, in the case of unification-augmented context-free parsers where parsing is interleaved with feature unification, the propagation of feature structures imposes difficulties on the ability of the parser to effectively perform ambiguity packing. We demonstrate that a clever heuristic for prioritizing the execution order of grammar rules and parsing actions can achieve a high level of ambiguity packing that is provably optimal. We present empirical evaluations of the proposed technique, performed with both a Generalized LR parser and a chart parser, that demonstrate its effectiveness.- Anthology ID:
- 2000.iwpt-1.16
- Volume:
- Proceedings of the Sixth International Workshop on Parsing Technologies
- Month:
- February 23-25
- Year:
- 2000
- Address:
- Trento, Italy
- Editors:
- Alberto Lavelli, John Carroll, Robert C. Berwick, Harry C. Bunt, Bob Carpenter, John Carroll, Ken Church, Mark Johnson, Aravind Joshi, Ronald Kaplan, Martin Kay, Bernard Lang, Alon Lavie, Anton Nijholt, Christer Samuelsson, Mark Steedman, Oliviero Stock, Hozumi Tanaka, Masaru Tomita, Hans Uszkoreit, K. Vijay-Shanker, David Weir, Mats Wiren
- Venue:
- IWPT
- SIG:
- SIGPARSE
- Publisher:
- Association for Computational Linguistics
- Note:
- Pages:
- 147–158
- Language:
- URL:
- https://aclanthology.org/2000.iwpt-1.16
- DOI:
- Bibkey:
- Cite (ACL):
- Alon Lavie and Carolyn Penstein Rosé. 2000. Optimal Ambiguity Packing in Context-free Parsers with Interleaved Unification. In Proceedings of the Sixth International Workshop on Parsing Technologies, pages 147–158, Trento, Italy. Association for Computational Linguistics.
- Cite (Informal):
- Optimal Ambiguity Packing in Context-free Parsers with Interleaved Unification (Lavie & Rosé, IWPT 2000)
- Copy Citation:
- PDF:
- https://aclanthology.org/2000.iwpt-1.16.pdf
Export citation
@inproceedings{lavie-rose-2000-optimal,
title = "Optimal Ambiguity Packing in Context-free Parsers with Interleaved Unification",
author = "Lavie, Alon and
Ros{\'e}, Carolyn Penstein",
editor = "Lavelli, Alberto and
Carroll, John and
Berwick, Robert C. and
Bunt, Harry C. and
Carpenter, Bob and
Carroll, John and
Church, Ken and
Johnson, Mark and
Joshi, Aravind and
Kaplan, Ronald and
Kay, Martin and
Lang, Bernard and
Lavie, Alon and
Nijholt, Anton and
Samuelsson, Christer and
Steedman, Mark and
Stock, Oliviero and
Tanaka, Hozumi and
Tomita, Masaru and
Uszkoreit, Hans and
Vijay-Shanker, K. and
Weir, David and
Wiren, Mats",
booktitle = "Proceedings of the Sixth International Workshop on Parsing Technologies",
month = feb # " 23-25",
year = "2000",
address = "Trento, Italy",
publisher = "Association for Computational Linguistics",
url = "https://aclanthology.org/2000.iwpt-1.16",
pages = "147--158",
abstract = "Ambiguity packing is a well known technique for enhancing the efficiency of context-free parsers. However, in the case of unification-augmented context-free parsers where parsing is interleaved with feature unification, the propagation of feature structures imposes difficulties on the ability of the parser to effectively perform ambiguity packing. We demonstrate that a clever heuristic for prioritizing the execution order of grammar rules and parsing actions can achieve a high level of ambiguity packing that is provably optimal. We present empirical evaluations of the proposed technique, performed with both a Generalized LR parser and a chart parser, that demonstrate its effectiveness.",
}
<?xml version="1.0" encoding="UTF-8"?>
<modsCollection xmlns="http://www.loc.gov/mods/v3">
<mods ID="lavie-rose-2000-optimal">
<titleInfo>
<title>Optimal Ambiguity Packing in Context-free Parsers with Interleaved Unification</title>
</titleInfo>
<name type="personal">
<namePart type="given">Alon</namePart>
<namePart type="family">Lavie</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Carolyn</namePart>
<namePart type="given">Penstein</namePart>
<namePart type="family">Rosé</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<originInfo>
<dateIssued>2000-feb 23-25</dateIssued>
</originInfo>
<typeOfResource>text</typeOfResource>
<relatedItem type="host">
<titleInfo>
<title>Proceedings of the Sixth International Workshop on Parsing Technologies</title>
</titleInfo>
<name type="personal">
<namePart type="given">Alberto</namePart>
<namePart type="family">Lavelli</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">John</namePart>
<namePart type="family">Carroll</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Robert</namePart>
<namePart type="given">C</namePart>
<namePart type="family">Berwick</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Harry</namePart>
<namePart type="given">C</namePart>
<namePart type="family">Bunt</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Bob</namePart>
<namePart type="family">Carpenter</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Ken</namePart>
<namePart type="family">Church</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Mark</namePart>
<namePart type="family">Johnson</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Aravind</namePart>
<namePart type="family">Joshi</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Ronald</namePart>
<namePart type="family">Kaplan</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Martin</namePart>
<namePart type="family">Kay</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Bernard</namePart>
<namePart type="family">Lang</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Alon</namePart>
<namePart type="family">Lavie</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Anton</namePart>
<namePart type="family">Nijholt</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Christer</namePart>
<namePart type="family">Samuelsson</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Mark</namePart>
<namePart type="family">Steedman</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Oliviero</namePart>
<namePart type="family">Stock</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Hozumi</namePart>
<namePart type="family">Tanaka</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Masaru</namePart>
<namePart type="family">Tomita</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Hans</namePart>
<namePart type="family">Uszkoreit</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">K</namePart>
<namePart type="family">Vijay-Shanker</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">David</namePart>
<namePart type="family">Weir</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Mats</namePart>
<namePart type="family">Wiren</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<originInfo>
<publisher>Association for Computational Linguistics</publisher>
<place>
<placeTerm type="text">Trento, Italy</placeTerm>
</place>
</originInfo>
<genre authority="marcgt">conference publication</genre>
</relatedItem>
<abstract>Ambiguity packing is a well known technique for enhancing the efficiency of context-free parsers. However, in the case of unification-augmented context-free parsers where parsing is interleaved with feature unification, the propagation of feature structures imposes difficulties on the ability of the parser to effectively perform ambiguity packing. We demonstrate that a clever heuristic for prioritizing the execution order of grammar rules and parsing actions can achieve a high level of ambiguity packing that is provably optimal. We present empirical evaluations of the proposed technique, performed with both a Generalized LR parser and a chart parser, that demonstrate its effectiveness.</abstract>
<identifier type="citekey">lavie-rose-2000-optimal</identifier>
<location>
<url>https://aclanthology.org/2000.iwpt-1.16</url>
</location>
<part>
<date>2000-feb 23-25</date>
<extent unit="page">
<start>147</start>
<end>158</end>
</extent>
</part>
</mods>
</modsCollection>
%0 Conference Proceedings %T Optimal Ambiguity Packing in Context-free Parsers with Interleaved Unification %A Lavie, Alon %A Rosé, Carolyn Penstein %Y Lavelli, Alberto %Y Carroll, John %Y Berwick, Robert C. %Y Bunt, Harry C. %Y Carpenter, Bob %Y Church, Ken %Y Johnson, Mark %Y Joshi, Aravind %Y Kaplan, Ronald %Y Kay, Martin %Y Lang, Bernard %Y Lavie, Alon %Y Nijholt, Anton %Y Samuelsson, Christer %Y Steedman, Mark %Y Stock, Oliviero %Y Tanaka, Hozumi %Y Tomita, Masaru %Y Uszkoreit, Hans %Y Vijay-Shanker, K. %Y Weir, David %Y Wiren, Mats %S Proceedings of the Sixth International Workshop on Parsing Technologies %D 2000 %8 feb 23 25 %I Association for Computational Linguistics %C Trento, Italy %F lavie-rose-2000-optimal %X Ambiguity packing is a well known technique for enhancing the efficiency of context-free parsers. However, in the case of unification-augmented context-free parsers where parsing is interleaved with feature unification, the propagation of feature structures imposes difficulties on the ability of the parser to effectively perform ambiguity packing. We demonstrate that a clever heuristic for prioritizing the execution order of grammar rules and parsing actions can achieve a high level of ambiguity packing that is provably optimal. We present empirical evaluations of the proposed technique, performed with both a Generalized LR parser and a chart parser, that demonstrate its effectiveness. %U https://aclanthology.org/2000.iwpt-1.16 %P 147-158
Markdown (Informal)
[Optimal Ambiguity Packing in Context-free Parsers with Interleaved Unification](https://aclanthology.org/2000.iwpt-1.16) (Lavie & Rosé, IWPT 2000)
- Optimal Ambiguity Packing in Context-free Parsers with Interleaved Unification (Lavie & Rosé, IWPT 2000)
ACL
- Alon Lavie and Carolyn Penstein Rosé. 2000. Optimal Ambiguity Packing in Context-free Parsers with Interleaved Unification. In Proceedings of the Sixth International Workshop on Parsing Technologies, pages 147–158, Trento, Italy. Association for Computational Linguistics.