Grammar (BNF) and Reverse Polish Notation
Introduced| English | Meaning |
|---|---|
| postfix/ˈpəʊstfɪks/ | An expression notation that places each operator after its operands, such as 3 4 + for adding three and four. |
| precedence/ˈpresɪdəns/ | The rules determining which operators or actions are applied before others. |
| grammar/ˈɡræmə/ | The rules and patterns governing how words are formed and combined in a language. |
| syntax diagram/ˈsɪntæks ˈdaɪəɡræm/ | A diagram showing the permitted sequences and alternatives in a language's grammatical rules. |
| Reverse Polish Notation/rɪˈvɜːs ˈpəʊlɪʃ nəʊˈteɪʃn/ | Reverse Polish Notation |
| Backus-Naur Form/ˈbækəs nɔː fɔːm/ | A notation that defines a formal grammar using production rules connecting non-terminal symbols to permitted sequences of symbols. |
| production rules/prəˈdʌkʃn ruːlz/ | production rules |
| terminal/ˈtɜːmɪnl/ | A symbol that appears literally in strings of a formal language and is not expanded by a grammar rule. |
| non-terminal/nɒn ˈtɜːmɪnl/ | A symbol representing a grammatical category that can be expanded using production rules. |
| infix/ˈɪnfɪks/ | An expression notation that places an operator between its operands, such as 3 + 4. |
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:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
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.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
BNF builds rules from terminals and non-terminals (recursion gives repetition); RPN reorders an expression to drop brackets.
Why does the rule
Difficulty 1/5 · 100 coins + a small bonus on first completion today
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.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
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?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
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.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
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 * +.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
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.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
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.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
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.
Difficulty 3/5 · 200 coins + a small bonus on first completion today
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