Análisis sintáctico ascendente con un algoritmo evolutivo

Abstract

Los métodos de análisis sintáctico clásicos buscan las distintas interpretaciones de una sentencia mediante técnicas de búsqueda completas. Pero el tamaño del espacio de búsqueda crece exponencialmente con la longitud de la sentencia y el tamaño de la gramática, de forma que los métodos de búsqueda exhaustivos pueden ser insuficientes. Sin embargo, existen otras técnicas de búsqueda, como los algoritmos evolutivos, que aunque no garantizan encontrar el valor óptimo, permiten ajustar la calidad de las soluciones obtenidas incrementando el número de puntos explorados. Este trabajo presenta un algoritmo evolutivo para realizar el análisis sintáctico con gramáticas probabilísticas. El algoritmo trabaja con análisis parciales, que los operadores genéticos combinan para extender el análisis a segmentos más largos de sentencia. En el articulo se describen los principales elementos del algoritmo, presentando también los resultados obtenidos para un texto extraído del corpus de Susanne.

Classic parsing methods are based on complete search techniques to find the different interpretations of a sentence. However, the size of the search space increases exponentially with the length of the sentence or text to be parsed and the size of the grammar, so that exhaustive search methods can fail to reach a solution in a reasonable time. Nevertheless, large problems can be solved approximately by some kind of stochastic techniques, which do not guarantee the optimum value, but allow adjusting the probability of error by increasing the number of points explored. This paper presents the implementation of a stochastic parser based on a genetic algorithm. This algorithm produces successive generations of individuals, which are partial parses of a sentence. Genetic operators combine individuals to produce longer parses. The model has been implemented, and the results obtained for a number of sentences extracted form the Susanne corpus are presented.