Resumen: Semana del 24 al 31 de abril

(1/8)

(f)lex y los autómatas finitos

• (f)lex es un programa cuya función es generar parsers, es decir, programas de análisis léxico
• Para funcionar, (f)lex hace un uso intensivo de los autómatas finitos

(2/8)

(f)lex y los autómatas finitos no deterministas

• Primero, las reglas de traducción son convertidas en autómatas finitos no deterministas
• Los AFN son computacionalmente más sencillos de crear que los AFD, y pueden convertirse en AFD posteriormente, por lo que se usan como primer paso para traducir las reglas

(3/8)

(f)lex y los autómatas finitos deterministas

• Las reglas de traducción, ya convertidas a un AFN, son posteriormente convertidas en un AFD
• Como se vio antes, los AFD eliminan la ambigüedad de los AFN, lo que permite generar un programa con tiempo de ejecución finito
• Las reglas de conversión de AFN a AFD se vieron en estas lecciones

(4/8)

(f)lex y la compactación de autómatas finitos deterministas

• Ya con un AFD, se puede reducir aun más el tamaño de este mediante algoritmos de minimización
• Minimizar el AFD reduce la redundancia, así como el tamaño del programa resultante
• Al igual que la anterior, las reglas de minimización de AFD se vieron en estas lecciones

(5/8)

El siguiente tema: recursividad

• La recursividad en una gramática consiste en sustituir una regla gramatical, en todo o en parte, por sí misma
• Un ejemplo de recursividad es la gramática para XML vista en estas lecciones
• Si se tiene que A es una regla gramatical, y x un conjunto de terminales y no terminales que no empiezan con A, la recursividad puede ser:
  • Hacia la izquierda, cuando se tiene una forma A → A x
  • Hacia la derecha, cuando se tiene una forma A → x A

(6/8)

Recursividad izquierda (LL): caso inmediato

• La recursividad izquierda se da a menudo en casos inmediatos; es decir, cuando la regla se repite directamente en sí misma
• Para resolver un caso A → A α | β donde α, β son conjuntos de terminales y no terminales que no empiezan con A, se reemplaza por lo siguiente:
  • A → β A'
  • A' → α A' | ε (terminación épsilon)

(7/8)

Recursividad izquierda (LL): caso inmediato generalizado

• Este procedimiento puede generalizarse para una cantidad indeterminada de terminales y no terminales
• Si se tiene una lista de producciones A → A α1 | α2 | (...) | αn | β1 | β2 | (...) | βm, se pueden sustituir por lo siguiente:
  • A → β1 A' | β2 A' | (...) | βm A'
  • A' → α1 A' | α2 A' | (...) | αn A'| ε

(8/8)

Recursividad izquierda (LL): algoritmo general

• El procedimiento anterior no funciona si se tienen recursiones no inmediatas (es decir, es hasta que se hace un número de sustituciones que se nota la recursión inmediata)
• Para eliminar la recursividad en forma generalizada, se tiene un algoritmo que tiene por entrada una gramática sin ciclos ni producciones épsilon, y de ella se obtiene una gramática con la misma función, pero ahora sí sin recursividad por la izquierda (aunque puede haber recursividad por la derecha, y usualmente así es)
• El algoritmo es el siguiente:
  • Ordenar los no terminales de A1 a An
  • De i = 1 a n
    • De j = 1 a 1 - i
      • Cambiar cada Ai → Ajγ por todas las producciones de Aj: Ai → δ1γ | δ2γ | (...) | δkγ
    • Eliminar la recursividad inmediata por la izquierda para todas las producciones Ai, como se vio arriba