Grammar (BNF) and Reverse Polish Notation · Gramática (BNF) e Notação Polonesa Reversa
| English | Português |
|---|---|
| postfix/ˈpəʊstfɪks/ | posfixo |
| precedence/ˈpresɪdəns/ | precedência |
| grammar/ˈɡræmə/ | gramática |
| syntax diagram/ˈsɪntæks ˈdaɪəɡræm/ | diagrama de sintaxe |
| Reverse Polish Notation/rɪˈvɜːs ˈpəʊlɪʃ nəʊˈteɪʃn/ | Notação Polonesa Reversa |
| Backus-Naur Form/ˈbækəs nɔː fɔːm/ | Forma Backus-Naur |
| production rules/prəˈdʌkʃn ruːlz/ | regras de produção |
| terminal/ˈtɜːmɪnl/ | terminal |
| non-terminal/nɒn ˈtɜːmɪnl/ | não 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.
A notação sem colchetes, e sem ambiguidade
- Escrever
3 + 4 * 2depende de uma convenção: que multiplicação tem precedência sobre adição. Mudar a convenção altera o significado da expressão. - Um lógico polonês, Jan Łukasiewicz, mostrou nos anos 1920 que, ao colocar o operador antes dos operandos, os colchetes tornam-se desnecessários. Invertendo, colocando o operador depois, obtém-se uma forma que uma máquina pode avaliar usando apenas uma pilha.
- É por isso que a Java Virtual Machine e a maioria dos interpretadores de bytecode funcionam em pós-fixação. Sem tabela de precedência, sem colchetes, sem ambiguidade.
- Esta lição ensina como a gramática 文法 de uma linguagem é escrita em BNF e como diagrama de sintaxe, e como a Notação Polonesa Reversa 逆波兰表示法 é convertida e avaliada.
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
- Uma gramática define quais sequências de tokens são programas válidos. Forma de Backus-Naur 巴科斯-诺尔范式 (BNF) a escreve como regras de produção 产生式:
<symbol> ::= alternative1 | alternative2 | ...
- Um símbolo terminal 终结符 é texto literal que aparece no programa. Um símbolo não-terminal 非终结符 é o nome de outra regra, escrito entre colchetes angulares.
<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: · Em BNF, um símbolo terminal é:
Terminals are literal tokens; non-terminals are names of other production rules. · Terminais são tokens literais; não-terminais são nomes de outras regras de produção.
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
Recursão é como BNF repete
- BNF não tem símbolo de "repita", então repetição é escrita definindo uma regra em termos dela mesma.
- Leia
<identifier> ::= <letter> | <identifier> <letter> | <identifier> <digit>como: um identificador é uma única letra, ou um identificador seguido por uma letra, ou um identificador seguido por um dígito. - Juntas, essas alternativas significam "uma letra seguida por qualquer número de letras ou dígitos", o que também explica por que um identificador não pode começar com um dígito: nenhuma alternativa permite isso.
- Um diagrama de sintaxe 语法图, ou diagrama de ferrovia, expressa as mesmas regras graficamente, com um loop onde BNF usa recursão. As duas notações são equivalentes.
O loop e a recursão dizem a mesma coisa
Match each grammar/notation term to its meaning. · Associe cada termo de gramática/notação ao seu significado.
BNF builds rules from terminals and non-terminals (recursion gives repetition); RPN reorders an expression to drop brackets. · BNF constrói regras a partir de terminais e não-terminais (recursão dá repetição); RPN reordenam uma expressão para eliminar parênteses.
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. · As alternativas juntas significam uma letra seguida de qualquer número de letras ou dígitos, e nenhuma alternativa permite começar com um 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".
Exemplo resolvido: teste uma string contra a gramática
- Usando as regras acima, quais de
count2,2countemy_varsão identificadores válidos? count2: válido. Construa-o:cé um<letter>, logo um<identifier>; adicioneo,u,n,tpela segunda alternativa; adicione2pela terceira.2count: inválido. Todas as alternativas começam com um<letter>ou com outro<identifier>, e nenhuma cadeia pode começar com um dígito.my_var: inválido, pois_não é um terminal em nenhuma regra aqui. Cite a regra que falha, não apenas "parece errado".
Using those rules, which strings are valid identifiers? Select all · todos that apply. · Usando essas regras, quais strings são identificadores válidos? Selecione todos os que se aplicam.
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. · Uma única letra é um identificador pela primeira alternativa. 2count não pode começar com um dígito, e _ não é um terminal em nenhuma regra aqui.
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.
Infixo e pós-fixo
- Infixo 中缀 coloca o operador entre seus operandos,
3 + 4 * 2, e portanto precisa de regras de precedência e colchetes para ser inequívoco. - Notação Polonesa Reversa, ou pós-fixo 后缀, coloca o operador depois dos operandos:
3 4 2 * +. Não precisa de nenhum. - A ordem em que os operadores aparecem na forma pós-fixo é a ordem em que são aplicados, exatamente o que uma máquina precisa 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.
Convertendo infixo para pós-fixo
- Use uma pilha de operadores. Escaneie da esquerda para a direita: envie um operando diretamente à saída; para um operador, primeiro pop para a saída quaisquer operadores empilhados de precedência maior ou igual 优先级, depois empilhe este.
- Empilhe um colchete de abertura. Em um colchete de fechamento, pop para a saída até o colchete de abertura correspondente, depois descarte o par.
- Ao final, pop tudo o que restar na pilha para a saída.
Operator precedence — what RPN removes · Precedência de operadores — o que a RPN elimina
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. · Na matemática infixa comum, × e ÷ têm precedência maior que + e −, então você deve aplicar as regras na ordem certa. A Notação Polonesa Reversa escreve os operandos primeiro (3 4 2 × + 1 −), fixando a ordem para que nenhuma regra de precedência seja necessária.
What is the RPN (postfix) form of the infix expression (3 + 4) * 2? · Qual é a forma RPN (pós-fixa) da expressão infixa (3 + 4) * 2?
The brackets force 3+4 first: 3 4 +, then multiply by 2: 3 4 + 2 *. · Os parênteses forçam 3+4 primeiro: 3 4 +, depois multiplicar por 2: 3 4 + 2 *.
Convert (A + B) * (C - D) to Reverse Polish Notation, using * for the multiplication. · Converta (A + B) * (C - D) para Notação Polonesa Reversa, usando * para a multiplicação.
Each bracket is converted in turn and the multiplication is popped last, so it appears at the end. No brackets survive. · Cada parêntese é convertido por sua vez e a multiplicação é empilhada por último, aparecendo no final. Nenhum parêntese sobrevive.
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.
Exemplo resolvido: converta, depois avalie
- Converta $(A + B) \times (C - D)$ para RPN. Empilhe
(; saiaA; empilhe+; saiaB; ao encontrar)pop de volta até o(correspondente, resultando emA B +. Empilhe×. O segundo colchete comporta-se idêntico, resultando emC D -. Ao final pop o×. Resultado:A B + C D - ×. - Avalie agora para $A=3, B=4, C=5, D=2$. Empilhe 3, empilhe 4;
+pop ambos e empilha 7. Empilhe 5, empilhe 2;-pop ambos e empilha 3.×pop 7 e 3 e empilha 21. - O operador sempre toma os dois superiores itens, e o primeiro popado é o operando direito. Isso importa para
-e/, onde a ordem muda a resposta.
Evaluate the RPN expression 3 4 2 * +. · Avalie a expressão RPN 3 4 2 * +.
Push 3, 4, 2; * pops 4 and 2 → 8; + pops 3 and 8 → 11. · Empilhe 3, 4, 2; * remove 4 e 2 → 8; + remove 3 e 8 → 11.
Reverse Polish Notation needs no brackets or precedence rules, and can be evaluated directly with a stack. · Notação Polonesa Reversa não precisa de parênteses ou regras de precedência, e pode ser avaliada diretamente com uma pilha.
Push operands; each operator pops its operands and pushes the result — which is exactly how a stack machine runs. · Empilhe operandos; cada operador remove seus operandos e empilha o resultado — que é exatamente como uma máquina de pilha opera.
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.
Avaliando com pilha, passo a passo
- Escaneie da esquerda para a direita: empilhe cada operando; ao encontrar um operador, pop os dois superiores, aplique-o e empilhe o resultado. Ao final, a pilha conterá um valor: a resposta.
| Token | Pilha após |
|---|---|
3 |
3 |
4 |
3, 4 |
2 |
3, 4, 2 |
* |
3, 8 |
+ |
11 |
- Esta é uma máquina de pilha: sem colchetes, sem tabela de precedência, sem lookahead. É assim que a JVM e muitos interpretadores de bytecode avaliam cada expressão.
When evaluating RPN, the first item popped from the stack is the left-hand operand of the operator. · Ao avaliar RPN, o primeiro item removido da pilha é o operando esquerdo do operador.
The first popped is the right-hand operand. It makes no difference for + and *, but reversing it breaks subtraction and division. · O primeiro removido é o operando direito. Não faz diferença para + e *, mas inverter isso quebra subtração e divisão.
Put the steps of evaluating 3 4 2 * + with a stack in order. · Coloque as etapas de avaliação de 3 4 2 * + com uma pilha em ordem.
Operands go on, each operator consumes the top two and leaves its result. No brackets and no precedence table are needed. · Operandos vão para cima, cada operador consome os dois de cima e deixa seu resultado. Sem parênteses e sem tabela de precedência necessárias.
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.
Marcas que escapam
- Um terminal é texto literal; um não-terminal nomeia outra regra. Não os troque.
- BNF expressa repetição por recursão. Se uma regra se refere a si mesma, diga isso e explique o que significa.
- Na avaliação, o operador toma os dois superiores itens, e o primeiro popado é o operando direito. Inverter isso quebra subtração e divisão.
- RPN não precisa de colchetes. Escrever colchetes na resposta pós-fixa perde o ponto que estava sendo testado.
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
Entendeu?
- Regras de produção BNF combinam terminais (texto literal) e não-terminais (nomes de regras), e expressam repetição por recursão; um diagrama de sintaxe é a forma gráfica equivalente
- teste uma string construindo-a das regras, e nomeie a regra que falha quando é inválido
- infixo precisa de precedência e colchetes; RPN (pós-fixo) coloca o operador depois dos operandos e não precisa de nenhum
- converta com uma pilha de operadores, e avalie empilhando operandos e aplicando cada operador aos dois superiores, o primeiro popado sendo o operando direito