|
An Earley Parsing Algorithm for Range Concatenation Grammars| old_uid | 6288 |
|---|
| title | An Earley Parsing Algorithm for Range Concatenation Grammars |
|---|
| start_date | 2009/02/16 |
|---|
| schedule | 14h-16h |
|---|
| online | no |
|---|
| summary | The work presented in this talk is joint work with Wolfgang Maier (Tuebingen) and Yannick Parmentier (Nancy). We present different parsing algorithms for Range Concatenation Grammars (RCG, Boullier 2000), formulating them within the framework of parsing as deduction.
The goal of this work is twofold: firstly, different parsing
strategies are formulated using deduction rules which allows a better comparison of the algorithms. We cover several top-down and bottom-up strategies, amongst others also the algorithm proposed in Boullier (2000). Secondly, we propose a new Earley parser; the central idea of this new algorithm is to postpone the computation of actual ranges until a clause has been entirely completed. We achieve this by
propagating constraints on range boundaries in the perations of the parser. Comparisons between implementations of the directional top-down parser that computes all possible instantiations when predicting a clause and the Earley parser with constraint propagation show that the latter is faster and, furthermore, generates a considerably lower
number of items. |
|---|
| responsibles | Information non disponible, Crabbé |
|---|
| |
|