Grammar (BNF) and Reverse Polish Notation · 语法(BNF)与逆波兰记法
| English | 中文 | Pinyin · 拼音 |
|---|---|---|
| postfix/ˈpəʊstfɪks/ | 后缀 | hòu zhuì |
| precedence/ˈpresɪdəns/ | 优先级 | yōu xiān jí |
| grammar/ˈɡræmə/ | 文法 | wén fǎ |
| syntax diagram/ˈsɪntæks ˈdaɪəɡræm/ | 语法图 | yǔ fǎ tú |
| Reverse Polish Notation/rɪˈvɜːs ˈpəʊlɪʃ nəʊˈteɪʃn/ | 逆波兰表示法 | nì bō lán biǎo shì fǎ |
| Backus-Naur Form/ˈbækəs nɔː fɔːm/ | 巴科斯-诺尔范式 | bā kē sī - nuò ěr fàn shì |
| production rules/prəˈdʌkʃn ruːlz/ | 产生式 | chǎn shēng shì |
| terminal/ˈtɜːmɪnl/ | 终结符 | zhōng jié fú |
| non-terminal/nɒn ˈtɜːmɪnl/ | 非终结符 | fēi zhōng jié fú |
| infix/ˈɪnfɪks/ | 中缀 | 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.
没有括号、也没有歧义的记法
- 写下
3 + 4 * 2,你依赖的是一个约定:乘法比加法结合得更紧。换个约定,这个表达式的意思就变了。 - 波兰逻辑学家 Jan Łukasiewicz 在 1920 年代证明:把运算符放在操作数之前,括号就不必要了。把它反过来,放在操作数之后,就得到一种机器只用一个栈就能求值的形式。
- 这就是 Java 虚拟机和大多数字节码解释器采用后缀形式的原因。没有优先级表,没有括号,没有歧义。
- 这一课讲一门语言的文法(grammar)怎样写下来——用 BNF 和语法图——以及逆波兰表示法(Reverse Polish Notation)怎样转换和求值。
Backus-Naur Form
- A grammar says which sequences of tokens are valid programs. Backus-Naur Form 巴科斯-诺尔范式 (BNF) writes it as production rules 产生式:
- 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.
巴科斯-诺尔范式
- 文法规定哪些词法单元序列是合法的程序。巴科斯-诺尔范式(Backus-Naur Form,BNF)把它写成产生式(production rules):
<symbol> ::= alternative1 | alternative2 | ...
- 终结符(terminal)是出现在程序里的字面文本。非终结符(non-terminal)是另一条规则的名字,写在尖括号里。
<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: · 在 BNF 中,一个终结符是:
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
BNF 靠递归表达重复
- BNF 没有"重复"符号,所以重复要通过让一条规则用它自己来定义来表达。
- 把
<identifier> ::= <letter> | <identifier> <letter> | <identifier> <digit>读作:标识符是一个字母,或者一个标识符后跟一个字母,或者一个标识符后跟一个数字。 - 这几个选项合起来的意思是"一个字母后跟任意多个字母或数字",这也解释了标识符为什么不能以数字开头:没有任何一个选项允许。
- 语法图(syntax diagram),又叫铁路图,用图形表达同样的规则,BNF 用递归的地方它用一个环。两种记法是等价的。
那个环和那个递归说的是同一件事
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. · BNF 从终结符和非终结符构建规则(递归给出重复);RPN 重新排序一个表达式以去掉括号。
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".
例题:用文法检验一个字符串
- 用上面的规则,
count2、2count和my_var中哪些是合法的标识符? count2:合法。一步步构造:c是<letter>,所以是<identifier>;按第二个选项接上o、u、n、t;按第三个选项接上2。2count:不合法。每个选项要么从<letter>起,要么从另一个<identifier>起,没有任何链条能以数字开头。my_var:不合法,因为_不是这里任何规则中的终结符。要说出是哪条规则不满足,而不是只说"看着不对"。
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. · 按第一个选项,单个字母就是标识符。2count 不能以数字开头,而 _ 不是这里任何规则中的终结符。
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.
中缀与后缀
- 中缀(infix)把运算符放在操作数之间,
3 + 4 * 2,因此需要优先级规则和括号才能没有歧义。 - 逆波兰表示法,即后缀(postfix),把运算符放在操作数之后:
3 4 2 * +。它两样都不需要。 - 后缀形式中运算符出现的顺序就是它们被施行的顺序,而这正是需要告诉机器的东西。
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.
中缀转后缀
- 用一个运算符栈。从左向右扫描:操作数直接送到输出;遇到运算符,先把栈里优先级(precedence)更高或相等的运算符弹到输出,再把它压入。
- 左括号直接压栈。遇到右括号,弹出到输出直到匹配的左括号,然后把这对括号丢弃。
- 扫描结束后,把栈里剩下的全部弹到输出。
Operator precedence — what RPN removes · 运算符优先级——RPN 去掉了什么
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. · 在普通的中缀数学中,× 和 ÷ 比 + 和 − 结合得更紧,所以你必须以正确的顺序应用规则。逆波兰记法先写操作数(3 4 2 × + 1 −),固定顺序,所以不需要优先级规则。
What is the RPN (postfix) form of the infix expression (3 + 4) * 2? · 中缀表达式 (3 + 4) * 2 的 RPN(后缀)形式是什么?
The brackets force 3+4 first: 3 4 +, then multiply by 2: 3 4 + 2 *. · 括号强制先算 3+4:3 4 +,然后乘以 2:3 4 + 2 *。
Convert (A + B) * (C - D) to Reverse Polish Notation, using * for the multiplication. · 把 (A + B) * (C - D) 转成逆波兰表示法,乘法用 * 表示。
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.
例题:先转换,再求值
- *把 $(A + B) \times (C - D)$ 转成逆波兰式。*压入
(;输出A;压入+;输出B;遇)弹回到匹配的(,得到A B +。压入×。第二个括号同理,得到C D -。最后弹出×。结果:A B + C D - ×。 - *再对 $A=3, B=4, C=5, D=2$ 求值。*压 3、压 4;
+弹出两者并压入 7。压 5、压 2;-弹出两者并压入 3。×弹出 7 和 3 并压入 21。 - 运算符总是取栈顶两个,而先弹出的是右操作数。这对
-和/很要紧,顺序反了答案就变了。
Evaluate the RPN expression 3 4 2 * +. · 求值 RPN 表达式 3 4 2 * +。
Push 3, 4, 2; * pops 4 and 2 → 8; + pops 3 and 8 → 11. · 压入 3、4、2;* 弹出 4 和 2 → 8;+ 弹出 3 和 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.
用栈逐步求值
- 从左向右扫描:每个操作数压栈;遇到运算符就弹出栈顶两个,施行它,再把结果压栈。结束时栈里剩一个值:答案。
| 词法单元 | 之后的栈 |
|---|---|
3 |
3 |
4 |
3, 4 |
2 |
3, 4, 2 |
* |
3, 8 |
+ |
11 |
- 这就是栈机:没有括号、没有优先级表、不用向前看。JVM 和许多字节码解释器就是这样对每个表达式求值的。
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. · 把用栈对 3 4 2 * + 求值的步骤按顺序排列。
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.
容易丢掉的分
- 终结符是字面文本;非终结符是另一条规则的名字。不要互换。
- BNF 用递归表达重复。如果一条规则引用了它自己,要说出来并说明它的含义。
- 求值时运算符取栈顶两个,而先弹出的是右操作数。弄反了,减法和除法就错了。
- 逆波兰式不需要括号。在后缀答案里写上括号,恰好丢掉它要考的那一分。
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
你掌握了
- BNF 产生式把终结符(字面文本)和非终结符(规则名)组合起来,并用递归表达重复;语法图是等价的图形形式
- 检验字符串时用规则一步步把它构造出来,不合法时说出是哪条规则不满足
- 中缀需要优先级和括号;**逆波兰式(后缀)**把运算符放在操作数之后,两样都不需要
- 用运算符栈转换,求值时压入操作数并对栈顶两个施行每个运算符,先弹出的是右操作数