《《形式语言基础》PPT课件.ppt》由会员分享,可在线阅读,更多相关《《形式语言基础》PPT课件.ppt(19页珍藏版)》请在三一办公上搜索。
1、编译程序的设计原理与实现,如何让计算机认识、理解 和 执行 高级程序设计语言?,第 2 章 形式语言基础,计算机处理语言,首先应考虑语言的形式化、规范化,使其具有可计算性和可操作性;这就是形式语言理论研究的问题。形式语言诞生于1956年,由chomsky创立。通常,语言研究至少涉及三个方面:语法、语义和语用;这里仅侧重于语法的研究。,形式语言的基本观点是:语言是符号串之集合!,形式语言理论研究的基本问题是:,研究符号串集合的表示方法、结构特性,以及运算规律。,【前 言】,【内容提要】,第 2 章 形式语言基础,2.1 形式语言是符号串集合 2.2 形式语言是由文法定义的 2.3 主要语法成分的
2、定义 2.4 两类特性文法 2.5 文法变换方法 2.6 关于形式语言的分类问题,字母表-元素(符号)的非空有限集合;符号串-符号的有限序列;符号串集合-有限个或者无限个符号串组成的集合;规 则-以某种形式表达的在一定范围内共同遵守的章程和制度;这里,指符号串的组成规则。,2.1 形式语言是符号串集合,【形式语言】是字母表上的符号,按一定的规则组成的所有符号串集合;其中的每个符号串称为句子。,【名词解释】:,三要素!,【例2.1】L1=00,01,10,11;字母表1=0,1,句子有:00,01,10,11,【注】b0=(epsilon空符号串),b1=b,b2=bb,b3=bbb,L1 为有
3、限语言;L2 为无限语言。,形式语言概念示例:,【例2.2】L2=abmc,bn|m0,n0 字母表2=a,b,c,句型1:abmc,有句子:abc,abbc,abbbc,句型2:bn;有句子:,b,bb,bbb,两个语言!,1.连接:.=如 a.b=ab,2.1.1 符号串(集合)的运算,3.方幂:n=n-1=n-1,4.闭包:,n个,.符号串的运算,设,为两个符号串,则:,的正闭包:+=1|2|n|,的星闭包:*=0|1|2|n|,0=(空符号串)什麽符号也没有的符号串!,1=;2=;,2.或:|=(或者),这是一种泛指!,2.1.1 符号串(集合)的运算(续1),【例】:,ab|cd=a
4、b(或者 cd),abc.de=abcde,(a|b)1=(a|b)=a|b,(a|b)*=(a|b)0|(a|b)1|(a|b)2|,(a|b)2=(a|b)(a|b)=aa|ab|ba|bb,即:(a|b)*=(a|b)n,n0,同理:(a|b)+=(a|b)n,n0,符号串运算示例,泛指:由a,b组成的任意符号串!(包括空串),1.乘积:AB=xy|xA 且 yB,2.1.1 符号串(集合)的运算(续2),4.闭包:A 的正闭包:A+=A1A2AnA 的星闭包:A*=A0A1A2An,设 A 和 B 为两个符号串集合,则:,3.方幂:An=AAA=AAn-1=An-1A,n个,A0=;,
5、A1=A;A2=AA;A3=AAA;,.符号串集合的运算,符号串集合运算示例:,【例2.3】设 A=a,b,B=c,d 则 A+B=a,b,c,d 则 AB=xy|xA,yB=ac,ad,bc,bd,【例2.4】设 A=a 则 A*=A0A1A2An=+a+aa+aaa+=,a,aa,aaa,=an|n0,【例2.5】设 A=a,b,A*=?A*=A0A1A2An A0=;A1=A=a,b;A2=A.A=a,b.a,b=aa,ab,ba,bb;A3=A.A2=a,b.aa,ab,ba,bb=aaa,aab,aba,abb,baa,bab,bba,bbb;A*=x|x=(a|b)n,n0,符号串
6、集合运算示例(续):,推论:若 A为任一字母表,则 A*就是该字母表上的所有符号串(包括空串)的集合。,S,A 定义的对象(S 句子,最大的定义对象,又 称为开始符号;A为句型aAc的短语),a,b,c-为字母表中的符号;-空符号串。-,|-为描述符号(-定义为;|或者是),2.1.2 符号串集合的文法描述,【例2.5】L=abnc|n0,字母表:=a,b,c;展开:L=ac,abc,abbc,abbbc,右图给出的表示,S-aAc,A-bA|,长久以来,探讨符号串集合(即形式语言)的各种描述方法,一直是语言计算机处理的重要任务之一。,方法-文法规则;,其中:,从开始符号出发,对符号串中的定义
7、对象,采用推导的方法(用其规则右部替换左部)产生新的符号串,如此进行,直到新符号串中不再出现定义的对象为止,则最终的符号串就是一个句子。,S-aAc A-bA|,规则应用说明示例:,【句子产生过程】(=推导算符):,怎样利用上述文法规则表示语言L?,S,=aAc,=ac,=ac,S,=aAc,=abAc,=abc,=abc,S,=aAc,=abAc,=abbAc,=abbc,一个句子!,又一个句子!,S abnc,n0,再一个句子!,【定义】文法(grammar)是规则的有限集,其中的上下文无关文法可定义为四元组:G(Z)=(VN,VT,Z,P),VN:非终结符集(定义的对象集,如:语法成分等
8、);VT:终结符集(字母表);Z:开始符号(研究范畴中,最大的定义对象);P:规则集(又称产生式集);,A-或者 A-|其中,描述符号:-(定义为),|(或者是)文法符号:Z,AVN,,(VN+VT)*,2.2 形式语言是由文法定义的,每个元素,每个规则,2.2.1 什麽是文法?,2.2 形式语言是由文法定义的(续3),【注意】提供了规则集,就相当给出了一个文法:,G(S):,2.2.2 文法是怎样定义语言的?,则 L(G)=x|Z x,xVT*,即:一个文法所定义的语言,就是由该文法开始,设 有文法 G(Z),L(G)为G所定义的语言;,VT=a,b,c;,Z=S;,P:,VN=S,A;,G
9、(Z)=(VN,VT,Z,P),利用=进行连续推导之意!,符号推导出的所有仅含终结符的符号串之集合。,其中的每个符号串皆称为句子。,2.1,【例2.6】标识符的文法,【标识符】指字母开头的字母、数字序列。,令 G(Z)=(VN,VT,Z,P),同理,【无符号整数】文法 可写成:,G(N):,N-d N|d,其四元组也可写成:G(N)=(N,d,N,P),得:I=(|d)n,n0,令:I=A|A=A|d A|,标识符文法所定义的语言求解:,上面构造的标识符文法属于正规文法(定义在后)类,正确性检验较容易;下面给出一个算法:,求解 I 值步骤:,先求解 A:A=(|d)A,A=(|d)2 A,A=
10、(|d)n A,代入 A=得:A=(|d)n,n0,I=A|代入 A=(|d)n,n0,正规方程式,标识符:字母开头的字母、数字序列;,则 VN=E(算术表达式),T(项),F(因式);VT=i(变量或常数),+,-,*,/,(,);Z=E;P:,【例2.7】简单算术表达式文法,【注】此文法定义了算术表达式的层次嵌套结构:,E-T|E+T|E-T,T-F|T*F|T/F,F-i|(E),令 G(Z)=(VN,VT,Z,P),(表达式),表达式,项,因式,算术表达式文法应用示例:,根据 语言定义式2.1,,证明 i*(i+i-i),是文法G(E)的一个句子,(即 合法的算术表达式):,E,=T,=T*F,=T*(E),=T*(E-T),=T*(E+T-T),=F*(E+T-T),=i*(E+T-T),=,观察推导过程,可以看到:一旦产生式选择错了,会导致失败!,=i*(i+i-i),合法的算术表达式是指:,练习题,【习题2.1】解释下列词语:形式语言;文法;文法所定义的语言。【习题2.2】试构造下述语言L的文法:L=ambn|m0,n1;【习题2.3】试求下述文法G(Z)所定义的语言:G(Z):Z-b|bB,B-bZ,