编译原理第二章课件(续)——张淑艳

《编译原理第二章课件(续)——张淑艳》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、程序设计语言编译原理*中国科大温故知新字母表符号符号串语言集合组合集合区别ε,ɸ和{ε}符号串的连接：符号串x和y的连接表示为xy符号串的长度符号串的幂运算：设x是一个符号串，则：x0=ε，x1=x，x2=xx，…，xn=x…x*中国科大温故知新符号串集合的连接Σ*的子集U和V的连接（积）定义为UV={αβ

2、α∈U&β∈V}指数：Vn=VV…V，V0={ε}闭包：V*=V0∪V1∪V2∪V3∪…正闭包：V+=VV*=V1∪V2∪V3∪…练习U:{A,B,…,Z,a,b,…,z},V:{0,1,…,9}UV,V6,V*,U(V)*,U+*中国科大温故知新符号符号串单词符号词法分

3、析器（正规式）表达式语句程序块程序语法分析器（上下文无关文法）语法分析树语言集合字母表集合组合*中国科大温故知新定义1：上下文无关文法是四元组G=（VT,VN,S,P）VT:终结符集合VN:非终结符集合,VT∩VN=ɸS:开始符号,S∈VNP:产生式集合，产生式形式:P,P∈VN,∈(VN∪VT)*例:变量i是一个算术表达式；若E1和E2是算术表达式，则E1+E2、E1*E2和(E1)也是算术表达式EiEE+EEE*EE(E)Ei

4、E+E

5、E*E

6、(E)简化表示({i,+,*,(,)},{E},E,P)*中国科大E(E)(E+E)(i+E)(i+i)温

7、故知新上下文无关文法如何定义语言？推导把产生式看成重写规则，把当前符号串中的非终结符用其产生式右部的串来代替。Ei

8、E+E

9、E*E

10、(E)E(E)EE+EEiEiEE*EE+E*Ei+E*Ei+(E)*Ei+(E+E)*Ei+(i+E)*Ei+(i+i)*Ei+(i+i)*iEE*EEE+EEiE(E)EE+EEiEiEi*中国科大温故知新定义2：符号串的推导与归约：已给文法G=(VN,VT,S,P）令α,β∈(VN∪VT)*，且Aγ∈P，此时，由符号串αAβ能够直接推出符号串αγβ，我们称：符号串αγβ是符号串αAβ的直接推导；符

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

12、α∈VT*，且S+α}i+i和i+(i+i)*i都是Ei

13、E+E

14、E*E

15、(E)的句子*中国

16、科大例：考虑文法G1定义的语言。G1:S→bAA→aA

17、aSbAbaSbAbaAbaaSbAbaAbaA…baa..a…L(G1)={ban

18、n≥1}*中国科大例：考虑文法G2定义的语言。G2：S→ABA→aA

19、aB→bB

20、bL(G2)={ambn

21、m,n≥1}SABaBSABaAB……aba…aBa…abSAB…a…aB…a…abb…Ba…ab…ba…abB*中国科大L(G2)={ambn

22、m,n≥1}G2：S→ABA→aA

23、aB→bB

24、bG2’S→ACBA→aA

25、aC→aCb

26、εB→bB

27、b(1)给定一个文法G，就可以从结构

28、上唯一地确定其语言GL(G)(2)给定一种语言L，能确定其文法，但这种文法可能不是唯一的：LG1或G2*中国科大例：构造一个文法G3使L(G3)={anbn

29、n≥1}G3:S→aSb

30、ab例：有文法G4:S→aSbS→ab它确定的语言是什么？L(G4)={anbn

31、n≥1}例：已知语言为L(G)={abna

32、n≥1}试给出其文法。G5:S→aBaB→bB

33、bG5’:S→aBaB→Bb

34、b例：有文法G6确定什么语言？S→aB

35、bBB→a

36、bL(G6)={aa,ab,ba,bb}*中国科大2.3.1上下文无关文法EE+E

37、E*E

38、(E)

39、E

40、idEE(E)(

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

42、E+E

43、E*E

44、(E)给出句子i*i+i的最右及最左推导。EE+iE*E+iE+EE*i+ii*i+i最右推导：EE*E+Ei*E+EE+Ei*i+Ei*i+i最左推导：E