条件语句 if B then S if B then S 循环语句 while B do S repeat S until B for i:=E step E2 until Ea do S 过程调用语句 P(X,X2,.,X） 返回语句 retm (E） 重要的是，必须了解这些语句在不同语言中的不同语义。 3.说明句 说明句旨在定义名字的性质。编译程序把这些性质登记在符号表中，并检查程序中 名字的引用和说明是否相一致。许多说明句没有相应的目标代码。但有些说明句，如过 程说明和可变数组说明则有相应的目标代码。 4.简单句和复合句 简单句是指那些不包含其它语句成分的基本句，如赋值句、如句等等。 复合句则指那些句中有句的语句。例如， IF(X-EQ-Y)GOTO 15 是FORTRAN的一个复合句；而 if B then S else S2; begin S;S2.S end 是Pascal中的复合句。 2.3程序语言的语法描述 对于高级程序设计语言及其编译程序而言，语言的语法定义是非常重要的。本节介 绍语法结构的形式描述问题。我们将重点讨论上下文无关文法、语法分析树，以及文法的 二义性问题。最后还将对形式语言进行简单概述。 在引入文法定义之前，首先介绍几个概念 设是一个有穷字母表，它的每个元素称为一个符号。上的一个符号串是指由》 中的符号所构成的一个有穷序列。不包含任何符号的序列称为空字，记为ε。用∑·表示 上的所有符号串的全体，空字e也包括在其中。例如，若公=a,b,则公·={e,a,b, a触，b,ba,bb,a,.l。中表示不含任何元素的空集}。这里要注意e、}和{c的区别。 *的子集U和V的（连接）积定义为 UV={a∈U&邸∈V 即集合UV中的符号申是由U和V的符号串连接而成的。注意，一般而言，V≠U,但 (V)W=U(VW)。V自身的n次（连接）积记为
26 Ve=VV.V 规定V0=1e。令 V=UVUv2UV30. 称V*是V的闭包。记V+=VW,称V是V的正则闭包 闭包V中的每个符号串都是由V中的符号串经有限次连接而成的。 2.3.1上下文无关文法 文法是描述语言的语法结构的形式规则（即语法规则）。这些规则必须是准确的，易 于理解的，而且，应当有相当强的描述能力，足以描述各种不同的结构。由这种规则所形 成的程序语言应有利于句子分析和翻译，而且，最好能通过这些规则自动产生有效的语法 分析程序。 所谓上下文无关文法是这样一种文法，它所定义的语法范畴（或语法单位）是完全独 立于这种范畴可能出现的环境的。例如，在程序语言中，当碰到-一个算术表达式时，我们 完全可以对它“就率论事”进行处理，而不必考虑它所处的上下文。但在自然语言中，一个 句子，一个词乃至一个字，它们的语法性质和所处的上下文往往有密切的关系。因此，上 下文无关文法当然不宜于描述任何自然语言，但对于现今的程序语言来说，上下文无关文 法基本上是够用了。本节，我们将讨论什么是上下文无关文法和上下文无关语言。以后， 凡“文法” 词若无特别说明，则均指上下文无关文法。 下面，我们从一个具体英文例句的分析出发，引进有关上下文无关文法的基本概念。 比如，我们写了这样一个句子： He gave me a book 显然这是一个语法上正确的句子，因为它满足英语中的基本语法规则。如果我们用“→” 表示“由.组成”或“定义为”，那么，可以有下面语法规则： <句子><主语><调语><间接宾语><直接宾语> <主语>→<代词> <谓语>+动词 <间接宾语 <代词> <直接宾语>→<冠词><名词> <代词>He <代词>→m <冠词>+a <动词>→e <名词>+bo0k 把He gave me a book与上述规则进行对照，看其中的语法范畴是否处于适当位置，我 们得出结论：它是一个语法上正确的句子。说得更确切一点，有了这些规则后，我们就可 以推导或产生出上述句子（从<句子>出发，反复把上述规则中“→”左边的成分替换成右 边的成分)：
22 <句子>→<主语><谓语><间接宾语><直接宾语> →<代词><谓语><间接宾语><直接宾语 →He<谓语><间接宾语><直接宾语> →He<动词><间接宾语><直接宾语> →He gave<间接宾语><直接宾语> →He婴ve<代词><直接宾语> →He gave me<直接宾语> →He gave me<冠词><名词> →He gave me a<名词> He 我们可以用种图示化的方法来表示这种推导，如图2.1，说明ee mea book是 个语法正确的句子。这种图形表示称为语法分析树。 图2.1语法树 上述定义英文句子的规则可以说就是一个上下文无关文法。其中，He,me,book 心，a等，称为终结符号；<句子>、<主语>、<谓语>、<动词>、<代词>等，称为非 终结符号；这个文法最终是要定义<句子>的语法结构，所以<句子>在这里称为开始符 号；<间接宾语>·<冠词><名词>这种书写形式称为产生式。 归纳起来，一个上下文无关文法G包括四个组成部分：一组终结符号，一组非终结符 号，一个开始符号，以及一组产生式。 所谓终结符号乃是组成语言的基本符号，在程序语言中就是以前屡次提到的单词符 号，如基本字标识符、常数，算符和界符等。从语法分析的角度来看，终结符号是，个语 言的不可再分的基本符号。 非终结符号（也称语法变量）用来代表语法范畴。例如，“算术表达式”、“布尔表达 式”、“赋值句”、“分程序”、“过程”等，它们都是现今程序语言常见的语法范畴。我们也可 以说 个非终结符代 一个 一定的语法概念。因此， 一个非终结符是一个类（或集合）记 号，而不是一个个体记号。例如，“算术表达式”这个非终结符乃代表一定算术式组成的 类。因而，也可以说，每个非终结符号表示一定符号串的集合（由终结符号和非终结符号 组成的符号申)。 开始符号是一个特殊的非终结符号，它代表所定义的语言中我们最终感兴趣的语法 范畴，这个语法范畴通常称为“句子”。但在程序语言中，我们最终感兴趣的是“程序”这个 语法范畴，而其它的语法范砖都只不过是构造“程序“的一块块砖石
28 产生式（也称产生规则或简称规则）是定义语法范畴的一种书写规则。一个产生式的 形式 A-a 其中，箭头（有时也用：=）左边的A是一个非终结符，称为产生式的左部符号：箭头右边 的α是由终结符号或与非终结符号组成的一符号串，称为产生式的右部。我们有时也 说，产生式A→α是关于A的一条产生规则。产生式是用来定义语法范畴的。例如，令i 代表已定义的范畴“变量”，郡么，产生式 算术表达式 意味着把“算术表达式”这个范畴定义为“变量”。在有的书上，“→”也用“：=”表示，这种 表示方法也称巴科斯范式。 有时，只用一个产生式并不足以定义一个语法范畴，而需要用好儿个产生式。特别 是，需要含有递归的产生式。我们再看一个例子。假定要定义一类含+、的算术表达 式，这个定义可以这样给出： “变量是一个算术表达式： 若E和E是算术表达式，则E,+E、￥E2和(E)也是算术表达式。” 对于这个定义，若用产生式来描述，则可将它写成： E-+E+E E→E0E E+(E) 其中，E代表“算术表达式”；i代表“变量”。这四个产生式的全体才定义了上述的加、乘 “算术表达式”这一概念。这四个产生式中的后三个都是递归的，也就是说，产生式左部的 符号直接在右部出现，用递归方式定义语法范畴是一种非常重要的手段，对此应特别注 意。递归性常常并不像上面例子所示的那样直接，后面，我们将会遇到间接递归的例子。 形式上说，一个上下文无关文法G是一个四元式(V,VN,S,其中 V是一个非空有限集，它的每个元素称为终结符号： Vx是一个非空有限集，它的每个元素称为非终结符号，V∩VN=: S是一个非终结符号，称为开始符号： 是一个产生式集合（有限），每个产生式的形武是P+a,其中，P∈VN,a∈(VU Vw)·。开始符号S至少必须在某个产生式的左部出现一次。 注意，为了书写方便，若干个左部相同的产生式，如 P◆a P+2 Pa 可合并为一个，缩写成 P+alal.lau 其中，每个4有时也称为是P的一个侯选式
29 箭头‘→’读为“定义为”，直竖“'读为“或”，它们是元语言符号。 在后面的讨论中，根据不同情况，我们将用大写字母A、B、C.或汉语词组（如，算术 表达式)代表非终结符号，特别是用小写字母a、b,c.代表终结符，用a3、Y等代表由终结 符和非终结符组成的符号串。为简便起见，当引用具体的文法例子时，仅列出产生式和指 出开始符号。 例如，下面是一个上下文无关文法： E→ilEAE A*+13 其中，E、A是非终结符，E是开始符号，而1、+和*是终结符。 一个上下文无关文法如何定义一个语言呢？其中心思想是，从文法的开始符号出发 反复连续使用产生式，对非终结符施行换和展开。例如，我们考虑下面的文法 E→E+E1E*EI(E)Ii (2.1) 其中，唯一的非终结符E可以看成是代表一类算术表达式。我们可以从E出发，进行一 系列的推导，推出种种不同的算术表达式来。例如，根据规则 E*(E) 我们可以说：从E可直接（一步地）推出‘(E)'。与前面一样，我们用‘→'表示“直接推 出”，这样，这句话就可表示为 E=(E) 若对(E)’中的E使用规则E→E+E,就有 (E)(E+E) 即，从‘(E)'可直接推出‘(E+E)'。把上述这两步合并起来，就有 E=(E)=(E+E) 再对“(E+E)'中的E相继两次使用规则E→1之后，我们就有 E=(E)→(E+E)→(i+E)→(i+i) 我们称这样的一串替换序列是从E推出(i+)的一个推导。这个推导提供了一个证明， 证明(1+)是文法(2.1)所定义的一个算术表达式。注意，推导每前进一步总是引用一条 规则（产生式），而符号‘一'指仅推导一步的意思 严格地说，我们称aA邮直接推出aB,即 aAB->aYB 仅当Ay是一个产生式，且a(VUY)”。如果→.→2，则我们称这个序列 是从a至的一个推导。若存在-个从a至a的推导，则称a可推导出a。我们用a四 三a表示：从m出发，经一步或若干步，可推导出a。而用a表示：从出发，经0 步或若干步，可推导出a。换言之，a一B意味若，或者a=B,或者a一B。 假定G是一个文法，S是它的开始符号。如果S一a,则称a是一个句型。仅含终结 符号的句型是一个句子。文法G所产生的句子的全体是一个语言，将它记为(G)。 L(G)=alSaa∈V片 例如，终结符号串(1*i+)是文法(2.1)的一个句子。因为