Ahora que he esbozado los conceptos básicos de un analizador patentado, pasemos a generar sus métodos a partir de la gramática, como prometí. También mostraré cómo implementar un analizador Packrat usando el decorador @memoize .
Contenido de la serie Python PEG Parser La última vez, vimos algunos métodos de analizador sintáctico. Con algunas restricciones que eliminaremos un poco más adelante, son fáciles de generar automáticamente a partir de la gramática.
Necesitamos dos cosas: algo que lea la gramática y construya una estructura de datos apropiada; y algo que toma esta estructura de datos y genera un analizador sintáctico. También necesitamos otros métodos auxiliares, pero no son interesantes, por lo que los omitiré.
Entonces, estamos creando un compilador compilador simple. Simplificaré un poco la notación gramatical en la medida en que solo tengamos reglas y alternativas; En realidad, esto es suficiente para la gramática del juguete que utilicé en las partes anteriores:
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
Usando la notación completa, podemos describir la gramática como:
grammar: rule+ ENDMARKER rule: NAME ':' alternative ('|' alternative)* NEWLINE alternative: item+ item: NAME | STRING
Este es nuestro primer meta-gramática (gramática para gramáticas), y nuestro generador de analizadores será un metacompilador (un compilador es un programa que traduce programas de un lenguaje a otro; un metacompilador es un compilador donde la entrada es una gramática, y la salida es un analizador sintáctico).
Una manera fácil de describir una metagramática es usar solo los tipos de datos integrados: la parte correcta de la regla es una lista de listas de elementos, cada uno de los cuales puede ser solo una cadena. (Por cierto, podemos separar NAME y STRING comprobando si el primer carácter es una comilla)
Para las reglas, uso la clase de Rule simple, y toda la gramática es una lista de dichos objetos. Aquí está la clase Rule , excluyendo __repr__ y __eq__ :
class Rule: def __init__(self, name, alts): self.name = name self.alts = alts
Y aquí está la clase GrammarParser que lo usa:
class GrammarParser(Parser): def grammar(self): pos = self.mark() if rule := self.rule(): rules = [rule] while rule := self.rule(): rules.append(rule) if self.expect(ENDMARKER): return rules
Presta atención al uso de ENDMARKER . Allí me aseguro de que no quede nada después de la última regla (y esto puede suceder si hay un error tipográfico en la gramática). También señalé el lugar donde el método grammar() devuelve una lista de reglas. Todo lo demás es muy similar a la clase ToyParser del último artículo, por lo que no me detendré en eso. Solo observe que item() devuelve una cadena, la alternative() devuelve una lista de cadenas y la variable alts dentro de rule() recopila una lista de la lista de cadenas. Luego, el método rule() combina el nombre de la regla (string) y la convierte en un objeto Rule .
Si aplicamos este algoritmo a nuestra gramática de juguetes, el método grammar() devolverá la siguiente lista de reglas:
[ Rule('statement', [['assignment'], ['expr'], ['if_statement']]), Rule('expr', [['term', "'+'", 'expr'], ['term', "'-'", 'term'], ['term']]), Rule('term', [['atom', "'*'", 'term'], ['atom', "'/'", 'atom'], ['atom']]), Rule('atom', [['NAME'], ['NUMBER'], ["'('", 'expr', "')'"]]), Rule('assignment', [['target', "'='", 'expr']]), Rule('target', [['NAME']]), Rule('if_statement', [["'if'", 'expr', "':'", 'statement']]), ]
Ahora que tenemos la parte de análisis de nuestro metacompilador, hagamos un generador de código. Juntos forman un metacompilador elemental:
def generate_parser_class(rules): print(f"class ToyParser(Parser):") for rule in rules: print() print(f" @memoize") print(f" def {rule.name}(self):") print(f" pos = self.mark()") for alt in rule.alts: items = [] print(f" if (True") for item in alt: if item[0] in ('"', "'"): print(f" and self.expect({item})") else: var = item.lower() if var in items: var += str(len(items)) items.append(var) if item.isupper(): print(" " + f"and ({var} := self.expect({item}))") else: print(f" " + f"and ({var} := self.{item}())") print(f" ):") print(f" " + f"return Node({rule.name!r}, [{', '.join(items)}])") print(f" self.reset(pos)") print(f" return None")
Este código es bastante feo, pero funciona (más o menos), y en el futuro lo reescribiré de todos modos.
Algunas líneas dentro del for alt in rule.alts pueden requerir explicación: para cada elemento de la alternativa, elegimos una de las 3 opciones:
- si el elemento es un literal de cadena, por ejemplo
'+' , generamos self.expect('+') - si el elemento está completamente en mayúscula, por ejemplo
NAME , generamos (name := self.expect(NAME)) - de lo contrario, por ejemplo, si es
expr , generamos (expr := self.expr())
Si hay varios elementos con el mismo nombre en una variante (por ejemplo, term '-' term ), entonces agregamos un dígito al segundo. También hay un pequeño error aquí que corregiré en el próximo episodio.
Aquí hay un poco del resultado de su trabajo (toda la clase sería muy aburrida). No se preocupe por el código redundante if (True and ... ) que se necesita para que cada condición generada pueda comenzar con and . El compilador de bytes de Python optimiza esto.
class ToyParser(Parser): @memoize def statement(self): pos = self.mark() if (True and (assignment := self.assignment()) ): return Node('statement', [assignment]) self.reset(pos) if (True and (expr := self.expr()) ): return Node('statement', [expr]) self.reset(pos) if (True and (if_statement := self.if_statement()) ): return Node('statement', [if_statement]) self.reset(pos) return None ...
Presta atención al decorador @memoize : lo @memoize para pasar a otro tema: usar la memorización para hacer que el analizador generado sea lo suficientemente rápido.
Aquí está la función memoize() que implementa este decorador:
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
Como en otros decoradores, contiene una función anidada que reemplaza (o envuelve) una función decorada, por ejemplo, el método de la statement() de la clase ToyParser . Dado que la función que se está envolviendo es un método, el contenedor también es en realidad un método: su primer argumento se llama self y se refiere a la instancia de ToyParser para la que se llama al método decorado.
El reiniciador almacena en caché el resultado de la llamada al método para cada posición de entrada, ¡por eso se llama el analizador de paquete! [aprox. trans. packrat es un "ladrón", pero este término no se traduce en fuentes en ruso.] Caché es un diccionario de diccionarios, que se almacena en una instancia de Parser . La clave del diccionario externo es la posición en el flujo de datos de entrada; También agregué self.memos = {} al Parser .__ init__() para inicializarlo. Los diccionarios internos se agregan según sea necesario; sus claves consisten en un método y sus argumentos. (No hay argumentos en el diseño actual, pero podríamos memorizar la función expect() que tiene una, lo cual es bastante trivial)
El resultado del método del analizador se presenta en forma de tupla, porque en realidad hay dos valores: el resultado en sí (para nuestros métodos generados, este es Node para la regla de coincidencia) y un puntero a la posición actual en la secuencia de entrada, que obtenemos de self.mark() . Por lo tanto, almacenamos en caché tanto el valor de retorno ( res ) como la nueva posición ( endpos ) en el diccionario interno con valores memorizados. En llamadas posteriores al mismo método de análisis con los mismos argumentos en la misma posición de entrada, los tomaremos del caché. Para hacer esto, simplemente mueva el puntero a la posición de entrada usando self.reset() y mire en el caché.
También es importante almacenar en caché los resultados negativos; de hecho, la mayoría de las llamadas serán negativas. En este caso, el valor de retorno es None y la posición de entrada no cambia. Puede agregar assert para verificar esto.
Nota En Python, es costumbre implementar un caché en una variable local en la función memoize() . En nuestro caso, esto no funcionará: como descubrí al final de la depuración, cada instancia de Parser debe tener su propio caché. Sin embargo, puede deshacerse de los diccionarios anidados utilizando ( pos , func , args ) como clave.
La próxima semana prepararé códigos y trazas para mostrar cómo se ensambla y ejecuta todo esto al analizar un programa de ejemplo. Todavía estoy buscando una mejor manera de visualizar la colaboración del búfer de tokenización, el analizador y el caché. Tal vez pueda crear un gif animado en ASCII en lugar de solo mostrar las listas de seguimiento como texto.
Licencia para este artículo y código citado: CC BY-NC-SA 4.0