Mencioné la recursividad izquierda como un obstáculo varias veces, y es hora de resolverlo. El principal problema es que un analizador con un descenso recursivo a la izquierda se bloquea instantáneamente debido a un desbordamiento de la pila.
Contenido de la serie Python PEG Parser Considere esta regla gramatical hipotética:
expr: expr '+' term | term
Si implementamos esta gramática en el método del analizador recursivo a la izquierda, obtendríamos algo como lo siguiente:
def expr(): if expr() and expect('+') and term(): return True if term(): return True return False
Por lo tanto, expr() comienza con una llamada a expr() , que comienza con una llamada a expr() , que comienza con una llamada ... Esto solo puede terminar con un desbordamiento de la pila, expresado como una excepción RecursionError .
La solución tradicional es reescribir la gramática. En las partes anteriores, hice exactamente eso. De hecho, la regla gramatical anterior puede reescribirse de la siguiente manera:
expr: term '+' expr | term
Sin embargo, en el paso de construir el árbol de análisis, su forma sería diferente. Esto podría arruinar la situación si agregamos el operador '-' a la gramática (ya que a - (b - c) no a - (b - c) lo mismo que (a - b) - c ). Esto generalmente se resuelve con funciones PEG más potentes, como la agrupación y la iteración, y podríamos reescribir la regla anterior como:
expr: term ('+' term)*
En realidad, así es como se escribe la gramática actual de Python para el analizador pgen (que tiene los mismos problemas con las reglas recursivas izquierdas).
Sin embargo, hay un pequeño problema: dado que los operadores como '+' y '-' (en Python) son en su mayoría binarios, cuando analizamos algo como a + b + c , tenemos que pasar por el resultado del análisis (que esencialmente una lista de ['a', '+', 'b', '+', 'c'] ) para crear un árbol de análisis recursivo a la izquierda (que se vería más o menos así [['a', '+', 'b'] , '+', 'c'] ).
La gramática recursiva izquierda original ya insinúa la asociatividad deseada, por lo que sería bueno generar un analizador directamente desde este formulario. Y podemos! Un lector señaló un buen truco con pruebas matemáticas que fue fácil de implementar. Ahora intentaré explicarlo.
Veamos un ejemplo de input foo + bar + baz . El árbol de análisis que nos gustaría obtener de este corresponde a (foo + bar) + baz . Esto requiere tres llamadas recursivas a la izquierda a la función expr() : una corresponde al operador de nivel superior '+' (es decir, la segunda); uno más - al operador interno '+' (es decir, el primero); y la tercera es la elección de la segunda alternativa (es decir, term ).
Como no soy bueno dibujando diagramas reales usando herramientas especiales, lo mostraré aquí usando el arte ASCII:
expr------------+------+ | \ \ expr--+------+ '+' term | \ \ | expr '+' term | | | | term | | | | | 'foo' 'bar' 'baz'
La idea es que en la función expr() , necesitamos un "oráculo" que nos diga si elegir la primera alternativa (es decir, la llamada recursiva a expr() ) o la segunda (es decir, el term() llamada). En la primera llamada a expr() oráculo debe decirnos que sigamos la primera alternativa ( expr() ); en la segunda llamada (recursiva), de manera similar, pero en la tercera debería hacernos llamar a term() . En el código, se verá así:
def expr(): if oracle() and expr() and expect('+') and term(): return True if term(): return True return False
¿Cómo escribir tal oráculo? Veamos ... Podríamos intentar rastrear el número de llamadas expr() recursivas a la izquierda en la pila de llamadas y compararlo con el número de operadores '+' en la siguiente expresión. Si la pila de llamadas es más profunda que el número de declaraciones, el oráculo debería devolver falso (nos obliga a seleccionar el term() ). No puedo esperar para implementar esto con sys._getframe() , pero hay una mejor manera: ¡volteemos la pila de llamadas!
La idea es que comencemos con una llamada donde el oráculo devuelva falso y guardemos el resultado. Esto nos da la secuencia expr() -> term() -> 'foo' . (Debería devolver un árbol de análisis para el term inicial, es decir, 'foo' . El código anterior solo devuelve True , pero en la segunda parte de la serie de artículos ya mostré cómo devolver el árbol de análisis.) Tal oráculo es fácil de implementar, ya que debería simplemente devuelva False en la primera llamada: no se requiere la comprobación de la pila ni la mirada hacia el futuro.
Luego llamamos nuevamente a expr() , y esta vez el oráculo devuelve True , pero en lugar de la llamada recursiva izquierda a expr() , sustituimos el resultado guardado de la llamada anterior. Y dado que el operador esperado '+' y el siguiente token adecuado también están presentes, esto nos dará un árbol de análisis para foo + bar .
Una vez más, repetimos el algoritmo, y nuevamente todo resulta: esta vez obtenemos un árbol de análisis para la expresión completa, y es realmente recursivo a la izquierda ( (foo + bar) + baz ).
Luego repetimos el algoritmo nuevamente. Pero esta vez, aunque Oracle devuelve True , y el resultado guardado de la llamada anterior también está disponible, no hay más operador '+' , y la primera alternativa falla. Por lo tanto, probamos la segunda opción, que tiene éxito, y encuentra solo el término inicial ( 'foo' ). Este resultado es peor que el obtenido de la primera alternativa, por lo que en esta etapa nos detenemos y guardamos el análisis más largo (es decir (foo + bar) + baz ).
Para convertir esto en código de trabajo, primero modifiqué un poco el algoritmo para combinar la llamada oracle() con la llamada recursiva izquierda a expr() . Llamémoslo oracle_expr() . Código:
def expr(): if oracle_expr() and expect('+') and term(): return True if term(): return True return False
A continuación, escribiremos un contenedor que implemente la lógica descrita anteriormente. Utiliza una variable global (no se preocupe, la eliminaré más adelante). La función oracle_expr() leerá la variable global y el contenedor lo controlará:
saved_result = None def oracle_expr(): if saved_result is None: return False return saved_result def expr_wrapper(): global saved_result saved_result = None parsed_length = 0 while True: new_result = expr() if not new_result: break new_parsed_length = <calculate size of new_result> if new_parsed_length <= parsed_length: break saved_result = new_result parsed_length = new_parsed_length return saved_result
El código, por supuesto, es terrible, pero al menos transmite la esencia del algoritmo. Vamos a refactorizarlo para que podamos estar orgullosos de ello.
El entendimiento más importante (que me pertenece, aunque probablemente no sea el primero en notar esto) es que podemos usar el caché de memorización en lugar de una variable global. En él almacenaremos el resultado de llamada a llamada. Entonces nos deshacemos de una función separada oracle_expr() , porque podemos generar una llamada estándar a expr() independientemente de si está en una posición recursiva a la izquierda o a la derecha.
Por lo tanto, necesitamos un decorador @memoize_left_rec separado, que se usa solo para las reglas recursivas de la izquierda. Llama a la función oracle_expr() , extrae el valor almacenado de la memoria caché de memorización y contiene un bucle que llama a la función expr() varias veces, hasta que cada nuevo resultado sea comparable con una porción cada vez más larga de los datos de entrada que el anterior. Y, por supuesto, dado que cada posición de entrada y cada método de análisis se almacena en caché por separado, no le preocupa el retroceso o algunas reglas recursivas (por ejemplo, en la gramática del juguete que utilicé, tanto expr como term se dejan recursivos).
Otra de las ventajas del prototipo que creé en la tercera parte es que facilita verificar si el nuevo resultado es más largo que el anterior: el método mark() devuelve el índice en la matriz de tokens de entrada, por lo que podemos usarlo en lugar de parsed_length .
Omito la prueba de por qué este algoritmo siempre funciona, no importa cuán loca sea la gramática. De hecho, ni siquiera lo leí. Veo que esto funciona para casos simples, como expr en la gramática de mi juguete, así como para casos algo más complejos (por ejemplo, usando la recursión izquierda oculta detrás de elementos opcionales en una alternativa, o usando la recursión mutua entre varias reglas). La situación más difícil que puedo recordar en la gramática de Python todavía está resuelta por este algoritmo, por lo que confío en el teorema y en las personas que lo probaron.
Escribamos el código de batalla.
Primero, el generador de analizadores debe determinar qué reglas se dejan recursivas. Este es un problema resuelto en la teoría de grafos. No voy a mostrar el algoritmo aquí, y de hecho incluso quiero simplificarlo aún más. Supongo que las únicas reglas recursivas a la izquierda en la gramática son directamente recursivas a la izquierda, como expr en nuestra gramática de juguetes. Luego, para verificar la recursividad izquierda, solo debe buscar una alternativa que comience con el nombre de la regla actual:
def is_left_recursive(rule): for alt in rule.alts: if alt[0] == rule.name: return True return False
Ahora cambiaremos el generador de analizador para que, para las reglas recursivas a la izquierda, genere otro decorador. Recuerde que en la tercera parte, @memoize todos los métodos del analizador en @memoize . Ahora haremos un pequeño cambio en el generador, de modo que para las reglas recursivas a la izquierda usemos @memoize_left_rec , y luego implementemos la magia en el decorador memoize_left_rec . ¡No es necesario cambiar el resto del generador y otro código! (Aunque tuve que jugar con el código de visualización)
Como referencia, aquí está el decorador @memoize original @memoize , copiado de la parte 3. Recuerde que self es una instancia de Parser que tiene un atributo memo (inicializado con un diccionario vacío) y los métodos mark() y reset() que obtienen y establecen la posición actual tokenizer:
def memoize(func): def memoize_wrapper(self, *args): pos = self.mark() memo = self.memos.get(pos) if memo is None: memo = self.memos[pos] = {} key = (func, args) if key in memo: res, endpos = memo[key] self.reset(endpos) else: res = func(self, *args) endpos = self.mark() memo[key] = res, endpos return res return memoize_wrapper
El decorador @memoize recuerda las llamadas anteriores para cada posición en la secuencia de entrada: para cada posición en la matriz (perezosa) de tokens de entrada hay un diccionario de memo separado. Las primeras cuatro líneas de memoize_wrapper dedicadas a obtener el diccionario de memo correcto.
Y aquí está @memoize_left_rec . Solo la rama else es ligeramente diferente de la implementación en @memoize anterior:
def memoize_left_rec(func): def memoize_left_rec_wrapper(self, *args): pos = self.mark() memo = self.memos.get(pos) if memo is None: memo = self.memos[pos] = {} key = (func, args) if key in memo: res, endpos = memo[key] self.reset(endpos) else:
Probablemente sea interesante cómo funciona esto para el método expr() . Veamos cómo se ejecutará el siguiente código:
@memoize_left_rec def expr(self): pos = self.mark() if ((expr := self.expr()) and self.expect('+') and (term := self.term())): return Node('expr', [expr, term]) self.reset(pos) if term := self.term(): return Node('term', [term]) self.reset(pos) return None
En el ejemplo de análisis foo + bar + baz .
Cada vez que llama a la función expr() , la llamada es "enganchada" por el decorador que está buscando la llamada anterior en la posición actual. En la primera llamada, llegamos a la rama else , donde repetidamente llamamos a la función decorada expr() . Obviamente, primero llegaremos al decorador primero, pero esta vez ya hay algún valor en el caché, por lo que la recursión se interrumpe.
¿Qué pasa después? El valor de caché inicial se calcula en esta línea:
Esto lleva al hecho de que expr() decorado devuelve None , después de lo cual cae el primer if en expr() (cuando expr: = self.expr() ). Es decir, pasamos al segundo if , que reconoce con éxito el term (en nuestro ejemplo, 'foo' ) y expr devuelve una instancia de Node . ¿De dónde volvemos? Al while en el decorador. Actualizamos el caché de la memoria con un nuevo resultado (esa instancia de Node ) y luego ejecutamos la siguiente iteración.
Se vuelve a llamar a expr() , y esta vez la llamada recursiva interceptada devuelve una instancia en caché de Node (término), y luego continúa con la llamada a expect('+') . Todo está en orden, ya que ahora estamos en el primer operador '+' . Después de eso, buscamos un término que también tenga éxito (se encuentra 'bar' ).
Entonces, ahora expr() , después de haber reconocido foo + bar , regresa al while , que realiza las mismas acciones: actualiza la memoria caché con un nuevo resultado (más largo) e inicia la siguiente iteración.
Este juego se repite nuevamente. Nuevamente, la llamada recursiva interceptada expr() recupera un nuevo resultado (esta vez foo + bar ) del caché, y esperamos ver otro '+' (segundo) y otro term ( 'baz' ). Creamos un Node representa (foo + bar) + baz , y lo devolvemos al while , que lo coloca en el caché y se repite nuevamente.
Pero ahora iremos a lo largo de otra rama del algoritmo. Esperamos encontrar otro '+' , ¡pero no lo encontramos! Por lo tanto, esta llamada a expr() regresa a su segunda alternativa y solo devuelve el term . Cuando esto aparece antes del while , resulta que este resultado es más corto que el anterior. Por lo tanto, interrumpe y devuelve un resultado más largo ( (foo + bar) + baz ) al que inició la llamada expr() (por ejemplo, la llamada a la statement() no se muestra aquí).
Entonces, aquí es donde termina la historia de hoy: implementamos con éxito la recursividad izquierda en un analizador PEG. La próxima semana planeo discutir la adición de "acciones" a la gramática, lo que nos permitirá personalizar el resultado devuelto por el método del analizador para esta alternativa (en lugar de devolver siempre una instancia de Node ).
Si quieres jugar con el código, mira el repositorio de GitHub . (También agregué un código de visualización para la recursión izquierda, pero no estoy muy contento con él, por lo que no proporcionaré un enlace aquí).
Licencia para este artículo y código citado: CC BY-NC-SA 4.0