Análisis sintactivo discriminante inverso

Abstract

Desde la invención por Donald Knuth del análisis sintáctico LR(k) -el método práctico más potente que permite analizar el texto de entrada conforme va siendo leído-, un gran esfuerzo investigador se ha concentrado en desarrollar técnicas eficientes para abordar el problema del tamaño cuando K 1, que sin embargo no han sido consideradas suficientemente satisfactorias en la práctica, donde está firmemente establecido el más sencillo pero menos potente método LALR(1), Esta tesis afirma que esta situación no es enteramente satisfactoria para la generación de analizadores para lenguajes de programación, y propone un enfoque nuevo discriminante inverso al análisis LR(k) completo, mediante la construcción de un autómata de estados finitos que explore el sufijo mínimo de la pila desde su cima para discriminar cada acción de análisis ascendente, cuya corrección y linealidad de tiempo de análisis se demuestran aquí formalmente. El método ha sido implementadoy evaluado para gramáticas prácticas, resultando en analizadores con potencia LR(1) completa considerablemente menores que los analizadores producidos por generadores basados en LALR(1), tales como yacc, y en un despreciable coste de exploración de la pila. Elloha sido posible porque los analizadores clásicos directos construyen un reconocedor para el lenguaje completo desde la base a la cima de pilas más ventanas de prelectura, mientras que el analizador discriminante inverso utiliza típicamente unos pocos sómbolos de la cima de la pila más la ventana, donde se concentra la mayor parte de la información para el análisis, lo que era evidente para los primeros diseñadores de analizadores de precedencia.#