Diferencias

Muestra las diferencias entre dos versiones de la página.

--- algoritmos-oia:teleng:bnf [2019/11/08 13:07]
santo [Parser recursivo descendente predictivo [EL IMPORTANTE]]
+++ algoritmos-oia:teleng:bnf [2019/11/11 11:53] (actual)
santo [Parser recursivo descendente con backtracking (no predictivo)]
@@ Línea 56: / Línea 56: @@
 La idea es que, de acuerdo a la regla que usemos, consumir el texto de un cierto elemento se descompone en consumir el texto de otros. Por ejemplo para consumir una expresión, si usamos la segunda regla, tendremos que primero consumir un número, luego consumir el símbolo +, y finalmente consumir una expresión.
+La clave es la parte de **predictivo**: En cada paso, hay que saber cuál de las reglas utilizar. Por ejemplo, en la función que se encarga de consumir una expresión, hay que saber si vamos a usar la primera regla o la segunda. Esta predicción la hacemos considerando las propiedades de la gramática que estemos trabajando, mirando el texto que sigue en el string, etc, y variará en cada caso. En los casos más simples, basta mirar el siguiente caracter para predecir qué regla hay que aplicar, pero a veces puede hacer falta mirar más adelante.
+Juntando todas estas ideas, un ejemplo para la gramática de más arriba, que sería un parser básico que solamente dice si el texto está bien (respeta la gramática) o no, sería:
+<code cpp>
+#include <iostream>
+using namespace std;
+string texto = "123+43+23$"; // Es comodo poner un $ especial al final, para evitar chequeos de fuera de rango
+int posicion;
+bool quedaAlgunMas() {
+    for (int i = posicion; i < int(texto.size()); i++)
+        if (texto[i] == '+')
+            return true;
+    return false;
+}
+bool consumir(char c) {
+    if (texto[posicion] != c) return false;
+    posicion++;
+    return true;
+}
+bool noEsDigito(char c) {
+    return c < '0' || c > '9';
+}
+// Declaramos primero todas las funciones de la gramatica:
+// En este caso no hace falta, pero muchas veces si, porque se
+// llaman en ciclo y entonces no hay forma de ordenarlas en el archivo
+// sin declararlas primero.
+bool expresion();
+bool numero();
+bool digito();
+bool expresion() {
+    if (quedaAlgunMas()) { // Prediccion para este caso
+        // Si queda algun mas, aplicamos la regla 2
+        if (!numero()) return false;
+        if (!consumir('+')) return false;
+        return expresion();
+    } else {
+        // Sino, la regla 1
+        return numero();
+    }
+}
+bool numero() {
+    // El primer chequeo en este caso es solamente para evitar evaluar posicion+1 si texto[posicion] == '$'
+    // Por ejemplo eso pasaria al intentar parsear "123+" [incompleto]. Querriamos que ese texto de "false",
+    // no tener un error fuera de rango.
+    // Se podria sacar afuera como su propio chequeo aparte, pero lo dejamos asi para que el parser
+    // quede escrito mas "mecanico", enfatizando que salvo la condicion para la prediccion,
+    // todo el resto del codigo se sigue en forma 100% automatica de la gramatica.
+    if (noEsDigito(texto[posicion]) || noEsDigito(texto[posicion+1])) { // Prediccion para este caso
+        // Regla 1
+        return digito();
+    } else {
+        // Regla 2
+        if (!digito()) return false;
+        return numero();
+    }
+}
+bool digito() {
+    // Estrictamente como esta escrita la gramatica,
+    // tenemos 10 reglas y podriamos verificar una por una
+    // En este caso como siempre es igual, las resumimos en codigo
+    if (noEsDigito(texto[posicion])) return false;
+    posicion++;
+    return true;
+}
+int main() {
+    posicion = 0; // Siempre debe empezar en 0
+    bool parseOk = expresion();
+    if (parseOk && texto[posicion] == '$') // Si no pedimos texto[posicion] == '$', puede haber dado ok un prefijo, pero no se consumio todo.
+        cout << "OK!" << endl;
+    else
+        cout << "ERROR!" << endl;
+}
+</code>
+Ejecutando el ejemplo anterior cambiando el string, se puede ver que indica error exactamente cuando la cadena no respeta las reglas. Por ejemplo para
+  * ''string texto = "$"''
+  * ''string texto = "123+$"''
+  * ''string texto = "123++57$"''
+  * ''string texto = "123+21x3$"''
+Indica error.
+Notar que las llamadas recursivas que se van haciendo copian exactamente el árbol de parsing. Esto es muy útil, en particular si quisiéramos generar el árbol de parsing podríamos hacerlo durante la misma recursión: cada función en lugar de solo un bool, devolvería el subárbol calculado, y entonces como resultado de una función de parsing se retornaría un nodo raíz al cual se adicionan en orden los nodos raíces de los subárboles devueltos por las llamadas hijo.
+Sin embargo, en muchos casos es más cómodo "utilizar" el árbol directamente en la recursión, en lugar de construirlo explícitamente para luego procesarlo. Por ejemplo, en este ejemplo, podríamos ir calculando el resultado de la cuenta, y obtener un programa que hace la cuenta. Para esto hay que saber qué retornar en cada caso, a partir de lo que retornan los hijos. En nuestro ejemplo:
+  * Para una expresión, podríamos retornar la suma de lo que devuelvan los hijos (o directamente lo que devuelve el único hijo, si se usa la regla 1)
+  * Para un número, podemos calcular el resultado de agregar un dígito a la izquierda, y aplicar eso a los hijos que tenemos.
+  * Para el caso de un dígito, se puede pasar directamente el char a entero.
+El código que calcularía esto es:
+<code cpp>
+#include <iostream>
+using namespace std;
+string texto = "123+43+2$"; // Es comodo poner un $ especial al final, para evitar chequeos de fuera de rango
+int posicion;
+bool quedaAlgunMas() {
+    for (int i = posicion; i < int(texto.size()); i++)
+        if (texto[i] == '+')
+            return true;
+    return false;
+}
+void consumir(char c) {
+    if (texto[posicion] != c) throw "ERROR";
+    posicion++;
+}
+bool noEsDigito(char c) {
+    return c < '0' || c > '9';
+}
+// Declaramos primero todas las funciones de la gramatica:
+// En este caso no hace falta, pero muchas veces si, porque se
+// llaman en ciclo y entonces no hay forma de ordenarlas en el archivo
+// sin declararlas primero.
+int expresion();
+string numero(); // Usamos string para los numeros en este caso, que es mas ineficiente, porque es dificil agregar por izquierda.
+                 // Agregar por derecha es simplemente "10*num + d".
+                 // Eso indica que en este problema particular,
+                 // hubiera sido mejor cambiar la gramatica para que la regla sea "<num> <digito>" en lugar de "<digito> <num>"
+char digito();
+int expresion() {
+    if (quedaAlgunMas()) { // Prediccion para este caso
+        // Si queda algun mas, aplicamos la regla 2
+        string num = numero();
+        consumir('+');
+        int e = expresion();
+        return stoi(num) + e;
+    } else {
+        // Sino, la regla 1
+        return stoi(numero());
+    }
+}
+string numero() {
+    // El primer chequeo en este caso es solamente para evitar evaluar posicion+1 si texto[posicion] == '$'
+    // Por ejemplo eso pasaria al intentar parsear "123+" [incompleto]. Querriamos que ese texto de "false",
+    // no tener un error fuera de rango.
+    // Se podria sacar afuera como su propio chequeo aparte, pero lo dejamos asi para que el parser
+    // quede escrito mas "mecanico", enfatizando que salvo la condicion para la prediccion,
+    // todo el resto del codigo se sigue en forma 100% automatica de la gramatica.
+    if (noEsDigito(texto[posicion]) || noEsDigito(texto[posicion+1])) { // Prediccion para este caso
+        // Regla 1
+        return string(1,digito());
+    } else {
+        // Regla 2
+        char d = digito();
+        string num = numero();
+        return d + num;
+    }
+}
+char digito() {
+    // Estrictamente como esta escrita la gramatica,
+    // tenemos 10 reglas y podriamos verificar una por una
+    // En este caso como siempre es igual, las resumimos en codigo
+    if (noEsDigito(texto[posicion])) throw "ERROR";
+    char d = texto[posicion];
+    posicion++;
+    return d;
+}
+int main() {
+    try {
+        posicion = 0; // Siempre debe empezar en 0
+        int result = expresion();
+        if (texto[posicion] != '$') // Si no pedimos texto[posicion] == '$', puede haber dado ok un prefijo, pero no se consumio todo.
+            throw "ERROR";
+        cout << "OK! Resultado : " << result << endl;
+    } catch (...) {
+        cout << "ERROR!" << endl;
+    }
+}
+</code>
+Este ejemplo muestra otra técnica posible para la detección de los errores en parsing: en lugar de retornar un valor especial destacado y tener que chequear error todo el tiempo, como los errores abortan todo el parsing completo, se usa un "throw" que lanza excepción, y todo el código del parser está rodeado de un try catch, de modo que en cuanto salta un error, termina toda la recursión automáticamente y el código pasa al caso error.
+Notar que en algunos casos, el problema nos garantiza que no hay casos de ERROR, y podemos omitir los chequeos de error en el parsing, asumiendo que el parsing sera correcto. Por ejemplo si el problema pidiera implementar una calculadora para expresiones que siguen cierta gramatica, y nos garantizan que el input siempre va a cumplir ese formato.
+La gramática que usamos de ejemplo era muy sencilla, y seguramente se podía haber creado un parser con for directamente leyendo los enteros y sumando, pero la misma técnica general aplica al parsing de cualquier gramática. Por ejemplo, si en nuestra "calculadora" pudiéramos usar * además de +, y hubiera paréntesis y corchetes que por regla debemos verificar que matcheen, con una gramática un poco cambiada podríamos aplicar estas técnicas de la misma manera exacta, mientras que adaptar la solución adhoc con for se vuelve muy engorroso por comparación.
 Una desventaja del parser recursivo descendente tal cual lo planteamos es que no puede manejar una gramática que tenga ninguna forma de recursión a izquierda (es decir, una regla como X ::= X Y Z, porque para usarla X tendría que llamar a X sin haber consumido nada, así que el programa cuelga). La solución a esto muchas veces es plantear un while para consumir todas esas repeticiones (porque en general esas construcciones en la gramática se usan para indicar "varias copias de ...", y podemos hacerlo con while). Otras veces se puede replantear la gramática para que no tenga recursión a izquierda (por ejemplo, si se puede elegir el orden, utilizar recursión a derecha).
@@ Línea 62: / Línea 265: @@
 Este parser permite trabajar con gramáticas ambiguas, y en ese caso se puede utilizar para encontrar y enumerar todos los árboles de parsing posibles. Pero tiene el gran defecto de tener en la mayoría de los casos una complejidad exponencial en la longitud del texto. En competencias de programación, si de verdad necesitamos un parser, virtualmente siempre podremos utilizar un parser predictivo, por lo cual tener que implementar un recursivo descendente para gramáticas en general es algo sumamente inusual.
-NOTA: Este parser no se puede utilizar si la gramática tiene recursión a izquierda, pues en ese caso nunca termina.
+NOTA: A diferencia del parser predictivo, este parser general por backtracking sin predicción no se puede utilizar si la gramática tiene recursión a izquierda, pues en ese caso nunca termina. Un ejemplo de recursión a izquierda sería una regla del estilo <numero> ::= <numero> <digito>, a diferencia de <numero> ::= <digito> <numero> que sería recursión a derecha.
+Por ejemplo, para la gramatica
+<X> ::= a <X> a | a <X> a <X> | b <X> | b
+Que tiene solamente un tipo de elemento X, podríamos generar el siguiente parser recursivo descendente:
+<code cpp>
+#include <iostream>
+#include <string>
+#include <vector>
+using namespace std;
+string texto;
+// Devuelve todos los posibles end, al parsear un X empezando en posicion
+vector<int> X(int posicion) {
+    vector<int> ret;
+    // Regla aXa
+    if (texto[posicion] == 'a') {
+        for (int pos2 : X(posicion+1)) {
+            if (texto[pos2] == 'a')
+                ret.push_back(pos2+1);
+        }
+    }
+    // Regla aXaX
+    if (texto[posicion] == 'a') {
+        for (int pos2 : X(posicion+1)) {
+            if (texto[pos2] == 'a') {
+                for (int pos3 : X(pos2+1))
+                    ret.push_back(pos3);
+            }
+        }
+    }
+    // Regla bX
+    if (texto[posicion] == 'b') {
+        for (int pos2 : X(posicion+1))
+            ret.push_back(pos2);
+    }
+    // Regla b
+    if (texto[posicion] == 'b')
+        ret.push_back(posicion+1);
+    return ret;
+}
+int main() {
+    cin >> texto;
+    bool primero = true;
+    for (int x : X(0)) {
+        if (primero)
+            primero = false;
+        else
+            cout << " ";
+        cout << x;
+    }
+    cout << endl;
+    return 0;
+}
+</code>
+Lo anterior permite contar cuantos arboles de parsing hay, pues X(0).size() sera exactamente eso: el vector resultado devuelve exactamente un valor por cada arbol de parsing posible, y el valor indica en donde termina el parsing (lo que sirve dentro de propio algoritmo para saber desde donde se debe intentar seguir parseando).
+De este modo, al ejecutar con aabbaba devuelve un arreglo {7}, que indica que hay un unico arbol de parsing que termina en 7. Como la cadena mide exactamente 7, significa que en este caso hay una unica forma posible de parsear el string completo. Si en cambio lo ejecutamos con aabbababbbbbbb obtenemos {7,14,13,12,11,10,9,8}, que indica todos los tamaños de prefijos que es posible parsear de acuerdo a la gramatica. Finalmente, para abababab responde {7,3,8,7,8,4}. Como el 8 aparace exactamente dos veces, hay exactamente dos árboles de parsing posibles para esta cadena de acuerdo a la gramática de arriba (pues el algoritmo explora todos los posibles exhaustivamente, probando en cada situación todas las posibles reglas que se podrían usar).
+Notar que la ventaja de este método es que no hubo que pensar ningún tipo de predicción: copiamos las reglas de la gramática mecánicamente, y el algoritmo va probando todas exhaustivamente mediante backtracking, devolviendo todas las posibilidades siempre.
-PENDING: Explicar el parser. FIXME
+====== Algoritmos polinomiales ======
 Como comentario final, existen algoritmos polinomiales que permiten parsear cualquier gramática BNF, como son el algoritmo de Earley y el CYK (de Cocke-Younger-Kasami). Si bien el planteo es diferente, en el fondo son algoritmos de [[:algoritmos-oia:programacion-dinamica|programación dinámica]] que plantean estados muy similares a los del backtracking del parser recursivo descendente que vimos, pero al utilizar memoización, se evita recalcular un mismo estado muchas veces.

OIA-Wiki

Herramientas de usuario

Herramientas del sitio

Diferencias

Herramientas de la página