Publication Details

How Many Dots Are Really Needed for Head-Driven Chart Parsing?

SMRŽ Pavel and KADLEC Vladimír. How Many Dots Are Really Needed for Head-Driven Chart Parsing?. In: SOFSEM 2006: Theory and Practice of Computer Science: 32nd Conference on Current Trends in Theory and Practice of Computer Science. Berlin: Springer Verlag, 2006, pp. 483-492. ISBN 3-540-31198-X.
Czech title
How Many Dots Are Really Needed for Head-Driven Chart Parsing?
Type
conference paper
Language
english
Authors
Smrž Pavel, doc. RNDr., Ph.D. (DCGM FIT BUT)
Kadlec Vladimír, Mgr. (FI MUNI)
Keywords

head-driven parsing

Abstract

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 minimizing
the extra information needed in the algorithms.
We demonstrate the advantages of the described methods by the significant
decrease 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.

Published
2006
Pages
483-492
Proceedings
SOFSEM 2006: Theory and Practice of Computer Science: 32nd Conference on Current Trends in Theory and Practice of Computer Science
Conference
32nd Conference on Current Trends in Theory and Practice of Computer Science, Meřín, CZ
ISBN
3-540-31198-X
Publisher
Springer Verlag
Place
Berlin, DE
BibTeX
@INPROCEEDINGS{FITPUB8005,
   author = "Pavel Smr\v{z} and Vladim\'{i}r Kadlec",
   title = "How Many Dots Are Really Needed for Head-Driven Chart Parsing?",
   pages = "483--492",
   booktitle = "SOFSEM 2006: Theory and Practice of Computer Science: 32nd Conference on Current Trends in Theory and Practice of Computer Science",
   year = 2006,
   location = "Berlin, DE",
   publisher = "Springer Verlag",
   ISBN = "3-540-31198-X",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/8005"
}
Back to top