La gramática es aún mejor si puede agregar (algunas) semánticas de acuerdo con las reglas. En particular, para el analizador Python que estoy desarrollando, necesito devolver un nodo AST de cada alternativa, ya que quiero seguir con la implementación AST actual en CPython.
Contenido de la serie Python PEG Parser Muchas gramáticas usan una convención que le permite agregar acciones a las reglas, generalmente un bloque de código dentro de {llaves ". Más precisamente, están vinculados a alternativas. El código en este bloque está escrito en el mismo lenguaje que el resto del compilador, por ejemplo, en C, complementado por alguna capacidad de referirse a elementos en la alternativa. En el pgen Python original, no pgen esta funcionalidad, pero para un nuevo proyecto me gustaría implementarla.
Así es como lo hacemos para el generador de analizador simplificado que estoy desarrollando como parte de esta serie de publicaciones.
La sintaxis de las acciones suele ser esta:
rule: item item item { action 1 } | item item { action 2 }
Dado que esto hace que la gramática sea más detallada, los generadores de analizadores generalmente permiten reglas de varias líneas, por ejemplo:
rule: item item item { action 1 } | item item { action 2}
Esto hace que el analizador sea un poco más complicado, pero es importante para la legibilidad, por lo que apoyaré dicho registro.
La eterna pregunta es cuándo ejecutar este bloque. En Yacc / Bison, esto se hace inmediatamente después de que el analizador reconoce la regla, ya que no hay reversión en la lista de tokens. Ejecutar cada acción exactamente una vez significa que puede haber efectos secundarios globales (como actualizar la tabla de símbolos u otra estructura de datos del compilador).
En los analizadores PEG con su retorno ilimitado a la lista de tokens, tenemos varias opciones:
- No ejecute ninguna acción hasta que todo haya sido analizado. No consideraré esto, porque quiero construir un AST justo durante el análisis.
- Realice siempre que se reconozca su alternativa. Se requiere que su código sea idempotente (es decir, que tenga el mismo efecto sin importar cuántas veces se haya ejecutado). Esto significa que la acción puede ejecutarse, pero su resultado finalmente puede descartarse.
- Guarde en caché el resultado y realice la acción solo por primera vez, cuando su alternativa se reconozca en esta posición.
Elegí la tercera opción: en cualquier caso, almacenamos en caché el resultado del método utilizando el algoritmo packrat, por lo que también podemos almacenar en caché los resultados.
En cuanto al contenido en {curlies}, por tradición usa el código C con un acuerdo basado en $ para referirse a elementos en una alternativa reconocida (por ejemplo, $1 para referirse al primer elemento) y la asignación $$ para indicar el resultado de la acción. Suena muy anticuado (tengo recuerdos del uso de la asignación de funciones en Algol-60 para indicar el valor de retorno), por lo que lo haré más Pythonic: dentro de los corchetes deberá poner una expresión, cuyo resultado será el resultado de la acción, y los enlaces a los elementos serán nombres simples que dan el texto del elemento. Como ejemplo, aquí hay una calculadora simple que puede sumar y restar números:
start: expr NEWLINE { expr } expr: expr '+' term { expr + term } | expr '-' term { expr - term } | term { term } term: NUMBER { float(number.string) }
Vamos a ejecutarlo en el ejemplo de 100 + 50 - 38 - 70 . Él calculará la respuesta, porque él reconoce las partes calculando ((100 + 50) - 38) - 70 , que por supuesto es 42 .
Un pequeño detalle: en la acción para el term number variable contiene un objeto TokenInfo , por lo que debe usar su atributo .string para obtener el token en forma de cadena.
¿Qué hacemos cuando una alternativa tiene múltiples ocurrencias con el mismo nombre de regla? El generador de analizador le da a cada aparición un nombre único, agregando 1 , 2 , etc. Para sucesos posteriores dentro de la misma alternativa. Por ejemplo:
factor: atom '**' atom { atom ** atom1 } | atom { atom }
La implementación completa es bastante aburrida, por lo que no me gustaría detenerme en ella. Te invito a que busques en mi repositorio y juegues con el código :
python3.8 -m story5.driver story5/calc.txt -g story5.calc.CalcParser
¡La visualización ahora le permite moverse hacia adelante y hacia atrás usando las teclas de flecha izquierda y derecha!
Licencia para este artículo y código citado: CC BY-NC-SA 4.0