Abstract
Constraint-based grammars based on Head Driven Phrase Structure Grammar employ typed feature structures (TFSs) which are often deeply nested. Unification in Prolog (B. Carpenter, G. Penn, ALE: The Attribute Logic Engine User's Guide, version 2.0, Technical report, Philosophy Department, Carnegie Mellon University, Pittsburgh, PA, 1994) is then too slow for them to be used in real products.
A recent abstract machine (S. Wintner, N. Francez, Efficient compilation of unification-based grammars, in: BCN Summer School 97 on Topics in Constraint-Based Natural Language Processing, Groningen University, 1997, pp. 90-126) translates grammatical descriptions of TFSs into abstract code, with parse times between 3 and 11 times faster, for sentences between 4 and 12 words.
We present a new faster method that allocates atomic composite types to TFSs, precompiles tables that replace unification by matching, and represents semantics in a compact skeletal form. A Prolog prototype already parses faster than the existing abstract machine, and would be even faster in an imperative implementation using arrays. (C) 2000 Published by Elsevier Science B.V. All rights reserved.
| Original language | English |
|---|---|
| Pages (from-to) | 771-791 |
| Number of pages | 21 |
| Journal | Future generation computer systems |
| Volume | 16 |
| Issue number | 7 |
| DOIs | |
| Publication status | Published - May 2000 |
Keywords
- constraints
- types
- feature structures
- HPSG
- ALE