Grammar (BNF) and Reverse Polish Notation · Gramática (BNF) y Notación Polaca Inversa
| English | Español |
|---|---|
| postfix/ˈpəʊstfɪks/ | notación posfija |
| 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/ | terminal |
| non-terminal/nɒn ˈtɜːmɪnl/ | no terminal |
| infix/ˈɪnfɪks/ | infixo |
The notation with no brackets, and no ambiguity
- Write
3 + 4 * 2and you are relying on a convention: that multiplication binds tighter than addition. Change the convention and the expression means something else. - A Polish logician, Jan Łukasiewicz, showed in the 1920s that if you put the operator before its operands the brackets become unnecessary. Reverse it, putting the operator after, and you get a form a machine can evaluate with nothing but a stack.
- That is why the Java Virtual Machine and most bytecode interpreters work in postfix. No precedence table, no brackets, no ambiguity.
- This lesson is how a language's grammar 文法 is written down, in BNF and as a syntax diagram, and how Reverse Polish Notation 逆波兰表示法 is converted and evaluated.
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 逆波兰表示法.
Backus-Naur Form
- A grammar says which sequences of tokens are valid programs. Backus-Naur Form 巴科斯-诺尔范式 (BNF) writes it as production rules 产生式:
- A terminal 终结符 symbol is literal text that appears in the program. A non-terminal 非终结符 symbol is the name of another rule, written in angle brackets.
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>
In BNF, a terminal symbol is: · En BNF, un símbolo terminal es:
Terminals are literal tokens; non-terminals are names of other production rules. · Los terminales son tokens literales; los no terminales son nombres de otras reglas de producción.
Recursion is how BNF repeats
- BNF has no "repeat" symbol, so repetition is written by defining a rule in terms of itself.
- Read
<identifier> ::= <letter> | <identifier> <letter> | <identifier> <digit>as: an identifier is a single letter, or an identifier followed by a letter, or an identifier followed by a digit. - Together those alternatives mean "a letter followed by any number of letters or digits", which also explains why an identifier cannot start with a digit: no alternative allows it.
- A syntax diagram 语法图, or railroad diagram, expresses the same rules graphically, with a loop where BNF uses recursion. The two notations are equivalent.
The loop and the recursion say the same thing
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
Match each grammar/notation term to its meaning. · Asocia cada término de gramática/notación con su significado.
BNF builds rules from terminals and non-terminals (recursion gives repetition); RPN reorders an expression to drop brackets. · 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.
Why does the rule
The alternatives together mean a letter followed by any number of letters or digits, and no alternative lets one start with a digit. · 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.
Worked example: test a string against the grammar
- Using the rules above, which of
count2,2countandmy_varare valid identifiers? count2: valid. Build it up:cis a<letter>, so an<identifier>; addo,u,n,tby the second alternative; add2by the third.2count: invalid. Every alternative starts from a<letter>or from another<identifier>, and no chain can begin with a digit.my_var: invalid, because_is not a terminal in any rule here. State the rule that fails, not just "it looks wrong".
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".
Using those rules, which strings are valid identifiers? Select all · todos that apply. · Usando esas reglas, ¿qué cadenas son identificadores válidos? Selecciona todas las que correspondan.
A single letter is an identifier by the first alternative. 2count cannot start with a digit, and _ is not a terminal in any rule here. · 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.
Infix and postfix
- Infix 中缀 puts the operator between its operands,
3 + 4 * 2, and therefore needs precedence rules and brackets to be unambiguous. - Reverse Polish Notation, or postfix 后缀, puts the operator after its operands:
3 4 2 * +. It needs neither. - The order in which the operators appear in the postfix form is the order they are applied, which is exactly what a machine needs to be told.
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.
Converting infix to postfix
- Use an operator stack. Scan left to right: send an operand straight to the output; for an operator, first pop to the output any stacked operators of higher or equal precedence 优先级, then push it.
- Push an opening bracket. On a closing bracket, pop to the output until the matching opening bracket, then discard the pair.
- At the end, pop everything left on the stack to the output.
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.
Operator precedence — what RPN removes · Precedencia de operadores — lo que elimina la RPN
In ordinary infix maths × and ÷ bind tighter than + and −, so you must apply rules in the right order. Reverse Polish Notation writes the operands first (3 4 2 × + 1 −), fixing the order so no precedence rules are needed. · 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.
What is the RPN (postfix) form of the infix expression (3 + 4) * 2? · ¿Cuál es la forma RPN (postfija) de la expresión infix (3 + 4) * 2?
The brackets force 3+4 first: 3 4 +, then multiply by 2: 3 4 + 2 *. · Los paréntesis obligan a 3+4 primero: 3 4 +, luego multiplicar por 2: 3 4 + 2 *.
Convert (A + B) * (C - D) to Reverse Polish Notation, using * for the multiplication. · Convierte (A + B) * (C - D) a Notación Polaca Inversa, usando * para la multiplicación.
Each bracket is converted in turn and the multiplication is popped last, so it appears at the end. No brackets survive. · 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.
Worked example: convert, then evaluate
- Convert $(A + B) \times (C - D)$ to RPN. Push
(; outputA; push+; outputB; on)pop back to the matching(, givingA B +. Push×. The second bracket behaves identically, givingC D -. At the end pop the×. Result:A B + C D - ×. - Now evaluate it for $A=3, B=4, C=5, D=2$. Push 3, push 4;
+pops both and pushes 7. Push 5, push 2;-pops both and pushes 3.×pops 7 and 3 and pushes 21. - The operator always takes the top two items, and the first popped is the right-hand operand. That matters for
-and/, where order changes the answer.
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.
Evaluate the RPN expression 3 4 2 * +. · Evalúa la expresión RPN 3 4 2 * +.
Push 3, 4, 2; * pops 4 and 2 → 8; + pops 3 and 8 → 11. · Empuja 3, 4, 2; * extrae 4 y 2 → 8; + extrae 3 y 8 → 11.
Reverse Polish Notation needs no brackets or precedence rules, and can be evaluated directly with a stack. · La Notación Polaca Inversa no necesita paréntesis ni reglas de precedencia, y se puede evaluar directamente con una pila.
Push operands; each operator pops its operands and pushes the result — which is exactly how a stack machine runs. · Empuja operandos; cada operador extrae sus operandos y empuja el resultado —lo cual es exactamente cómo funciona una máquina de pila.
Evaluating with a stack, step by step
- Scan left to right: push each operand; on an operator, pop the top two, apply it, and push the result. At the end the stack holds one value: the answer.
| Token | Stack after |
|---|---|
3 |
3 |
4 |
3, 4 |
2 |
3, 4, 2 |
* |
3, 8 |
+ |
11 |
- This is a stack machine: no brackets, no precedence table, no lookahead. It is how the JVM and many bytecode interpreters evaluate every expression.
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.
When evaluating RPN, the first item popped from the stack is the left-hand operand of the operator. · Al evaluar RPN, el primer elemento extraído de la pila es el operando izquierdo del operador.
The first popped is the right-hand operand. It makes no difference for + and *, but reversing it breaks subtraction and division. · El primero extraído es el operando derecho. No importa para + y *, pero invertirlo rompe la resta y la división.
Put the steps of evaluating 3 4 2 * + with a stack in order. · Coloca los pasos de evaluar 3 4 2 * + con una pila en orden.
Operands go on, each operator consumes the top two and leaves its result. No brackets and no precedence table are needed. · Los operandos van hacia arriba, cada operador consume los dos superiores y deja su resultado. No se necesitan paréntesis ni tabla de precedencia.
Marks that slip away
- A terminal is literal text; a non-terminal names another rule. Do not swap them.
- BNF expresses repetition by recursion. If a rule refers to itself, say so and say what it means.
- In evaluation the operator takes the top two items, and the first one popped is the right operand. Getting that backwards breaks subtraction and division.
- RPN needs no brackets. Writing brackets into a postfix answer loses the mark it was testing.
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.
You've got it
- BNF production rules combine terminals (literal text) and non-terminals (rule names), and express repetition by recursion; a syntax diagram is the equivalent graphical form
- test a string by building it from the rules, and name the rule that fails when it is invalid
- infix needs precedence and brackets; RPN (postfix) puts the operator after its operands and needs neither
- convert with an operator stack, and evaluate by pushing operands and applying each operator to the top two, the first popped being the right-hand operand
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.