| KADLEC, Vladimír and Pavel SMRŽ. How Many Dots Are Really Needed for Head-Driven Chart Parsing? Lecture Notes in Artificial Intelligence. Berlin: Springer, 2006, 3831/2006, No 1, p. 483-492, 9 pp. ISSN 0302-9743. |
Other formats:
BibTeX
LaTeX
RIS
@article{599446,
author = {Kadlec, Vladimír and Smrž, Pavel},
article_location = {Berlin},
article_number = {1},
keywords = {nlp; CFG; parsing},
language = {eng},
issn = {0302-9743},
journal = {Lecture Notes in Artificial Intelligence},
title = {How Many Dots Are Really Needed for Head-Driven Chart Parsing?},
volume = {3831/2006},
year = {2006}
}
TY - JOUR
ID - 599446
AU - Kadlec, Vladimír - Smrž, Pavel
PY - 2006
TI - How Many Dots Are Really Needed for Head-Driven Chart Parsing?
JF - Lecture Notes in Artificial Intelligence
VL - 3831/2006
IS - 1
SP - 483-492
EP - 483-492
PB - Springer
SN - 03029743
KW - nlp
KW - CFG
KW - parsing
N2 - This paper presents an improved form of head-driven chart parser that is appropriate for large context-free grammars. The basic method --- HDddm (Head-Driven dependent dot move) --- is introduced first. Both variants that improve the basic approach are based on the same idea --- to reduce the number of chart edges by modifying the form of items (dotted rules). The first one ``unifies'' the items that share the analyzed part of the relevant rule (thus, only one dot is needed to mark the position before and after the covered part). The second method applies the inverse strategy, it ``eliminates'' the parts that have not been covered yet (no dot needed). All the discussed alternatives are described in the form of parsing schemata. We also shortly mention a tricky technique (employing a special trie-like data structure developed originally for Scrabble) that enables to minimize the extra information needed in the algorithms. We demonstrate the advantages of the described methods by the significant decreases in the number of edges for charts. The results are given for the standard set of testing grammars (and respective inputs) as well as for a large and highly ambiguous Czech grammar.
ER -
KADLEC, Vladimír and Pavel SMRŽ. How Many Dots Are Really Needed for Head-Driven Chart Parsing? \textit{Lecture Notes in Artificial Intelligence}. Berlin: Springer, 2006, 3831/2006, No~1, p.~483-492, 9 pp. ISSN~0302-9743.
|
