Grammar (BNF) and Reverse Polish Notation
| English | Chinese | Pinyin |
|---|---|---|
| postfix | 后缀 | hòu zhuì |
| precedence | 优先级 | yōu xiān jí |
| grammar | 文法 | wén fǎ |
| syntax diagram | 语法图 | yǔ fǎ tú |
| Reverse Polish Notation | 逆波兰表示法 | nì bō lán biǎo shì fǎ |
| Backus-Naur Form | 巴科斯-诺尔范式 | bā kē sī - nuò ěr fàn shì |
| production rules | 产生式 | chǎn shēng shì |
| terminal | 终结符 | zhōng jié fú |
| non-terminal | 非终结符 | fēi zhōng jié fú |
| infix | 中缀 | zhōng zhuì |
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.
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>
In BNF, a terminal symbol is:
Terminals are literal tokens; non-terminals are names of other production rules.
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
Match each grammar/notation term to its meaning.
BNF builds rules from terminals and non-terminals (recursion gives repetition); RPN reorders an expression to drop brackets.
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.
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".
Using those rules, which strings are valid identifiers? Select all that apply.
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.
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.
Operator precedence — what RPN removes
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.
What is the RPN (postfix) form of the infix expression (3 + 4) * 2?
The brackets force 3+4 first: 3 4 +, then multiply by 2: 3 4 + 2 *.
Convert (A + B) * (C - D) to Reverse Polish Notation, using * for the multiplication.
Each bracket is converted in turn and the multiplication is popped last, so it appears at the end. No brackets survive.
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.
Evaluate the RPN expression 3 4 2 * +.
Push 3, 4, 2; * pops 4 and 2 → 8; + pops 3 and 8 → 11.
Reverse Polish Notation needs no brackets or precedence rules, and can be evaluated directly with a stack.
Push operands; each operator pops its operands and pushes the result — which is exactly how a stack machine runs.
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.
When evaluating RPN, the first item popped from the stack is the left-hand operand of the operator.
The first popped is the right-hand operand. It makes no difference for + and *, but reversing it breaks subtraction and division.
Put the steps of evaluating 3 4 2 * + with a stack in order.
Operands go on, each operator consumes the top two and leaves its result. No brackets and no precedence table are needed.
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.
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