Gramática (BNF) y Notación Polaca Inversa
Introducido| English | Significado |
|---|---|
| postfix/ˈpəʊstfɪks/ | postfijo |
| precedence/ˈpresɪdəns/ | precedencia |
| grammar/ˈɡræmə/ | gramática |
| syntax diagram/ˈsɪntæks ˈdaɪəɡræm/ | diagrama de sintaxis |
| Reverse Polish Notation/rɪˈvɜːs ˈpəʊlɪʃ nəʊˈteɪʃn/ | notación polaca inversa |
| Backus-Naur Form/ˈbækəs nɔː fɔːm/ | forma de Backus-Naur |
| production rules/prəˈdʌkʃn ruːlz/ | reglas de producción |
| terminal/ˈtɜːmɪnl/ | símbolo terminal |
| non-terminal/nɒn ˈtɜːmɪnl/ | símbolo no terminal |
| infix/ˈɪnfɪks/ | infixo |
La notación sin paréntesis y sin ambigüedad
- Escribe
3 + 4 * 2y estarás confiando en una convención: que la multiplicación tiene mayor jerarquía que la suma. Cambia la convención y la expresión tendrá un significado diferente. - Un lógico polaco, Jan Łukasiewicz, demostró en la década de 1920 que si colocas el operador antes de sus operandos, los paréntesis se vuelven innecesarios. Si lo inviertes, colocando el operador después, obtienes una forma que una máquina puede evaluar usando únicamente una pila.
- Por eso la Máquina Virtual de Java (JVM) y la mayoría de los intérpretes de bytecode funcionan en notación posfija. Sin tabla de precedencia, sin paréntesis, sin ambigüedades.
- Esta lección explica cómo se escribe la gramática 文法 de un lenguaje, mediante BNF y como diagrama de sintaxis, y cómo se convierte y evalúa la Notación Polaca Inversa 逆波兰表示法.
Forma de Backus-Naur
- Una gramática define qué secuencias de tokens son programas válidos. La Forma de Backus-Naur 巴科斯-诺尔范式 (BNF) la escribe como reglas de producción 产生式:
<symbol> ::= alternative1 | alternative2 | ...
- Un símbolo terminal 终结符 es texto literal que aparece en el programa. Un símbolo no terminal 非终结符 es el nombre de otra regla, escrito entre ángulos.
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<letter> ::= a | b | c | … | z
<identifier> ::= <letter> | <identifier> <letter> | <identifier> <digit>
En BNF, un símbolo terminal es:
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Los terminales son tokens literales; los no terminales son nombres de otras reglas de producción.
La recursión es cómo BNF repite
- BNF no tiene un símbolo de "repeticion", por lo que la repetición se escribe definiendo una regla en términos de sí misma.
- Lee
<identifier> ::= <letter> | <identifier> <letter> | <identifier> <digit>como: un identificador es una sola letra, o un identificador seguido de una letra, o un identificador seguido de un dígito. - Juntas, esas alternativas significan "una letra seguida de cualquier número de letras o dígitos", lo cual también explica por qué un identificador no puede comenzar con un dígito: ninguna alternativa lo permite.
- Un diagrama de sintaxis 语法图, o diagrama de ferrocarril, expresa las mismas reglas gráficamente, con un bucle donde BNF usa recursión. Ambas notaciones son equivalentes.

El bucle y la recursión dicen lo mismo
Asocia cada término de gramática/notación con su significado.
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
BNF construye reglas a partir de terminales y no terminales (la recursión da repetición); RPN reordena una expresión para eliminar paréntesis.
¿Por qué la regla
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Las alternativas juntas significan una letra seguida de cualquier número de letras o dígitos, y ninguna alternativa permite comenzar con un dígito.
Ejemplo resuelto: probar una cadena contra la gramática
- Usando las reglas anteriores, ¿cuáles de
count2,2countymy_varson identificadores válidos? count2: válido. Constrúyelo paso a paso:ces una<letter>, por tanto un<identifier>; añadeo,u,n,tusando la segunda alternativa; añade2usando la tercera.2count: inválido. Todas las alternativas comienzan con una<letter>o con otro<identifier>, y ninguna cadena puede comenzar con un dígito.my_var: inválido, porque_no es un terminal en ninguna de estas reglas. Indica cuál es la regla que falla, no solo digas "parece incorrecto".
Usando esas reglas, ¿qué cadenas son identificadores válidos? Selecciona todas las que correspondan.
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
Una sola letra es un identificador según la primera alternativa. 2count no puede comenzar con un dígito, y _ no es un terminal en ninguna de estas reglas.
Infijo y posfijo
- Infijo 中缀 coloca el operador entre sus operandos,
3 + 4 * 2, y por lo tanto necesita reglas de precedencia y paréntesis para ser inequívoco. - La Notación Polaca Inversa, o posfijo 后缀, coloca el operador después de sus operandos:
3 4 2 * +. No necesita ninguno de los dos. - El orden en que aparecen los operadores en la forma posfija es el orden en que se aplican, que es exactamente lo que una máquina necesita saber.
Convertir infijo a posfijo
- Usa una pila de operadores. Escanea de izquierda a derecha: envía un operando directamente a la salida; para un operador, primero popa a la salida cualquier operador apilado de precedencia igual o superior 优先级, luego empújalo.
- Empuja un paréntesis de apertura. Al encontrar un paréntesis de cierre, popa a la salida hasta llegar al paréntesis de apertura correspondiente, luego descarta el par.
- Al final, popa todo lo que quede en la pila hacia la salida.
Precedencia de operadores — lo que elimina la RPN
En matemáticas infixas ordinarias, × y ÷ tienen mayor precedencia que + y −, por lo que se deben aplicar reglas en el orden correcto. La Notación Polaca Inversa escribe los operandos primero (3 4 2 × + 1 −), fijando el orden para que no sean necesarias reglas de precedencia.
¿Cuál es la forma RPN (postfija) de la expresión infix (3 + 4) * 2?
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Los paréntesis obligan a 3+4 primero: 3 4 +, luego multiplicar por 2: 3 4 + 2 *.
Convierte (A + B) * (C - D) a Notación Polaca Inversa, usando * para la multiplicación.
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Cada paréntesis se convierte por turno y la multiplicación se extrae al final, por lo que aparece al final. No sobreviven paréntesis.
Ejemplo resuelto: convertir y luego evaluar
- Convierte $(A + B) \times (C - D)$ a RPN. Empuja
(; envíaA; empuja+; envíaB; al encontrar)popa de vuelta hasta el(correspondiente, obteniendoA B +. Empuja×. El segundo paréntesis se comporta idénticamente, obteniendoC D -. Al final popa el×. Resultado:A B + C D - ×. - Ahora evalúalo para $A=3, B=4, C=5, D=2$. Empuja 3, empuja 4;
+popa ambos y empuja 7. Empuja 5, empuja 2;-popa ambos y empuja 3.×popa 7 y 3 y empuja 21. - El operador siempre toma los dos elementos superiores, y el primero en ser poppeado es el operando derecho. Esto importa en
-y/, donde el orden cambia el resultado.
Evalúa la expresión RPN 3 4 2 * +.
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
Empuja 3, 4, 2; * extrae 4 y 2 → 8; + extrae 3 y 8 → 11.
La Notación Polaca Inversa no necesita paréntesis ni reglas de precedencia, y se puede evaluar directamente con una pila.
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Empuja operandos; cada operador extrae sus operandos y empuja el resultado —lo cual es exactamente cómo funciona una máquina de pila.
Evaluando con una pila, paso a paso
- Escanea de izquierda a derecha: empuja cada operando; al encontrar un operador, popa los dos superiores, aplícalo y empuja el resultado. Al final, la pila contendrá un único valor: la respuesta.
| Token | Pila después |
|---|---|
3 |
3 |
4 |
3, 4 |
2 |
3, 4, 2 |
* |
3, 8 |
+ |
11 |
- Esta es una máquina de pila: sin paréntesis, sin tabla de precedencia, sin lookahead. Es así como la JVM y muchos intérpretes de bytecode evalúan cada expresión.
Al evaluar RPN, el primer elemento extraído de la pila es el operando izquierdo del operador.
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
El primero extraído es el operando derecho. No importa para + y *, pero invertirlo rompe la resta y la división.
Coloca los pasos de evaluar 3 4 2 * + con una pila en orden.
Dificultad 3/5 · 200 monedas + un pequeño bono en el primer intento de hoy
Los operandos van hacia arriba, cada operador consume los dos superiores y deja su resultado. No se necesitan paréntesis ni tabla de precedencia.
Puntos que se pueden perder
- Un terminal es texto literal; un no terminal nombra otra regla. No los intercambies.
- BNF expresa la repetición mediante recursión. Si una regla se refiere a sí misma, indícalo y explica su significado.
- En la evaluación, el operador toma los dos elementos superiores, y el primero en ser poppeado es el operando derecho. Hacerlo al revés invalida la resta y la división.
- RPN no necesita paréntesis. Escribir paréntesis en una respuesta posfija hace que pierdas los puntos que se estaban evaluando.
Lo has entendido
- Las reglas de producción BNF combinan terminales (texto literal) y no terminales (nombres de reglas), y expresan la repetición mediante recursión; un diagrama de sintaxis es la forma gráfica equivalente.
- Prueba una cadena construyéndola desde las reglas, y nombra la regla que falla cuando es inválida.
- Infijo necesita precedencia y paréntesis; RPN (posfijo) coloca el operador después de sus operandos y no necesita ninguno de los dos.
- Convierte usando una pila de operadores, y evalúa empujando operandos y aplicando cada operador a los dos superiores, siendo el primero en ser poppeado el operando derecho.