上下文无关文法

复习

　　上一章说，语法分析需要一种能描述程序结构的文法。这种文法叫上下文无关文法（CFG，Context-Free Grammar）。

　　回顾一下普通文法：产生式的左边可以是任意符号串。而上下文无关文法做了一个限制：每条产生式的左边，只能是一个单独的非终结符。

　　就这一条限制，让文法变得“上下文无关”：一个非终结符可以被改写成什么，只取决于它自己，而不取决于它周围出现的是什么。也就是说，改写它时不需要看“上下文”。

　　这个限制听起来是削弱，实际却恰到好处——因为程序语言的结构，大多是嵌套的，而这种嵌套正好适合用“一个成分可以不断包含更小的同类成分”的规则来描述。

　　看一个例子：

语句 → if 条件 语句
语句 → { 语句列表 }

　　第一条说“一个语句可以是 if 加条件再加一个语句”，第二条说“一个语句可以是一对花括号包起来的一串语句”。注意，两条规则的右边都出现了“语句”自己——规则是递归的，这正是它能描述任意深嵌套的原因。

　　再怎么深的 if 套 if、语句块套语句块，都会被这些规则一层层展开。有限的规则，描述无限深的嵌套——这正是文法的威力。

　　从起始符号出发，不断应用产生式，把非终结符替换成右边的符号串，这个过程叫推导。每一次推导，都可以画成一棵树：

　　推导完成时，叶子节点就是最终的词法单元，整棵树就是这串词的语法树。

　　所以，“判断合不合法”和“给出结构”，在文法的视角下其实是同一件事：合法，就是能被推导出来；结构，就是那棵推导树。

　　有了文法，下一步就是写一个程序，让它真的去“推导”——这就是语法分析器。下一章从最直观的一种写法开始。

思考题 1

　　上下文无关文法为什么适合描述程序语言？

思考题 2

　　“上下文无关”这个限定，具体指什么意思？

　　因为程序语言大量使用嵌套结构（括号、语句块、函数等），而上下文无关文法用递归规则恰好能描述任意深度的嵌套：一个成分可以由更小的同类成分构成，反复展开即可。

　　指每个非终结符能被改写成什么，只由它自身决定，不依赖它出现的位置或周围的符号。因为产生式左边只有一个非终结符，所以改写时无需检查上下文。

设计师 | 南国微雪