1、编译原理与技术编译原理与技术第第3章章 程序语言的语法描述程序语言的语法描述 编译原理与技术编译原理与技术2主要内容主要内容u文法和语言文法和语言u文法的分类文法的分类 u文法的等价变换文法的等价变换u语法分析概述语法分析概述 编译原理与技术编译原理与技术3程序语言的语法描述程序语言的语法描述 u程序语言的定义程序语言的定义 程序语言通常是一个能完整、准确和规则地程序语言通常是一个能完整、准确和规则地表达人们的意图，并用以指挥或控制计算机工表达人们的意图，并用以指挥或控制计算机工作的作的“符号系统符号系统”。它完整的定义包括语法、。它完整的定义包括语法、语义及语用三个方面。语义及语用三个方面。
2、一个程序语言的语法是指这样一组规则，使一个程序语言的语法是指这样一组规则，使用它可以形成和产生一个合适的程序。这些用它可以形成和产生一个合适的程序。这些规则一部分称为词法规则，另一部分称为语规则一部分称为词法规则，另一部分称为语法规则（或产生规则）。法规则（或产生规则）。编译原理与技术编译原理与技术4程序语言的语法描述程序语言的语法描述 一个程序语言的语义是指这样一组规则，使一个程序语言的语义是指这样一组规则，使用它可以定义一个程序的意义。静态语义是用它可以定义一个程序的意义。静态语义是一系列限定规则，确定哪些合乎语法的程序一系列限定规则，确定哪些合乎语法的程序是合适的；动态语义也称作运行语义
3、或执行是合适的；动态语义也称作运行语义或执行语义，表明程序要做些什么，要计算什么。语义，表明程序要做些什么，要计算什么。语用表示语言符号及其使用者之间的关系，语用表示语言符号及其使用者之间的关系，涉及符号的来源、使用和影响。涉及符号的来源、使用和影响。编译原理与技术编译原理与技术53.1 文法和语言文法和语言u文法的形式定义文法的形式定义 定义定义3.1:定义四元组定义四元组G=(VN，VT，P，S)是一个是一个文法。其中文法。其中VN,VT和和 P都是非空有限集合，分别都是非空有限集合，分别称为非终结符号集合、终结符号集合及产生式称为非终结符号集合、终结符号集合及产生式集合。集合。S称作识别
4、符号或开始符号，它是一个非称作识别符号或开始符号，它是一个非终结符，至少要在一条产生式中作为左部出现。终结符，至少要在一条产生式中作为左部出现。VN和和VT不含公共元素，即不含公共元素，即VNVT=。通。通常用常用V表示表示VNVT，称为文法，称为文法G的字母表。的字母表。编译原理与技术编译原理与技术63.1 文法和语言文法和语言 例例3.1：文法文法G1=(VN,VT,P,S)，其中，其中VN=S，VT=0,1，P=S0S1,S01。该文法只有一个非终结符该文法只有一个非终结符S，有两个终结符，有两个终结符0和和1，有两，有两条产生式，开始符号是条产生式，开始符号是S。很多时候，不用将文法很
5、多时候，不用将文法G的四元组显式地表示出来，的四元组显式地表示出来，而只将产生式写出。一般约定，第一条产生式的左部是而只将产生式写出。一般约定，第一条产生式的左部是开始符号，用尖括号括起来的是非终结符号，不用尖括开始符号，用尖括号括起来的是非终结符号，不用尖括号括起来的是终结符号，或者用大写字母表示非终结符号括起来的是终结符号，或者用大写字母表示非终结符号，小写字母表示终结符号。另外也有一种习惯写法，号，小写字母表示终结符号。另外也有一种习惯写法，将将G写成写成GS，其中，其中S是开始符号。因此，例是开始符号。因此，例3.1还可以还可以写成：写成：G：S0S1 或或 GS：S0S1 S01 S
6、01 编译原理与技术编译原理与技术73.1 文法和语言文法和语言 有时，为书写简洁，常把相同左部的产生式，形如有时，为书写简洁，常把相同左部的产生式，形如A1,A2,An，缩写为：，缩写为：A1|2|n。这里。这里的元符号的元符号|读做读做“或或”。如，例如，例3.1的产生式可以写成的产生式可以写成S 0S1|01。注意注意元符号元符号和和源符号源符号的区别：的区别：文法中使用的元符号文法中使用的元符号或或 =表示左部由右部定义，表示左部由右部定义，|表表示定义同一个左部的几个可选择的右部。而源符号是指示定义同一个左部的几个可选择的右部。而源符号是指文法定义的语言中的符号，全部由文法的终结符构
7、成。文法定义的语言中的符号，全部由文法的终结符构成。编译原理与技术编译原理与技术83.1 文法和语言文法和语言 例例3.2：文法文法G2=(VN,VT,P,S)，其中，其中 VN=标识符标识符,字母字母,数字数字，VT=a,b,c,x,y,z,0,1,9，P=标识符标识符字母字母|标识符标识符字母字母|标识符标识符数字数字 字母字母a|b|z 数字数字0|1|9 S=标识符标识符，这里使用尖括号，这里使用尖括号 和和 括起非终结符。括起非终结符。编译原理与技术编译原理与技术93.1 文法和语言文法和语言例例3.3：一个文法的几种写法：一个文法的几种写法：G=(S,A,a,b,P,S)其中其中P
8、=SaAb,Aab,AaAb,A G:SaAb Aab AaAb A GS:Aab AaAb A SaAb GS:Aab|aAb|SaAb编译原理与技术编译原理与技术103.1 文法和语言文法和语言u推导与归约推导与归约 定义定义3.2:设设是文法是文法G=(VN，VT，P，S)的产的产生式，生式，和和是是V*中的任意符号。若有符号串中的任意符号。若有符号串v，w满足：满足：v=，w=，则说，则说v直接产生直接产生w，或者说，或者说，w是是v的的直接推导直接推导。记作。记作vw。也可以。也可以说说w直接归约直接归约到到v。归约是推导的逆过程。归约是推导的逆过程。编译原理与技术编译原理与技术11
9、3.1 文法和语言文法和语言对例对例3.1文法文法G，可以给出直接推导的一些例子如下：，可以给出直接推导的一些例子如下：v=0S1，w=0011，直接推导：直接推导：0S10011，使用的规则：使用的规则：S01，这里，这里=0，=1。v=S，w=0S1，直接推导：直接推导：S0S1，使用的规则：使用的规则：S0S1，这里，这里=，=。v=0S1，w=00S11，直接推导：直接推导：0S100S11，使用的规则：使用的规则：S 0S1，这里，这里=0，=1。编译原理与技术编译原理与技术123.1 文法和语言文法和语言 对例对例3.2文法文法G，直接推导的例子有：，直接推导的例子有：v=标识符标
10、识符，w=标识符标识符字母字母，直接推导：直接推导：标识符标识符标识符标识符字母字母，使用的规则：使用的规则：标识符标识符标识符标识符字母字母，这里这里=。v=标识符标识符字母字母数字数字，w=字母字母字母字母数字数字，直接推导：直接推导：标识符标识符字母字母数字数字 字母字母字母字母数字数字，使用的规则：使用的规则：标识符标识符字母字母。这里这里=，=字母字母数字数字。v=abc数字数字，w=abc5，直接推导：直接推导：abc 数字数字 abc5,使用的规则：使用的规则：数字数字5，这里，这里=abc,=。编译原理与技术编译原理与技术13 定义定义3.3:如果存在直接推导的序列：如果存在直
11、接推导的序列：v=w0 w1 w2 wn=w,(n0)，则称，则称v推导推导出出w，推导长度，推导长度为为n。或者称。或者称w归约归约到到v。记作。记作v w。若有。若有v w，或或v=w，则记作，则记作v w。定义定义3.19:设设GS是一文法，如果符号串是一文法，如果符号串x是从是从开始符号推导出来的，即有开始符号推导出来的，即有S x，则称，则称x是文法是文法GS的的句型句型。若。若x仅由终结符号组成，即仅由终结符号组成，即S x，xVT*，则称，则称x为为GS的的句子句子。3.1 文法和语言文法和语言编译原理与技术编译原理与技术143.1 文法和语言文法和语言对例对例3.1文法，存在直
12、接推导序列文法，存在直接推导序列v=0S100S11 000S111 00001111=w，即即0S1 00001111，也可记作，也可记作0S1 00001111。对例对例3.2文法，存在直接推导序列文法，存在直接推导序列 v=标识符标识符 标识符标识符数字数字 字母字母数字数字 x数字数字 x1=w，即即标识符标识符 x1，也可记作，也可记作标识符标识符 x1。S,0S1,000111都是例都是例3.1的文法的文法G的句型，其中的句型，其中000111是是G的句子。的句子。标识符标识符字母字母,字母字母数字数字,a1等都是例等都是例3.2文法文法G的句型，其中的句型，其中a1是是G的句子。
13、的句子。编译原理与技术编译原理与技术153.1 文法和语言文法和语言例例3.4：终结符号串终结符号串(i*i+i)是文法是文法 EE+E|E*E|(E)|i 的的一个句子。因为有从开始符号一个句子。因为有从开始符号E至终结符号串至终结符号串(i*i+i)的的一个推导：一个推导：E(E)(E+E)(E*E+E)(i*E+E)(i*i+E)(i*i+i)而而E,(E),(E*E+E)等是文法的句型。等是文法的句型。编译原理与技术编译原理与技术163.1 文法和语言文法和语言 定义定义3.4:若推导过程中每一步都是替换最左（右）若推导过程中每一步都是替换最左（右）边的非终结符，则称该推导为边的非终结
14、符，则称该推导为最左（右）推导最左（右）推导。句型的最右推导称为句型的最右推导称为规范推导规范推导，其逆过程最左，其逆过程最左归约称为归约称为规范归约规范归约。例例3.5：文法文法GS:SAB AA0|1B B0|S1 给出句子给出句子101001的最左和最右推导。的最左和最右推导。解：最左推导：S AB 1B B10B 10S1 10AB1 101BB1 1010B1 101001 最右推导：S AB AS1AAB1 AA01 A1B01 A1001 1B1001 101001 编译原理与技术编译原理与技术173.1 文法和语言文法和语言 u文法产生的语言文法产生的语言 定义定义3.5:文法
15、文法G的全部句子组成的集合称为的全部句子组成的集合称为G产产生的语言，记为生的语言，记为L(G)，即，即 L(G)=x|S x，其中，其中S为开始符号，且为开始符号，且xVT*例例3.1的文法的文法G1 的语言是的语言是L(G)=0n1n|n1。例。例3.2的的文法文法G2的句子是字母打头的、由字母和数字组成的符号的句子是字母打头的、由字母和数字组成的符号串，也就是程序设计语言中用于表示名字的标识符，因串，也就是程序设计语言中用于表示名字的标识符，因此产生的语言就是所有标识符的集合。此产生的语言就是所有标识符的集合。编译原理与技术编译原理与技术183.1 文法和语言文法和语言 例例3.6：考虑
16、文法考虑文法G1:S bA A aA|a 求它所定义的语言。求它所定义的语言。解：从开始符S出发，可以推出如下句子：SbA ba SbA baA baa SbA baA baaA baaa 因此，文法G1产生以b开头、后面跟一个或多个a的所有符号串，从而L(G1)=ban|n1。编译原理与技术编译原理与技术193.1 文法和语言文法和语言 例例3.7：设有文法设有文法G2:S P|aPb P ba|bQa Q ab 求语言求语言L(G2)。解：从开始符S出发，可以推出如下句子：SPba SP bQa baba SaPbabab SaPbabQabababab 文法G2共能产生4个句子，因此L(
17、G2)=ba,baba,abab,ababab 编译原理与技术编译原理与技术203.1 文法和语言文法和语言 例例3.8：设设G3=(VN，VT，P，S)，VN=S,B,E，VT=a,b,e，P由下列产生式组成：由下列产生式组成：(1)SaSBE (2)SaBE (3)EBBE (4)aBab (5)bBbb (6)bEbe (7)eEee 求语言求语言L(G3)。解：L(G3)=anbnen|n1。编译原理与技术编译原理与技术213.1 文法和语言文法和语言u语言的验证语言的验证 一般来说，对一般来说，对“文法文法G产生语言产生语言L”的证明包的证明包括两部分：括两部分：（1）证明由）证明由
18、G产生的每个字符串都在产生的每个字符串都在L中。中。（2）证明）证明L中的每个字符串都能由中的每个字符串都能由G产生。产生。编译原理与技术编译原理与技术223.1 文法和语言文法和语言 例例3.9：验证文法验证文法G1:S (S)S|产生语言产生语言L(G1)=配对的配对的括号串的集合。括号串的集合。证明：（1）按推导步数进行归纳证明：推出的是配对括号串 归纳基础：S 归纳假设：少于n步的推导都产生配对的括号串 归纳步骤：n步的最左推导如下S (S)S (x)S (x)y 其中x、y是配对的括号串，从而(x)y也是配对的 括号串，即n步的推导也产生配对的括号串。因此，由G1产生的每个字符串都是
19、配对的括号串都在 L(G1)中。编译原理与技术编译原理与技术233.1 文法和语言文法和语言（2）按符号串的长度进行归纳证明：配对括号串可由S推出 归纳基础：S 归纳假设：长度小于2n的配对括号串都可以从S推导出来 归纳步骤：考虑长度为2n(n1)的w=(x)y，其中w、x、y 均为配对括号串，有S (S)S (x)S (x)y 即长度为2n的配对括号串都可以从S推导出来。因此，L(G1)中的每个字符串都能由G1产生。由（1）、（2）可知，文法G:S (S)S|产生语言L(G1)=配对的括号串的集合。编译原理与技术编译原理与技术24例例3.10：验证文法验证文法G2:EE+aa 产生的语言是所
20、有由若产生的语言是所有由若干个干个“+”分隔开的分隔开的a 组成的符号串，即组成的符号串，即L(G2)=a,a+a,a+a+a,a+a+a+a,.证明：(1)按a 的数目n归纳证明：每个符号串a+a+.+a L(G2)。归纳基础：因为Ea，所以Ea，aL(G2)。即n=1时成立。归纳假设：假设s=a+a+.+aL(G2)，且有n-1个a，则存在 推导E s。归纳步骤：使用产生式EE+a一次，再利用归纳假设可得推 导：E E+a s+a。因此，s+aL(G2)，其中 有n个a。因此，所有形如a+a+.+a的符号串在L(G2)中。3.1 文法和语言文法和语言编译原理与技术编译原理与技术25(2)按
21、推导的长度n归纳证明：sL(G2)必满足格式a+a+.+a。归纳基础：推导的长度为1时，只能为E a，而a是满足格式。归纳假设：长度为n-1的推导能推出满足格式a+a+.+a。归纳步骤：考虑长度为n1的推导E s。因为n 1，因此第一步 推导必然使用产生式EE+a，从而E E+a s+a=s，其中推导E s 长度为n-1，由归纳假设可知s 满足格式。因此，s=s+a 也满足格式a+a+.+a。因此，L(G2)中的所有符号串都满足格式a+a+.+a。由（1）、（2）可知，文法G2:EE+aa产生语言L(G2)=配对的括号串的集合。3.1 文法和语言文法和语言编译原理与技术编译原理与技术263.1
22、 文法和语言文法和语言u语言的文法表达语言的文法表达 由已知语言求其文法描述，实际上就是讨论由已知语言求其文法描述，实际上就是讨论语言中的句子，根据句子的特点利用层次分析语言中的句子，根据句子的特点利用层次分析的方法，构造相应的文法。构造过程中经常会的方法，构造相应的文法。构造过程中经常会用到下面形式的产生式。用到下面形式的产生式。l右递归（右递归（right recursive）产生式：产生式：A aA|a 产生产生a+，A aA|产生产生a*l左递归（左递归（left recursive）产生式：产生式：A Aa|a产生产生a+，A Aa|产生产生a*编译原理与技术编译原理与技术273.1
23、 文法和语言文法和语言 例例3.11：试构造语言试构造语言L1=anbnci|n1,i0=ab,aabb,abc,aabbc,abcc,aabbcc,的文法。的文法。解：L1中符号串的特点是：串中含一个或多个a并置，可以看作含有a+形式；串中含一个或多个b并置，可以看作含有b+形式；串中含有0个或多个c，可以看作是c*形式。因此，该语言可以看作是a+、b+与c*的连接。使用A aA|a 可以产生a+，使用B bB|b 可以产生b+，使用C cC|可以产生c*。而要表示它们的连接，只需将非终结符A、B、C连接起来即可。因此，满足要求的文法为G(Z):Z ABC A aA|a B bB|b C c
24、C|编译原理与技术编译原理与技术283.1 文法和语言文法和语言也可以使用左递归产生式，得到满足要求的另一个文法G(Z):Z ABC A Aa|a B Bb|b C cC|实际上，a+与b+的产生过程完全一致，可以将产生它们的产生式合并为A aAb|ab。则得到满足要求的另一个文法G(Z):Z AB A aAb|ab B cB|由此可以看出，已知语言求文法，文法不唯一，可以有不同的表达方法。编译原理与技术编译原理与技术293.1 文法和语言文法和语言 例例3.12：已知语言已知语言L2=x|x a,b,c*,且且x是回文字是回文字=,aa,bb,cc,aba,aca,bab,bcb,cac,c
25、bc,aabaa,，写出，写出该语言的文法。该语言的文法。解：L2中符号串的特点是：串中若包含符号，则以a开头必以a结束，以b开头必以b结束，串中符号对称出现。可以设计文法为 G(Z):Z aZa|bZb|cZc|a|b|c|。编译原理与技术编译原理与技术303.1 文法和语言文法和语言u分析树与语法树分析树与语法树 分析树分析树（parse tree）定义定义3.6:语法分析树用来描述句型的结构，是语法分析树用来描述句型的结构，是句型推导的一种树型表示，简称分析树。句型推导的一种树型表示，简称分析树。给定文法给定文法G=(VN,VT,P,S)，对于，对于G的任何句型都能构的任何句型都能构造相
26、应的分析树，这棵树满足下列条件：造相应的分析树，这棵树满足下列条件：每个结点都有一个标记。根结点的标记是开始符号每个结点都有一个标记。根结点的标记是开始符号S；非叶结点；非叶结点 的标记是非终结符；叶结点的标记是终结符或非终结符或的标记是非终结符；叶结点的标记是终结符或非终结符或。如果一个非叶结点如果一个非叶结点A有有n个儿子结点，从左到右标记为个儿子结点，从左到右标记为A1，A2，Ak，则，则AA1A2Ak一定是一定是P中的一个产生式。中的一个产生式。编译原理与技术编译原理与技术313.1 文法和语言文法和语言例例3.13：文法文法GS:S aAS|SA SbA|SS|ba 其句子其句子aa
27、bbaa的语法分析树如图的语法分析树如图3.1所示。所示。图3.1 aabbaa的语法分析树 编译原理与技术编译原理与技术323.1 文法和语言文法和语言 语法树表示了在推导过程中使用了哪个产生式和用在哪语法树表示了在推导过程中使用了哪个产生式和用在哪个非终结符上，它并没有表明施用产生式的顺序。个非终结符上，它并没有表明施用产生式的顺序。比如例比如例3.13中句子中句子aabbaa的推导过程可以列举的推导过程可以列举3个：个：推导过程推导过程1：S aAS aAa aSbAa aSbbaa aabbaa 推导过程推导过程2：S aAS aSbAS aabAS aabbaS aabbaa 推导过
28、程推导过程3：S aAS aSbAS aSbAa aabAa aabbaa 编译原理与技术编译原理与技术333.1 文法和语言文法和语言语法树语法树（syntax tree）定义定义3.7:抽象语法树用来表示程序层次结构，抽象语法树用来表示程序层次结构，它把分析树中对语义无关紧要的成分去掉，是它把分析树中对语义无关紧要的成分去掉，是分析树的抽象形式，简称语法树，也称语法结分析树的抽象形式，简称语法树，也称语法结构树或结构树。构树或结构树。语法树可看作分析树的浓缩，而分析树可看语法树可看作分析树的浓缩，而分析树可看成具体语法树。成具体语法树。编译原理与技术编译原理与技术343.1 文法和语言文法
29、和语言 例例3.14：条件语句产生式条件语句产生式S if B-expr then S1 else S2的的抽象语法树与语法分析树如图抽象语法树与语法分析树如图3.2所示。所示。(a)语法树 (b)分析树图3.2条件语句的语法树与分析树 抽象语法树中，操作符和关键字都不作为叶结点出抽象语法树中，操作符和关键字都不作为叶结点出现，而是作为内部结点。现，而是作为内部结点。编译原理与技术编译原理与技术353.1 文法和语言文法和语言 例例3.15：赋值语句产生式为赋值语句产生式为赋值语句赋值语句 i:=E，表达式的产生式为表达式的产生式为 E E+E|E*E|-E|id，则则a:=b*-c+b*-c
30、的语法树与分析树如图的语法树与分析树如图3.3所示。所示。(a)语法树 (b)分析树图3.3 赋值语句的语法树与分析树 编译原理与技术编译原理与技术363.2 文法和语言文法和语言u文法的二义性文法的二义性 二义性文法二义性文法 定义定义3.8:给定一个文法给定一个文法G，如果其产生的语言，如果其产生的语言L(G)中存在存在某个句子对应两棵或两棵以上中存在存在某个句子对应两棵或两棵以上分析树，则称文法分析树，则称文法G是二义性的。是二义性的。或者说，若一个文法中存在某个句子，它有或者说，若一个文法中存在某个句子，它有两个或两个以上不同的最左两个或两个以上不同的最左(最右最右)推导，则该文推导，
31、则该文法是二义的。法是二义的。编译原理与技术编译原理与技术373.1 文法和语言文法和语言 例例3.16：对于简单表达式文法对于简单表达式文法GE:EE+E|E-E|E*E|E/E|(E)|i 句子句子i*i+i有如下两个不同的最左推导，它们所对应的分析树如图有如下两个不同的最左推导，它们所对应的分析树如图3.4所示。所示。因此该文法是二义性文法。因此该文法是二义性文法。推导一：推导一：E E+E E*E+E i*E+E i*i+E i*i+i 推导二：推导二：E E*E i*E i*E+E i*i+E i*i+i(a)推导一的分析树 (b)推导二的分析树图3.4 句子i*i+i两棵不同的分析
32、树 编译原理与技术编译原理与技术383.1 文法和语言文法和语言 注意文法二义性和语言二义性的区别：注意文法二义性和语言二义性的区别：这是两个不同的概念，因为可能有两个不同的文法这是两个不同的概念，因为可能有两个不同的文法G和和G，其中，其中G是二义的，但是却有是二义的，但是却有L(G)=L(G)，也就是，也就是说，这两个文法所产生的语言是相同的。如果产生上下说，这两个文法所产生的语言是相同的。如果产生上下文无关语言的每一个文法都是二义的，则说该语言是二文无关语言的每一个文法都是二义的，则说该语言是二义的。义的。编译原理与技术编译原理与技术393.1 文法和语言文法和语言 文法二义性的消除文法
33、二义性的消除 方法一：方法一：设置一个规则，该规则可在每个二义性情况设置一个规则，该规则可在每个二义性情况下指出哪一个分析树（或语法树）是正确的。这样的规下指出哪一个分析树（或语法树）是正确的。这样的规则称作消除二义性规则（则称作消除二义性规则（disambiguating rule）。）。其优点为：无需修改文法（可能会很复杂）就可消除二义性；其优点为：无需修改文法（可能会很复杂）就可消除二义性；其缺点为：语言的语法结构再也不能由文法单独提供。其缺点为：语言的语法结构再也不能由文法单独提供。方法二：方法二：将文法改变成一个强制正确分析树的构造的将文法改变成一个强制正确分析树的构造的格式，就可以
34、解决二义性。格式，就可以解决二义性。编译原理与技术编译原理与技术403.1 文法和语言文法和语言 为了消除例题为了消除例题3.16中简单表达式文法中的二义性，可中简单表达式文法中的二义性，可以设置消除二义性规则，它建立了以设置消除二义性规则，它建立了3个运算相互之间的个运算相互之间的优先关系。其标准解决办法是给予加法和减法相同的优优先关系。其标准解决办法是给予加法和减法相同的优先权，而乘法和除法则有高一级的优先权，先权，而乘法和除法则有高一级的优先权，并按惯例规并按惯例规定它们都服从左结合。这样句子定它们都服从左结合。这样句子i*i+i相当于相当于(i*i)+i，它，它有惟一的分析树为图有惟一
35、的分析树为图3.4(a)。编译原理与技术编译原理与技术413.1 文法和语言文法和语言 现在来看重写文法以消除二义性的方法。为了处理文法现在来看重写文法以消除二义性的方法。为了处理文法中的运算优先权问题，就必须把具有相同优先权的算符中的运算优先权问题，就必须把具有相同优先权的算符归纳在一组中，并为每一种优先权规定不同的规则。归纳在一组中，并为每一种优先权规定不同的规则。例如，将例例如，将例3.11中文法分组为中文法分组为EE+E|E-E|TTT*T|T/T|FF(E)|i 在这个文法中，加法和减法则被归在在这个文法中，加法和减法则被归在E规则下，乘法和规则下，乘法和除法被归在除法被归在T规则下
36、。由于规则下。由于T只能由只能由E生成，这就意味着生成，这就意味着加法和减法在分析树和语法树中将被表现地加法和减法在分析树和语法树中将被表现地“更高一些更高一些”（也就是更接近于根结点），因此它们的优先权就比乘（也就是更接近于根结点），因此它们的优先权就比乘法和除法低一级。这样将算符放在不同的优先权级别中法和除法低一级。这样将算符放在不同的优先权级别中的办法是在语法说明中使用的办法是在语法说明中使用BNF的一个标准方法。这种的一个标准方法。这种分组称作分组称作优先级联优先级联（precedence cascade）。）。编译原理与技术编译原理与技术423.1 文法和语言文法和语言 分组后的文法
37、未指出算符的结合性而且仍有二义性。分组后的文法未指出算符的结合性而且仍有二义性。原因在于形如原因在于形如EE+E|E-E的产生式，它既是左递归又的产生式，它既是左递归又是右递归，若要得到符号串是右递归，若要得到符号串i+i-i，既可以先使用，既可以先使用E+E再再对第二个对第二个E使用使用E-E，也可以先使用，也可以先使用E-E再对递一个再对递一个E使使用用E+E。解决方法是强制匹配一边的递归，用。解决方法是强制匹配一边的递归，用EE+T|E-T|T代替代替EE+E|E-E|T，使加法和减法都服从左结，使加法和减法都服从左结合。若要使它们服从右结合，则可以改为合。若要使它们服从右结合，则可以改
38、为ET+E|T-E|T。也就是说，左递归规则使得它的算符在左边结合，。也就是说，左递归规则使得它的算符在左边结合，而右递归规则使得它们在右边结合。而右递归规则使得它们在右边结合。这样，若统一规定服从左结合，则例这样，若统一规定服从左结合，则例3.16中文法可以修改为中文法可以修改为EE+T|E-T|TTT*F|T/F|FF(E)|i 编译原理与技术编译原理与技术433.1 文法和语言文法和语言可以验证，该文法是一个无二义文法。句子可以验证，该文法是一个无二义文法。句子i+i*i-i惟一的分惟一的分析树与语法树如图析树与语法树如图3.5所示所示。(a)分析树 (b)语法树图3.5 句子i+i*i
39、-i的分析树与语法树编译原理与技术编译原理与技术44 下面介绍一种确定符号优先关系的方法，称简单优先关下面介绍一种确定符号优先关系的方法，称简单优先关系。它规定文法系。它规定文法G中任意两个符号的优先关系如下：中任意两个符号的优先关系如下：（1）X Y，当且仅当有产生式，当且仅当有产生式 ABY，且有推导，且有推导 B rX及及Y a。其中其中A、B为非终结符，为非终结符，X、Y为待定优先关系的两为待定优先关系的两个任意符号，个任意符号，、和和为由终结符和非终结符组成的为由终结符和非终结符组成的任意符号串，可以是空串。任意符号串，可以是空串。a是终结符。是终结符。3.1 文法和语言文法和语言编
40、译原理与技术编译原理与技术453.1 文法和语言文法和语言悬挂悬挂elseelse问题问题 考虑下面条件语句的文法：考虑下面条件语句的文法：statement if-stmt|other if-stmt if(exp)statement|if(exp)statement else statement exp 0|1 该文法是二义的，符号串该文法是二义的，符号串if(0)if(1)other else other两棵两棵分析树，如图分析树，如图3.6所示。所示。编译原理与技术编译原理与技术463.1 文法和语言文法和语言 图3.6符号串if(0)if(1)other else other两棵不同
41、的分析树（一）编译原理与技术编译原理与技术473.1 文法和语言文法和语言 图3.6 符号串if(0)if(1)other else other两棵不同的分析树（二）编译原理与技术编译原理与技术483.1 文法和语言文法和语言 第一棵分析树将第一棵分析树将else部分与第一个部分与第一个if语句结合；第二棵语句结合；第二棵分析树将分析树将else与第与第2个个if语句结合。这种二义性称作语句结合。这种二义性称作悬挂悬挂else问题问题（dangling else problem)。一般的程序语言中，条件语句的一般的程序语言中，条件语句的else部分总是与没有部分总是与没有else部分的最近的部
42、分的最近的if语句结合。这个消除二义性的规则被语句结合。这个消除二义性的规则被称为用于悬挂称为用于悬挂else问题的问题的最近嵌套规则最近嵌套规则（most closely nested rule）。）。编译原理与技术编译原理与技术493.1 文法和语言文法和语言 解决悬挂解决悬挂else二义性比处理前面的二义性困难，修改后二义性比处理前面的二义性困难，修改后为：为：statement matched-stmt|unmatched-stmtmatched-stmt if(exp)matched-stmt else matched-stmt|otherunmatched-stmt if(exp)
43、statement|if(exp)matched-stmt else unmatched-stmtexp 0|1 if语句中只允许有一个语句中只允许有一个matched-stmt出现在出现在else之前，之前，这样就迫使尽可能快地匹配所有的这样就迫使尽可能快地匹配所有的else部分。使用消除部分。使用消除二义性后的文法，符号串二义性后的文法，符号串if(0)if(1)other else other的分的分析树如图析树如图3.7所示。所示。编译原理与技术编译原理与技术503.1 文法和语言文法和语言 图3.7 消除二义性后的分析树 编译原理与技术编译原理与技术513.2 文法的分类文法的分类u
44、形式语言的分类形式语言的分类 Chomsky对文法中的规则施加不同限制，将对文法中的规则施加不同限制，将文法和语言分为四大类：文法和语言分为四大类：0型文法型文法1型文法型文法2型文法型文法3型文法型文法 编译原理与技术编译原理与技术523.2 文法的分类文法的分类0型文法型文法 定义定义3.9:文法文法G=(VN，VT，P，S)，如果它的每个，如果它的每个产生式形如产生式形如，其中，其中V*VNV*，V*，则，则G是是一个一个0型文法型文法。其中。其中V=VNVT。0型文法也称为型文法也称为短语文法短语文法（PSG,phrase structure grammars）。由定义可知，）。由定义
45、可知，0型文法的产生式左端是型文法的产生式左端是由终结符和非终结符组成的字符串，并且至少含有一由终结符和非终结符组成的字符串，并且至少含有一个非终结符。产生式右端是由终结符和非终结符组成个非终结符。产生式右端是由终结符和非终结符组成的任意字符串。的任意字符串。编译原理与技术编译原理与技术533.2 文法的分类文法的分类例例3.17：文法文法G0S：SACaB CaaaC CBDB CBE aDDa ADAC aEEa AE 则该文法是一个则该文法是一个0型文法，产生的语言为型文法，产生的语言为L0=|iI+=aa,aaaa,aaaaaaaa,由由0型文法生成的语言称为型文法生成的语言称为0型语
46、言型语言（或递归可枚举（或递归可枚举语言）。它可由语言）。它可由图灵（图灵（Turing）机）机识别。识别。编译原理与技术编译原理与技术543.2 文法的分类文法的分类1型文法型文法 对于程序设计语言来，对于程序设计语言来，0型文法有很大的随意性，还须型文法有很大的随意性，还须加以限制。对加以限制。对0型文法产生式的形式进一步加以限制，型文法产生式的形式进一步加以限制，可以得到可以得到1型文法。型文法。定义定义3.10:文法文法G=(VN，VT，P，S)，如果它是，如果它是0型文法，型文法，并且每个产生式形如并且每个产生式形如 1A 2 12，其中，其中 1,2 V*，V+，A VN，则，则G
47、是一个是一个1型文法型文法。1型文法也称为型文法也称为上下文有关文法上下文有关文法（CSG,context-sensitive grammars）。只有当非终结符）。只有当非终结符A的前后分别为的前后分别为 1,2 时，才能将时，才能将A替换为替换为。即对非终结符进行替换时，。即对非终结符进行替换时，务必考虑上下文，这也是称之为上下文有关文法的原因。务必考虑上下文，这也是称之为上下文有关文法的原因。并且一般不允许替换成空串并且一般不允许替换成空串。编译原理与技术编译原理与技术553.2 文法的分类文法的分类 1 型文法还有另一种定义形式：型文法还有另一种定义形式：定义定义3.11:文法文法G=
48、(VN，VT，P，S)，如果它是，如果它是0型文法，型文法，并且每个产生式并且每个产生式满足满足|（产生式（产生式S例外，但例外，但S不得出现在任何产生式的右部），则不得出现在任何产生式的右部），则G是一个是一个1型文法型文法。其中其中|和和|分别为分别为 和和 的长度。的长度。由该定义可知，由该定义可知，1型文法除了可能有型文法除了可能有S外，其余产生外，其余产生式右端的符号串长度大于等于左端符号串长度。式右端的符号串长度大于等于左端符号串长度。上述两种定义是等价的。即任一种形式定义的文法产上述两种定义是等价的。即任一种形式定义的文法产生的语言都可由另一种形式定义的文法产生。需要注意生的语言
49、都可由另一种形式定义的文法产生。需要注意的是，根据定义，含有的是，根据定义，含有 产生式的文法不是产生式的文法不是1型文法。由型文法。由于实际需要，我们将于实际需要，我们将S作为作为1型文法的特例接受。型文法的特例接受。编译原理与技术编译原理与技术563.2 文法的分类文法的分类例例3.18：文法文法G1S：S|A AaABC AabC CBBC bBbb bCbc cCcc则该文法是一个则该文法是一个1型文法，产生的语言为型文法，产生的语言为L1=ai bi ci|i0=,abc,aabbcc,1型文法产生的语言称为型文法产生的语言称为上下文有关语言上下文有关语言CSL，它可，它可由由线性限
50、界自动机线性限界自动机识别。识别。编译原理与技术编译原理与技术573.2 文法的分类文法的分类2型文法型文法 对对1型文法的产生式进一步限制，可得型文法的产生式进一步限制，可得2型文法。型文法。定义定义3.12:文法文法G=(VN，VT，P，S)，如果它是，如果它是1型型文法，并且每个产生式文法，并且每个产生式A满足满足AVN，V+，（产生式（产生式S例外），则例外），则G是一个是一个2型文法型文法。2型文法也称为型文法也称为上下文无关文法上下文无关文法（CFG,context-free grammars）。用）。用取代非终结符取代非终结符A时，与时，与A所在所在的上下文无关，因此取名为上下文
