Dos importes para la misma factura
Un programa de facturación calcula 100 - 20 - 10: el precio, un descuento y un vale. Una persona del equipo dice que salen 70 euros. Otra dice 90.
Las dos leen los mismos tokens en el mismo orden. Los agrupan de otra forma. Un compilador tiene que agruparlos siempre igual, y esa forma está escrita en una gramática.
Al final de esta lección
Nota
Puedo construir un árbol sintáctico a partir de tokens.
Palabras clave
| Palabra | Qué significa | Ejemplo |
|---|---|---|
| Gramática | las reglas de qué órdenes de tokens se admiten | |
| Árbol sintáctico | un árbol que muestra cómo se agrupan los tokens | |
| Analizador sintáctico | la parte del compilador que construye el árbol | |
| Precedencia | qué operador se agrupa primero | * antes que + |
| Asociatividad | hacia qué lado se agrupan operadores iguales | izquierda |
| Descenso recursivo | un analizador con una función por regla |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Una gramática dice cómo se agrupan
Una gramática es una lista corta de reglas. Cada regla nombra una parte de la frase y dice de qué está hecha.
Las tres reglas de abajo dan a * y / más precedencia que a + y -. Una suma está hecha de productos, así que los productos se agrupan antes. Los bucles de las dos primeras reglas agrupan por la izquierda: esa es la asociatividad.
Ejemplo: tres reglas para cuentas
| Regla | Está hecha de | Ejemplo |
|---|---|---|
| expr | Un term, y después + o - con otro term, las veces que haga falta | 100 - 20 - 10 |
| term | Un factor, y después * o / con otro factor, las veces que haga falta | 20 * 3 |
| factor | Un número, un nombre, un - y otro factor, o una expr entre paréntesis | 7, price, -3 o (1 + 2) |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Una función por cada regla
Un analizador de descenso recursivo tiene una función por regla. parse_expr llama a parse_term, y parse_term lee lo que hay dentro.
Cada vuelta del bucle de parse_expr usa el árbol que ya tiene como lado izquierdo. Así el árbol crece hacia la izquierda. La demo trabaja solo con números, + y *.
Descenso recursivo en Python
# Descenso recursivo para sumas y productos de números.
tokens = ["2", "+", "3", "*", "4"]
pos = [0]
def peek():
if pos[0] < len(tokens):
return tokens[pos[0]]
return None
def parse_term():
# Un término: números unidos por *.
left = int(tokens[pos[0]])
pos[0] = pos[0] + 1
while peek() == "*":
right = int(tokens[pos[0] + 1])
pos[0] = pos[0] + 2
left = ["*", left, right]
return left
def parse_expr():
# Una expresión: términos unidos por +.
left = parse_term()
while peek() == "+":
pos[0] = pos[0] + 1
left = ["+", left, parse_term()]
return left
print(parse_expr())
# Cambia tokens por ["2", "*", "3", "+", "4"] y vuelve a ejecutar.
bison construye el analizador
Un generador de analizadores sintácticos como bison lee una gramática y escribe el analizador en C. En calc.y, la regla expr tiene una línea por operador. Así sola es ambigua: 20 - 5 - 5 podría agruparse de dos formas.
Dos líneas %left lo deciden. Cada una dice que sus operadores se agrupan por la izquierda. La línea de más abajo tiene más precedencia.
Entra en la carpeta del compilador
cd ~/compilerSe muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Asegura que la calculadora existe
makeSe muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Las dos líneas de precedencia
grep -n "%left" calc.ySe muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
El menos agrupa por la izquierda
echo "20 - 5 - 5" | ./calcSe muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Los paréntesis cambian el árbol
echo "2 * (3 + 4)" | ./calcSe muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Un menos sin nada delante
echo "-3" | ./calcSe muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Un error frecuente
Advertencia
Mucha gente cree que la asociatividad no importa, porque 1 + 2 + 3 da 6 se agrupe como se agrupe. Eso solo vale para la suma y el producto. Con - y / cada agrupación da otro número. Por eso una gramática dice siempre hacia qué lado se agrupa cada operador.
Cambia la asociatividad en una copia
El primer Run copia calc.y en right.y y cambia el %left de * y / por %right. El original no cambia.
Los dos Runs siguientes construyen otra calculadora, right, con esa copia. Luego das la misma cuenta a las dos calculadoras.
Copia la gramática con %right
sed "s/%left '\*'/%right '*'/" calc.y > right.ySe muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
bison escribe el nuevo analizador
bison -o right.tab.c right.ySe muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Construye la calculadora right
gcc -o right right.tab.c lex.yy.cSe muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Divide con right
echo "60 / 4 / 3" | ./rightSe muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Divide con calc
echo "60 / 4 / 3" | ./calcSe muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Para ir más lejos
Añade a tu analizador las comparaciones < y >, con menos precedencia que + y -. price * 2 > 10 da [">", ["*", "price", 2], 10].
Pero 1 < 2 < 3 debe dar ValueError: una comparación no se encadena. Escribe una regla nueva por encima de expr y explica por qué no lleva bucle.