Gramática (BNF) e Notação Polonesa Reversa
Introduzido| English | Significado |
|---|---|
| postfix/ˈpəʊstfɪks/ | pós-fixo |
| 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 de 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 |
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.
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>
Em BNF, um símbolo terminal é:
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Terminais são tokens literais; não-terminais são nomes de outras regras de produção.
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
Associe cada termo de gramática/notação ao seu significado.
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
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.
Por que a regra
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
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.
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".
Usando essas regras, quais strings são identificadores válidos? Selecione todos os que se aplicam.
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
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.
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.
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.
Precedência de operadores — o que a RPN elimina
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.
Qual é a forma RPN (pós-fixa) da expressão infixa (3 + 4) * 2?
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Os parênteses forçam 3+4 primeiro: 3 4 +, depois multiplicar por 2: 3 4 + 2 *.
Converta (A + B) * (C - D) para Notação Polonesa Reversa, usando * para a multiplicação.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Cada parêntese é convertido por sua vez e a multiplicação é empilhada por último, aparecendo no final. Nenhum parêntese sobrevive.
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.
Avalie a expressão RPN 3 4 2 * +.
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
Empilhe 3, 4, 2; * remove 4 e 2 → 8; + remove 3 e 8 → 11.
Notação Polonesa Reversa não precisa de parênteses ou regras de precedência, e pode ser avaliada diretamente com uma pilha.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Empilhe operandos; cada operador remove seus operandos e empilha o resultado — que é exatamente como uma máquina de pilha opera.
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.
Ao avaliar RPN, o primeiro item removido da pilha é o operando esquerdo do operador.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
O primeiro removido é o operando direito. Não faz diferença para + e *, mas inverter isso quebra subtração e divisão.
Coloque as etapas de avaliação de 3 4 2 * + com uma pilha em ordem.
Dificuldade 3/5 · Moedas 200 + pequeno bônus na primeira conclusão hoje
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.
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.
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