Análisis sintáctico estocástico y paralelismo

Abstract

Los algoritmos de análisis sintáctico tipo CYK presentan una naturaleza intrínsecamente paralela: existen muchas celdas de la tabla de análisis que pueden ser calculadas simultáneamente. En este trabajo se realiza un estudio sobre cual debe ser la técnica de paralelismo adecuada para obtener un rendimiento óptimo del algoritmo CYK extendido, un algoritmo de análisis sintáctico estocástico que mantiene el mismo nivel de expresividad de la gramática original y hace más viables las posteriores tareas de parsing robusto. Se consideran dos métodos de paralelización: memoria distribuida y memoria compartida. Los excelentes resultados obtenidos con el segundo de ellos convierten a este algoritmo en una alternativa que podría competir con otras técnicas de parsing mucho más eficientes a priori.