Después de reunir todas las partes del generador de analizador PEG en la publicación anterior, estoy listo para mostrar cómo implementar algunas otras cosas interesantes.
Contenido de la serie Python PEG Parser Consideraremos las siguientes características de PEG:
- Elementos con nombre:
NAME=item (el nombre se puede usar en la acción) - Lookaheads:
&item (positivo) y !item (negativo) - Agrupación de elementos entre paréntesis: (
item item ... ) - Artículos opcionales:
[item item ...] y item? - Elementos duplicados:
item* (cero o más) y item+ (uno o más)
Argumentos nombrados
Comencemos con elementos con nombre. Esto es conveniente cuando tenemos varios de ellos en una alternativa para la misma regla, por ejemplo:
expr: term '+' term
Podemos referirnos al segundo term agregando el número 1 al nombre de la variable, de modo que en la acción resulte así:
expr: term '+' term { term + term1 }
Pero no a todos les gusta, y personalmente, preferiría escribir algo como esto:
expr: left=term '+' right=term { left + right }
Esto se admite fácilmente en la meta-gramática cambiando la regla para el item siguiente manera:
item: | NAME = atom { NamedItem(name.string, atom) } | atom { atom } atom: | NAME { name.string } | STRING { string.string }
(Donde el atom es solo un item viejo)
Esto requiere que agreguemos la definición de la clase NamedItem a grammar.py . Es una de esas clases de datos que mencioné anteriormente, también tiene los atributos de name y item .
También tenemos que hacer pequeños cambios en el generador de código, que dejaré como ejercicio para el lector (o puede consultar mi repositorio :-). El código generado ahora asignará el resultado de hacer coincidir cada elemento con una variable con el nombre especificado, y no con el nombre obtenido del nombre de la regla del elemento. Esto también funcionará para elementos que son tokens (ya sea de la forma NAME o literales de cadena como ':=' ).
Mirar hacia adelante
Seguido por lookahead. Probablemente haya encontrado este concepto en expresiones regulares. Durante la búsqueda anticipada, la alternativa analizada se puede rechazar o aceptar de inmediato, sin cambiar el puntero del tokenizador.
De hecho, la búsqueda anticipada se puede usar como una forma más elegante de eliminar la confusión con las excepciones del analizador, que escribí en un artículo anterior. En lugar de permitir que las acciones rechacen una alternativa ya aceptada devolviendo None, podemos agregar una instrucción antes del OP para excluir "}" . La vieja regla se veía así:
| OP { None if op.string in ("{", "}") else op.string }
La nueva versión se ve así:
| !"}" OP { op.string }
Esto transfiere el procesamiento de corchetes de la acción a la gramática, donde pertenece. No necesitamos marcar "{" , ya que corresponde a una alternativa anterior (de hecho, esto también es cierto para la versión anterior, pero lo olvidé :-).
Agregamos gramática para lookaheads a la regla para el item siguiente manera:
item: | NAME = atom { NamedItem(name.string, atom) } | atom { atom } | "&" atom { Lookahead(atom, True) } | "!" atom { Lookahead(atom, False) }
Una vez más, necesitamos agregar la clase de datos Lookahead a Lookahead (¡e importarla en @subheader !) Y modificar un poco el generador agregando el siguiente método auxiliar:
def lookahead(self, positive, func, *args): mark = self.mark() ok = func(*args) is not None self.reset(mark) return ok == positive
En nuestro caso, el código generado para esta alternativa se ve así:
if (True and self.lookahead(False, self.expect, "}") and (op := self.expect(OP)) ): return op . string
Como puede ver en el fragmento de gramática anterior, la búsqueda anticipada no puede obtener nombres propios. Esto es fácil de solucionar, pero todavía no tengo idea de lo útil que sería. Además, para pronósticos negativos, el valor siempre será None .
Agrupación entre paréntesis
Ahora implementemos grupos con corchetes. El mejor lugar para agregarlos al metagrama es la regla del atom :
atom: | NAME { name.string } | STRING { string.string } | "(" alts ")" { self.synthetic_rule(alts) }
Las dos primeras alternativas no han cambiado. La acción para la nueva alternativa utiliza un truco (cuya implementación permanece sin explicación), que permite al meta-analizador agregar nuevas reglas a la gramática sobre la marcha. Esta función auxiliar (definida en el meta-analizador) devuelve el nombre del nuevo objeto de regla. Consistirá en un prefijo fijo seguido de un número, lo que lo hace único, por ejemplo, _synthetic_rule_1 .
Puede preguntar qué sucede si finalmente se descarta la regla sintética. No sé cómo evitar esto, pero no debería haber ningún problema: en el peor de los casos, habrá una regla no utilizada en la gramática. Y gracias a la memorización, la misma acción nunca se ejecutará dos veces para la misma posición de entrada, por lo que tampoco es un problema (pero incluso si ese fuera el caso, en el peor de los casos tendríamos una regla muerta).
Usar alts dentro de corchetes significa que podemos definir una barra vertical como un delimitador dentro de un grupo. Por ejemplo, que nuestra nueva solución de acción no coincidiría accidentalmente con { , podríamos cambiar la negación a esto:
| !("{" | "}") OP { op.string }
¡Además, los grupos también pueden contener acciones! Esto no ayudaría a resolver el problema con las acciones, pero en otras situaciones puede ser útil. Y dado que, en cualquier caso, generamos una regla sintética, no requiere ningún trabajo adicional para implementarla (excepto la implementación de synthetic_rule :-).
Artículos opcionales
Como en el antiguo pgen, uso corchetes para indicar un grupo de tokens opcionales. Aquí es donde resulta útil. Por ejemplo, una regla gramatical que describe un Python for loop puede usarlo para indicar que puede existir una extensión de else . Y nuevamente podemos expandir la gramática del atom siguiente manera:
atom: | NAME { name.string } | STRING { string.string } | "(" alts ")" { self.synthetic_rule(alts) } | "[" alts "]" { Maybe(self.synthetic_rule(alts)) }
Aquí Maybe es otra clase de datos, con un solo atributo de item . Modificamos el generador de código para que el resultado de la función sintética no falle si este valor es None . Para hacer esto, puede agregar or True en la implementación. Por ejemplo, para [term] :
if (True and ((term := self.term()) or True) ): return term
Artículos duplicados
Cambiar a repetición es otra función PEG útil (la notación se toma prestada de expresiones regulares y también se usa en pgen). Hay dos formas: agregar * a un átomo significa "cero o más repeticiones", mientras que agregar + significa "una o más repeticiones". Por otras razones, tuve que reescribir las reglas gramaticales para el item y el atom , agregando una regla intermedia, que llamé molecule :
item: | NAME '=' molecule { NamedItem(name.string, molecule) } | "&" atom { Lookahead(atom) } | "!" atom { Lookahead(atom, False) } | molecule { molecule } molecule: | atom "?" { Maybe(atom) } | atom "*" { Loop(atom, False) } | atom "+" { Loop(atom, True) } | atom { atom } | "[" alts "]" { Maybe(self.synthetic_rule(alts)) } atom: | NAME { name.string } | STRING {string.string } | "(" alts ")" { self.synthetic_rule(alts) }
Tenga en cuenta que esto introduce una sintaxis alternativa para elementos opcionales ( atom? ). No requiere esfuerzos de implementación adicionales, ya que esta es solo otra forma de crear un nodo Maybe .
Refactorizar estas reglas fue necesario porque no quiero que ciertas situaciones sean válidas:
- repeticiones opcionales (ya que esto es solo una repetición de cero o más);
- repeticiones (interno capturaría todas las coincidencias, ya que PEG siempre usa un algoritmo codicioso)
- valores opcionales repetidos (que interrumpirían el análisis si el elemento opcional no coincide).
Sin embargo, esta todavía no es una solución ideal, ya que puedes escribir algo como (foo?)* . Será necesario agregar un cheque a esta situación en el generador de analizadores, pero lo haré fuera del artículo.
La clase de datos Loop tiene dos atributos: item y nonempty . El código generado utilizará el método de loop() analizador auxiliar loop() . Es muy similar al método lookahead() mostrado anteriormente:
def loop(self, nonempty, func, *args): mark = self.mark() nodes = [] while node := func(*args) is not None: nodes.append(node) if len(nodes) >= nonempty: return nodes self.reset(mark) return None
Si nonempty es False (en el sentido de que la gramática era * ), esto no conducirá a un error. No se encontrarán entradas y se devolverá una lista vacía. Para que esto suceda, implementamos el generador de analizador para que is not None agregue is not None . Un cheque más suave de una publicación anterior devolvería False en el caso de una lista vacía.
¡Eso es todo por hoy! Iba a hablar sobre el operador de "corte" ( ~ ) presente en TatSu, pero hasta ahora no he tenido la oportunidad de encontrarlo. Ni siquiera estoy listo para discutirlo todavía: la documentación de TatSu da solo un ejemplo simple que me interesa un poco. No lo encontré en otros generadores de analizadores de PEG, por lo que, tal vez, esta característica es solo TatSu. Quizás algún día les cuente sobre él. (Mientras tanto, lo implementé por si acaso, nunca se sabe. :-)
Creo que el próximo artículo será sobre mi experiencia escribiendo una gramática PEG que pueda analizar la gramática de Python. Te diré cómo se llevó a cabo el sprint de los desarrolladores del núcleo de Python, que fue en Londres esta semana con el apoyo logístico de Bloomberg y el apoyo financiero de PSF y algunas otras compañías (por ejemplo, Dropbox me pagó el hotel y el vuelo). Un agradecimiento especial a Emily Morhouse y Pablo Galindo Salgado, quienes ayudaron mucho en la implementación de las herramientas y las pruebas. A continuación, escribiremos pruebas de rendimiento, y luego agregaremos acciones a esta gramática para que pueda crear árboles AST que el compilador de código de bytes CPython pueda compilar. ¡Hay cosas mucho más interesantes por delante!
Licencia para este artículo y código citado: CC BY-NC-SA 4.0