编译原理文法和语言精选文档.ppt

《编译原理文法和语言精选文档.ppt》由会员分享，可在线阅读，更多相关《编译原理文法和语言精选文档.ppt（59页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、编译原理文法和语言1本讲稿第一页，共五十九页第第2章章文法和语言文法和语言【学习目标学习目标】本章是为语言的语法描述寻求工具本章是为语言的语法描述寻求工具 掌握对程序设计语言给出精确、无二义掌握对程序设计语言给出精确、无二义（严谨、易读）的语法描述的手段之一（严谨、易读）的语法描述的手段之一文法。文法。对形式语言的理论有一个初步基础对形式语言的理论有一个初步基础 根据文法的特点指导语法分析过程根据文法的特点指导语法分析过程2本讲稿第二页，共五十九页2.1 文法的直观表示文法的直观表示文法：文法：阐明语法的一个工具，也可以说是以有穷的集合刻阐明语法的一个工具，也可以说是以有穷的集合刻画无穷的集合

2、的一个工具。画无穷的集合的一个工具。语言：语言：程序设计语言。程序设计语言。一、语言概述一、语言概述4语言是由符合语法的句子组成的集合。语言是由符合语法的句子组成的集合。汉语汉语-所有符合汉语语法的句子的全体所有符合汉语语法的句子的全体英语英语-所有符合英语语法的句子的全体所有符合英语语法的句子的全体程序设计语言程序设计语言-所有该语言的程序的全体所有该语言的程序的全体 每个句子构成的规律每个句子构成的规律语法语法4研究语言研究语言 每个句子的含义每个句子的含义 语义语义 每个句子和使用者的关系每个句子和使用者的关系语用语用3本讲稿第三页，共五十九页形式语言：只考虑语法而不考虑语义的符号语言。

3、形式语言：只考虑语法而不考虑语义的符号语言。4每种语言具有两个可识别的特性每种语言具有两个可识别的特性语言的形式语言的形式与该形式相关联的意义与该形式相关联的意义4“形式形式”指语言的所有规则，描述出现什么符号指语言的所有规则，描述出现什么符号串串4语言可以看成在一个基本符号集上定义的，按一语言可以看成在一个基本符号集上定义的，按一定规则构成的基本符号串组成的所有集合。定规则构成的基本符号串组成的所有集合。4形式语言理论是对符号串集合的表示法、结构及形式语言理论是对符号串集合的表示法、结构及其特性的研究，是程序设计语言语法分析研究的其特性的研究，是程序设计语言语法分析研究的基础。基础。4本讲稿

4、第四页，共五十九页4表达语言时，一般无法穷尽语言的所有句子，表达语言时，一般无法穷尽语言的所有句子，常用规则加以描述常用规则加以描述4 例：汉语句子的构成规则：例：汉语句子的构成规则：句子句子=主语主语谓语谓语主语主语=代词代词|名词名词代词代词=我我|你你|他他名词名词=王明王明|大学生大学生|工人工人|英语英语谓语谓语=动词动词直接宾语直接宾语动词动词=是是|学习学习直接宾语直接宾语=代词代词|名词名词二、文法的直观概念二、文法的直观概念5本讲稿第五页，共五十九页推导：推导：“我是大学生我是大学生”是汉语的一个句子是汉语的一个句子句子句子 主语主语 谓语谓语 代词代词谓语谓语 我我谓语谓语

5、 我我动词动词直接宾语直接宾语 我是我是直接宾语直接宾语 我是我是名词名词 我是大学生我是大学生 6本讲稿第六页，共五十九页2.2 符号与符号串符号与符号串一、相关概念一、相关概念程序设计语言是由程序构成的集合，程序是由基程序设计语言是由程序构成的集合，程序是由基本符号按照一定的规则构成的集合。本符号按照一定的规则构成的集合。1.符号、字母表和符号串符号、字母表和符号串4基本符号：基本符号：可以相互区别的基本元素，如字母，可以相互区别的基本元素，如字母，数字，标点符号。数字，标点符号。4字母表：字母表：基本符号的非空有穷集合，常用基本符号的非空有穷集合，常用表示。表示。例：例：=0,1，=a,

6、b,c,x,y,z7本讲稿第七页，共五十九页4符号串：由字母表中的符号串：由字母表中的符号构成的任何有穷序列符号构成的任何有穷序列称为符号串。称为符号串。符号串中的符号是有顺序的。符号串中的符号是有顺序的。例如例如 =0,1上的符号串上的符号串0,1,00,01,11,10 注意：注意：表示空符号串表示空符号串,它表示不包含任何符号串，它表示不包含任何符号串，不是不是空格符。空格符。符号串集合：符号串集合：字母表上若干个符号串组成的集合字母表上若干个符号串组成的集合.例：字母表例：字母表=0,1 的符号串集合的符号串集合A=1,00,01;约定：小写字母约定：小写字母 a,b,r表示符号表示符

7、号.小写字母小写字母 s,t,z表示符号串表示符号串;8本讲稿第八页，共五十九页4符号串符号串s的头（前缀）和尾（后缀）的头（前缀）和尾（后缀）：如果如果s=xy是一符号串，那么是一符号串，那么x是是s的头，的头，y是是s的的尾。若尾。若x是非空，则是非空，则y是固有尾；若是固有尾；若y非空，则非空，则x是固有头。是固有头。前缀前缀：移走符号串：移走符号串s尾部的零个或多个符号得尾部的零个或多个符号得到的串。到的串。如：设如：设s=abc,那么那么s的前缀是的前缀是，a，ab，abc 后缀：后缀：移走符号串移走符号串s头部的零个或多个符号头部的零个或多个符号得到的串。得到的串。如：如：s=ab

8、c的后缀是的后缀是，c，bc，abc，s的固有尾是的固有尾是，c，bc。4 9本讲稿第九页，共五十九页4符号串符号串s的子串：的子串：从从s中删去中删去任何任何前缀或后缀得到的串前缀或后缀得到的串.如如:bc是符号串是符号串abc的一个子串的一个子串.4对符号串对符号串s，s和和两者都两者都是符号串是符号串s的前缀、的前缀、后缀和子串。后缀和子串。4符号串符号串s的真前缀，真后缀，真子串：的真前缀，真后缀，真子串：任何非空符号串任何非空符号串 x，是，是s的前缀，后缀或子的前缀，后缀或子串，并且串，并且 s x10本讲稿第十页，共五十九页2.符号串的运算符号串的运算(1)符号串相等：符号串相等

9、：符号串符号串x，y，如果两者诸符号依次相等，则两，如果两者诸符号依次相等，则两符号串相等。符号串相等。(2)符号串的长度：符号串的长度：符号串中包含符号的个数。符号串中包含符号的个数。|abc|=3；|=0；(3)符号串的连结：符号串的连结：x=abc，y=def 则则xy=abcdef；yx=defabc；xy yx x=x =x；11本讲稿第十一页，共五十九页(4)符号串集合的乘积：符号串集合的乘积：设设A、B为两个符号串集合，其乘积为为两个符号串集合，其乘积为AB=xy|x A，y B；例：例：A=aa，bb，B=cc，dd，则，则AB=aacc，aadd，bbcc，bbdd A=A

10、=A；(5)空集：空集：不含任何元素的集合称为空集。记为不含任何元素的集合称为空集。记为；对任何集合对任何集合A：A =A=;注意：注意：12本讲稿第十二页，共五十九页(6)符号串的方幂：符号串的方幂：x是字母表上的符号串，则是字母表上的符号串，则x的幂运算为：的幂运算为：x0=;x1=x;x2=xx;xn=xn-1x=x xn-1 (n0)xn表示表示n个个x相连结。相连结。eg：x=ok；则；则 x0=;x1=ok;x2=okok;(7)符号串集合的方幂：符号串集合的方幂：A为符号串集合，则为符号串集合，则A的幂运算为：的幂运算为：A0=;A1=A;A2=AA;.An=An-1A=AAn-

11、1;(n0)A=aa，bb，则，则A0=；A1=aa，bb；A2=AA=aaaa，aabb，bbaa，bbbb;.13本讲稿第十三页，共五十九页(8)符号串集合的闭包和正闭包符号串集合的闭包和正闭包集合集合A的闭包表示为的闭包表示为A*（亦称为自反闭包或星（亦称为自反闭包或星闭包）定义为：闭包）定义为：A*=A0 A1 A2 A3 =Ak，k0正闭包表示为正闭包表示为A+具体定义为具体定义为A+=A1 A2 A3 =Ak，k1由定义可以看到由定义可以看到A*=A0 A+例：例：=a,b *=,a,b,aa,ab,ba,bb,aaa,aab,+=a,b,aa,ab,ba,bb,aaa,aab,1

12、4本讲稿第十四页，共五十九页3、语言、语言(1)由由一一组组符符号号所所构构成成的的集集合合。即即：字字母母表表 上上的的每个语言是每个语言是*的一个子集。的一个子集。例如：例如：字母表字母表=a,b=a,b，*=,a,b,aa,ab,ba,bb,aaa,aab,=,a,b,aa,ab,ba,bb,aaa,aab,集合集合ab,aabb,aaabbb,ab,aabb,aaabbb,a,an nb bn n,或表示为或表示为w|ww|w*且且w=aw=an nb bn n,n1,n1为为字母表字母表 上上的一个语的一个语言。言。集合集合a,aa,aaa,a,aa,aaa,或表示为或表示为w|ww

13、|w*，且且w=aw=an n，n1 n1 为为字母表字母表 上上的一个语言。的一个语言。(2)是一个语言。是一个语言。(3)即即 是一个语言。是一个语言。15本讲稿第十五页，共五十九页2.3 文法和语言的形式定义文法和语言的形式定义如何来描述一种语言？如何来描述一种语言？如果语言是有穷的（只含有有穷多个句子），可以将如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示句子逐一列出来表示如果语言是无穷的，找出语言的如果语言是无穷的，找出语言的有穷表示有穷表示。语言的有。语言的有穷表示有两个途径：穷表示有两个途径：生成方式生成方式（文法）：（文法）：语言中的每个句子可以用严格语言中的

14、每个句子可以用严格定义的规则来构造。定义的规则来构造。识别方式（自动机）：识别方式（自动机）：用一个过程，当输入的一个任意串用一个过程，当输入的一个任意串属于语言时，该过程经有限次计算后就会停止并回答属于语言时，该过程经有限次计算后就会停止并回答“是是”，若不属于，要么能停止并回答，若不属于，要么能停止并回答“不是不是”，（要么永远，（要么永远继续下去。）继续下去。）16本讲稿第十六页，共五十九页一、规则（重写规则、产生式或生成式）一、规则（重写规则、产生式或生成式）4规则是形如规则是形如或或=的的(，)有序对，有序对，其其中中 V+，V*中的一个符号中的一个符号称为规则的左部称为规则的左部称

15、作规则的右部。称作规则的右部。4例：例：4文法可利用规则来描述。文法可利用规则来描述。17本讲稿第十七页，共五十九页二、文法的定义二、文法的定义1、文法、文法G定义为四元组定义为四元组(VN，VT，P，S)其中其中VN：非终结符号；非终结符号；VT：终结符号集；：终结符号集；P：规则集：规则集合；合；VN，VT和和P是非空有穷集。是非空有穷集。S：开始符或识别符，是一个非终结符，至少要在：开始符或识别符，是一个非终结符，至少要在一条规则的一条规则的左部左部出现。出现。VN VT=，V=VN VT，V称为文法称为文法G的字母表的字母表例例1：文法：文法G=(VN，VT，P，S)，其中其中 VN=

16、S，VT=0，1，P=S0S1，S01。18本讲稿第十八页，共五十九页文法文法G习惯上只将规则写出。习惯上只将规则写出。如例如例1还可以写成：还可以写成：G：S0S1 S01或或GS：S0S1S01 或或GS：S0S1|S0119本讲稿第十九页，共五十九页总结一个文法的几种写法总结一个文法的几种写法 G=(S,A，a,b，P，S)其中其中P：SaAb Aab AaAb A G：SaAb Aab AaAb A GS：S aAb Aab AaAb A GS：SaAb Aab|aAb|20本讲稿第二十页，共五十九页三、推导的定义三、推导的定义用文法定义语言的中心思想是：从文法的开始符号出发，反复使用

17、用文法定义语言的中心思想是：从文法的开始符号出发，反复使用合适规则，对非终结符施行替换和展开。合适规则，对非终结符施行替换和展开。1 1、直接直接推导：推导：是文法是文法G G的产生式，若有的产生式，若有v v，w w满足：满足：v=v=，w=,w=,其中其中VV*,V,V*。则称。则称v v直接推导到直接推导到w w,或或w w直接归直接归约到约到v v记作记作 v vw w，2 2、推导：、推导：如果存在直接推导的序列：如果存在直接推导的序列：v=Wv=W0 0 W W1 1 W W2 2 W Wn n=w,=w,(n(n0)0)；称；称v v推导出推导出w(w(推导长度为推导长度为n)n

18、)，或称，或称w w归约到归约到v v。记作记作v wv w。若有若有v wv w，或，或v=wv=w，则记作，则记作v v w w，(n(n=0)=0)*21本讲稿第二十一页，共五十九页例3：G：S0S1，S01 0S1 00S11 00S11 000S111 000S111 00001111 S 0S1 00S11 000S111 00001111 S 00001111 S S 00S11 00S11+*22本讲稿第二十二页，共五十九页43、规范推导、规范推导最左最左(最右最右)推导：在推导的任何一步推导：在推导的任何一步，其，其中中、是句型，都是对是句型，都是对中的最左（右）非中的最左（

19、右）非终结符进行替换终结符进行替换 最右推导被称为规范推导。最右推导被称为规范推导。例例4：GE E：EE+T|TEE+T|T TT*F|F TT*F|F F(E)|a F(E)|aE EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a（最左推导最左推导）E EE+T E+T*F E+T*a E+F*a E+a*a T+a*a F+a*a a+a*a（最右推导最右推导）23本讲稿第二十三页，共五十九页四、句型、句子和语言的定义四、句型、句子和语言的定义1.句型句型:文法文法GS，若，若S x，则称，则称x是是G的句型。的句型。2.句子句子:文法文法GS，若，若S

20、x，且，且xVT*，则称，则称x是是G的句子。句子是句型的特殊，只包含终结符。的句子。句子是句型的特殊，只包含终结符。例例5 5：G G：S0S1，S01 S 0S1 00S11 000S111 00001111 G的句型的句型S,0S1,00S11,000S111,00001111 G的句子的句子000011113.语言语言:文法文法G的一切句子的集合的一切句子的集合,记为记为L(G)，*24本讲稿第二十四页，共五十九页例例 6 文法文法GS：（1）SaSBE（2）SaBE（3）EBBE（4）aBab（5）bBbb（6）bEbe（7）eEee SanBnEn anbnen 则则 L（G）=a

21、nbnen|n1 因为因为San-1S（BE）n-1 an（BE）n，继续，继续推导时，将用规则推导时，将用规则(3)(7)替换替换*25本讲稿第二十五页，共五十九页S a S BE (SaSBE)a aBEBE (SaBE)aabEBE(aBab)aabBEE(EBBE)aabbEE（bBbb)aabbeE（bEbe)aabbee（eEee)G生成的每个串都在生成的每个串都在L(G)中中L(G)中的每个串确实能被中的每个串确实能被G生成生成26本讲稿第二十六页，共五十九页五、语言和文法五、语言和文法4给定一个文法，能从结构上唯一确定其语言给定一个文法，能从结构上唯一确定其语言4给定一个语言，

22、不能唯一确定其文法，即一个给定一个语言，不能唯一确定其文法，即一个语言可有多个文法与之对应语言可有多个文法与之对应4已知语言描述，写出文法已知语言描述，写出文法，应满足：，应满足：所描述的语言的任何句子都能由该文法产生所描述的语言的任何句子都能由该文法产生该文法推导不出不是已知语言的任何句子该文法推导不出不是已知语言的任何句子4已知文法，写出语言描述已知文法，写出语言描述，应满足：，应满足：该文法能推导出的任何句子都包含在所描述的该文法能推导出的任何句子都包含在所描述的语言中语言中描述的语言中不包含该文法推导不出的句子描述的语言中不包含该文法推导不出的句子27本讲稿第二十七页，共五十九页六、文

23、法的等价六、文法的等价若若L（G1）=L（G2），称文法），称文法G1和和G2是等价的是等价的如文法如文法G G1AA：A0R A0R 与与G G2SS：S0S1 S0S1 等价等价 A01 S01A01 S01 RA1 RA1作业：作业：P47:1P47:1，4 4，5 528本讲稿第二十八页，共五十九页2.4 文文 法法 的的 类类 型型一、文法分类一、文法分类 通过对产生式施加不同的限制，将文法分为四类通过对产生式施加不同的限制，将文法分为四类 设有文法设有文法G=(VN，VT，P，S);40型文法：（短语结构文法）型文法：（短语结构文法）图灵机图灵机对任一产生式对任一产生式，都有，都有

24、(V(VN NVVT T)+，且，且至至少包含一个非终结符，少包含一个非终结符，(V(VN NVVT T)*41 1型文法：（上下文有关文法）型文法：（上下文有关文法）对任一产生式对任一产生式，都有，都有|，仅仅仅仅 SS除外。除外。29本讲稿第二十九页，共五十九页文法文法GS是是1型文法型文法 SaSBC|aBC CB DBDB DB DCDC DCBC aBab bBbb bCbc cCccSaSBC aaBCBC aabCBC aabbcc*30本讲稿第三十页，共五十九页42 2型文法：（型文法：（上下文无关上下文无关文法）文法）对任一产生式对任一产生式，都有，都有VVN N ，(V(V

25、N NVVT T)*4设文法设文法G G(V(VN N,V,VT T,P,S),P,S)是一个是一个2 2型文法，型文法，V VN N S,A,B,VS,A,B,VT T a,b a,b 其中其中P P为为:(0)S (0)S aB aB (1)S (1)S bA bA (2)A (2)A a a (3)A (3)A aS|bAA aS|bAA (4)B (4)B b b (5)B (5)B bS|aBBbS|aBB31本讲稿第三十一页，共五十九页43 3型文法：（型文法：（正规文法正规文法）右线性文法右线性文法任一产生式任一产生式的形式都为的形式都为AaBAaB或或AaAa，其中，其中AVA

26、VN N ，BVBVN N ，aVaVT T(a a可为可为)左线性文法左线性文法任一产生式任一产生式的形式都为的形式都为ABaABa或或AaAa，其中，其中AVAVN N ，BVBVN N ，aVaVT T(a a可为可为)32本讲稿第三十二页，共五十九页例：例：GE：EE+T|T TT*F|F F(E)|a G是是上下文无关文法上下文无关文法。例文法例文法G=(S,A,B,0,1,P,S)，其中，其中P由下列产生由下列产生式组成：式组成：S0A A1BS1B B1BS0 B1A0A B0A0SG是是正规文法正规文法。33本讲稿第三十三页，共五十九页二、四类文法之间的关系二、四类文法之间的关

27、系四种四种文法文法之间之间的的逐级逐级“包含包含”关系关系2型文法型文法1型文法型文法0型文法型文法3型文法型文法34本讲稿第三十四页，共五十九页2.5 上下文无关文法及其语法树上下文无关文法及其语法树4上下文无关文法有足够的能力描述程序设计语上下文无关文法有足够的能力描述程序设计语言的语法结构言的语法结构例例:文法文法GE：Ea|E+E|E*E|(E)E表示算术表达式表示算术表达式,a表示程序的表示程序的“变量变量”，该文法定义了由变量，该文法定义了由变量，+，*,(和和)组成的算术表达组成的算术表达式的语法结构式的语法结构句型推导句型推导的的直观表示直观表示-语法树语法树35本讲稿第三十五

28、页，共五十九页设设G为一为一上下文无关文法上下文无关文法，若一棵树满足下列，若一棵树满足下列4个条件，则称作个条件，则称作G的语法树的语法树(推导树，派生树）推导树，派生树）1.每个结点都有一个标记，此标记是每个结点都有一个标记，此标记是V的一个符号的一个符号2.根的标记是根的标记是 文法开始符号文法开始符号S3.如果结点如果结点n至少有一个除自己外的子孙并有标记至少有一个除自己外的子孙并有标记A，则肯定，则肯定AVVN N4.如果结点如果结点n有标记有标记A,其直接子孙结点从左到右的次序是其直接子孙结点从左到右的次序是n1，n2，nk，其标记分别为，其标记分别为A1，A2，Ak，那么，那么A

29、A1A2，Ak一定是一定是P中的一个产生式中的一个产生式语法树的结果：语法树的结果：从左到右读出叶子的标记而构成的行从左到右读出叶子的标记而构成的行一、语法树一、语法树36本讲稿第三十六页，共五十九页GE E：EE+T|TEE+T|T TT*F|F TT*F|F F(E)|a F(E)|aE EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*aEE+TEE+TTEE+TTFEE+TTFaT*FFaa给定文法给定文法G=(VN,VT,P,S)，对于，对于G的任何句型都能构的任何句型都能构造与之关联的语法树造与之关联的语法树(推导树推导树)37本讲稿第三十七页，共五十九

30、页用于描述上下文无关文法用于描述上下文无关文法句型推导句型推导的的直观方法直观方法叶子结点叶子结点：树中：树中没有子孙的结点没有子孙的结点。从左到右从左到右读出推导树的读出推导树的叶子标记叶子标记连接成的连接成的文文法符号法符号串串，为，为GS的的句型句型。该推导树称为该。该推导树称为该句型句型的的语法树语法树。用于描述上下文无关文法用于描述上下文无关文法句型推导句型推导的的直观方法直观方法用于描述上下文无关文法用于描述上下文无关文法句型推导句型推导的的直观方法直观方法 例例:GS:SaASASbAASSSaAba用于描述上下文无关文法用于描述上下文无关文法句型推导句型推导的的直观方法直观方法

31、句型句型aabbaa的的语法树语法树（推导树）（推导树）S a A S S b A a a b a38本讲稿第三十八页，共五十九页推导过程中推导过程中施用施用产生式产生式的的顺序顺序 例例:GS:SaASASbAASSSaAbaSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa S a A S S b A a a b a39本讲稿第三十九页，共五十九页例：例：GE E：EE+T|TEE+T|T TT*F|F TT*F|F F(E)|a F(E)|a 试给出表达式试给出表达式a+a*a的推导，并画

32、出语法树。的推导，并画出语法树。左左:E EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a右右:E EE+T E+T*F E+T*a E+F*a E+a*a T+a*a F+a*a a+a*a 混合混合:E EE+T T+T T+T*F F+T*F F+F*F a+F*F a+F*a a+a*a40本讲稿第四十页，共五十九页4例如，有一个例如，有一个2型文法型文法 G=(S,A,B,a,b,P,S),其中其中P:(0)S aB|bA (1)A a|aS|bAA (2)B b|bS|aBB 采用最左推采用最左推导产生句子生句子aabbab:S aB aaBB aa

33、bSB aabbAB aabbaB aabbab一棵语法树表示了一个句型的种种可能的不同推导一棵语法树表示了一个句型的种种可能的不同推导过程，一个句型是否只对应唯一的一棵语法树呢过程，一个句型是否只对应唯一的一棵语法树呢?是是否只有唯一的一个最左否只有唯一的一个最左(最右最右)推导呢推导呢?41本讲稿第四十一页，共五十九页4语法树语法树其中其中P:(0)S aB|bA (1)A a|aS|bAA (2)B b|bS|aBB分析句子分析句子aabbab SaBaBBbSbbAa42本讲稿第四十二页，共五十九页例：例：GE:GE:E aE aE E+EE E+EE E*EE E*EE (E)E (

34、E)E E E+E E+E E*E E*E a a a a a a E E E*E E*E a E+E a E+E a a a a句型句型 a*a+a 的两个的两个不同的最左不同的最左推导：推导：(1)EE+EE*E+E a*E+E a*a+E a*a+a(2)E E*E a*E a*E+E a*a+E a*a+a43本讲稿第四十三页，共五十九页4 若一个文法存在某个句子对应两棵不同的语法若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是树，则称这个文法是二义二义的。的。或者，若一个文法存在某个句子有两个不同的或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是最左（

35、右）推导，则称这个文法是二义二义的的4文法的二义性和语言的二义性是两个不同的概文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同的文法念。因为可能有两个不同的文法G G和和GG，其中，其中G G是二义的，但是却有是二义的，但是却有L(G)=L(G)L(G)=L(G)，也就是说，也就是说，这两个文法所产生的语言是相同的。这两个文法所产生的语言是相同的。44本讲稿第四十四页，共五十九页如果产生上下文无关语言的每一个文法都是二义的，如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的。对于一个程序设计语则说此语言是先天二义的。对于一个程序设计语言来说，常常希望它的文法是无

36、二义的，因为希言来说，常常希望它的文法是无二义的，因为希望对它的每个语句的分析是唯一的。望对它的每个语句的分析是唯一的。二义文法改造为无二义文法二义文法改造为无二义文法GE:E a GEGE:E a 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）|a|a E (E)E (E)规定优先顺序和结合律规定优先顺序和结合律45本讲稿第四十五页，共五十九页2.6 句型的分析句型的分析句型分析句型分析就是就是识别识别一个符号串是否为某文法的一个符号串是否为某文法的句句型型，是某个，是某个推导推导的构造过程。的构造过程。

37、在语言的编译实现中，在语言的编译实现中，完成句型分析完成句型分析的的程序程序称为称为分析程序分析程序或或识别程序识别程序。分析算法称。分析算法称识别算法识别算法。从左到右的分析算法从左到右的分析算法，即，即总是从总是从左左到到右右地地识别输识别输入符号串入符号串，首先识别符号串中的，首先识别符号串中的最左最左符号，进符号，进而而依次识别右边依次识别右边的一个符号，的一个符号，直到分析结束直到分析结束。46本讲稿第四十六页，共五十九页一、句型的分析算法分类一、句型的分析算法分类分析算法可分为：分析算法可分为：自上而下分析法自上而下分析法：从文法的开始符号出发从文法的开始符号出发，反复使用文法的产

38、生，反复使用文法的产生式，式，寻找寻找与与输入符号串输入符号串匹配匹配的的推导推导。自下而上分析法自下而上分析法：从从输入符号串输入符号串开始开始，逐步进行逐步进行归约归约，直至，直至归约归约到到文法的文法的开始符号开始符号。两种方法反映了两种不同的语法树的构造过程。两种方法反映了两种不同的语法树的构造过程。47本讲稿第四十七页，共五十九页1、自上而下的语法分析、自上而下的语法分析例：文法例：文法G：S cAd A ab A a识别输入串识别输入串w=cabd是否为该文法的是否为该文法的句子句子S S S c Adc Ad a b推导过程：推导过程：S cAd cAd cabd48本讲稿第四十

39、八页，共五十九页2、自下而上的语法分析、自下而上的语法分析例：文法例：文法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 cAd49本讲稿第四十九页，共五十九页3、句型分析的有关问题、句型分析的有关问题1）在自上而下的分析方法中）在自上而下的分析方法中如何如何选择选择使用使用哪个哪个产产生式进行推导生式进行推导？假定要被代换的最左非终结符是假定要被代换的最左非终结符是B，且有，且有n条规条规则：则：BA1|A2|An，如何确定用哪

40、个右部去替，如何确定用哪个右部去替代代B？2）自下而上分析法中，分析程序工作的每一步，）自下而上分析法中，分析程序工作的每一步，都是从当前串中都是从当前串中选择一个选择一个子串子串，将它，将它归约归约到到某个某个非终结符非终结符，该子串称为，该子串称为“可归约串可归约串”,如何如何识别识别可归约串可归约串？3）存在确定和不确定分析，本课只讨论确定分析）存在确定和不确定分析，本课只讨论确定分析50本讲稿第五十页，共五十九页4、短语、直接短语、句柄的定义、短语、直接短语、句柄的定义对于文法对于文法GS（1）句型的短语）句型的短语:S=A且且 A=，则称则称是是句型句型相对于非终结符相对于非终结符A

41、的的短语。短语。（2）句型的直接短语：）句型的直接短语：若有若有A ，则称则称是是句型句型相对于非终结符相对于非终结符A 的的直接短语。直接短语。（3）句型的句柄：）句型的句柄：一个句型的一个句型的最左直接短语最左直接短语称称为为该句型该句型的的句柄。句柄。*+51本讲稿第五十一页，共五十九页4语法树子树分析法：语法树子树分析法：短语：短语：任意一颗子树的叶子结点从左至右顺序排任意一颗子树的叶子结点从左至右顺序排列的字符串（按给定句型排除）。列的字符串（按给定句型排除）。直接短语：直接短语：只有父子两层的子树的叶子结点从左只有父子两层的子树的叶子结点从左至右顺序排列的字符串。至右顺序排列的字符

42、串。句柄句柄：最左最下的只有父子两层的子树的叶子结：最左最下的只有父子两层的子树的叶子结点从左至右顺序排列的字符串。点从左至右顺序排列的字符串。52本讲稿第五十二页，共五十九页4例例1：考虑文法：考虑文法GE:ET|E+T TF|T*F F(E)|a分析分析a+a*a中的短语、直接短语和句柄中的短语、直接短语和句柄53本讲稿第五十三页，共五十九页 1、文法中、文法中不含有不含有有害规则有害规则和和多余规则多余规则有害规则有害规则：形如：形如UU的产生式。会的产生式。会引起引起文法的文法的二义性二义性多余规则多余规则：文法中：文法中任何句子的推导任何句子的推导都都不会用到的不会用到的规则规则如：

43、如：1）文法中某些）文法中某些非终结符不在任何规则的右部出现非终结符不在任何规则的右部出现，该非终结符称为该非终结符称为不可到达不可到达。2）文法中某些）文法中某些非终结符非终结符，由它，由它不能推出终结符号串不能推出终结符号串，该非终结符称该非终结符称为为不可终止不可终止。2.7 文法的实用限制文法的实用限制54本讲稿第五十四页，共五十九页2、上下文无关文法中的、上下文无关文法中的规则规则4具有形式具有形式A，的规则称为，的规则称为规则规则4因为因为规则会使得有关文法的一些讨论和证规则会使得有关文法的一些讨论和证明变得复杂明变得复杂,有时会限制这种规则的出现有时会限制这种规则的出现4两种定义

44、的唯一差别是两种定义的唯一差别是句子在不在语言中句子在不在语言中55本讲稿第五十五页，共五十九页化简文法化简文法例例1：GS：1)SBe 2)BCe C为不可终止为不可终止3)BAf 4)AAe 5)Ae 6)CCf C为不可终止为不可终止 7)Df D为不可到达为不可到达 产生式产生式 2），），6），），7）为）为多余规则多余规则应去应去掉。掉。56本讲稿第五十六页，共五十九页本章小结本章小结:1、了解概念：文法，推导，直接推导，最左、了解概念：文法，推导，直接推导，最左(右右)推导，产生式，句型，短语，直接短语，句柄，推导，产生式，句型，短语，直接短语，句柄，语法树，规范推导，二义文法等

45、语法树，规范推导，二义文法等2、熟悉、熟悉4种文法的定义、文法的构造和文法的推种文法的定义、文法的构造和文法的推导导3、掌握语法树的构造和最左（右）推导；熟悉、掌握语法树的构造和最左（右）推导；熟悉二义文法、二义性的证明；二义文法、二义性的证明；4、掌握句型分析、掌握句型分析57本讲稿第五十七页，共五十九页典型例题典型例题 1.1.已知文法已知文法GAGA，写出它定义的语言描述，写出它定义的语言描述 如：如：GA:A 0B|1CGA:A 0B|1C B 1|1A|0BB B 1|1A|0BB C 0|0A|1CC C 0|0A|1CC答案答案:GA:GA定义的语言由定义的语言由0 0、1 1符

46、号串组成，串中符号串组成，串中0 0和和1 1的的个数相同个数相同.2.2.给出语言描述，构造文法给出语言描述，构造文法.如：构造一文法如：构造一文法,其定义的语言是由算符其定义的语言是由算符+,*,(,)+,*,(,)和运和运算对象算对象a a构成的算术表达式的集合构成的算术表达式的集合.答案答案1:GE EE+T|T 1:GE EE+T|T ；TT*F|F TT*F|F ；F(E)|aF(E)|a答案答案2:GE EE+E|E*E|(E)|a2:GE EE+E|E*E|(E)|a58本讲稿第五十八页，共五十九页4作业：给定文法作业：给定文法GE:EET+|T TTF*|F FFP|P P(E)|i试根据语法树求句型试根据语法树求句型TF*PP+短语、直接短语和短语、直接短语和句柄句柄59本讲稿第五十九页，共五十九页