Análisis sintactivo discriminante inverso

  1. Fortes Gálvez, José
Dirigida por:
  1. Oliver Lecarme Director/a

Universidad de defensa: Universidad de Las Palmas de Gran Canaria

Año de defensa: 1999

Tribunal:
  1. Igor Litovsky Presidente/a
  2. Antonio Falcón Martel Secretario/a
  3. Octavio Santana Suárez Vocal
  4. Casiano Rodríguez León Vocal
  5. Lucien Farre Jacques Vocal

Tipo: Tesis

Teseo: 73479 DIALNET

Resumen

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.#