文法（BNF）と逆ポーランド記法

The notation with no brackets, and no ambiguity

• Write 3 + 4 * 2 and 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.

Backus-Naur Form

• A grammar says which sequences of tokens are valid programs. Backus-Naur Form 巴科斯-诺尔范式 (BNF) writes it as production rules 产生式:

<symbol> ::= alternative1 | alternative2 | ...

• 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.

<digit>      ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<letter>     ::= a | b | c | … | z
<identifier> ::= <letter> | <identifier> <letter> | <identifier> <digit>

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

Worked example: test a string against the grammar

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.

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.

Worked example: convert, then evaluate

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.

• This is a stack machine: no brackets, no precedence table, no lookahead. It is how the JVM and many bytecode interpreters evaluate every expression.

Marks that slip away

You've got it