计算机程序编译原理 第2章 形式语言概论.ppt

《计算机程序编译原理 第2章 形式语言概论.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第2章形式语言概论文法和语言形式化定义文法的类型语言和语法树文法和语言的几点说明分析方法简介本章小结字母表和符号串字母表是元素的非空有穷集合，用表示。字母表中的元素称为符号。例如：汉语的字母表中包括汉字、数字及标点符号等。PASCAL语言的字母表是由字母、数字、若干专用符号及BEGIN、IF之类的保留字组成。符号的有穷序列称为符号串，如compiler,string等。什么符号也不包含的符号串称为空符号表，用表示。符号串所包含的符号的个数称为符号串的长度。空符号串的长度为零。符号串的运算连接运算。设x,y是两个符号串

2、，则xy称为x与y的连接。如x=cate,y=nation,则xy=catenation,特别地，==，其中是任意符号串。符号串的方幂。设x是符号串，则把x自身连接n次得到符号串z,即z=xx…..xx称为符号串x的方幂，写成z=xn。符号串集合的乘积。设A,B是两个符号串集合，则AB表示A与B的乘积，定义为AB={xy

3、xA,yB}。例如，A={ab,c},B={d,efg},则AB={abd,abefg,cd,cefg}。特别地，{}A=A{}=A,A=A=A=,其中为空集。，空符号

4、串不属于空集。符号串集合的方幂。同一符号串集合的乘积。符号串集合的正闭包。符号串集合A正闭包A+=A1A2….An….即A+为集合A上所有符号串的集合。符号串集合的自反闭包。符号串集合A正闭包A*={}A+=A+{}A+=AA*=A*A文法定义2.1设VN,VT分别是非空有限的非终结符号集和终结符号集，V=VNVT,VNVT=，一个产生式是一个序偶对（，），其中V+,V*，通常表示为：->或::=，称为产生式的左部，称为产生式的右部。定义2.2文法G是一个四元组，G=（VN,

5、VT,P,S）,其中VN,VT分别是非空有限的非终结符号集和终结符号集，VNVT=，P是产生式集，SVN称为文法的识别符号或开始符号。如果产生式集合中的产生式有共同的左部，如->，->，则可将其简写为：->

6、。文法G=（VN，VT，P，S）VN={标识符，字母，数字}VT={a,b,c,…x,y,z,0,1,…,9}P={<标识符>→<字母><标识符>→<标识符><字母><标识符>→<标识符><数字><字母>→a,…,<字母>→z<数字>→0,…,<数字>→9}S=<标识符>习惯上只将产生式写出。并有

7、如下约定：1、第一条产生式的左部是开始符号；2、用尖括号括起的是非终结符，否则为终结符。或者大写字母表示非终结符，小写字母表示终结符；3、G可写成G[S]，其中S是开始符号；文法例子0型文法：对任一产生式α→β，都有α(VN∪VT)+，β(VN∪VT)*。1型文法（上下有关文法）：对任一产生式α→β，都有

8、β

9、≥

10、α

11、，仅仅S→ε除外。2型文法（上下无关文法）：对任一产生式α→β，都有αVN，β(VN∪VT)*。3型文法（正规文法）：任一产生式α→β的形式都为A→aB或A→a，其中AVN，BVN，aVT。文

12、法分类文法举例例2.61型文法G6=（VN，VT，P，S），其中VN={S，X，Y，Z}，VT={x，y，z}，P={S→xSYZ

13、xYZ,xY→xy,yY→yy,yZ→yz,ZY→YZ,zZ→zz}例2.72型文法G7=（VN，VT，P，S），其中VN={S，T}，VT={a，b，c,d}，P={S→aTd,T→bT

14、cT

15、b

16、c}例2.82型文法G8=（VN，VT，P，B），其中VN={B}，VT={(，)}，P={B→(B)

17、BB

18、()}例2.92型文法G9=（VN，VT，P，S），其中VN={S}，VT={0，1

19、}，P={S→0S1,S→01}例2.10正规文法G10=（VN，VT，P，A），其中VN={A,B,C,D}，VT={x,y,z}，P={A→xB

20、yC,B→zB

21、y

22、yC,C→xD,D→yD

23、x}推导定义2.3G=（VN,VT,P,S），α→β是文法G的产生式，γ,δ∈V*，若有v,w满足：v=γαδ,w=γβδ,则说：v（应用规则α→β）直接产生w或说：w是v的直接推导或说：w直接归约到v记作vw。例G[S]：S→0S1，S→01直接推导：0S10011（v=0S1，w=0011，使用规则S→01，γ=0，δ=

24、1）S0S1（v=S，w=0S1，使用规则S→0S1，γ=ε，δ=ε）0S100S11（v=0S1，w=00S11，使用规则S→0S1，γ=0，δ=1）定义2.4v+u若存在v=0=>1=>…=>n=u,(n>0)则称u为u的一个推导，记为v+u。定义2.5v*u表示v+u或v=u最左推导定义2.6