Grammar (BNF) and Reverse Polish Notation
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.
Practice
In BNF, a terminal symbol is:
Terminals are literal tokens; non-terminals are names of other production rules.
Practice
A recursive BNF rule (a symbol defined partly in terms of itself) is used to express:
Recursion lets a rule match an arbitrarily long sequence, like an identifier of many characters.
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 *.
Practice
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.
Practice
Evaluate the RPN expression 3 4 2 * +.
Push 3, 4, 2; * pops 4 and 2 → 8; + pops 3 and 8 → 11.
Practice
A key advantage of RPN is that it:
RPN removes the need for brackets and precedence at evaluation time, and maps directly onto a stack machine.
You've got it
Key idea
- 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