《形式语言基础》PPT课件.ppt
编译程序的设计原理与实现,如何让计算机认识、理解 和 执行 高级程序设计语言？,第 2 章 形式语言基础,计算机处理语言，首先应考虑语言的形式化、规范化，使其具有可计算性和可操作性；这就是形式语言理论研究的问题。形式语言诞生于1956年，由chomsky创立。通常，语言研究至少涉及三个方面：语法、语义和语用；这里仅侧重于语法的研究。,形式语言的基本观点是：语言是符号串之集合！,形式语言理论研究的基本问题是：,研究符号串集合的表示方法、结构特性,以及运算规律。,【前 言】,【内容提要】,第 2 章 形式语言基础,2.1 形式语言是符号串集合 2.2 形式语言是由文法定义的 2.3 主要语法成分的定义 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 为有限语言;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=ab（或者 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=;,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,符号串集合运算示例(续)：,推论：若 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|,长久以来，探讨符号串集合(即形式语言)的各种描述方法，一直是语言计算机处理的重要任务之一。,方法-文法规则；,其中：,从开始符号出发，对符号串中的定义对象，采用推导的方法（用其规则右部替换左部）产生新的符号串，如此进行，直到新符号串中不再出现定义的对象为止，则最终的符号串就是一个句子。,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:非终结符集（定义的对象集，如：语法成分等)；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(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=(|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,
