China-pub.com 下载 第3章 上下文无关文法及分析 本章要点 ·分析过程 ·扩展的表示法：EBNF和语法图 ·上下文无关文法 ·上下文无关语言的形式特性 ·分析树与抽象语法树 ·TNY语言的语法 ·二义性 分析的任务是确定程序的语法，或称作结构，也正是这个原因，它又被称作语法分析 (syntax analysis)。程序设计语言的语法通常是由上下文无关(context--free grammar)的文法规 则(grammar rule)给出，其方式同扫描程序识别的由正则表达式提供的记号的词法结构相类 似。上下文无关文法的确利用了与正则表达式中极为类似的命名惯例和运算。二者的主要区别 在于上下文无关文法的规则是递归的(recursive)。例如一般来说，if语句的结构应允许可其中 嵌套其他的语句，而在正则表达式中却不能这样做。这个区别造成的影响很大。由上下文无 关文法识别的结构类比由正则表达式识别的结构类大大增多了。用作识别这些结构的算法也与 扫描算法差别很大，这是因为它们必须使用递归调用或显式管理的分析栈。用作表示语言语义 结构的数据结构现在也必须是递归的，而不再是线性的（如同用于词法和记号中的一样）了。 经常使用的基本结构是一类树，称作分析树(parse tree)或语法树(syntax tree). 同第2章相似，在学习分析算法和如何利用这些算法进行真正的分析之前需要先学习上下 文无关文法的理论，但是又与在扫描程序中的情形不同一一其中主要只有一种算法方法（表示 为有穷自动机)，分析涉及到要在许多属性和能力截然不同的方法中做出选择。按照它们构造 分析树或语法树的方式，算法大致可分为两种：自顶向下分析(top-down parsing)和由底向 上分析(bottom-up parsing)。对这些分析方法的详细讨论将放到以后的章节中，本章只给出分 析过程的一般性描述，之后还要学习上下文无关文法的基础理论。最后一节则从一个上下文无 关文法的角度给出TNY语言的文法。对上下文无关文法理论和语法树熟悉的读者可以跳过本 章中间的某些内容（或将其作为复习）。 3.1分析过程 分析程序的任务是从由扫描程序产生的记号中确定程序的语法结构，以及或隐式或显式地 构造出表示该结构的分析树或语法树。因此，可将分析程序看作一个函数，该函数把由扫描程 序生成的记号序列作为输入，并生成语法树作为它的输出： 记号序列分析程序、酒法树 记号序列通常不是显式输入参数，但是当分析过程需要下一个记号时，分析程序就调用诸如 getToken的扫描程序过程以从输入中获得它。因此，编译器的分析步骤可减为对分析程序的 个调用，如下所示： syntaxTree parse (
下载 第3章 上下文无关文法及分析 本章要点 • 分析过程 • 扩展的表示法：E B N F和语法图 • 上下文无关文法 • 上下文无关语言的形式特性 • 分析树与抽象语法树 • TINY语言的语法 • 二义性 分析的任务是确定程序的语法，或称作结构，也正是这个原因，它又被称作语法分析 （syntax analysis）。程序设计语言的语法通常是由上下文无关（ context-free grammar）的文法规 则（grammar rule）给出，其方式同扫描程序识别的由正则表达式提供的记号的词法结构相类 似。上下文无关文法的确利用了与正则表达式中极为类似的命名惯例和运算。二者的主要区别 在于上下文无关文法的规则是递归的（r e c u r s i v e）。例如一般来说，if 语句的结构应允许可其中 嵌套其他的i f语句，而在正则表达式中却不能这样做。这个区别造成的影响很大。由上下文无 关文法识别的结构类比由正则表达式识别的结构类大大增多了。用作识别这些结构的算法也与 扫描算法差别很大，这是因为它们必须使用递归调用或显式管理的分析栈。用作表示语言语义 结构的数据结构现在也必须是递归的，而不再是线性的（如同用于词法和记号中的一样）了。 经常使用的基本结构是一类树，称作分析树（parse tree）或语法树（syntax tree）。 同第2章相似，在学习分析算法和如何利用这些算法进行真正的分析之前需要先学习上下 文无关文法的理论，但是又与在扫描程序中的情形不同——其中主要只有一种算法方法（表示 为有穷自动机），分析涉及到要在许多属性和能力截然不同的方法中做出选择。按照它们构造 分析树或语法树的方式，算法大致可分为两种：自顶向下分析（ top-down parsing）和由底向 上分析（bottom-up parsing）。对这些分析方法的详细讨论将放到以后的章节中，本章只给出分 析过程的一般性描述，之后还要学习上下文无关文法的基础理论。最后一节则从一个上下文无 关文法的角度给出T I N Y语言的文法。对上下文无关文法理论和语法树熟悉的读者可以跳过本 章中间的某些内容（或将其作为复习）。 3.1 分析过程 分析程序的任务是从由扫描程序产生的记号中确定程序的语法结构，以及或隐式或显式地 构造出表示该结构的分析树或语法树。因此，可将分析程序看作一个函数，该函数把由扫描程 序生成的记号序列作为输入，并生成语法树作为它的输出： 记号序列 语法树 记号序列通常不是显式输入参数，但是当分析过程需要下一个记号时，分析程序就调用诸如 g e t T o k e n的扫描程序过程以从输入中获得它。因此，编译器的分析步骤可减为对分析程序的 一个调用，如下所示： syntaxTree = parse(); 分析程序
70 翁译原理及实践 China-pub.co 下载 在单遍编译中，分析程序合并编译器中所有的其他阶段，这还包括了代码生成，因此也就 不需要构造显式的语法树了（分析步骤本身隐式地表示了语法树），由此就发生了一个 parse(): 调用。在编译器中更多的是多遍，此时后面的遍将语法树作为它们的输入。 语法树的结构在很大程度上依赖于语言特定的语法结构。这种树通常被定义为动态数据结 构，该结构中的每个节点都由一个记录组成，而这个记录的域包括了编译后面过程所需的特性 (即：并不是那些由分析程序计算的特性)。节点结构通常是节省空间的各种记录。特性域还可 以是在需要时动态分配的结构，它就像一个更进一步节省空间的工具。 在分析程序中有一个比在扫描程序中更为复杂的问题，这就是对于错误的处理。在扫描程 序中，如果遇到的一个字符是不正规记号的一部分，那么它只需生成一个出错记号并消耗掉这 个讨厌的字符即可（在某种意义上，通过生成一个出错记号，扫描程序就克服了发生在分析程 序上的困难)。但对于分析程序而言，它必须不仅报告一个出错信息，而且还须从错误状态恢 复(recover)并继续进行分析（去找到尽可能多的错误）。分析程序有时会执行错误修复 尽可能接近真正错误时继续分析下去。由于要到错误真正地已经发生了分析程序才会发现它， 所以做到这一点并不简单。由于错误恢复技术依赖于所使用的特定分析算法，所以本章先就不 学习它了。 3.2上下文无关文法 上下文无关文法说明程序设计语言的语法结构。除了上下文无关文法涉及到了递归规则之 外，这样的说明与使用正则表达式的词法结构的说明十分类似。例如在一个运算中，就可以使 用带有加法、减法和乘法的简单整型算术表达式。这些表达式可由下面的文法给出 exp-exp op expl (exp)I number 叩+1-1* 3.2.1与正则表达式比较 在第2章中为number?给出的正则表达式规则如下所示 number=digit digit d1g1t=0111213141516171819 试与上面上下文无关文法的样本作一比较。基本正则表达式规则有3种运算：选择（由竖 线元字符表示)、并置（不带元符号）以及重复（由星号元符号提供）。此外还可用等号来表示 正则表达式的名字定义，此时名字用斜体书写以示与真正字符序列的区别。 文法规则使用相似的表示法。名字用斜体表示（但它是一种不同的字体，所以可与正则表 达式相区分)。竖线仍表示作为选择的元符号。并置也用作一种标准运算。但是这里没有重复 的元符号（如正则表达式中的星号◆），稍后还会再讲到它。表示法中的另一个差别是现在用箭 头符号“一”代替了等号来表示名字的定义。这是由于现在的名字不能简单地由其定义取代， 而需要更为复杂的定义过程来表示，这是由定义的递归本质决定的⊙。在我们的示例中，x即的 日参见本章后面的语法规则和等式
在单遍编译中，分析程序合并编译器中所有的其他阶段，这还包括了代码生成，因此也就 不需要构造显式的语法树了（分析步骤本身隐式地表示了语法树），由此就发生了一个 p a r s e ( ) ; 调用。在编译器中更多的是多遍，此时后面的遍将语法树作为它们的输入。 语法树的结构在很大程度上依赖于语言特定的语法结构。这种树通常被定义为动态数据结 构，该结构中的每个节点都由一个记录组成，而这个记录的域包括了编译后面过程所需的特性 （即：并不是那些由分析程序计算的特性）。节点结构通常是节省空间的各种记录。特性域还可 以是在需要时动态分配的结构，它就像一个更进一步节省空间的工具。 在分析程序中有一个比在扫描程序中更为复杂的问题，这就是对于错误的处理。在扫描程 序中，如果遇到的一个字符是不正规记号的一部分，那么它只需生成一个出错记号并消耗掉这 个讨厌的字符即可（在某种意义上，通过生成一个出错记号，扫描程序就克服了发生在分析程 序上的困难）。但对于分析程序而言，它必须不仅报告一个出错信息，而且还须从错误状态恢 复（ r e c o v e r）并继续进行分析（去找到尽可能多的错误）。分析程序有时会执行错误修复 （error repair），此时它从提交给它的非正确的版本中推断出一个可能正确的代码版本（这通常 是在简单情况下才发生的）。错误恢复的一个尤为重要的方面是有意义的错误信息报告以及在 尽可能接近真正错误时继续分析下去。由于要到错误真正地已经发生了分析程序才会发现它， 所以做到这一点并不简单。由于错误恢复技术依赖于所使用的特定分析算法，所以本章先就不 学习它了。 3.2 上下文无关文法 上下文无关文法说明程序设计语言的语法结构。除了上下文无关文法涉及到了递归规则之 外，这样的说明与使用正则表达式的词法结构的说明十分类似。例如在一个运算中，就可以使 用带有加法、减法和乘法的简单整型算术表达式。这些表达式可由下面的文法给出： e x p→exp op exp | (e x p) | n u m b e r op → + | - | * 3.2.1 与正则表达式比较 在第2章中为n u m b e r给出的正则表达式规则如下所示： number = digit digit* digit = 0|1|2|3|4|5|6|7|8|9 试与上面上下文无关文法的样本作一比较。基本正则表达式规则有 3种运算：选择（由竖 线元字符表示）、并置（不带元符号）以及重复（由星号元符号提供）。此外还可用等号来表示 正则表达式的名字定义，此时名字用斜体书写以示与真正字符序列的区别。 文法规则使用相似的表示法。名字用斜体表示（但它是一种不同的字体，所以可与正则表 达式相区分）。竖线仍表示作为选择的元符号。并置也用作一种标准运算。但是这里没有重复 的元符号（如正则表达式中的星号*），稍后还会再讲到它。表示法中的另一个差别是现在用箭 头符号“→”代替了等号来表示名字的定义。这是由于现在的名字不能简单地由其定义取代， 而需要更为复杂的定义过程来表示，这是由定义的递归本质决定的 。在我们的示例中，e x p的 7 0 编译原理及实践 下载 参见本章后面的语法规则和等式
China-pub.Com 71 下载上 第3章上下文无关文法及分析 规则是递归的，其中名字cxp出现在箭头的右边 读者还要注意到文法规则将正则表达式作为部件。在xp规则和op规则中，实际有6个表示 语言中记号的正则表达式。其中5个是单字符记号：+、-、*、（和），另一个是名字number 记号的名字表示数字序列。 与这个例子的格式相类似的文法规则最初是用在A1go60语言的描述中。其表示法是由 John Backus为Algole6O报告开发，之后又由Peter Naur更新，因此这个格式中的文法通常被称作 Backus-Naur范式(Backus-Naur form)或BNE文法. 3.2.2上下文无关文法规则的说明 同正则表达式类似，文法规则是定义在一个字母表或符号集之上。在正则表达式中，这些 符号通常就是字符，而在文法规则中，符号通常是表示字符串的记号。在前一章中，我们利用 C中的枚举类型定义了在扫描程序中的记号：本章为了避免涉及到特定实现语言（例如C)中 表示记号的细节，就使用了正则表达式本身来表示记号。此时的记号就是一个固定的符号，如 同在保留字w11。中或诸如+或：=这样的特殊符号一样，使用在第2章曾用到的代码字体书写 串本身。对于作为表示多于 一个串的标识符和数的记号来说，代码字体为斜体，这就同假设这 个记号是正则表达式的名字（这是它经常的表示）一样。例如，将TNY语言的记号字母表表 示为集合 (if,then,else,end,repeat,until,read,write. identifier,number,+,-,./=,<(,),:= 而不是记号集（如在TNY扫描程序中定义的一样）： (IF,THEN,ELSE,END,REPEAT,UNTIL,READ,WRITE,ID,NUM, PLUS,MINUS,TIMES,OVER,EQ,LT,LPAREN,RPAREN,SEMI,ASSIGN 假设有一个字母表，BNF中的上下文无关文法规则(context---free grar mmar rule in BNF)是 由符号串组成。第1个符号是结构名字，第2个符号是元字符一，这个符号之后是一个符号串， 该串中的每个符号都是字母表中的一个符号（即一个结构的名字）或是元符号」。 在非正式术语中，对BNF的文法规则解释如下：规则定义了在箭头左边名字的结构。这个 结构被定义为由被竖线分隔开的选择右边的一个选项组成。每个选项中的符号序列和结构名字 定义了结构的布局。例如，前例中的文法规则： exp-exp op exp (exp)number p→+1-1 第1个规则定义了一个表达式结构（用名字xp)由带有一个算符和另一个表达式的表达式， 或一个位于括号之中的表达式，或一个数组成。第2个规则定义一个算符（利用名字即）由符 号+、-或*构成。 这里所用的元符号和惯例与广泛使用中的类似，但读者应注意到这些惯例并没有统一的 标准。实际上，用以代替箭头元符号一的通常有=（等号）小、：（冒号）和：=（双冒号等号） 在普通文本文件中，找到能替代斜体用法的方法也很有必要，通常的办法是在结构名字前后 加尖括号<…>并将原来斜体的记号名字大写：因此，使用不同的惯例，上面的文法规则就可 变为： <exp>:=<exp><op><exp>I <exp>I NUMBER <0p>::=+1-1t 每一个作者都还有这些表示法的其他变形。本节后面将会谈到一些非常重要的变形（其中
规则是递归的，其中名字e x p出现在箭头的右边。 读者还要注意到文法规则将正则表达式作为部件。在 e x p规则和o p规则中，实际有6个表示 语言中记号的正则表达式。其中5个是单字符记号：+、-、*、( 和 )，另一个是名字n u m b e r。 记号的名字表示数字序列。 与这个例子的格式相类似的文法规则最初是用在 A l g o l 6 0语言的描述中。其表示法是由 John Backus为A l g o l 6 0报告开发，之后又由Peter Naur更新，因此这个格式中的文法通常被称作 B a c k u s - N a u r范式（Backus-Naur form）或B N F文法。 3.2.2 上下文无关文法规则的说明 同正则表达式类似，文法规则是定义在一个字母表或符号集之上。在正则表达式中，这些 符号通常就是字符，而在文法规则中，符号通常是表示字符串的记号。在前一章中，我们利用 C中的枚举类型定义了在扫描程序中的记号；本章为了避免涉及到特定实现语言（例如 C）中 表示记号的细节，就使用了正则表达式本身来表示记号。此时的记号就是一个固定的符号，如 同在保留字w h i l e中或诸如+或: =这样的特殊符号一样，使用在第 2章曾用到的代码字体书写 串本身。对于作为表示多于一个串的标识符和数的记号来说，代码字体为斜体，这就同假设这 个记号是正则表达式的名字（这是它经常的表示）一样。例如，将 T I N Y语言的记号字母表表 示为集合 {if, then, else, end, repeat, until, read, write, i d e n t i f i e r, n u m b e r, +, -, *, /, =, <, (, ), ;, := } 而不是记号集（如在T I N Y扫描程序中定义的一样）： {IF, THEN, ELSE, END, REPEAT, UNTIL, READ, WRITE, ID, NUM, PLUS, MINUS, TIMES, OVER, EQ, LT, LPAREN, RPAREN, SEMI, ASSIGN } 假设有一个字母表，B N F中的上下文无关文法规则（context-free grammar rule in BNF）是 由符号串组成。第1个符号是结构名字，第 2个符号是元字符→，这个符号之后是一个符号串， 该串中的每个符号都是字母表中的一个符号（即一个结构的名字）或是元符号｜。 在非正式术语中，对B N F的文法规则解释如下：规则定义了在箭头左边名字的结构。这个 结构被定义为由被竖线分隔开的选择右边的一个选项组成。每个选项中的符号序列和结构名字 定义了结构的布局。例如，前例中的文法规则： exp → exp op exp | (e x p) | n u m b e r op → + | - | * 第1个规则定义了一个表达式结构（用名字e x p）由带有一个算符和另一个表达式的表达式， 或一个位于括号之中的表达式，或一个数组成。第 2个规则定义一个算符（利用名字 o p）由符 号+、-或*构成。 这里所用的元符号和惯例与广泛使用中的类似，但读者应注意到这些惯例并没有统一的 标准。实际上，用以代替箭头元符号→的通常有 =（等号）、：（冒号）和 : : =（双冒号等号）。 在普通文本文件中，找到能替代斜体用法的方法也很有必要，通常的办法是在结构名字前后 加尖括号< . . . >并将原来斜体的记号名字大写；因此，使用不同的惯例，上面的文法规则就可 变为： <exp> ::= <exp> <op> <exp> | ( <exp> ) | NUMBER <op> ::= + | - | * 每一个作者都还有这些表示法的其他变形。本节后面将会谈到一些非常重要的变形（其中 第 3章 上下文无关文法及分析 7 1 下载
72 翁译原理及实践 China-pub.Co 下载 一些有时也会碰到)。这里要先讲一下有关表示法方面的另外两个较小的问题。 在BNF的元符号中使用括号有时很有用，这同括号可在正则表达式中重新安排优先权很相 似。例如，可将上面的文法规则重写为如下一个单一的文法规则： exp-exp("+"""")exp"("exp")"I number 在这个规则中，括号很必要，它用于将箭头右边的表达式之间的算符选择组合在一起，这 是因为并置优先于选择（同在正则表达式中一样）。因此，下面的规则就具有了不同（但不正 确)的含义： exp-exp"+"""*"exp"("exp")"I number 请读者再留意一下：当将括号包含为一个元符号时，就有必要区分括号记号与元符号，这 一点是通过将括号记号放在引号中做到的，这同在正则表达式中的一样（为了具有连贯性，也 将算符符号放在引号中)。 由于经常可将括号中的部分分隔成新的文法规测，所以在BNF中的括号并不像元符号一样 缺之不可。实际上如果允许在箭头左边的相同名字可出现任意次，那么由竖线元符号给出的选 择运算在文法规则中也不是一定要有的。例如，简单的表达式文法可写作： ep→exp op exp ep→(exp) exp→number p→- 然而，通常把文法规则写成每个结构的所有选择都可在一个规则中列出来，而且每个结构 名字在箭头左边只出现一次。 有时我们需要为说明简便性而给出一些用简短表示法写出的文法规则的示例。在这些情形 中，应将结构名字大写，并小写单个的记号符号（它们经常仅仅是一个字符）；因此，按这种 速记方法可将简单的表达式文法写作： E→EOEI(E)In O++|-* 有时当正在将字符如同记号一样使用时，且无需使用代码字体来书写它们，则也可简化表 示法如下： E→EOEI(E)la 0一+1-1 3.2.3推导及由文法定义的语言 现在讨论文法规则如何确定一种“语言”或者是记号的正规串集。 下文无关文法规则确定了为由规则定义的结构的记号符号符合语法的串集。例如，算术 表达式 (34-3)★42 与7个记号的正规串相对应 number-number)*number 其中aumberi记号具有由扫描程序确定的结构且串本身也是一个正规的表达式，这是因为
一些有时也会碰到）。这里要先讲一下有关表示法方面的另外两个较小的问题。 在B N F的元符号中使用括号有时很有用，这同括号可在正则表达式中重新安排优先权很相 似。例如，可将上面的文法规则重写为如下一个单一的文法规则： exp → exp ( "+" | "-" | "*") exp | "("e x p")" | n u m b e r 在这个规则中，括号很必要，它用于将箭头右边的表达式之间的算符选择组合在一起，这 是因为并置优先于选择（同在正则表达式中一样）。因此，下面的规则就具有了不同（但不正 确）的含义： exp → exp "+" | "-" | "*" exp | "("e x p")" | n u m b e r 请读者再留意一下：当将括号包含为一个元符号时，就有必要区分括号记号与元符号，这 一点是通过将括号记号放在引号中做到的，这同在正则表达式中的一样（为了具有连贯性，也 将算符符号放在引号中）。 由于经常可将括号中的部分分隔成新的文法规则，所以在 B N F中的括号并不像元符号一样 缺之不可。实际上如果允许在箭头左边的相同名字可出现任意次，那么由竖线元符号给出的选 择运算在文法规则中也不是一定要有的。例如，简单的表达式文法可写作： exp → exp op exp exp → (e x p) exp → n u m b e r op → + op → - op → * 然而，通常把文法规则写成每个结构的所有选择都可在一个规则中列出来，而且每个结构 名字在箭头左边只出现一次。 有时我们需要为说明简便性而给出一些用简短表示法写出的文法规则的示例。在这些情形 中，应将结构名字大写，并小写单个的记号符号（它们经常仅仅是一个字符）；因此，按这种 速记方法可将简单的表达式文法写作： E → E O E｜( E ) | n O → + | - | * 有时当正在将字符如同记号一样使用时，且无需使用代码字体来书写它们，则也可简化表 示法如下： E → E O E｜( E ) | a O → + | - | * 3.2.3 推导及由文法定义的语言 现在讨论文法规则如何确定一种“语言”或者是记号的正规串集。 上下文无关文法规则确定了为由规则定义的结构的记号符号符合语法的串集。例如，算术 表达式 ( 3 4 - 3 ) * 4 2 与7个记号的正规串相对应 ( number - number ) * n u m b e r 其中n u m b e r记号具有由扫描程序确定的结构且串本身也是一个正规的表达式，这是因为 7 2 编译原理及实践 下载
China-pub.Com 第3章上下文无关文法及分析 73 下载H 每一个部分都与由文法规则 exp-exp op expl (exp)number 一+1-1* 给出的选择对应。另一方面，串 (34-3*42 就不是正规的表达式，这是因为左括号没有一个右括号与之匹配，且xp的文法规则中的 第2个选择要求括号需成对生成。 文法规则通过推导确定记号符号的正规串。推导(derivation)是在文法规则的右边进行选 择的一个结构名字替换序列。推导以一个结构名字开始并以记号符号串结束。在推导的每一个 步骤中，使用来自文法规则的选择每一次生成一个替换。 例如，图3-1利用同在上面简单表达式文法中的一样给出的文法规则为表达式(34-3)*42 提供了一个推导。在每一步中，为替换所用的文法规则选择都放在了右边（还为便于在后面引 用为每一步都编了号)。 ()ep→exp op e ep→exp op exp] →exp op number [ep→aumber】 →exp*number [op→t1 (4) →《en】曹number [ep→(ep)】 →(exp op exp)*aumber [ep→exp op exp →(exp op nu er）*number [ep-→number】 (7) 一(exp-number）number (8) (number-number)*number [ep→number】 图3-1算术表达式34-3)*2的推导 请注意，推导步骤使用了与文法规则中的箭头元符号不同的箭头，这是由于推导步骤与文 法规则有一点差别：文法规则定义(define),而推导步骤却通过替换来构造(construct)。在 图3-1的第1步中，串exp op exp从规则cxp一exp op exp的（在BNF中对于exp的第1个选择）右 边替换了单个的exp。在第2步中，串exp op exp中的exp被符号number从选择exp一number的 右边替换掉以得到串exp op number。在第3步中，符号*从规则op→*中替换op(在BNF中对 于op的第3个选择)以得到串exp*number,等等。 由推导从cxp符号中得到的所有记号符号的串集是被表达式的文法定义的语言(language defined by the grammar)。这个语言包括了所有合乎语法的表达式。可将它用符号表示为： L(G={slp*s} 其中G代表表达式文法，s代表记号符号的任意数组串（有时称为句子(sentence),而符 号一*表示由如前所述的替换序列组成的推导（星号用作指示步骤的序列，这与在正则表达式 中指示重复很相像)。由于它们通过推导“产生”L(G)中的串，文法规则因此有时也称作 生式(production)。 文法中的每一个结构名定义了符合语法的记号串的自身语言。例如，在简单表达式文法中 由叩定义的语言定义了语言(+，-，*)只由3个符号组成。我们通常对由文法中最普通的结 构定义的语言最感兴趣。用于程序设计语言的文法经常定义一个称作程序的结构，而该结构的 语言是程序设计语言的所有符合语法的程序的集合（注意这里在两个不同的意思中所使用的 “语言”)
每一个部分都与由文法规则 exp → exp op exp | (e x p) | n u m b e r op → + | - | * 给出的选择对应。另一方面，串 ( 3 4 - 3 * 4 2 就不是正规的表达式，这是因为左括号没有一个右括号与之匹配，且 e x p的文法规则中的 第2个选择要求括号需成对生成。 文法规则通过推导确定记号符号的正规串。推导（ d e r i v a t i o n）是在文法规则的右边进行选 择的一个结构名字替换序列。推导以一个结构名字开始并以记号符号串结束。在推导的每一个 步骤中，使用来自文法规则的选择每一次生成一个替换。 例如，图3 - 1利用同在上面简单表达式文法中的一样给出的文法规则为表达式 ( 3 4 - 3 ) * 4 2 提供了一个推导。在每一步中，为替换所用的文法规则选择都放在了右边（还为便于在后面引 用为每一步都编了号）。 图3-1 算术表达式( 3 4 - 3 ) * 4 2 的推导 请注意，推导步骤使用了与文法规则中的箭头元符号不同的箭头，这是由于推导步骤与文 法规则有一点差别：文法规则定义（ d e f i n e），而推导步骤却通过替换来构造（ c o n s t r u c t）。在 图3 - 1的第1步中，串exp op exp从规则e x p→exp op exp的（在B N F中对于e x p的第1个选择）右 边替换了单个的e x p。在第2步中，串exp op exp中的e x p被符号n u m b e r从选择e x p→n u m b e r的 右边替换掉以得到串exp op n u m b e r。在第3步中，符号*从规则o p→*中替换o p（在B N F中对 于o p的第3个选择）以得到串exp * n u m b e r，等等。 由推导从e x p符号中得到的所有记号符号的串集是被表达式的文法定义的语言（ l a n g u a g e defined by the grammar）。这个语言包括了所有合乎语法的表达式。可将它用符号表示为： L (G) = {s | exp Þ *s } 其中G代表表达式文法，s 代表记号符号的任意数组串（有时称为句子（ s e n t e n c e）），而符 号Þ*表示由如前所述的替换序列组成的推导（星号用作指示步骤的序列，这与在正则表达式 中指示重复很相像）。由于它们通过推导“产生” L (G）中的串，文法规则因此有时也称作产 生式（p r o d u c t i o n）。 文法中的每一个结构名定义了符合语法的记号串的自身语言。例如，在简单表达式文法中 由op 定义的语言定义了语言{+, -, *}只由3个符号组成。我们通常对由文法中最普通的结 构定义的语言最感兴趣。用于程序设计语言的文法经常定义一个称作程序的结构，而该结构的 语言是程序设计语言的所有符合语法的程序的集合（注意这里在两个不同的意思中所使用的 “语言”）。 第 3章 上下文无关文法及分析 7 3 下载