Hace unos años, alguien me preguntó si tenía sentido convertir Python en un analizador PEG (o en una gramática PEG; no recuerdo exactamente quién y cuándo fue). Luego lo miré un poco, pero no llegué a ninguna conclusión y, por lo tanto, dejé este tema. Recientemente aprendí más sobre PEG (Parsing Expression Grammars, Parsing Expression Grammar), y ahora creo que esta es una alternativa interesante al generador de analizador autoescrito que se desarrolló hace 30 años cuando recién comenzaba a trabajar en Python. Lo llamé "pgen", y este fue probablemente el primer código que escribí para Python.
Contenido de la serie Python PEG Parser La razón por la que actualmente estoy interesado en el analizador PEG es porque estoy un poco molesto por las limitaciones de pgen. Se basa en su propia implementación de LL (1), que tiene una serie de supuestos. Por ejemplo, no me gustaban las reglas gramaticales que podían generar líneas vacías, así que las prohibí. Y de este modo simplificó el algoritmo para crear tablas de análisis. También inventé mi propia notación gramatical tipo EBNF, que todavía me gusta mucho.
Aquí hay algunos problemas con pgen que me molestan. El "1" en el nombre LL (1) implica que solo analiza el siguiente token, y esto limita nuestra capacidad de crear buenas reglas gramaticales. Por ejemplo, una declaración de Python puede ser una expresión o una asignación (u otra cosa, pero todas comienzan con una palabra clave resaltada, como if o def ). Me gustaría describir la sintaxis usando la notación pgen. Tenga en cuenta que este es solo un ejemplo simplificado, que es un subconjunto de Python, como generalmente se hace al describir el diseño del lenguaje. Esta será una gramática de juguete que será útil para futuras demostraciones.
statement: assignment | expr | if_statement expr: expr '+' term | expr '-' term | term term: term '*' atom | term '/' atom | atom atom: NAME | NUMBER | '(' expr ')' assignment: target '=' expr target: NAME if_statement: 'if' expr ':' statement
Algunas palabras sobre notación: NAME y NUMBER son tokens y están predefinidos fuera de la gramática. Las cadenas entre comillas de tipo '+' o 'if' también son tokens. (Pospongamos hablar de ellos la próxima vez) Las reglas gramaticales comienzan con el nombre de la regla, seguido de : y luego una o más alternativas, separadas por | .
El problema es que si describe la gramática de esta manera, entonces pgen no funcionará. Esto se debe al hecho de que algunas reglas ( expr y term ) se dejan recursivas, y él no es lo suficientemente inteligente como para manejar correctamente tales situaciones. Por lo general, esto se resuelve reescribiendo solo estas reglas, dejando las otras reglas sin cambios. Por ejemplo:
expr: term ('+' term | '-' term)* term: atom ('*' atom | '/' atom)*
Esto revela varias posibilidades de EBNF en pgen: puede anidar alternativas entre paréntesis y crear repeticiones colocando * después del elemento. Entonces, la regla para la expresión expr aquí significa "es un término seguido de cero o más repeticiones de la secuencia <término más o menos, seguido de término>". Esta gramática toma el mismo lenguaje que la primera versión, pero nuevamente no refleja la intención de diseño del lenguaje. En particular, no muestra que los operadores estén vinculados a la izquierda, y esto es importante cuando intenta generar código.
Pero hay otro problema molesto en este ejemplo (y también en Python). Debido al análisis de un solo token, el analizador no puede determinar lo que está mirando: el comienzo de una expresión o asignación. Al comienzo del procesamiento del operador, el analizador debe decidir solo el primer token, qué alternativa analiza. (¿Por qué? Así es como funciona la implementación del análisis en pgen) Digamos que nuestro programa es el siguiente:
answer = 42
Este programa está representado por tres tokens: NAME (con valor de answer ), = y NUMBER (con valor 42 ). Lo único que sabemos al comienzo del análisis es el primer token NAME . La regla que estamos tratando de analizar en esta etapa es la statement (el carácter inicial de la gramática). Se definen tres alternativas para ello: expr , assignment y if_statement . Podemos excluir inmediatamente if_statement , porque el token anterior no es if . Pero tanto expr como la assignment pueden comenzar con el token NAME , y debido a esto, pgen rechaza nuestra gramática como ambigua.
Esto no es del todo correcto, ya que técnicamente la gramática en sí no lo es; No puedo encontrar una formulación más precisa, así que detengámonos en esta. ¿Y cómo pgen resuelve esto? Calcula algo llamado PRIMER conjunto para cada regla gramatical, y si se cruzan, arroja una excepción.
Entonces, ¿no podemos resolver este problema proporcionando al analizador un búfer de visualización más grande? Para nuestro ejemplo, un segundo token de vista previa es suficiente, ya que en esta gramática el segundo token de asignación debería ser = . Pero en un lenguaje más realista como Python, es posible que necesite un búfer ilimitado, ya que el contenido a la izquierda de = token = puede ser arbitrariamente complejo, por ejemplo:
table[index + 1].name.first = 'Steven'
En este caso, tendrá que analizar diez fichas antes de que nos encontremos con = . Pero te aseguro que puede haber expresiones más largas. Para resolver este problema en pgen, cambiamos el analizador de gramática para aceptar algunas expresiones incorrectas, agregando una verificación adicional en un pase posterior. Lanzará un error SyntaxError si no puede coincidir con los lados izquierdo y derecho. Para nuestro lenguaje de juguetes, todo se reduce a escribir lo siguiente:
statement: assignment_or_expr | if_statement assignment_or_expr: expr ['=' expr]
Los corchetes indican una parte opcional. Y luego, en el próximo paso del compilador (digamos, generación de código de bytes), verificamos si hay = o no, y si es así, verificamos que el lado izquierdo coincida con la sintaxis de target .
Hay un problema similar para los argumentos de llamada de función. Nos gustaría escribir algo como esto (nuevamente, en una versión simplificada de la sintaxis de Python):
call: atom '(' arguments ')' arguments: arg (',' arg) * arg: posarg | kwarg posarg: expr kwarg: NAME '=' expr
Pero un algoritmo de análisis que tenga en cuenta solo el siguiente token no puede decirle al analizador si NAME al comienzo de los argumentos es el comienzo de posarg (ya que expr puede comenzar con NAME ) o el comienzo de kwarg . Nuevamente, el analizador actual de Python resuelve este problema determinando:
arg: expr ['=' expr]
y luego completa la alternativa en un paso posterior del compilador. (Incluso cometimos un pequeño error y analizamos foo((a) = 1) misma manera que foo(a = 1) . Esto se solucionó solo en Python 3.8)
Entonces, ¿cómo resuelve estos problemas un analizador PEG? ¡Usando un buffer de respaldo infinito! Su implementación típica utiliza el llamado analizador de paquete, que no solo carga todo el programa en la memoria antes de analizarlo, sino que también permite que el analizador vuelva a un número arbitrario de tokens. Aunque el término PEG se refiere principalmente a la notación gramatical, los analizadores generados a partir de gramáticas de PEG son típicamente analizadores con descenso recursivo y retorno ilimitado. El analizador Packrat hace que el ego sea eficiente al recordar las reglas que ya se han analizado para posiciones específicas.
Esto simplifica el algoritmo, pero por supuesto hay un precio: la memoria. Hace treinta años, tenía una buena razón para usar LL (1): la memoria era cara. Él (como otras tecnologías como LALR (1), que se hizo famoso por YACC) usa una máquina de estado y una pila para construir eficientemente un árbol de análisis.
Afortunadamente, las computadoras que ejecutan CPython tienen mucha más memoria que hace 30 años, y almacenar todo el archivo en la memoria ya no es un problema. Por ejemplo, el archivo sin prueba más grande en stdlib que pude encontrar es _pydecimal.py , que toma alrededor de 223kb. En el mundo de gigabytes, esto no es esencialmente nada, lo que me hizo echar un vistazo diferente a los analizadores.
Pero hay una cosa más en el actual analizador de CPython que me molesta. Los compiladores son cosas complejas, y la implementación de CPython no es una excepción. Aunque el resultado del analizador pgen es un árbol de análisis, no se usa directamente como entrada para el generador de código de bytes: primero se convierte en un árbol de sintaxis abstracta (AST), y solo entonces este AST se compila en código de bytes. (De hecho, es aún más complicado allí, pero por ahora no entraremos en detalles)
¿Por qué no compilar inmediatamente desde un árbol de análisis? Así fue exactamente, pero hace unos 15 años descubrimos que el compilador era demasiado complicado. Entonces aislamos AST y la fase de transformación de AST del árbol de análisis por separado. A medida que Python evolucionó, AST se mantuvo más estable que el análisis, lo que redujo la probabilidad de errores en el compilador.
AST también es más fácil de trabajar con bibliotecas de terceros que desean probar el código Python. Se puede obtener utilizando el popular módulo ast . También le permite crear nodos desde cero y modificar los existentes, así como compilar partes en código de bytes. Este último permitió la creación de toda una industria de extensiones de lenguaje para Python. (El árbol de análisis también es accesible para los usuarios de Python a través del módulo de análisis, pero trabajar con él es mucho más difícil; por lo tanto, no es tan popular)
Ahora quiero combinar estas cosas y ver si podemos crear un nuevo analizador para CPython, que usa PEG y packrat para crear el AST directamente durante el análisis. Por lo tanto, será posible omitir la generación del árbol intermedio de análisis, lo que puede ahorrarnos memoria, incluso a pesar del uso de un búfer infinito para los tokens. Todavía estoy en proceso de implementación, pero ya tengo un prototipo que puede compilar un subconjunto de Python en AST aproximadamente a la misma velocidad que el analizador CPython actual. Sin embargo, usa más memoria y me parece que expandir el subconjunto al lenguaje completo ralentizará el analizador PEG. Pero hasta ahora no he pensado en ninguna optimización, por lo que continuaré trabajando.
La última ventaja de cambiar a PEG es que proporciona más flexibilidad para una mayor evolución del lenguaje. En el pasado, se decía que las restricciones LL (1) en pgen mantenían la gramática de Python simple. Este puede muy bien ser el caso, pero tenemos muchos otros procesos para evitar el crecimiento descontrolado del lenguaje (principalmente el proceso PEP, que es ayudado por requisitos muy estrictos de compatibilidad con versiones anteriores y una nueva estructura de gestión). Así que no estoy preocupado por eso.
Me gustaría contar mucho más sobre PEG y mi implementación, pero será en las próximas publicaciones después de que limpie el código.
Licencia para este artículo y código citado: CC BY-NC-SA 4.0