编译原理第二章课件(续)-张淑艳.ppt

《编译原理第二章课件(续)-张淑艳.ppt》由会员分享，可在线阅读，更多相关《编译原理第二章课件(续)-张淑艳.ppt（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、程序设计语言程序设计语言编译原理编译原理温故知新温故知新字母表字母表符号符号符号串符号串语言语言集合集合集合集合组合组合组合组合集合集合集合集合区别区别,和和符号串的连接：符号串符号串的连接：符号串符号串的连接：符号串符号串的连接：符号串x x和和和和y y的连接表示为的连接表示为的连接表示为的连接表示为xyxy符号串的长度符号串的长度符号串的长度符号串的长度符号串的幂运算：设符号串的幂运算：设符号串的幂运算：设符号串的幂运算：设x x是一个符号串，则：是一个符号串，则：是一个符号串，则：是一个符号串，则：x x0 0=，x x1 1=x=x，x x2 2=xx=xx，x xn n=xx=xx

2、温故知新温故知新符号串集合的连接符号串集合的连接*的子集的子集的子集的子集U U和和和和V V的连接（积）定义为的连接（积）定义为的连接（积）定义为的连接（积）定义为 UV=UV=|U&U&V V 指数：指数：指数：指数：Vn=VVV，V0=闭包：闭包：闭包：闭包：V*=V0 V1 V2 V3 正闭包：正闭包：正闭包：正闭包：V+=VV*=V1 V2 V3 练习练习练习练习 U:U:A A,B B,Z Z,a a,b b,z z,V:,V:0,1,9 0,1,9 UV,VUV,V6 6,V,V*,U(V),U(V)*,U,U+温故知新温故知新 符号符号符号符号符号串符号串符号串符号串单词符号单

3、词符号单词符号单词符号词法分析器（正规式）词法分析器（正规式）词法分析器（正规式）词法分析器（正规式）表达式表达式表达式表达式语句语句语句语句程序块程序块程序块程序块程序程序程序程序语语语语法法法法分分分分析析析析器器器器（上上上上下下下下文文文文无无无无关关关关文文文文法法法法）语法分析树语法分析树语法分析树语法分析树语言语言语言语言集合集合集合集合字母表字母表字母表字母表集合集合集合集合组合组合组合组合温故知新温故知新定义定义定义定义1 1：上下文无关文法：上下文无关文法：上下文无关文法：上下文无关文法是四元组是四元组G=（VT,VN,S,P）VT:终结符集合终结符集合VN:非终结符集合非

4、终结符集合,VT VN=S:开始符号开始符号,SVNP:产生式集合，产生式集合，产生式形式产生式形式:P ,P VN,(VN VT)*例例例例 :变量变量变量变量i i是一个算术表达式；是一个算术表达式；是一个算术表达式；是一个算术表达式；若若若若E1E1和和和和E2E2是算术表达式，则是算术表达式，则是算术表达式，则是算术表达式，则E1+E2E1+E2、E1*E2E1*E2和和和和(E1)(E1)也是也是也是也是算术表达式算术表达式算术表达式算术表达式E E i i E E E E+E EE E E E*E EE E (E E)E E i i|E E+E E|E E*E E|(|(E E)简

5、化表示简化表示简化表示简化表示(i i,+,*,(,),+,*,(,),E E,E E,P )E E(E E)(E E+E E)(i i+E E)(i i+i i)温故知新温故知新上下文无关文法如何定义语言？上下文无关文法如何定义语言？推导推导把产生式看成重写规则，把当前符号串中的非终把产生式看成重写规则，把当前符号串中的非终结符用其产生式右部的串来代替。结符用其产生式右部的串来代替。E E i i|E E+E E|E E*E E|(|(E E)E E (E E)E EE E+E E E Ei iE Ei iE E E E E*EE*E E+E*EE+E*E i+E*Ei+E*E i+(E)*

6、Ei+(E)*E i+(E+E)*Ei+(E+E)*E i+(i+E)*Ei+(i+E)*E i+(i+i)*Ei+(i+i)*E i+(i+i)*ii+(i+i)*iE E E E*E EE EE E+E E E Ei iE E(E E)E EE+EE+EE E i iE E i iE E i i温故知新温故知新定义定义2：符号串的：符号串的推导与归约推导与归约：已给文法：已给文法G=(VN,VT,S,P）令令,(VNVT)*，且，且A P，此时，由符号串，此时，由符号串A能能够够直接推出直接推出符号串符号串，我们称：，我们称：符号串符号串是符号串是符号串A的的直接推导直接推导；符号串符号串

7、A是符号串是符号串的的直接归约直接归约 记作记作:A 若有若有1,2,n(VNVT)*且且1 2 n-1 n则称则称n是是1的推导。的推导。特别约定：若在推导关系特别约定：若在推导关系1 n中允许中允许1=n，则称则称n是是1 的广义推导的广义推导记作：记作：记作：记作：1 1+n*n n记作：记作：记作：记作：1 1温故知新温故知新定义定义3：句型、句子和语言句型、句子和语言，已给文法，已给文法G=(VN,VT,S,P）若若 S*,(VNVT)*，则称，则称为文法为文法G的的句型句型 若若 S*,VT*，则称，则称为文法为文法G的的句子句子 文法文法G所对应的所对应的语言是句子的集合语言是句

8、子的集合，记作，记作L(G)=|VT*，且，且S+i+i 和和 i+(i+i)*i 都是都是E E i i|E E+E E|E E*E E|(|(E E)的句子的句子例：考虑文法例：考虑文法G1定义的语言。定义的语言。G1:SbA AaA|aS bAbaS bA baAbaaS bAbaAbaAbaa.aL(G1)=ban|n1例：考虑文法例：考虑文法G2定义的语言。定义的语言。G2：SAB AaA|a BbB|bL(G2)=ambn|m,n1S ABaBS AB aABabaaB aabS AB aaBaabbB aabbaabBL(G2)=ambn|m,n1 G2：SAB AaA|a Bb

9、B|b G2 SACB AaA|a C aCb|BbB|b(1)(1)(1)(1)给定一个文法给定一个文法给定一个文法给定一个文法G G G G，就可以从结构上唯一地确定其，就可以从结构上唯一地确定其，就可以从结构上唯一地确定其，就可以从结构上唯一地确定其语言语言语言语言 G G G GL(G)L(G)L(G)L(G)(2)(2)(2)(2)给定一种语言给定一种语言给定一种语言给定一种语言L L L L，能确定其文法，但这种文法可，能确定其文法，但这种文法可，能确定其文法，但这种文法可，能确定其文法，但这种文法可能不是唯一的：能不是唯一的：能不是唯一的：能不是唯一的：L L L LG1G1G1

10、G1或或或或G2G2G2G2例：构造一个文法例：构造一个文法G3使使L(G3)=anbn|n1G3:SaSb|ab例：有文法例：有文法G4:SaSb Sab它确定的语言是什么？它确定的语言是什么？L(G4)=anbn|n1例：已知语言为例：已知语言为 L(G)=abna|n1 试给出其文法。试给出其文法。G5:SaBaBbB|bG5:SaBaBBb|b例：有文法例：有文法G6 确定什么语确定什么语言？言？S aB|bB B a|bL(G6)=aa,ab,ba,bb2.3.1 上下文无关文法上下文无关文法E E E E+E E|E E *E E|(|(E E)|)|E E|id|idE E E

11、E (E E)(E E+E E)最左推导最左推导:任何一步任何一步任何一步任何一步 都是对都是对的最左非终结符进的最左非终结符进行替换的。行替换的。E E lm E E lm (E E)lm (E E+E E)lm (id+(id+E E)lm (id+id)(id+id)最右推导（规范推导）最右推导（规范推导）E E rm E E rm (E E)rm (E E+E E)rm (E E+id)+id)rm (id+id)(id+id)？2.3.1 上下文无关文法上下文无关文法例：例：例：例：文法文法文法文法G G G G:E E E E i|i|i|i|E+E|E*E|(E)E+E|E*E|

12、(E)E+E|E*E|(E)E+E|E*E|(E)给出句子给出句子给出句子给出句子 i*i+i i*i+i i*i+i i*i+i 的最右及最左推导的最右及最左推导的最右及最左推导的最右及最左推导 。E E E E E+E+E+E+i i i i E*E+iE*E+iE*E+iE*E+i E+EE+EE+EE+E E*E*E*E*i i i i+i i i i i i i i*i i i i+i i i i最右推导：最右推导：最右推导：最右推导：E E E E E*E+EE*E+EE*E+EE*E+E i i i i*E+E*E+E*E+E*E+E E+EE+EE+EE+E i i i i*i

13、 i i i+E+E+E+E i i i i*i i i i+i i i i最左推导：最左推导：最左推导：最左推导：E E E E i*Ei*Ei*Ei*E i i i i*E+E*E+E*E+E*E+E E*EE*EE*EE*E i i i i*i i i i+E+E+E+E i i i i*i i i i+i i i i2.3.2 语法分析树与二义性语法分析树与二义性语法分析树语法分析树语法分析树语法分析树：句型推导的图形表示，简称：句型推导的图形表示，简称：句型推导的图形表示，简称：句型推导的图形表示，简称语法树语法树语法树语法树。E EE E()E EE E()E EE EE E+i

14、iE E()E EE EE E+E E (E E)(E E+E E)(i i+E E)(i i+i i)E E (E E)(E E+E E)(E E+i i)(i i+i i)i iE E()E EE EE E+i iE EE E()E EE E()E EE EE E+i iE E()E EE EE E+i iE E()E EE EE E+i i一棵语法树表示了一个句型种种可能的不同推导过程。一棵语法树表示了一个句型种种可能的不同推导过程。一棵语法树表示了一个句型种种可能的不同推导过程。一棵语法树表示了一个句型种种可能的不同推导过程。2.3.2 语法分析树与二义性语法分析树与二义性E E*E

15、i*E i*E+E i*i+E i*i+iE EE EE E*+E EE Ei ii ii iE EE Ei iE E*+E EE Ei ii i文法的二义性文法的二义性：若一个文法存在：若一个文法存在某个句子某个句子/句型句型对应对应两棵不同两棵不同的语法树的语法树，则称此文法是二义性文法。，则称此文法是二义性文法。E i|E+E|E*E|(E)句子句子：i*i+iE E+E E*E+E i*E+E i*i+E i*i+i2.3.2 语法分析树与二义性语法分析树与二义性消除二义性：消除二义性：E EE EE E*+E EE Ei ii ii iE EE Ei iE E*+E EE Ei ii

16、 i用一种层次观点看待表达式用一种层次观点看待表达式用一种层次观点看待表达式用一种层次观点看待表达式按照优先集和结合性按照优先集和结合性按照优先集和结合性按照优先集和结合性2.3.2 语法分析树与二义性语法分析树与二义性用一种层次观点看待表达式用一种层次观点看待表达式用一种层次观点看待表达式用一种层次观点看待表达式i*i i*i+i+ii*i*(i+i)(i+i)i*i*(i*i+i)(i*i+i)i*i*(i+i)i*i*(i+i)+i*ii*i+i i取消二义性的文法取消二义性的文法取消二义性的文法取消二义性的文法E E E E T T T T|E+T|E+T|E+T|E+TT T T T

17、 F|TF|TF|TF|T*F F F F F F F F i|i|i|i|（E E E E）E ET TE E+T T F F*T T F Fi i F Fi ii i E E T T F F*T T F Fi ii iE i|E+E|E*E|(E)2.3.2 语法分析树与二义性语法分析树与二义性例：给出例：给出例：给出例：给出文法文法文法文法GG，判断是否为二义文法，如果是，取消二义性判断是否为二义文法，如果是，取消二义性判断是否为二义文法，如果是，取消二义性判断是否为二义文法，如果是，取消二义性语句语句语句语句 if if 条件条件条件条件 then then 语句语句语句语句|if i

18、f 条件条件条件条件 then then 语句语句语句语句 else else 语句语句语句语句|其它语句其它语句其它语句其它语句例例例例 推导句型推导句型推导句型推导句型：if if 条件条件条件条件 then if then if 条件条件条件条件 then then 语句语句语句语句 else else 语句语句语句语句最左推导：最左推导：最左推导：最左推导：语句语句语句语句 if if 条件条件条件条件 then then 语句语句语句语句 if if 条件条件条件条件 then then if if 条件条件条件条件 then then 语句语句语句语句 else else 语句语句

19、语句语句 语句语句语句语句 if if 条件条件条件条件 then then 语句语句语句语句 else else 语句语句语句语句 if if 条件条件条件条件 then then if if 条件条件条件条件 then then 语句语句语句语句 else else 语句语句语句语句 2.3.2 语法分析树与二义性语法分析树与二义性语句语句语句语句 if if 条件条件条件条件 then then 语句语句语句语句|if|if 条件条件条件条件 thenthen语句语句语句语句elseelse语句语句语句语句|其它语句其它语句其它语句其它语句取消二义性的文法：取消二义性的文法：语句语句语句

20、语句 匹配句匹配句匹配句匹配句|非匹配句非匹配句非匹配句非匹配句匹配句匹配句匹配句匹配句 if if 条件条件条件条件 then then 匹配句匹配句匹配句匹配句 else else 匹配句匹配句匹配句匹配句|其它语句其它语句其它语句其它语句非匹配句非匹配句非匹配句非匹配句 if if 条件条件条件条件 then then 语句语句语句语句|if|if 条件条件条件条件 then then 匹配句匹配句匹配句匹配句 else else 非匹配句非匹配句非匹配句非匹配句练习练习1、令文法为、令文法为 E T|E+T|E-TT F|T*F|T/FF(E)|i给出给出 i*(i+i)的最右推导及语

21、法树的最右推导及语法树2、证明下面的文法是二义的、证明下面的文法是二义的SiSeS|iS|iE T T*F T*(E)T*(E+T)T*(E+F)T*(E+i)T*(T+i)T*(F+i)T*(i+i)F*(i+i)i*(i+i)E T|E+T|E-TT F|T*F|T/FF(E)|i句子：句子：i*(i+i)句子：句子：iiieiS iSeS iiSeS iiieS iiieiSiSeS|iS|iS iS iiSeS iiieS iiiei1.1.1.1.不能有形如：不能有形如：不能有形如：不能有形如：PPPPPPPP的产生式；的产生式；的产生式；的产生式；2.2.2.2.不能有不能有不能有

22、不能有多余产生式多余产生式多余产生式多余产生式，每个非终结符，每个非终结符，每个非终结符，每个非终结符P P P P必须都有用处必须都有用处必须都有用处必须都有用处。(1)(1)(1)(1)在推导文法的所有句子时，始终都用不到的产生式；如，在推导文法的所有句子时，始终都用不到的产生式；如，在推导文法的所有句子时，始终都用不到的产生式；如，在推导文法的所有句子时，始终都用不到的产生式；如，从开始符号，不存在推导从开始符号，不存在推导从开始符号，不存在推导从开始符号，不存在推导 S S S S P P P P(2)(2)(2)(2)在推导过程中，一旦使用此产生式，将无法推出任何句子在推导过程中，一

23、旦使用此产生式，将无法推出任何句子在推导过程中，一旦使用此产生式，将无法推出任何句子在推导过程中，一旦使用此产生式，将无法推出任何句子的产生式；如，的产生式；如，的产生式；如，的产生式；如，对于非终结符对于非终结符对于非终结符对于非终结符P P P P，不存在，不存在，不存在，不存在P P P P ,VVVVT T T T*2.3.2 语法分析树与二义性语法分析树与二义性例：有文法例：有文法G:Z Be A Ae|e B Ce|Af C Cf D fZ BeA Ae|eB Af*上下文无关文法的限制：上下文无关文法的限制：上下文无关文法的限制：上下文无关文法的限制：上下文上下文上下文上下文无关

24、文无关文无关文无关文法法法法2.3.3 形式语言鸟瞰形式语言鸟瞰文法文法文法文法 G G=(=(V VT T ,V VN N,S S,P P)乔姆斯基把文法分为四类：乔姆斯基把文法分为四类：乔姆斯基把文法分为四类：乔姆斯基把文法分为四类：0 0型文法：型文法：型文法：型文法：，,(V VN N V VT T)*,至少有一个至少有一个至少有一个至少有一个非终结符非终结符非终结符非终结符1 1型文法：型文法：型文法：型文法：|，但，但，但，但S S 可以例外可以例外可以例外可以例外AA 是是1 1型文法的一个产生式型文法的一个产生式2 2型文法：型文法：型文法：型文法：A A ，A A V VN

25、N,(V(VN N V VT T)*)*3 3型文法：型文法：型文法：型文法：A A B B或或或或A A ，A,BA,B V VN N,V VT T*短语文短语文短语文短语文法法法法0 0型文法型文法型文法型文法1 1型文法型文法型文法型文法2 2型文法型文法型文法型文法3 3型文法型文法型文法型文法上下文有关上下文有关上下文有关上下文有关文法文法文法文法右线性文法右线性文法右线性文法右线性文法 正规文法正规文法正规文法正规文法2.3.3 形式语言鸟瞰形式语言鸟瞰 例例 L=anbn|n1正规文法无法描述正规文法无法描述上下文无关文法可以描述上下文无关文法可以描述 S aSb|ab例例 L=

26、anbncn|n 1上下文无关文法不可描述上下文无关文法不可描述上下文有关文法可以描述上下文有关文法可以描述S aSBC S aBCCB BCaB ab bB bbbC bccC cc0 0型文法型文法型文法型文法1 1型文法型文法型文法型文法2 2型文法型文法型文法型文法3 3型文法型文法型文法型文法S S a a n n-1-1S S(BCBC)n n 1 1S S a an n(BCBC)n n S S a an nB Bn nC Cn nS S a a n nbBbBn n 1 1C Cn nS S a a n nb bn nC Cn n S S a an nb bn ncCcCn n-1-1S S a an nb bn nc cn n*+温故知新温故知新上下文无关文法上下文无关文法上下文无关文法上下文无关文法四元组定义四元组定义四元组定义四元组定义推导推导推导推导分析树分析树分析树分析树图形化表示图形化表示图形化表示图形化表示最左推导最左推导最左推导最左推导最右推导最右推导最右推导最右推导二义性二义性二义性二义性消除二义性消除二义性消除二义性消除二义性