东南大学编译原理

《东南大学编译原理》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2语言与文法翟玉庆周晓宇字母表和符号字母表：符号的非空有穷集合符号:语言中不可再分的单位字母表：Σ，V或其它大写字母V1={a,b,c}V2={+,-,0,1,…,9}Σ={x

2、xASCII字符}符号串（字符串）某字母表上的符号的有穷序列a,b,c,abc,bc,…：V1上的符号串1250,+2,-1835,…：V2上的符号串空串（ε）：不含任何符号的串语句字母表上符合某种构成规则的符号串序列Heisagoodstudent.Peanuteatsmonkey.我们约定，用a,b,c,…表示符号;用,,…表示符号串;用A,B,C,…表示符号或符号

3、串的集合语言某字母表上的句子的集合。符号串集合的积设A={1,2,…}，B={1,2,...}，二者的笛卡尔积AB={A,B}若A={a,b},B={c,e,d}，那么AB={ac,ae,ad,bc,be,bd}字符串集合的幂A0={ε}，An=AAn-1={?}若

4、A

5、=m，那么，

6、A0

7、=1，

8、A1

9、=m，

10、An

11、=mnKleene闭包和正闭包Kleene闭包：A*=A0A1A2…{a,b}*={?}正闭包:A+=A1A2…=A*-{ε}{a,b}+={?}一个语言是其字母表上闭包的子集.文法（grammar）表达语

12、言构成规则的形式化方法自然语言文法示例产生式<句子><主语><谓语><宾语><主语><形容词><名词><谓语><动词><宾语><形容词><名词><形容词>yongpop<名词>menmusic<动词>like产生式文法的组成非终结符（VN）终结符（VT）开始符号产生式推导与规约推导：使用产生式的右部取代左部的过程规约：推导的逆过程，用产生式的左部取代右部的过程推导及规约的顺序推导及规约的顺序最左归约和最右归约称为规范归约。句型、句子与语言句型：从文法开始符号S开始，每步推导（包括0步推导）所得到的字符串S，其中(VNVT)*

13、句子：仅含终结符的句型语言：由S推导所得的句子的集合L(G)={

14、S，且VT*}，G为文法文法规则的递归定义非终结符的定义中包含了非终结符自身设={0,1}<整数><数字><整数>

15、<数字><数字>0

16、1使用递归定义时要谨慎，要有递归出口，否则，可能永远产生不出句子扩充的BNF表示()——提因子Uax

17、ay

18、az改写为Ua(x

19、y

20、z){}——重复次数的指定<标识符><字母>{<字母>

21、<数字>}05[]——任选符号<整数>[+

22、-]<数字>{<数字>}元语言符号用来说明文法符号之间关系的符号

23、文法与语言的形式定义Chomsky

24、0型文法G：四元组(VN,VT,P,S)0型文法（短语文法或无限制文法）P：，其中V+并至少含有一个非终结符,V*.是对产生式限制最少的文法；识别0型语言的自动机称为图灵机(TM)；对0型文法的产生式作某些限制，可以得到其他类型的文法。Chomsky1型文法长度增加文法（上下文有关文法）P：，除可能有S外均有

25、

26、>=

27、

28、；若有S，规定S不得出现在产生式右部。或P中产生式，除可能有S外均有A，其中,V*，AVN，V+。Chomsky1型文法（续）1型文法对非终结符进行替换时必须考虑上下文。

29、除文法开始符号外不允许将其它的非终结符替换成。识别1型语言的自动机称为线性界限自动机(LBA)。Chomsky2型文法P：A，其中AVN，V*。产生式左部一定是非终结符，产生式右部可以是VN、VT或。非终结符的替换不必考虑上下文，故也称作上下文无关文法。识别2型语言的自动机称为下推自动机(PDA)。Chomsky3型文法P中产生式具有形式AB，A，或者AB，A，其中A，BVN，VT*。也称为正规文法RG、线性文法：若所有产生式均是左线性，则称为左线性文法；若所有产生式均是右线性，则称为右线性文法。Chomsky3型文

30、法（续）产生式要么均是右线性产生式，要么是左线性产生式，不能既有左线性产生式，又有右线性产生式。识别3型语言的自动机称为有限状态自动机。由文法产生语言例：设文法G1＝({S},{a,b},P,S)，其中P为:(0)SaS(1)Sa(2)Sb答：L(G1)={ai(a

31、b)

32、i>=0}由文法产生语言例：设文法G2＝({S},{a,b},P,S)，其中P为:(0)SaSb(1)Sab答：L(G2)={anbn

33、n>=1}由语言构造文法例：设L1={a2nbn

34、n>=1且a,bVT}，试构造生成L1的文法G1。解：n=1，L1=aabn=2，L1

35、=aaaabbn=3，L1=aaaaaabbb得：SaaSbSaab由语言构造文法-题型构