资源描述：
《编译原理与实现 第2章 文法和语言.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第2章文法和语言Athousand-lijourneyisstartedbytakingthefirststep.千里之行，始于足下第2章文法和语言(P12)2.1字母表和符号串2.2文法2.3推导2.4句型和句子2.5语言2.6递归规则与递归文法2.7短语、简单短语和句柄2.8语法树2.9子树与短语2.10由树构造推导过程2.11文法的二义性2.12有关文法的实用限制2.13文法和语言分类学习重点1文法的定义、分类和二义性2最左推导、规范推导(或最右推导)3语言、句型和句子4短语、简单短语(或直接短语)和句柄5语法树形式语言(P12)如果不考虑语义和
2、语用，只从语法这一侧面来看语言，它是由符合某种语法（用规则定义）的句子构成的集合，这种意义下的语言称作形式语言。例汉语：所有符合汉语语法的句子的全体英语：所有符合英语语法的句子的全体程序设计语言：所有符合该语言语法的程序的全体形式语言形式语言抽象地定义为一个数学系统，即能用数学符号和规则描述的语言。形式语言理论是对符号串集合的表示法、结构及其特性的研究。这种理论对程序设计语言的设计和编译程序的构造有着重大的作用。2.1字母表和符号串(P12)字母表(或符号集)：元素的非空有穷集合。例二进制数语言的字母表={0,1}汉语的字母表中包括汉字、数字及标点符
3、号等PASCAL语言的字母表是由字母、数字、若干专用符号及BEGIN、IF之类的保留字组成C语言的字母表由字母、数字、若干专用符号以及if、else、while等关键字组成2.1字母表和符号串符号：字母表中的元素。例={a,b,for,1}，则a,b,for,1都是的符号。不要把符号理解成字符。典型的符号有字母、数字、各种标点符号和各种运算符。2.1字母表和符号串符号串：由字母表上0个或多个符号所组成的任何有穷序列。空符号串ε也是字母表上的符号串，它由0个符号组成。例={0,1}，则ε，0，1，01，10，00，11，100，0110，11111
4、0000等二进制数都是上的符号串={a,b,c,+,*}，则ε，a，b，c，+，*，aa，ab，ac，a+，a*，ba，bb，bc，b+，b*，aaa，bbb等都是上的符号串一个字母表上的全部符号串所组成的集合是无穷的。2.1字母表和符号串符号串的长度：指符号串x中所含符号的个数，记为
5、x
6、。特别地，
7、ε
8、=0。例={a,b,c,+,*}，
9、abc
10、=3，
11、abc+*abc
12、=8符号串相等：若x、y是字母表∑上的两个符号串，那么当且仅当组成x的各符号与组成y的各符号依次相等时，则符号串x与符号串y相等，记作x=y。例当x=abbc，y=abbc
13、时，则x=y当x=ab，y=ba时，则x≠y2.1字母表和符号串符号串的前缀：指从符号串x的末尾删除0或多个符号后得到的符号串。例u、uni、university都是university的前缀符号串的后缀：指从符号串x的开头删除0或多个符号后得到的符号串。例ty、sity、university都是university的后缀符号串的子串：指从符号串x的开头和末尾删除0或多个符号后得到的符号串，例ver是university的子串,符号串的前缀、后缀都是它的子串。2.1字母表和符号串符号串的连接：若x、y是两个符号串，则xy是将符号串y连接在符号串x的后面
14、。例x=ab，y=ba，则xy=abba若x、y是字母表∑上的两个符号串，则xy也是字母表∑上的符号串。除εx=xε=x外，连接没有交换率，即xy≠yx。2.1字母表和符号串集合的乘积运算：令A、B为两个符号串集合，AB={xy
15、x∈A,y∈B}。对于空集合有{ε}，有{ε}A=A{ε}=A。例A={a,b}，B={c,d}，则AB={ac,ad,bc,bd}符号串的幂运算：若x是符号串，则：x0=ε,x1=x，x2=xx，…，xn=xx…x=xxn-1=xn-1x，其中n>0。例x=abc,x0=ε，x1=abc，x2=abcabc，…2.1字母表和
16、符号串集合的幂运算：设A为符号串集合，则：A0={ε}A1=AA2=AA…An=AA…A=AAn-1=An-1A，其中n>0例A={a，b}，则A0={ε}A1={a,b}A2={aa,ab,ba,bb}…2.1字母表和符号串集合的正闭包：设A为一个集合，则：A+=A1∪A2∪….∪An∪…例A={a,b}，则A+={a,b,aa,ab,ba,bb,aaa,aab,…}集合的闭包：设A为一个集合，则：A*=A0∪A+例A={a,b}，则A*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}一个集合的闭包比正闭包多个ε。例：2.2文法(P14)
17、文法实际上就是描述语言语法结构的形式规则。例例文法G的形式定义：G=(Vn，Vt，P，Z)Vn
