Grammar (BNF) and Reverse Polish Notation
| English | Chinese | Pinyin |
|---|---|---|
| grammar | 文法 | wén fǎ |
| Reverse Polish Notation | 逆波兰表示法 | nì bō lán biǎo shì fǎ |
| Backus-Naur Form | 巴科斯-诺尔范式 | bā kē sī - nuò ěr fàn shì |
| production rule | 产生式 | chǎn shēng shì |
| terminal | 终结符 | zhōng jié fú |
| non-terminal | 非终结符 | fēi zhōng jié fú |
| infix | 中缀 | zhōng zhuì |
| postfix | 后缀 | hòu zhuì |
Grammar 文法 and Reverse Polish Notation 逆波兰表示法
- A grammar defines which token sequences are valid programs.
- BNF and syntax diagrams are two equivalent ways to write one.
- Reverse Polish Notation writes expressions without brackets — perfect for a stack.
Backus-Naur Form 巴科斯-诺尔范式 (BNF)
- A production rule 产生式 lists the valid alternatives for a symbol:
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<identifier> ::= <letter> | <identifier> <letter> | <identifier> <digit>
- Terminal 终结符 symbols are literal text; non-terminal 非终结符 symbols are other rule names.
- The recursive
<identifier>rule means "a letter followed by any number of letters or digits". - A syntax (railroad) diagram shows the same rules graphically — the two notations are equivalent.
A syntax diagram for the identifier rule: a letter, then any number of letters or digits
In BNF, a terminal symbol is:
Terminals are literal tokens; non-terminals are names of other production rules.
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.
Reverse Polish Notation
- Infix 中缀: the operator is between operands (
3 + 4 * 2) — needs brackets and precedence. - RPN (postfix 后缀): the operator follows its operands (
3 4 2 * +) — no brackets needed. - Convert infix → RPN using an operator stack; e.g.
(3 + 4) * 2→3 4 + 2 *.
A context switch saves one process's state and loads another's
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 *.
Evaluating RPN with a stack
- Scan left to right: push each operand; on an operator, pop the top two, apply it, push the result.
| Token | Stack |
|---|---|
3 |
3 |
4 |
3, 4 |
2 |
3, 4, 2 |
* |
3, 8 |
+ |
11 |
- This needs no brackets and suits a stack machine — how the JVM and many bytecode interpreters work.
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.
You've got it
- BNF production rules use terminals (literal) and non-terminals (rule names); recursion gives repetition
- a syntax diagram is the graphical equivalent of BNF
- RPN (postfix) puts the operator after its operands — no brackets
- evaluate RPN with a stack: push operands, apply operators to the top two