Esta semana estamos haciendo que el generador de analizadores sea "independiente", es decir, generará su propio analizador.
Contenido de la serie Python PEG Parser Entonces, ya tenemos un generador de analizadores, parte del cual es un analizador de gramática. Podríamos llamarlo un meta-analizador. El meta-analizador funciona de manera similar al generado: GrammarParser hereda de Parser y usa el mismo mecanismo mark() / reset() / hope() . Sin embargo, allí estaba todo escrito a mano. ¿Pero es eso correcto?
Al diseñar un compilador, es habitual que el compilador se escriba en el lenguaje que compila. Recuerdo con amor que el compilador Pascal que utilicé cuando aprendí a programar estaba escrito en Pascal, GCC está escrito en C y el compilador Rust está escrito en Rust.
Como hacerlo Al principio, implemente un compilador para un subconjunto o una versión anterior de un idioma en otro idioma. (¡Permítame recordarle que el compilador Pascal original se escribió en FORTRAN!) Luego, el nuevo compilador se escribe en el idioma de destino y se compila utilizando el compilador bootstrap implementado al principio. Tan pronto como el nuevo compilador comienza a funcionar lo suficientemente bien, el compilador de arranque se elimina y cada versión posterior del lenguaje o compilador se limita a lo que se puede compilar usando la versión anterior del compilador.
Hagámoslo para nuestro meta analizador. Escribiremos una gramática para la gramática (meta-gramática), y luego generaremos un nuevo meta-analizador a partir de esto. Afortunadamente, planeé este movimiento desde el principio, por lo que será bastante simple. Las acciones que agregamos en el episodio anterior son un componente importante porque no necesitamos cambiar el generador, por lo que necesitamos crear una estructura de datos compatible.
Aquí hay una versión simplificada del metagrama sin acciones:
start: rules ENDMARKER rules: rule rules | rule rule: NAME ":" alts NEWLINE alts: alt "|" alts | alt alt: items items: item items | item item: NAME | STRING
Te mostraré cómo agregar acción de abajo hacia arriba. Recuerde de la Parte 3 que hay objetos Rule que tienen el name y los alts . Inicialmente, alts era solo una lista de listas de líneas (una lista externa para alternativas y una lista interna para cada elemento de la alternativa), pero para implementar las acciones, la cambié para que las alternativas fueran representadas por objetos Alt con items y atributos de action . Los elementos todavía se representan como cadenas simples. Por item obtenemos:
item: NAME { name.string } | STRING { string.string }
Esto requiere una pequeña explicación: cuando el analizador procesa el token, devuelve un objeto TokenInfo que tiene type , string y otros atributos. No queremos que el generador TokenInfo objetos TokenInfo , por lo que las acciones aquí extraen la cadena del token. Tenga en cuenta que para todos los tokens en mayúsculas, como NAME , el analizador generado utiliza la versión de cadena (aquí name ) como el nombre de la variable.
A continuación hay items que deberían devolver una lista de cadenas:
items: item items { [item] + items } | item { [item] }
Aquí uso reglas recursivas a la derecha, por lo que no dependemos del procesamiento de la recursividad izquierda, que se agrega en la Parte 5. (¿Por qué no? Siempre es bueno mantener las cosas lo más simple posible, y esta gramática no se beneficiará en gran medida de un cambio en la recursión izquierda). item lista, pero los items recursivamente no lo están, ya que ya es una lista.
Regla alt para crear un objeto Alt :
alt: items { Alt(items) }
Omitiré las acciones para las rules y start , ya que se definen de esta manera.
Sin embargo, hay dos preguntas abiertas. Primero, ¿cómo encuentro la definición de las clases Rule y Alt ? Para hacer esto, necesitamos agregar varias declaraciones de import al código generado. La forma más sencilla sería pasar la bandera al generador, que dice "esto es una metagramática", y dejar que el generador inserte una import adicional al comienzo del programa generado. Pero ahora que tenemos las acciones, muchos otros analizadores también querrán personalizar su importación, entonces, ¿por qué no ver si podemos implementar un enfoque más general?
Hay muchas formas de implementarlo. Un mecanismo simple y general es agregar una sección de "definiciones de variables" en la parte superior de la gramática y permitir que el generador use estas variables para controlar varios aspectos del código generado. Decidí usar el símbolo @ para comenzar a definir la variable, seguido del nombre de la variable ( NAME ) y el valor ( STRING ). Por ejemplo, podemos poner el siguiente bloque de código en la parte superior de la metagramática:
@subheader "from grammar import Rule, Alt"
El generador de analizador imprimirá el valor de la variable del subheader después de la importación estándar, que se agrega de forma predeterminada (por ejemplo, para importar memoize ). Si desea múltiples elementos de import , puede usar una cadena con comillas triples, por ejemplo,
@subheader """ from token import OP from grammar import Rule, Alt """
Esto es fácil de agregar a la meta-gramática: dividiremos la regla de start en lo siguiente:
start: metas rules ENDMARKER | rules ENDMARKER metas: meta metas | meta meta: "@" NAME STRING NEWLINE
(No recuerdo por qué lo llamé "meta", pero elegí este nombre cuando escribí el código, y me atendré a él. :-)
Debemos agregar esto al metaparser bootstrap. Ahora que la gramática no es solo una lista de reglas, agreguemos un objeto de gramática con los atributos de metas y rules . Podemos establecer las siguientes acciones:
start: metas rules ENDMARKER { Grammar(rules, metas) } | rules ENDMARKER { Grammar(rules, []) } metas: meta metas { [meta] + metas } | meta { [meta] } meta: "@" NAME STRING { (name.string, eval(string.string)) }
(Tenga en cuenta que meta devuelve una tupla; y también que usa eval() para procesar comillas).
¡No mencioné la implementación de acciones en las reglas para alt ! La razón es que salen un poco desordenados. Pero no tiene sentido posponer más, así que aquí:
alt: items action { Alt(items, action) } | items { Alt(items, None) } action: "{" stuffs "}" { stuffs } stuffs: stuff stuffs { stuff + " " + stuffs } | stuff { stuff } stuff: "{" stuffs "}" { "{" + stuffs + "}" } | NAME { name.string } | NUMBER { number.string } | STRING { string.string } | OP { None if op.string in ("{", "}") else op.string }
La suciedad en la definición es causada por mi deseo de hacer que el código arbitrario de Python sea válido entre llaves de acción rizadas, incluidas las anidadas en otras llaves. Para este propósito, utilizamos un token OP especial, que nuestro tokenizer genera para todos los signos de puntuación reconocidos por Python (devolviendo un token único con el tipo OP para operadores de varios caracteres, como <= o ** ). Los únicos otros tokens que pueden ocurrir en las expresiones de Python son nombres, números y cadenas. Por lo tanto, el código entre las llaves externas de la acción, al parecer, se puede expresar a través de repeticiones de NAME | NUMBER | STRING | OP NAME | NUMBER | STRING | OP NAME | NUMBER | STRING | OP .
Por desgracia, esto no funcionará porque el OP también coincide con llaves, y dado que el analizador PEG siempre es codicioso, esto capturará el corchete de cierre y nunca veremos el final de la acción. Por lo tanto, agregamos un pequeño ajuste, permitiendo que la acción arroje un error de elección alternativa, devolviendo Ninguno. No sé si esto es una ocurrencia estándar en otros analizadores de PEG. Se me ocurrió esto en el acto cuando tuve que resolver el problema de reconocer el paréntesis de cierre (incluso sin pares anidados). Esto parece funcionar bien, y creo que encaja en la filosofía general del análisis PEG. Esto puede considerarse como una forma especial de previsión (que analizaré a continuación).
Usando este pequeño truco, podemos hacer que la comparación en el OP caiga en una llave rizada. Entonces será posible una comparación de stuff y action .
Con estas cosas, un metaparser de arranque puede analizar un meta-gramática, y el generador puede convertirlo en un nuevo meta-analizador que pueda analizarse a sí mismo. Y, lo que es más importante, el nuevo meta-analizador aún puede analizar la misma meta-gramática. Si compilamos la meta-gramática con el nuevo meta-compilador, el resultado es el mismo: esto prueba que el meta-analizador generado funciona correctamente.
Aquí está la meta gramática de acción completa. Puede analizarse a sí mismo, ya que sabe cómo combinar líneas largas:
@subheader """ from grammar import Grammar, Rule, Alt from token import OP """ start: metas rules ENDMARKER { Grammar(rules, metas) } | rules ENDMARKER { Grammar(rules, []) } metas: meta metas { [meta] + metas } | meta { [meta] } meta: "@" NAME STRING NEWLINE { (name.string, eval(string.string)) } rules: rule rules { [rule] + rules } | rule { [rule] } rule: NAME ":" alts NEWLINE { Rule(name.string, alts) } alts: alt "|" alts { [alt] + alts } | alt { [alt] } alt: items action { Alt(items, action) } | items { Alt(items, None) } items: item items { [item] + items } | item { [item] } item: NAME { name.string } | STRING { string.string } action: "{" stuffs "}" { stuffs } stuffs: stuff stuffs { stuff + " " + stuffs } | stuff { stuff } stuff: "{" stuffs "}" { "{" + stuffs + "}" } | NAME { name.string } | NUMBER { number.string } | STRING { string.string } | OP { None if op.string in ("{", "}") else op.string }
Ahora que tenemos una meta-gramática funcional, estamos casi listos para hacer algunas mejoras.
Pero primero debes pensar un poco: ¡líneas vacías! Resulta que el módulo tokenize stdlib crea tokens adicionales para rastrear tokenize línea insignificantes (token NL ) y comentarios (token COMMENT ). En lugar de incluirlos en la gramática (¡lo intenté, no hay mucha diversión!), Hay un código muy simple que podemos agregar a nuestra clase de tokenizadores para filtrarlos. Aquí está el método mejorado peek_token :
def peek_token(self): if self.pos == len(self.tokens): while True: token = next(self.tokengen) if token.type in (NL, COMMENT): continue break self.tokens.append(token) self.report() return self.tokens[self.pos]
Esto elimina completamente los tokens NL y COMMENT , por lo que ya no tenemos que preocuparnos por ellos en la gramática.
Finalmente, ¡hagamos mejoras en la meta-gramática! Serán puramente cosméticos: no me gusta cuando me veo obligado a escribir todas las alternativas en una línea. La meta gramática que mostré arriba no se analiza en sí misma debido a tales cosas:
start: metas rules ENDMARKER { Grammar(rules, metas) } | rules ENDMARKER { Grammar(rules, []) }
Esto se debe al hecho de que el tokenizer crea un token NEWLINE al final de la primera línea, y en este momento el meta-analizador considerará que este es el final de la regla. Además, esta NEWLINE será seguida por el token INDENT , porque la siguiente línea está sangrada. Hasta el comienzo de la siguiente regla, un token DEDENT también estará presente.
Aquí se explica cómo manejarlo. Para comprender el comportamiento del módulo tokenize , podemos ver la secuencia de tokens generados para bloques sangrados ejecutando el módulo tokenize como un script y pasándole un texto:
$ python -m tokenize foo bar baz dah dum ^D
Vemos que esto produce la siguiente secuencia de tokens (simplifiqué un poco la salida del código anterior):
NAME 'foo' NAME 'bar' NEWLINE INDENT NAME 'baz' NEWLINE NAME 'dah' NEWLINE DEDENT NAME 'dum' NEWLINE
Por lo tanto, un grupo seleccionado de cadenas se indica mediante DEDENT y DEDENT . Ahora podemos reescribir la rule meta-gramática para la rule siguiente manera:
rule: NAME ":" alts NEWLINE INDENT more_alts DEDENT { Rule(name.string, alts + more_alts) } | NAME ":" alts NEWLINE { Rule(name.string, alts) } | NAME ":" NEWLINE INDENT more_alts DEDENT { Rule(name.string, more_alts) } more_alts: "|" alts NEWLINE more_alts { alts + more_alts } | "|" alts NEWLINE { alts }
(Divido las acciones en líneas para que se lean normalmente en una columna de texto estrecha. Esto es posible porque el tokenizador ignora los saltos de línea dentro de las llaves correspondientes).
Lo bueno de esto es que ni siquiera necesitamos cambiar el generador: la estructura de datos creada por esta meta-gramática mejorada es la misma que antes. También preste atención a la tercera opción para la rule : esto nos permite escribir:
start: | metas rules ENDMARKER { Grammar(rules, metas) } | rules ENDMARKER { Grammar(rules, []) }
que algunos pueden encontrarlo más limpio que la versión que mostré anteriormente. Ambas formas son fáciles de resolver, por lo que no necesitamos discutir sobre el estilo.
En la próxima publicación, mostraré cómo implementé varias funciones PEG, como elementos opcionales, repeticiones e información sobre herramientas. (Para ser honesto, planeé hablar sobre ellos en este artículo, pero ya es demasiado grande. Así que lo dividiré en dos partes).
Licencia para este artículo y código citado: CC BY-NC-SA 4.0