上下文无关文法与语言(5)

其中第一个产生式B?BB是说：把两个括号匹配的串连接起来得到的串仍然是括号匹配的。这样的断言是有道理的，因为我们可以分别对这两个串进行匹配。第二个产生式B?(B)是说：把一个括号匹配的串用一对括号括起来所得到的串仍然是括号匹配的。同样这样的断言也是有道理的，因为如果中间的串是匹配的，那么把它里面所有的括号都去掉后就只剩下最外边的一对括号了，而此时它们仍然是匹配的。第三个产生式B?ε是基础，它是说空串是括号匹配的。

上面这段非形式化的论证应该能够使人相信Gbal产生的确实是所有的括号匹配的串。反过来的方向需要证明——也就是每个括号匹配的串都能够由该文法产生。不过，这个证明并不难，只需要对括号匹配的串的长度进行归纳就行了，因此我们把该证明的细节留给读者作为练习。

前边曾经提到过所有括号匹配的串组成的语言不是正则语言，现在应该来证明这件事情了。如果L(Gbal)是正则的，那么根据正则语言的泵引理，一定存在一个和该语言相关的常数n。考虑括号匹配的串w=(n)n，也就是n个左括号后面跟着n个右括号。如果根据泵引理把w打断为w=xyz，那么y只包含左括号，因此串xz中右括号就比左括号多了，因而xz不是括号匹配的，这跟括号匹配的串的语言是正则语言的假设相矛盾。 □

当然，除了括号之外，编程语言中还包含许多其它的东西，但是括号确实是算术或条件表达式中一个基本的组成部分。虽然图5.2中的文法中只有两个运算符：加号和乘号，但它仍然是算术表达式的非常典型的结构。并且它包含了详细的标识符的结构，该结构使用第3.3.2节中提到的编译器的词法分析部分来进行处理可能是比较适合的。然而，图5.2中描述的这个语言也不是正则的。例如，在这个语言中，(na)n是合法的表达式。可以通过泵引理来证明：如果这个语言式正则的，那么去掉一些左括号同时保持a和所有的右括号不动，这样得到的串应该仍然是表达式，然而实际上不是。

典型的编程语言中有很多方面跟括号匹配很相似。一般来说它们本身也是括号，不过可以在各种类型的表达式中。例如一个代码块的开始和结束，就像Pascal语言中的begin和end，或者C语言中的花括号{…}。也就是说如果把C程序中的花括号替换为圆括号，即把{换为(，把}换为) ，这样所得到的串一定是括号匹配的。

有时会出现另外一种相关的情况，只不过在这时“括号”匹配时不考虑未被匹配的左括号。比如C语言中处理if和else的时候，一个if子句可以不和else子句匹配而单独存在，也可以和一个else子句匹配。一个生成所有这样可能的if和else的序列的文法是：（其中if和else分别用i和e来代替）

S ? ε| SS | iS | iSe

例如，ieie, iie和iei都是可能的if和else的序列，而且都是用上面的文法生成的。也有一些不能用该文法生成的非法串，比如ei和ieeii。

对于一个由i和e组成的串是否能有该文法生成，有一个简单的测试方法——只需要从左边开始依次检查每个e即可，具体方法如下（该方法正确性的证明留给读者作为练习）：在这个e的左边找到第一个i，如果找不到的话，那么这个串就无法通过该测试，因而得出它不在该语言中的结论。如果找到了这个i，那么就把它和正在被检查的e一起去掉，然后继续重复这个过程：如果没有e了，那么这个串就通过了这个测试，因而得出它在该语言中的结论。如果还有e，那么就继续对最左边的e进行上面的检查过程。 例5.20：考虑串iee，第一个e和是它左边的i匹配，把它们去掉后该串变成了e。由于还有e，因此我们得继续进行检查，但这次没有i在它左边了，因此检查测试失败了，所以iee不在该语言中。注意这个结论是正确的，因为在C程序中else的个数不可能比if多。

再来一个例子，考虑iieie。第一个e是跟它左边的i匹配的，把它们去掉后还剩下iie。这个e继续和它左边的i匹配，再把它们去掉后还剩下i，这时没有e了，因此测试成功通过。这个结论也是有道理的，因为iieie所对应的C程序的结构就像图5.10中的结构。事实上，这个匹配算法同时也能告诉我们（及编译器）每个if所匹配的的else（如果有的话）到底是哪个，而这一点是很重要的，因为编译器需要创建程序员所设计的控制流逻辑。□

if （条件）{

…

if （条件）语句； else 语句； …

if （条件）语句； else 语句； … }

图5.10：一个if-else结构，其中的两个else分别和它们前面的if匹配，第一个if没有else和它匹配。

5.3.2 语法分析器生成器YACC

语法分析器是从源程序中创建语法分析树的函数，它的生成过程已经被所有的UNIX系统中都有的YACC命令所规范化了。YACC的输入是一个CFG，并且该CFG的具体表示方法和我们这里所用到的只在具体细节上有所不同。每个产生式都和一个动作相关联，而这个动作是一个C代码的片段。当语法分析树的一个节点（和它的子节点）被创建时，它们相应产生式所对应的这段C代码就被执行。一般的，动作是用来构造这个节点的代码，尽管在一些YACC应用中语法分析树实际上并没有真正的被构造出来，这时该动作就做一些别的事情，比如生成一段目标代码。

例5.21：图5.11是一个YACC中的CFG的例子。这个文法和图5.2中的是一样的。我们把动作部分省略掉了，展现出来的仅仅是它们（需要的）花括弧和它们在YACC输入中的位置。

图5.11：一个YACC中的文法的例子

注意下面是YACC和我们文法表示法的一些对应部分：

? 冒号被用来作为产生式的符号，我们的是?

? 所有具有同样的头的产生式都被编为一组，并且它们的体互相之间用竖线分隔开

来。我们也使用这种表示法，但不是必须的。 ? 同一个头所对应的体的列表靠一个分号来结束。我们没有使用这样的结束符号。 ? 终结符都用单引号引起来。很多字符都能被一对单引号引起来。虽然我们没有展

现出来，YACC允许它的用户自己定义终结符号。在源程序中出现的这些终结符号能被词法分析器检测和分离出来，并且通过它的返回值传递给语法分析器。 ? 没有被引起来的字母和数字组成的串是变元名。我们已经通过这个方法来赋予上

面两个变元更加有意义的名字——Exp和Id——虽然它们也能用E和I 来表示。

5.3.3 标记语言

下面我们将会考虑一系列的“语言”，它们叫做标记语言。这些语言中的“串”是使用了一些该语言中的标记符（tags）的文档。标记符告诉我们一些该文档中不同串的语义。

有一个你可能最熟悉的标记语言：HTML（超文本标记语言，HyperText Markup Language）。这个语言有两个主要的功能：在文档之间建立链接和定义一个文档的格式（“样子”）。我们只给出一个关于HTML结构的简单看法，但是下面的例子能够展示它的结构，也能够展示一个CFG是怎样描述合法的HTML文档的，还能够展示CFG是怎样在文档的处理过程（即文档在显示器和打印机上的显示）中起到引导作用的。

我讨厌的东西： 1. 发霉的面包。

2. 在快车道上开的很慢的人。

（a） 显示的文本

我讨厌的东西：

发霉的面包。

在快车道上开的很慢的人。

（b） HTML源码

图5.12：一个HTML文档和它的印刷版本

例5.22：图5.12（a）展示了一段文字，它包括了一个项目列表，图5.12（b）展示了它在HTML中的表达。注意从图5.12（b）可以看出HTML是由普通的问题掺杂着一些标记符组成的。对某个标记符x的匹 …… 此处隐藏：4196字，全部文档内容请下载后查看。喜欢就下载吧 ……