发布时间 : 星期日 文章上下文无关文法与语言更新完毕开始阅读
其中第一个产生式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的匹配1是采用
有时标记符
和是用来表示它们之间的文字是需要强调表示的，也就是要把它们改为斜体字或者其它合适的字体。
另外还有两个不匹配使用的标记符的例子：
和
有许多类的串和HTML文档相关。这里不把它们全都列出来了，而是仅仅给出那些对理解例5.22中的文本有关键作用的一些，并且对于其中的每一类都给出了一个具有描述性的名字的变元。
1. Text是任何有字面意义的字符串，也就是说它里面没有标记符。一个Text元素的
例子是图5.12（a）中的“Moldy bread.” 2. Char是任何只包含单个的、在HTML文本中合法字符的串。注意空格也算作字
符。 3. Doc代表文档，它是“Element”的序列，下面会给出Element的定义，并且这个
定义和Doc的定义是互归纳的。 4. Element或者是一个Text串，或者是一对互相匹配的标记符以及它们中间的文档，
或者是一个不匹配的标记符后面跟着一个文档。 5. ListItem是标记符
图5.13：HTML文法的一部分
图5.13是一个CFG，它描述了我们所介绍的HTML语言中的各种结构。在第1行中它说明了一个字符可以是“a”或者“A”或者很多其它可能的HTML字符集中的字符。第2行中它用两个产生式说明Text可以是空串或者任何由合法字符后面跟着一些文本构成的串。换句话说，Text就是零个或多个字符。注意虽然‘<’和‘>’可以分别用序列<；和>；来表示，但它们并不是合法字符。总之，绝对不可能在Text中找到标记符。 第3行是说一个文档是包含零个或多个“element”的序列。接着从第4行知道一个element或者是text，或者是强调了的文档，或者是段落开始符号后面跟着一个文档，或者是一个列表。另外对于HTML中其它的标记符也有相应的不同的Element的产生式。接着，第5行说一个ListItem是由标记符
HTML的有些方面的说明并不需要上下文无关文法的能力，在这些方面用正则表达式就足够了。比如，图5.13的第1行和第2行可以用正则表达式(a + A + ?)*来表示和Text表示的同样的语言。然而，HTML的有些方面确实需要CFG的能力。例如，每一对包含开