Introducción
Una de las asignaturas que más me gustó de la carrera de informática fue la de procesado de lenguajes. Se dividía más o menos en dos partes. La primera se centraba en los distintos algoritmos que hay de reconocimiento de lenguajes y la segunda en la semántica de ese lenguaje.
La primera parte era muy formal. Muchas matemáticas. La clasificación de los lenguajes de Chomsky. Los algoritmos para reconocer los lenguajes de contexto libre deterministas: expresiones regulares, LL(1), LL(k), LR(1), SLR, LALR, etc. La mayoría de estos algoritmos son complejos. Hay que calcular conjuntos, hacer grafos, transformarlos y aplicar métodos más o menos arduos.
Sin embargo, con el tiempo, he descubierto que no me enseñaron nada sobre las PEGs. Quizás únicamente una breve mención a los analizadores descendentes recursivos. Las PEGs son "gramáticas de expresiones reconocedoras" (Parsing Expression Grammars). La idea es muy simple: Probamos una cosa y, si no podemos, probamos con la siguiente.
La gran diferencia
Para reconocer una cadena como "a" en una entrada como "ac" se compara carácter a carácter. El resultado será que hay una parte reconocida "a" y sobra la "c". Una forma de asegurarnos que no sobran caracteres es añadiendo un indicador de fin de entrada. En este caso la cadena a reconocer sería "a#" y la entrada sería "ac#". Obviamente, no reconocería nada. Este truco permite centrarnos en reconocer sólo lo que se pueda reconocer y dejar sobrantes si fuera necesario.
Generalmente queremos reconocer varias cadenas. Aquí es donde las PEGs son distintas. En una gramática de contexto libre (GCL) las opciones no se ordenan. Las distintas opciones se separan con | en las GCL y se lee más o menos como "o". Es decir, "a" | "ab" sería reconoce "a" o reconoce "ab". Si introducimos la cadena "abc" reconocerá "ab" y sobra "c".
Con las PEGs no es así. Hay que reconocer ordenadamente. Las distintas opciones se separan con / en las PEG y se lee más o menos como "y si no, prueba con". Es decir "a" / "ab" sería prueba "a" y si no, prueba con "ab". Si introducimos la cadena "abc" probará primero con "a" y la reconocerá, descartando probar con "ab". Es decir que reconoce "a" y sobra "bc".
Las consecuencias de este cambio son dobles:
- Dependiendo del orden obtenemos gramáticas distintas. Es decir, "a"/"ab" no es lo mismo que "ab"/"a".
- Nunca hay ambigüegades. Esto es debido a que, si hay dos posibilidades, una estará delante de la otra.
Operadores
La restricción del orden puede parecer muy inconveniente, pero realmente no perdemos mucha expresividad respecto a una CFG. Por ejemplo, todos los operadores unarios de las expresiones regulares pueden expresarse con PEGs mediante estas transformaciones.
R = A* ===> R = A R / ε
R = A+ ===> R = A R / A
R = A? ===> R = A / ε
Donde ε es la cadena vacía.
Además, tenemos dos operadores más que surgen de la forma en las que las PEGs se implementan.
Cuando tenemos dos opciones la implementación de la PEG tiene que probar la primera. Si se reconoce, no hay problema. Se consume e ignoramos las otras opciones. Así que para reconocer "a" / "b" en "ac" sería:
"a" / "b" en "ac"
Opción 1:
"a" en "ac". Coinciden las "a". Avanzo.
"" en "c". Nada más que comprobar. Éxito.
Si no se reconoce, hay que volver atrás (backtracking).
"ab" / "ac" en "acd"
Opción 1:
"ab" en "acd". Coinciden las "a". Avanzo.
"b" en "cd". No coinciden. Fallo.
Vuelvo atrás a "acd" y pruebo opción 2:
"ac" en "acd". Coinciden las "a". Avanzo.
"c" en "cd". Coinciden las "c". Avanzo.
"" en "d". Nada más que comprobar. Éxito.
Esta vuelta atrás tiene que usarse si utilizamos las opciones ordenadas /. Ya que la tenemos, podemos utilizarla en otros casos. Por ejemplo. Supongamos que queremos reconocer todas las palabras (no vacías) formadas por "a" y "b" excepto las que empiecen por "baba". Las palabras formadas por "a" y "b" son ("a" / "b")+. ¿Cómo le quitamos ahora "baba"?
La idea es simple. Intentemos reconocer "baba" y, si la encontramos, fallamos. Si no la encontramos, volvemos atrás y seguimos como si nada. Esta operación la notaremos con el operador prefijo ! La gramática sería:
!"baba" ("a" / "b")+
Si introducimos "babab" reconoceremos "baba" y por tanto, fallamos. No reconocemos la gramática. Si introducimos "babb" no reconocemos "baba" aunque habremos consumido "bab". No pasa nada, volvemos atrás a "babb" y seguimos como si nada.
La misma operación se podría realizar fallando si no reconocemos. En este caso se notaría "&". Por ejemplo, reconocer &"bxx" "b" en "bxxba" tiene éxito, pero sobra "xxba". Es una manera de requerir cierto contexto (las "xx" que siguen a la "b") antes de aceptar (sólo la "b").
Implementación
Existe una última característica de las PEG que las hace infinitamente mejores que las CFG: se pueden programar a mano. Nada de Lex/Yacc. Esto se debe a que las PEG son, ni más ni menos, que los reconocedores descendente recursivos.
Por ejemplo. En C++ una regla R = A B sería algo como:
bool R(POSICION& p)
{
return A(p) && B(p);
}
La regla R = A / B es:
bool R(POSICION& p)
{
POSICION q=p; //Prepara el backtracking
return A(p) || B(p=q);
}
Una regla R=A* es
bool R(POSICION& p)
{
POSICION q=p; //Prepara el backtracking
while(A(q)) p=q;
return true;
}
La regla R = &A B es
bool R(POSICION& p)
{
POSICION q=p; //Prepara el backtracking
return A(q) && B(p);
}
Como se ve, las reglas se programan más o menos directamente con un par de variables bien escogidas. En la realidad es algo más complejo porque queremos informar de errores, construir el AST, etc. Pero también es verdad que en la realidad podemos definir clases y abstraernos de más operaciones. El resultado es que la implementación suele ser directa.
El ataque de las ratas
Al leer la palabra "backtracking" deben haberse encendido todas las luces rojas de la complejidad. El backtracking (o vuelta atrás) es de complejidad exponencial. Esto quiere decir que si introduzco una cadena con un carácter más de longitud el resultado puede tardar el doble en calcularse. Esto es inmanejable en la práctica y el efecto es "se ha quedado colgado".
No hay que asustarse. En la realidad las PEGs se pueden calcular en tiempo lineal. Sí, sí. Lineal, O(n) para los amigos de la notación O de Landau. ¿Y cómo es posible esto? Mediante una técnica que se denomina memoización.
La memoización no es más que guardar en una tabla los resultados que ya conocemos de manera que, antes de calcularlos, busco en la tabla. ¿Que ya están? Pues tengo ya lo que buscaba. ¿Que no están? Pues los calculo y los guardo en la tabla para la próxima. El resultado es que sólo tengo que calcular cada regla en cada posición una única vez. Esto es lo que en diseño de algoritmos se denomina programación dinámica.
Como el número de reglas es fijo y las tablas hash son de complejidad amortizada constante el resultado es que la complejidad sólo depende linealmente de la longitud de la entrada. Es decir, O(n). Bien es verdad que también el consumo de espacio va a ser O(n), pero hoy en día la memoria disponible en los PCs normales permite usar las PEGs sobre ficheros de millones de caracteres.
¿Y lo de las ratas? Bueno, a este tipo de reconocedores descendentes recursivos con memoización se los denomina "packrat" que, aunque mis conocimientos de inglés me dicen lo contrario, me suena a "paquete de ratas".
Edit: Ya lo he descubierto. Podemos traducir "packrat" como "atesorador" ya que coincide la idea de memoizar con la definición de "packrat" que he encontrado en Babylon.
0 comentarios:
Publicar un comentario