Diferencias

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

--- algoritmos-oia:teleng:bnf [2019/11/11 11:34]
santo [Parser recursivo descendente con backtracking (no predictivo)]
+++ algoritmos-oia:teleng:bnf [2019/11/11 11:53] (actual)
santo [Parser recursivo descendente con backtracking (no predictivo)]
@@ Línea 267: / Línea 267: @@
 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.
-PENDING: Explicar el parser. FIXME
+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.
+====== 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