Análisis sintáctico de sentencias incompletas

Abstract

Describimos un algoritmo de análisis sintáctico para gramáticas independientes del contexto (GICs), capaz de procesar entradas incompletas, incluyendo secuencias desconocidas de longitud igualmente desconocida. El analizador descrito genera como salida un bosque compartido finito que compila todos los análisis posibles de la entrada, a menudo infinitos en número. En contraste con trabajos anteriores, nuestra propuesta hace uso de técnicas avanzadas de programación dinámica que se traducen en una notable mejora del rendimiento computacional del sistema. Introducimos una construcción deductiva basada en el formalismo conocido como parsing schemata, lo que nos permite simplificar considerablemente la fase descriptiva.

We describe a context-free parsing algorithm to deal with ill-formed input, including also unknown parts of unknown length. The parser produces a finite shared-forest compiling all parses, often infinite in number. In contrast to previous works, our proposal derives profite from a finer dynamic programming construction, resulting on an improved computational behavior. We also introduce a deductive construction based on the parsing schemata formalism, which is on the advantage of simplification on the description task.