| English | 释义 | 拼音 |
|---|---|---|
| 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ì |
没有括号、也没有歧义的记法
- 写下
3 + 4 * 2,你依赖的是一个约定:乘法比加法结合得更紧。换个约定,这个表达式的意思就变了。 - 波兰逻辑学家 Jan Łukasiewicz 在 1920 年代证明:把运算符放在操作数之前,括号就不必要了。把它反过来,放在操作数之后,就得到一种机器只用一个栈就能求值的形式。
- 这就是 Java 虚拟机和大多数字节码解释器采用后缀形式的原因。没有优先级表,没有括号,没有歧义。
- 这一课讲一门语言的文法(grammar)怎样写下来——用 BNF 和语法图——以及逆波兰表示法(Reverse Polish Notation)怎样转换和求值。
巴科斯-诺尔范式
- 文法规定哪些词法单元序列是合法的程序。巴科斯-诺尔范式(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>
在 BNF 中,一个终结符是:
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
终结符是字面的记号;非终结符是其他产生式规则的名字。
BNF 靠递归表达重复
- BNF 没有"重复"符号,所以重复要通过让一条规则用它自己来定义来表达。
- 把
<identifier> ::= <letter> | <identifier> <letter> | <identifier> <digit>读作:标识符是一个字母,或者一个标识符后跟一个字母,或者一个标识符后跟一个数字。 - 这几个选项合起来的意思是"一个字母后跟任意多个字母或数字",这也解释了标识符为什么不能以数字开头:没有任何一个选项允许。
- 语法图(syntax diagram),又叫铁路图,用图形表达同样的规则,BNF 用递归的地方它用一个环。两种记法是等价的。

那个环和那个递归说的是同一件事
把每个语法/记法术语与它的含义配对。
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
BNF 从终结符和非终结符构建规则(递归给出重复);RPN 重新排序一个表达式以去掉括号。
规则
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
这些选项合起来意味着一个字母后跟任意多个字母或数字,而且没有一个选项允许以数字开头。
例题:用文法检验一个字符串
- 用上面的规则,
count2、2count和my_var中哪些是合法的标识符? count2:合法。一步步构造:c是<letter>,所以是<identifier>;按第二个选项接上o、u、n、t;按第三个选项接上2。2count:不合法。每个选项要么从<letter>起,要么从另一个<identifier>起,没有任何链条能以数字开头。my_var:不合法,因为_不是这里任何规则中的终结符。要说出是哪条规则不满足,而不是只说"看着不对"。
用这些规则,哪些字符串是合法的标识符?选出所有适用的。
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
按第一个选项,单个字母就是标识符。2count 不能以数字开头,而 _ 不是这里任何规则中的终结符。
中缀与后缀
- 中缀(infix)把运算符放在操作数之间,
3 + 4 * 2,因此需要优先级规则和括号才能没有歧义。 - 逆波兰表示法,即后缀(postfix),把运算符放在操作数之后:
3 4 2 * +。它两样都不需要。 - 后缀形式中运算符出现的顺序就是它们被施行的顺序,而这正是需要告诉机器的东西。
中缀转后缀
- 用一个运算符栈。从左向右扫描:操作数直接送到输出;遇到运算符,先把栈里优先级(precedence)更高或相等的运算符弹到输出,再把它压入。
- 左括号直接压栈。遇到右括号,弹出到输出直到匹配的左括号,然后把这对括号丢弃。
- 扫描结束后,把栈里剩下的全部弹到输出。
运算符优先级——RPN 去掉了什么
在普通的中缀数学中,× 和 ÷ 比 + 和 − 结合得更紧,所以你必须以正确的顺序应用规则。逆波兰记法先写操作数(3 4 2 × + 1 −),固定顺序,所以不需要优先级规则。
中缀表达式 (3 + 4) * 2 的 RPN(后缀)形式是什么?
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
括号强制先算 3+4:3 4 +,然后乘以 2:3 4 + 2 *。
把 (A + B) * (C - D) 转成逆波兰表示法,乘法用 * 表示。
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
两个括号依次转换,乘号最后弹出,所以出现在末尾。括号一个都不保留。
例题:先转换,再求值
- *把 $(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。 - 运算符总是取栈顶两个,而先弹出的是右操作数。这对
-和/很要紧,顺序反了答案就变了。
求值 RPN 表达式 3 4 2 * +。
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
压入 3、4、2;* 弹出 4 和 2 → 8;+ 弹出 3 和 8 → 11。
逆波兰记法不需要括号或优先级规则,并且能用一个栈直接求值。
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
压入操作数;每个运算符弹出它的操作数并压入结果——这正是一个栈机运行的方式。
用栈逐步求值
- 从左向右扫描:每个操作数压栈;遇到运算符就弹出栈顶两个,施行它,再把结果压栈。结束时栈里剩一个值:答案。
| 词法单元 | 之后的栈 |
|---|---|
3 |
3 |
4 |
3, 4 |
2 |
3, 4, 2 |
* |
3, 8 |
+ |
11 |
- 这就是栈机:没有括号、没有优先级表、不用向前看。JVM 和许多字节码解释器就是这样对每个表达式求值的。
对逆波兰式求值时,从栈顶先弹出的是运算符的左操作数。
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
先弹出的是右操作数。这对 + 和 * 没影响,但弄反了会让减法和除法出错。
把用栈对 3 4 2 * + 求值的步骤按顺序排列。
难度 3/5 · 今日首次完成可获 200 金币及少量额外奖励
操作数入栈,每个运算符消耗栈顶两个并留下结果。不需要括号,也不需要优先级表。
容易丢掉的分
- 终结符是字面文本;非终结符是另一条规则的名字。不要互换。
- BNF 用递归表达重复。如果一条规则引用了它自己,要说出来并说明它的含义。
- 求值时运算符取栈顶两个,而先弹出的是右操作数。弄反了,减法和除法就错了。
- 逆波兰式不需要括号。在后缀答案里写上括号,恰好丢掉它要考的那一分。
你掌握了
- BNF 产生式把终结符(字面文本)和非终结符(规则名)组合起来,并用递归表达重复;语法图是等价的图形形式
- 检验字符串时用规则一步步把它构造出来,不合法时说出是哪条规则不满足
- 中缀需要优先级和括号;**逆波兰式(后缀)**把运算符放在操作数之后,两样都不需要
- 用运算符栈转换,求值时压入操作数并对栈顶两个施行每个运算符,先弹出的是右操作数