《编译原理文法》由会员分享，可在线阅读，更多相关《编译原理文法（73页珍藏版）》请在金锄头文库上搜索。
1、编译原理编译原理_文法文法文法的直观概念和语言概述语言概述 表述一种语言时，无非是说明这种语言的句子，表述一种语言时，无非是说明这种语言的句子，如果语言只含有有穷多个句子，则只需列出句子如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，对于含有无穷句子的语言，存的有穷集就行了，对于含有无穷句子的语言，存在着如何给出它的有穷表示的问题。在着如何给出它的有穷表示的问题。 自然语言无法列出全部句子，但可以给出一些自然语言无法列出全部句子，但可以给出一些规则，用这些规则来说明规则，用这些规则来说明(或者定义或者定义)句子的组成句子的组成结构，用结构，用EBNF来表示这种句子的构成规则：来表示这
2、种句子的构成规则： 2EBNF表示句子的构成规则表示句子的构成规则句子句子 =主语谓语主语谓语主语主语 =代词名词代词名词代词代词 =我我你你他他名词名词 =王明王明大学生大学生工人工人英语英语谓语谓语 =动词直接宾语动词直接宾语动词动词 =是是学习学习直接宾语直接宾语 =代词名词代词名词 3 导出句子 首先首先去找去找 =左端的带有句子的规则并把它由左端的带有句子的规则并把它由 =右端的符右端的符号串代替，这个动作表示成：号串代替，这个动作表示成： 句子句子 主语谓语主语谓语 然后然后在得到的串主语谓语中，选取主语或谓在得到的串主语谓语中，选取主语或谓语，再用相应规则的语，再用相应规则的 =
3、右端代替之。比如，选取了主语右端代替之。比如，选取了主语，并采用规则主语，并采用规则主语 =代词，代词， 那么得到：那么得到：主语谓语主语谓语 代词谓语代词谓语， 重复做下去，即可得到一个句子。重复做下去，即可得到一个句子。 【例】句子：【例】句子：“我是大学生我是大学生”的全部动作过程是：的全部动作过程是：句子句子 主语谓语主语谓语 代词谓语代词谓语 我谓语我谓语 我动词直接宾语我动词直接宾语 我是直接宾语我是直接宾语 我是名词我是名词 我是大学生我是大学生4句子构成规则 “我是大学生我是大学生”的构成符合上述规则，而的构成符合上述规则，而“我大学生我大学生是是”不符合上述规则。这些规则成为
4、判别句子结构不符合上述规则。这些规则成为判别句子结构合法与否的依据，这些规则是一种元语言，用它合法与否的依据，这些规则是一种元语言，用它描述汉语。这里仅仅涉及汉语句子的结构描述。描述汉语。这里仅仅涉及汉语句子的结构描述。其中一种起描述作用的元语言称为其中一种起描述作用的元语言称为文法文法。5语言概述语言概述 语言是由句子组成的集合，是由一组符号所构成语言是由句子组成的集合，是由一组符号所构成的集合。的集合。汉语汉语所有符合汉语语法的句子的全体所有符合汉语语法的句子的全体英语英语所有符合英语语法的句子的全体所有符合英语语法的句子的全体程序设计语言程序设计语言所有该语言的程序的全体所有该语言的程序
5、的全体 每个句子构成的规律每个句子构成的规律研究语言研究语言 每个句子的含义每个句子的含义 每个句子和使用者的关系每个句子和使用者的关系6语言概述语言概述研究程序设计语言研究程序设计语言 每个程序构成的规律每个程序构成的规律 每个程序的含义每个程序的含义 每个程序和使用者的关系每个程序和使用者的关系语言研究的三个方面语言研究的三个方面 语法语法（Syntax）：表示构成语言句子的各个记号之间）：表示构成语言句子的各个记号之间的组合规律的组合规律 语义语义（Semantics）：表示各个记号的特定含义。）：表示各个记号的特定含义。（各个记号和记号所表示的对象之间的关系）（各个记号和记号所表示的对
6、象之间的关系） 语用语用（Pragmatics）：表示在各个记号所出现的行为）：表示在各个记号所出现的行为中，它们的来源、使用和影响。中，它们的来源、使用和影响。7语言概述语言概述每每种种语语言言具具有有两两个个可可识识别别的的特特性性，即即语语言言的的形形式式和该形式相关联的意义。和该形式相关联的意义。语语言言的的实实例例若若在在语语法法上上是是正正确确的的，其其相相关关联联的的意意义义可可以以从从两两个个观观点点来来看看，其其一一是是该该句句子子的的创创立立者者所所想想要要表表示示的的意意义义，另另一一是是接接收收者者所所检检验验到到的的意意义义。这这两两个个意意义义并并非非总总是是一一样
7、样的的，前前者者称称为为语语言言的的语语义义，后后者者是是其其语语用用意意义义。幽幽默默、双双关关语语和和谜谜语就是利用这两方面意义间的差异。语就是利用这两方面意义间的差异。8形式语言形式语言 如如果果不不考考虑虑语语义义和和语语用用，即即只只从从语语法法这这一一侧侧面面来看语言，这种意义下的语言称作来看语言，这种意义下的语言称作形式语言形式语言。 形形式式语语言言抽抽象象地地定定义义为为一一个个数数学学系系统统。“形形式式”是是指指这这样样的的事事实实：语语言言的的所所有有规规则则只只以以什什麽麽符符号号串串能出现的方式来陈述。能出现的方式来陈述。 形形式式语语言言理理论论是是对对符符号号串
8、串集集合合的的表表示示法法、结结构构及及其其特特性性的的研研究究。是是程程序序设设计计语语言言语语法法分分析析研研究究的的基础。基础。9语言的一般描述语言的一般描述程序设计语言是由一切程序所组成的集合，而程程序设计语言是由一切程序所组成的集合，而程序是由保留字，字母和数字这样一些基本符号所序是由保留字，字母和数字这样一些基本符号所组成，从字面上看，每个程序都是一个组成，从字面上看，每个程序都是一个“基本符号基本符号”串串，设有一基本符号集，那么程序设计语言可看，设有一基本符号集，那么程序设计语言可看成是成是在这个基本符号集上定义的、按一定规则构在这个基本符号集上定义的、按一定规则构成的一切基本
9、符号串组成的集合成的一切基本符号串组成的集合.10定义和记号定义和记号符号符号：可以相互区别的记号（元素）。字母是符：可以相互区别的记号（元素）。字母是符号，数字也是符号。号，数字也是符号。字母表字母表 ：符号（元素）的非空有穷集合。因此：符号（元素）的非空有穷集合。因此字母表也称为符号集。字母表也称为符号集。 不同的语言可以有不同的字母表，例如汉语的字不同的语言可以有不同的字母表，例如汉语的字母表中包括汉字、数字及标点符号等。母表中包括汉字、数字及标点符号等。C语言的语言的字母表是由字母、数字、若干专用符号。字母表是由字母、数字、若干专用符号。11定义和记号定义和记号符号串符号串：由字母表中
10、的符号组成的任何由字母表中的符号组成的任何有穷序列有穷序列称为符称为符号串号串.例如例如00 11 10 是字母表是字母表 =0，1上的符号串上的符号串. 字母表字母表A=a,b,c上的一些符号串有：上的一些符号串有：a,b,c,ab,aaca。 在符号串中，在符号串中，符号的顺序符号的顺序是很重要的，符号串是很重要的，符号串ab就不同就不同于于ba,abca和和aabc也不同。也不同。可以使用字母表示符号串，如可以使用字母表示符号串，如x=STR表示表示“x是由符号是由符号S、T和和R，并按此顺序并按此顺序组成的符号串组成的符号串”。符号串的长度：符号串的长度： 如果某符号串如果某符号串x中
11、有中有m个符号，则称其长个符号，则称其长度为度为m，表示为，表示为x=m，如，如001110的长度是的长度是6。空符号串：空符号串：即不包含任何符号的符号串，用即不包含任何符号的符号串，用表示，其长表示，其长度为度为0，即，即=0。12符号串的运算符号串的运算符号串的头、尾、固有头和固有尾符号串的头、尾、固有头和固有尾：如果如果z=xy是一符号串，那么是一符号串，那么x是是z的的头头，y是是z的的尾尾，如果，如果x是非空的，那么是非空的，那么y是是固有尾固有尾；同样如果；同样如果y非空，那么非空，那么x是是固有头固有头。例例:设设z=abc,那么那么z的头是的头是,a,ab,abc,除除abc
12、外，其它都是固外，其它都是固有头；有头；z的尾是的尾是,c,bc,abc,z的固有尾是的固有尾是,c,bc。 当对符号串当对符号串z=xy的头感兴趣而对其余部分不感兴趣时，的头感兴趣而对其余部分不感兴趣时，采用省略写法：采用省略写法：z=x； 如果只是为了强调如果只是为了强调x在符号串在符号串z中的某处出现，则可表示中的某处出现，则可表示为：为：z=x；符号；符号t是符号串是符号串z的第一个符号，则表示的第一个符号，则表示为为z=t。13符号串的运算符号串的运算符号串的连接符号串的连接：设设x和和y是符号串，它们的连接是符号串，它们的连接xy是把是把y的符的符号写在号写在x的符号之后得到的符号
13、串的符号之后得到的符号串. 由于由于的含义，显然有的含义，显然有x=x=x。例如例如 x=ST，y=abu，则它们的连接，则它们的连接xy=STabu，看出，看出x=2，y=3，xy=5符号串的方幂：符号串的方幂：符号串自身连接符号串自身连接n次得到的符号串次得到的符号串 an 定义为定义为 aaaa（n个个a），），a1=a, a2=aa且且a0=例；若例；若x=AB 则则: x0 = x1 =AB x2 = ABAB x3 = ABABAB xn = xxn-1 = xn-1 x (n0)14符号串的运算符号串的运算符号串集合：符号串集合：若集合若集合A中所有元素都是某字母表中所有元素都是
14、某字母表 上的符号串，上的符号串，则称则称A为字母表为字母表 上的符号串集合。上的符号串集合。两个符号串集合两个符号串集合A和和B的乘积的乘积 定义为定义为 AB = xy|x A且且y B 若若 集合集合A= ab,cde 集合集合B = 0,1 则则 AB = ab1,ab0,cde0,cde1 使用使用 * 表示表示 上的一切符号串（包括上的一切符号串（包括）组成的集合）组成的集合,称为称为的的闭包闭包。 上的上的除除外的所有符号串组成的集合记为外的所有符号串组成的集合记为 +,称为称为的的正闭正闭包包。15例：例：=a,b=a,b * *=,a,b,aa,ab,ba,bb,aaa,aa
15、b,=,a,b,aa,ab,ba,bb,aaa,aab, + +=a,b,aa,ab,ba,bb,aaa,aab,=a,b,aa,ab,ba,bb,aaa,aab,16定义和记号定义和记号语言语言是由句子组成的集合，是由一组符号所构成的集合。换言是由句子组成的集合，是由一组符号所构成的集合。换言之之,字母表字母表 上上的一个语言是的一个语言是 上的一些符号串的集合上的一些符号串的集合 (字母表字母表 上上的每个语言是的每个语言是 *的一个子集的一个子集)。例如：例如：字母表字母表=a,b =a,b ,* *=,a,b,aa,ab,ba,bb,aaa,aab,=,a,b,aa,ab,ba,bb,
16、aaa,aab,集合集合ab,aabb,aaabbb,aab,aabb,aaabbb,an nb bn n,或表示为或表示为w|ww|w* *且且w=aw=an nb bn n,n1,n1为为字母表字母表 上上的一个语言。的一个语言。集合集合a,aa,aaa,a,aa,aaa,或或表示为表示为w|ww|w* *且且w=aw=an n,n1 ,n1 为为字母表字母表 上上的一个语言。的一个语言。 是一个语言，是一个语言， 即即 是一个语言。是一个语言。17语言语言上上的有关运算的有关运算 设设L是是 上的一个语言上的一个语言,M是是 上的一个语言上的一个语言, 语言语言L和和M的并，交，差，补的
17、并，交，差，补是一个语言。是一个语言。 语言语言L和和M的并为的并为 L M，是一个语言是一个语言: w|w is in L or is in M 如：如： L1 =a,b,y,z M1 =1,28,9 L1 M1=a,b, y,z，1,28,9 语言语言L和和M的连接的连接是一个语言，记是一个语言，记为为 LM LM=st |sL且且 tM 如：如： L1M1 =a1,b1,y1,z1,a2,b2a9z9 有有L = L=L。 L的的n次连接次连接Ln= LL.L 18语言语言上上的运算的运算 语言语言L的的 闭包闭包记记为为 L*， L*= L0 L1 L2 . L0= ， Ln= L L
18、n-1= Ln-1 L,n 1 语言语言L的的正正闭包闭包记记为为 L+， L+= L1 L2 L3 . L+= LL*= L*L ，L*= L+ 如：如： L1 =a,b,y,z M1 =1,28,9 （L1 M1）=a,b, y,z，1,28,9 （L1 M1）*=a,b, y,z，1,28,9 ，aa,1a,xyz,6789st. L1（L1 M1）*=所有字母打头的字母和数字符号串所有字母打头的字母和数字符号串19文法和语言的形式定义文法和语言的形式定义如何来描述一种语言？如何来描述一种语言？如果语言是有穷的（只含有有穷多个句子），可如果语言是有穷的（只含有有穷多个句子），可以将句子逐
19、一列出来表示以将句子逐一列出来表示如果语言是无穷的，找出语言的有穷表示。语言如果语言是无穷的，找出语言的有穷表示。语言的有穷表示有两个途经：的有穷表示有两个途经：生成方式生成方式 （文法）：语言中的每个句子可以用严格定（文法）：语言中的每个句子可以用严格定义的规则来构造。义的规则来构造。识别方式识别方式（自动机）：用一个过程，当输入的一任意（自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止串属于语言时，该过程经有限次计算后就会停止并回并回答答“是是”，若不属于，要麽能停止，若不属于，要麽能停止并回答并回答“不是不是”，（要，（要麽永远继续下去。）麽永远继续下去。）
20、 20文法和语言的形式定义文法和语言的形式定义文法文法即是通过生成方式描述语言的：语言中的每个即是通过生成方式描述语言的：语言中的每个句子可以用严格定义的规则来构造。下面给出文句子可以用严格定义的规则来构造。下面给出文法的定义。进而在文法定义的基础上，给出推导法的定义。进而在文法定义的基础上，给出推导的概念，句型、句子和语言的定义。的概念，句型、句子和语言的定义。21文法的定义文法的定义文法文法G定义为定义为四元组四元组(VN，VT，P，S )其中其中VN为为非终结符号非终结符号(或语法实体，或变量或语法实体，或变量)集；集；VT为为终结符号集终结符号集；P为为产生式产生式(也称规则也称规则)
21、的集合；的集合； VN，VT和和P是非空有穷集。是非空有穷集。 S称作称作识别符号识别符号或或开始符号开始符号，它是一个非终结符，至少要在，它是一个非终结符，至少要在一条产生式中作为左部出现。一条产生式中作为左部出现。 VN和和VT不含公共的元素，即不含公共的元素，即VN VT = 用用V表示表示VN VT ，称为文法，称为文法G的字母表或字汇表的字母表或字汇表规则规则，也称产生式或生成式，也称产生式或生成式，是形如是形如或或 =的的(，)有有序对序对，其中，其中是字母表是字母表V的正闭包的正闭包V+中的一个符号，中的一个符号，是是V*中的一个符号。中的一个符号。称为规则的左部，称为规则的左部
22、，称作规则的右部。称作规则的右部。22文法的定义文法的定义例例: 文法文法G=（VN，VT，P，S）VN = S , VT = 0, 1 P= S0S1, S01 S为开始符号为开始符号23文法的定义文法的定义例例 文法文法G=（VN，VT，P，S） VN =标识符，字母，数字标识符，字母，数字 VT =a,b,c,x,y,z,0,1,9 P= a, z 0, 9 S=24文法的习惯写法文法的习惯写法只写出产生式只写出产生式 1 1 G： SaAb,Aab,AaAb,A 2 GS： SaAb , Aab,AaAb,A 3 GS: SaSb , Aab |aAb | 大写字母：非终结符大写字母：
23、非终结符 小写字母：终结符小写字母：终结符25推导的定义推导的定义1直接推导直接推导“” 如果如果是文法是文法G的产生式，的产生式，和和是是V V* *中的任意中的任意符号，若有符号，若有v,wv,w满足：满足： v=,w= v=,w= 则称则称v v直接产生直接产生w,w,或说或说w w是是v v的直接推导，也称的直接推导，也称w w直接直接归约到归约到v v，记作，记作 v v w w 例：例：G： S0S1， S01 0S1 00S11 00S11 000S111 000S111 00001111 S 0S126推导的定义推导的定义2 若存在直接推导的序列：若存在直接推导的序列：v =w
24、0 w1 . wn=w(n0) 则称则称这这个序列是一个从个序列是一个从v至至w的的长长度度为为n的推的推导导(简简称推称推导导)。或说。或说v推导出推导出w（推导长度为（推导长度为n）, 或说或说w归约到归约到v. 如果如果n1,记为记为v w 如果如果n0,记为记为v w(若有若有v w，或，或v=w)27推导的定义推导的定义2例：例：G： S0S1， S01 0S1 00S11 00S11 000S111 000S111 00001111 S 0S1 00S11 000S111 00001111 S 00001111 S 00001111 00S11 =* 00S1128句型、句子的定义
25、句型、句子的定义句型句型:有文法有文法G，若，若S =* x，则称，则称x是文法是文法G的句型。的句型。句子句子:有文法有文法G，若，若S =* x，且，且xVT*，则称，则称x是文法是文法 G的句子的句子 。例：例：G： S0S1， S01 S 0S1 00S11 000S111 00001111 G的句型：的句型：S,0S1 ,00S11 ,000S111,00001111 G的句子：的句子：00001111, 0129句型、句子的定义句型、句子的定义例：例：GE： EE+T|T TT*F|F F(E)|a EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a则
26、该文法的句子：用符号则该文法的句子：用符号a，+，*，( )构成构成 的算术表达式的算术表达式30语言的定义语言的定义 由文法由文法G生成的语言记为生成的语言记为L(G),它是文法它是文法G的的一切一切句子的集合句子的集合: L(G)=x|S =* x，S为文法开始符号，且为文法开始符号，且x VT* 例：例：G： S0S1， S01 L(G)=0n1n|n131语言的定义语言的定义例例: 文法文法GS：（1）SaSBE（2）SaBE（3）EBBE（4）aBab（5）bBbb（6）bEbe（7）eEee L(G)= anbnen | n1 32语言的定义语言的定义 S a S BE (SaSB
27、E) a aBEBE (SaBE) aabEBE (aBab ) aabBEE (EBBE ) aabbEE (bBbb) aabbeE （bEbe) aabbee （eEee) G生成的每个串都在生成的每个串都在L(G)中中 L(G)中的每个串确实能被中的每个串确实能被G生成生成33语言的定义语言的定义使用产生式使用产生式(1)n-1次，得到推导序列：次，得到推导序列：S =* an-1S(BE)n-1，然后使用产生式，然后使用产生式(2)1次，得到：次，得到：S =* an-1S(BE)n-1 an(BE)n。然后从。然后从an(BE)n继续推导，总是对继续推导，总是对EB使用产生式使用产
28、生式(3)的右部进行替换，而最终在得到的串中，所的右部进行替换，而最终在得到的串中，所有的有的B都先于所有的都先于所有的E。例如，若例如，若n=3, aaaBEBEBE aaaBBEEBE aaaBBEBEE aaaBBBEEE。即有：。即有： S =* anBnEn接着，使用产生式接着，使用产生式(4)一次，得到一次，得到S =* anbBn-1En，然后使用产，然后使用产生式生式(5)n-1次得到：次得到：S =* anbnEn，最后使用产生式，最后使用产生式(6)一次，使用产生式一次，使用产生式(7)n-1次，次，得到：得到：S =* anbnen 也能证明，对于也能证明，对于n1，串，
29、串anbnen是唯一形式的终结符号串是唯一形式的终结符号串34文法的等价文法的等价若若L(G1）=L（G2），则称文法），则称文法G1和和G2是等价的。是等价的。 文法文法G1A：A0R 与与G2S：S0S1 等价等价 A01 S01 RA135文法的类型文法的类型 通过对产生式施加不同的限制，通过对产生式施加不同的限制，Chomsky将文法将文法分为四种类型：分为四种类型：0型文法：型文法：对任一产生式对任一产生式，都有，都有(V(VN NVVT T) )* *，且至少要包含一个非终结符，且至少要包含一个非终结符, , (V(VN NVVT T) )* *1型文法：型文法：对任一产生式对任一
30、产生式，都有，都有|， 仅仅仅仅 S S除外除外2型文法：型文法：对任一产生式对任一产生式，都有，都有VVN N ， (V(VN NVVT T) )* *3 3型文法：型文法：任一产生式任一产生式的形式都为的形式都为AaBAaB或或AaAa，其中，其中AVAVN N ，BVBVN N ，aVaVT T36文法的类型文法的类型1 1型文法型文法例：例：1 1型（上下文有关）文法型（上下文有关）文法 文法文法GS： SCD AbbACaCA BaaBCbCB BbbBADaD CBDbD DAabD37文法的类型文法的类型2 2型文法型文法例：例：2 2型（上下文无关）文法型（上下文无关）文法 文
31、法文法GS：SABABS|0BSA|138文法的类型文法的类型3 3型文法型文法GS： S0A|1B|0A0A|1B|0SB1B|1|0 GI：I lTI lT lTT dTT lT d39文法的类型文法的类型2型文法型文法1型文法型文法0型文法型文法四种四种文法文法之间之间的的逐级逐级“包含包含”关系关系3型文法型文法40文法和语言文法和语言 0型文法产生的语言称为型文法产生的语言称为0型语言型语言1 1型文法或上下文有关文法（型文法或上下文有关文法（ CSG ）产生的语产生的语言称为言称为1 1型语言型语言或上下文有关或上下文有关语言（语言（CSL）2 2型文法或上下文无关文法（型文法或上
32、下文无关文法（ CFG ）产生的语产生的语言称为言称为2型语言型语言或上下文无关或上下文无关语言（语言（ CF L ） 3 3型文法或正则（正规）文法（型文法或正则（正规）文法（ RG ）产生的语产生的语言称为言称为3型语言型语言正则（正规）正则（正规）语言（语言（ RL ） 41文法和语言文法和语言 四种文法之间的关系是将四种文法之间的关系是将产生式产生式做进一步限制而做进一步限制而定义的。定义的。 语言之间的关系依次：有不是上下文有关语言的语言之间的关系依次：有不是上下文有关语言的0型语言，有不是上下文无关语言的型语言，有不是上下文无关语言的1型语言，有不型语言，有不是正则语言的上下文无关
33、语言。是正则语言的上下文无关语言。42文法和识别系统间的关系文法和识别系统间的关系 0型文法（短语结构文法）的能力相当于图灵机，型文法（短语结构文法）的能力相当于图灵机，可以表征任何递归可枚举集，而且任何可以表征任何递归可枚举集，而且任何0型语言都型语言都是递归可枚举的是递归可枚举的 1型文法（上下文有关文法）：产生式的形式为型文法（上下文有关文法）：产生式的形式为1 1AA2 21 12 2，即只有，即只有A A出现在出现在1 1和和2 2的上的上下文中时，才允许下文中时，才允许取代取代A A。其识别系统是线性界。其识别系统是线性界限自动机。限自动机。43文法和识别系统间的关系文法和识别系统
34、间的关系 2型文法（上下文无关文法型文法（上下文无关文法CFG）：产生式的形式）：产生式的形式为为AA，取代取代A A时与时与A A的上下文无关。其识别系的上下文无关。其识别系统是不确定的下推自动机。统是不确定的下推自动机。3型文法（正规文法型文法（正规文法RG）：产生的语言是有穷自）：产生的语言是有穷自动机（动机（FA）所接受的集合所接受的集合44文法描述文法文法G=(E,+,*,i,(,),P,E)其中其中P为：为：Ei , EE+E , EE*E , E(E) E表示算术表达式表示算术表达式, i表示程序的表示程序的“变量变量”，该文法定义了由变，该文法定义了由变量，量，+，*,( )组
35、成的算术表达式的语法结构，即：组成的算术表达式的语法结构，即： 变量是算术表达式；若变量是算术表达式；若E1和和E2是算术表达式，则是算术表达式，则E1+ E2，E1*E2和和(E1)也是算术表达式也是算术表达式描述一种简单赋值语句的产生式：描述一种简单赋值语句的产生式：赋值语句赋值语句i =E描述条件语句的产生式：描述条件语句的产生式：条件语句条件语句if条件条件then语句语句 if条件条件then语句语句else语句语句45句型、推导GE： EE+T|T TT*F|F F(E)|aEE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a EE+T E+T*F E+
36、T*a E+F*a E+a*a T+a*a F+a*a a+a*aEE+T T+T T+T*F F+T*F F+F*F a+F*F a+F*a a+a*a46规范推导规范推导 规范句型规范句型最左（最右）推导：在推导的任何一步最左（最右）推导：在推导的任何一步，其，其中中、是句型，都是对是句型，都是对中的最左（右）非终中的最左（右）非终结符进行替换结符进行替换最右推导被称为规范推导。最右推导被称为规范推导。由规范推导所得的句型称为规范句型由规范推导所得的句型称为规范句型47语法树语法树设设G=( VN,VT,P,S)为一为一CFG，若一棵树满足下列，若一棵树满足下列4个条件，则个条件，则此树称
37、作此树称作G的语法树的语法树(推导树推导树)(派生树）：派生树）：1. 每个结点都有一个标记，此标记是每个结点都有一个标记，此标记是V的一个符号的一个符号2. 根的标记是根的标记是S3. 若一结点若一结点n至少有一个它自己除外的子孙，并且有标记至少有一个它自己除外的子孙，并且有标记A，则肯定则肯定AVN4. 如果结点如果结点n有标记有标记A,其直接子孙结点从左到右的次序是其直接子孙结点从左到右的次序是n1，n2，nk，其标记分别为，其标记分别为A1，A2，Ak，那么，那么AA1A2，Ak一定是一定是P中的一个产生式中的一个产生式48语法树语法树句型推导的表示句型推导的表示给定文法给定文法G=(
38、VN,VT,P,S)，对于，对于G的任何句型都能构的任何句型都能构造与之关联的语法树造与之关联的语法树(推导树推导树)定理：定理： G为上下文无关文法，为上下文无关文法，对于对于，有，有S =* ，当且仅当当且仅当文法文法G有以有以为结果的一棵语法树为结果的一棵语法树(推导树推导树)49语法树的构造语法树的构造G=(S,A),(a,b),P,S)P: 1.S-aAS 2.A-SbA 3.A-SS 4.S-a 5.A-baSa A S S b A a a b a50句子句子aabbaa的推导过程的推导过程S=aAS=aAa=aSbAa=aSbbaa=aabbaaS=aAS=aSbAS=aabAS
39、=aabbaS=aabbaaS=aAS=aSbAS=aSbAa=aabAa=aabbaa如果在推导的任何一步(句型)，都是对中的最左(最右)非终结符进行替换，则称这种推导为最左(最右)推导.在形式语言中，最右推导被称为规范推导.右规范推导得到的句型称为规范句型51语法树构造语法树构造E EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*aE EE+T E+T*F E+T*a E+F*a E+a*a T+a*a F+a*a a+a*aE EE+T T+T T+T*F F+T*F F+F*F a+F*F a+F*a a+a*a E E E + T E + T T T *
40、 F T T * F F F a F F a a a a a 看不出句型中的符号被替代的顺序看不出句型中的符号被替代的顺序GE： EE+T|T TT*F|F F(E)|a52语法树实例 例例: GS:SaASASbAASSSaAba S a A S S b A a a b a句型句型aabbaa的的语法树语法树（推导树）（推导树）叶子结点叶子结点：树中没有子孙的结点。：树中没有子孙的结点。从左到右读出推导树的叶子标记连接成的文从左到右读出推导树的叶子标记连接成的文法符号法符号串串，为，为GS的的句型句型。也把该推导树称。也把该推导树称为该为该句型句型的的语法树语法树。53上下文无关文法的语法树
41、上下文无关文法的语法树推导过程中推导过程中施用施用产生式产生式的的顺序顺序 例例: GS:SaASASbAASSSaAba S a A S S b A a a b aSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa54语法树问题语法树问题一棵一棵语法法树表示了一个句型的种种可能的表示了一个句型的种种可能的( (但未必是但未必是所有的所有的) )不同推不同推导过程，包括最左程，包括最左( (最右最右) )推推导。但。但是，一个句型是否只是，一个句型是否只对应唯一的一棵唯一的一棵语法法树呢呢? ?
42、一一个句型是否只有唯一的一个最左个句型是否只有唯一的一个最左( (最右最右) )推推导呢呢? ?55语法树问题语法树问题例：例：GE:GE:E iE iE E+EE E+EE E*EE E*EE (E)E (E) E E E + E E + E E * E i E * E i i i i i E E E * E E * E i E + E i E + E i i i i句型句型 i*i+i 的两个不同的最左推导：的两个不同的最左推导：推导推导1：E E+E E*E+E i*E+E i*i+E i*i+i推导推导2：E E*E i*E i*E+E i*i+E i*i+i56二义文法二义文法 若一
43、个文法存在某个句子对应两棵不同的语法树，若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是则称这个文法是二义二义的。或者，若一个文法存在的。或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这某个句子有两个不同的最左（右）推导，则称这个文法是个文法是二义二义的。的。 判定任给的一个上下文无关文法是否二义，或它是判定任给的一个上下文无关文法是否二义，或它是否产生一个先天二义的上下文无关语言，这两个否产生一个先天二义的上下文无关语言，这两个问题是递归不可解的，但可以为无二义性寻找一问题是递归不可解的，但可以为无二义性寻找一组充分条件组充分条件 57二义文法二义文法文法的二义性和语
44、言的二义性是两个不同的概念。文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同的文法因为可能有两个不同的文法G G和和GG，其中，其中G G是二义是二义的，但是却有的，但是却有L(G)=L(G)L(G)=L(G)，也就是说，这两个文，也就是说，这两个文法所产生的语言是相同的。法所产生的语言是相同的。如果产生上下文无关语言的每一个文法都是二义的，如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的。对于一个程序设计语则说此语言是先天二义的。对于一个程序设计语言来说，常常希望它的文法是无二义的，因为希言来说，常常希望它的文法是无二义的，因为希望对它的每个语句的分析是唯一
45、的。望对它的每个语句的分析是唯一的。58二义文法二义文法二义文法改造为无二义文法二义文法改造为无二义文法GE: E i GEGE: E i GE：E T|E+TE T|E+T E E+E T F|T*F E E+E T F|T*F E E*E F E E*E F （E E）|i|i E (E) E (E) 规定优先顺序和结合律规定优先顺序和结合律 59句型的分析句型的分析句型分析句型分析就是识别一个符号串是否为某文法的句就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。型，是某个推导的构造过程。在语言的编译实现中，把完成句型分析的程序称在语言的编译实现中，把完成句型分析的程序称为为分
46、析程序分析程序或或识别程序识别程序。分析算法又称。分析算法又称识别算法识别算法。从左到右的分析算法从左到右的分析算法，即总是从左到右地识别输，即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号，直到分析结束。依次识别右边的一个符号，直到分析结束。60句型的分析算法分类句型的分析算法分类自上而下分析法自上而下分析法：从文法的开始符号出发，反复使用文法的产生式，从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导。从文法符号开始，寻找与输入符号串匹配的推导。从文法符号开始，将它做为语法树的根，向下逐步建
47、立语法树，使将它做为语法树的根，向下逐步建立语法树，使语法树的结果正好是输入符号串语法树的结果正好是输入符号串61句型的分析算法分类句型的分析算法分类自下而上分析法自下而上分析法：从输入符号串开始，逐步进行归约，直至归约到从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。是从输入符号串开始，以它做文法的开始符号。是从输入符号串开始，以它做为语法树的结果，自底向上地构造语法树为语法树的结果，自底向上地构造语法树62自上而下的语法分析自上而下的语法分析例：文法例：文法 G：S cAd A ab A a识别输入串识别输入串w=cabd是否为该文法的是否为该文法的句子句子SSScAdcAd a
48、 b推导过程：推导过程：S cAd cAd cabd63自下而上的语法分析自下而上的语法分析例：文法例：文法G： S cAd A ab A a识别输入串识别输入串w=cabd是否该文法的是否该文法的句子句子SAA c a b d c a b d c a b d 规约规约过程构造的推导：过程构造的推导： cAd cabd S cAd64自上而下的语法分析自上而下的语法分析(1)S cAd (2) A ab (3)A a识别输入串识别输入串w=cabd是否为该文法的句子是否为该文法的句子若若S cAd 后选择后选择(3)扩展扩展A，S cAd cad那将会那将会w的第二个符号可以与叶子结点的第二个
49、符号可以与叶子结点a得以匹配，得以匹配，但第三个符号却不能与下一叶子结点但第三个符号却不能与下一叶子结点d匹配匹配,分析分析失败失败,识别程序不能为串识别程序不能为串cabd构造语法树，即构造语法树，即cabd不是句子不是句子.65自下而上的语法分析自下而上的语法分析(1)S cAd (2) A ab (3)A a识别输入串识别输入串w=cabd是否为该文法的句子是否为该文法的句子对串对串cabd的分析中，如果不是选择的分析中，如果不是选择ab用产生式用产生式(2)而是选择而是选择a用产生式用产生式(3)将将a归约到了归约到了A，那么最终，那么最终就达不到归约到就达不到归约到S的结果，因而也无
50、从知道的结果，因而也无从知道cabd是一个句子是一个句子66句型分析的有关问题句型分析的有关问题在自上而下的分析方法中在自上而下的分析方法中如何选择如何选择使用使用哪个产生式哪个产生式进行推导？进行推导？假定要被代换的最左非终结符号是假定要被代换的最左非终结符号是B，且有，且有n条规则：条规则：BA1|A2|An，那么如何确定用哪个右部去替代，那么如何确定用哪个右部去替代B？在自下而上的分析方法中在自下而上的分析方法中如何识别可归约的串如何识别可归约的串？在分析程序工作的每一步，都是从当前串中在分析程序工作的每一步，都是从当前串中选择一选择一个子串，将它归约到某个非终结符号，个子串，将它归约到
51、某个非终结符号，该子串称为该子串称为“可归约串可归约串”。67句句 柄柄 文法文法GS 句型的短语句型的短语 S A且且 A ，则称则称是句型是句型 相对于非终结符相对于非终结符A的短语的短语 句型的直接短语句型的直接短语 若有若有A ，则称则称是句型是句型相对于相对于 非终结符非终结符A 的直接短语的直接短语 句型的句柄句型的句柄 一个句型的最左直接短语称为该句型的句柄一个句型的最左直接短语称为该句型的句柄68例例 ：i*i+i i*i+i 的短语、直接短语和句柄的短语、直接短语和句柄 E E + T T FT * F i3 短语短语：i1* * i2+ + i3， i1* * i2 ，F
52、i2 i1 ， i2 ， i3 。 i1 直接短语直接短语： i1 ， i2 ， i3 。句柄句柄： i1 GEGE：EE+T|TEE+T|T TT*F|F TT*F|F F(E)|i F(E)|i句型：句型：i*i+ii*i+i69化简文法化简文法文法中不含有文法中不含有有害规则有害规则和和多余规则多余规则有害规则有害规则：形如：形如UU的产生式。会引起文法的二义的产生式。会引起文法的二义性性多余规则多余规则：指文法中任何句子的推导都不会用到的：指文法中任何句子的推导都不会用到的规则，此规则在文法中以两种形式出现：规则，此规则在文法中以两种形式出现：1. 文法中某些非终结符不在任何规则的右部
53、出现，文法中某些非终结符不在任何规则的右部出现，该非终结符称为该非终结符称为不可到达的不可到达的。2. 文法中某些非终结符，由它不能推出终结符号文法中某些非终结符，由它不能推出终结符号串，该非终结符称为串，该非终结符称为不可终止的不可终止的。70化简文法化简文法例：例：GS ： 1. SBe 2. BCe D为不可到达为不可到达 3. BAf C为不可终止为不可终止 4. AAe 5. Ae 6. CCf 7. Df 产生式产生式 2，6，7为为多余规则多余规则应去掉。应去掉。71非终结符条件非终结符条件 对于文法对于文法GS，为了保证任一非终结符，为了保证任一非终结符A在在句子句子推导中出现
54、，必须满足如下两个条件：推导中出现，必须满足如下两个条件： 1. A必须在某句型中出现必须在某句型中出现 即有即有S A，其中，其中，属于属于V V* * 2. 必须能够从必须能够从A推出终结符号串推出终结符号串t来来 即即A t，其中，其中t VT*72上下文无关文法中的上下文无关文法中的规则规则上下文无关文法中某些规则可具有形式上下文无关文法中某些规则可具有形式A，称这种规则称这种规则为为规则规则因为因为规则会使得有关文法的一些讨论和证明变得复杂规则会使得有关文法的一些讨论和证明变得复杂,有有时会限制这种规则的出现时会限制这种规则的出现两种定义的唯一差别是两种定义的唯一差别是句子在不在语言中句子在不在语言中文法构思的启示是要找出语言的有穷描述，而如果语言文法构思的启示是要找出语言的有穷描述，而如果语言L有一个有穷的描述，则有一个有穷的描述，则L1=L 也同样有一个有穷的也同样有一个有穷的描述，并且可以证明，若描述，并且可以证明，若L是上下文有关语言、上下文无是上下文有关语言、上下文无关语言或正规语言，则关语言或正规语言，则L 和和L-分别是上下文有分别是上下文有关语言、上下文无关语言和正规语言。关语言、上下文无关语言和正规语言。73
