《形式语言基础》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+ = A1A2An A 的星闭包： 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,