形式语言基础1.ppt

编译程序的设计原理与实 现 如何让计算机如何让计算机 认识、理解和执行 高级程序设计语言？ 第2章 形式语言基础 计算机处理语言，首先应考虑语言的形式化、规 范化，使其具有可计算性和可操作性；这就是形式语 言理论研究的问题。 形式语言诞生于1956年，由Chomsky创立。通常 ， 语言研究至少涉及三个方面：语法、语义和语用； 形式语言的基本观点是 ： 语言是符号串之集合 ！ 形式语言理论研究的基本问题是： 研究符号串集合的表示方法、结构特性 以及运算规律。 因此： 【内容提要】 2.1 形式语言是符号串集合 2.2 形式语言是由文法定义的 2.3 各种语法成分的定义 2.4 两类特性文法 2.5 文法变换方法 2.6 形式语言的分类 第2章 形式语言基础 字母表 - 元素(符号)的非空有限集合； 符号串 - 符号的有限序列； 符号串集合 - 有限个或者无限个符号串组成 的集合； 规 则 - 以某种形式表达的在一定范围内共 同遵守的章程和制度；这里，指符号串的组成 规则。 2.1 形式语言是符号串集合 【形式语言】是字母表上的符号按一定的 规则组成的所有符号串集合；其中的每个符号串 称为一个句子。 【名词解释】：三要素！ 【例2.1】 L1= 00,01,10,11 ; 字母表1= 0,1, 句子有：00,01,10,11 【注】 (1) b0=（空符号串）,b1=b,b2=bb,b3=bbb, (2) 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.3】： (2) abc. = . abc=abc (1) abc.de= abcde (4) (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组成的 任意符号串！ （包括空串） (3) ab|cd = ab或者cd 1. 乘积： AB = xy | xA 且 yB 4.闭包： A的正闭包：A+ = A1A2An A的星闭包：A* = A0A1A2An 设 A 和 B 为两个符号串集合，则： 2. 和： AB = A+B = x | xA 或 xB 3.方幂： An = AAA = AAn-1 = An-1A n个 A0 = ; A1 =A ; A2 =AA ; A3 =AAA ; .符号串集合的运算 2.1.1 符号串(集合)的运算 符号串集合运算示例 【例2.4】 设 A=a,b,B=c,d 则 A+B=a,b,c,d 则 AB=xy|xA,yB=ac,ad,bc,bd 【例2.5】 设 A=a 则 A* = A0A1A2An =+a+aa+aaa+ =,a,aa,aaa, =an|n0 【例2.6】 设 A=a, b， A* = ? A* = A0A1A2An A0 =; A1 = A =a, b; A2 = AA=a, ba, b=aa,ab,ba,bb; A3 = AA2=a, baa,ab,ba,bb =aaa,aab,aba,abb,baa,bab,bba,bbb; A* = x | x=(a|b)n , n0 符号串集合运算示例(续)： 推论：若 A 为任一字母表，则 A* 就是该字母表 上的所有符号串(包括空串)的集合。 2.2 形式语言是由文法定义的 形式语言是符号串的集合，对形式语言的描述 有两种方式： (1) 枚举方式：语言为有穷集合时 设有字母表A=a,b,c, 有 L1=a,aa,ab,ac, L2=c,cc (2) 使用文法：语言为无穷集合时，无法枚举 设有字母表B=0,1, B+=0,1,00,10,11,01,000, 用 A 表示B+，可以表示为 A-0 A-1 A-A0 A-A1 文法：用有穷的集合刻画无穷的集合的工具。 【定义】 文法(grammar)是规则的有限集，通常可 以表示为四元组： G(Z)=(VN, VT, Z, P) VN : 非终结符集 ( 定义的对象集，如：语法成分等 ) ； VT : 终结符集 ( 字母表 ) ； Z : 开始符号 ( 研究范畴中最大的定义对象 ) ； P : 规则集 ( 又称产生式集 ) ； 2.2 形式语言是由文法定义的 每个元素 2.2.1 什么是文法 ？ Z - 或者 A - | 注：此文法实际称为上下文无关文法 描述符号 ： -(定义为/生成)，|(或者是) 文法符号 ： Z , AVN， , (VN+VT)* 每个规则 【注意】提供了规则集，就相当给出了一个文法： S - aAc A - bA | G(S) : VT= a,b,c ; Z = S ; P : VN= S,A ; G(Z)=(VN, VT, Z, P) 2.2.1 什么是文法 ？ 【例2.7】 L = abnc | n0 ，字母表：= a,b,c； 展开：L =ac,abc,abbc,abbbc, 可以用右图给出的 S - aAc A - bA | 文法规则来表示： 2.2.2 文法是怎样定义语言的？ 则 L(G) = x | Z x, x VT* 即：一个文法所定义的语言，就是由该文法开始 设有文法G(Z)，L(G)为G所定义的语言； 利用推导算符 = 进行连续推导 符号推导出的所有仅含终结符的所有符号串之集合。 其中的每个符号串皆称为句子。 = + 2.1 使用文法的 规则进行 形式语言是字母表上的符号按一定的规则组成的 所有符号串集合。 从开始符号出发，对符号串中的定义对象，采 用推导的方法（用其规则右部替换左部）产生新的 符号串，如此进行，直到新符号串中不再出现定义 的对象为止，则最终的符号串就是一个句子。 S - aAc A - bA | 利用文法规则表示语言 【句子产生过程】(= 推导算符 ) S= aAc = ac = ac S= aAc = abAc = abc = abc S= aAc = bAc = abbAc = abbc 一个句子! 又一个句子! S abnc ,n0 = +再一个句子! 非终结符号 【例2.8】标识符的文法 【标识符】指字母开头的字母、数字序列。 令G(Z)=(VN, VT, Z, P) 则 VN = I(标识符) , A(标识符尾) ； VT = (字母) , d(数字) ； Z = I ; P : I - A | A - A | d A | 同理，【无符号整数】文法可写成： G(N): N - d N | d 其四元组也可写成：G(N)=( N, d, N, P ) 得： I = (|d)n , n0 令： I = A | A = A | d A | 求解文法所定义的语言(1) 上面构造的标识符文法 属于正规文法 I - A | A - A | d A | 先求解 A: A=(|d) A , A=(|d)2 A , , A=(|d)n A 代入 A= 得： A= (|d)n , n0 I= A | 代入 A= (|d)n , n0 正规方程式 标识符：字母开头的字母、数字序列 求解文法所定义的语言(2) 则 L(G)的求解过程 代入法 ： Z - aAc A - bA | 【例2.9】 G(Z): 所以： L(G)= abnc | n0 A = bA = bbA = = bn ,n0 Z = a A c a bn c , n0 = + A bn = + 即： A bn = + ，n0 即： Z abnc ，n0 = + 则 VN = E(算术表达式),T(项),F(因式)； VT = i(变量或常数), + , - , * , / , ( , ) ； Z = E ; P : 【例2.10】简单算术表达式文法 【注】此文法定义了算术表达式的层次嵌套结构: E - T | E + T | E - T T - F | T * F | T / F F - i | ( E ) 令 G(Z)= (VN, VT, Z, P) ( 表达式 ) 表达式项因式 文法E - E + E | E E | E * E | E / E | i | (E) ? 算术表达式文法应用示例： 根据 语言定义式2.1， G(E): E-T |E+T |E-T T-F |T* F |T/F F-i |(E) 证明 i*(i+i-i) 是文法G(E)的一个句子 (即合法的算术表达式): = + E i*(i+i-i) 成立吗？ E = + E i*(i+i-i) =T =T*F =T*(E ) =T*(E-T) =T*(E+T- T) =F*(E+T-T)=i*(E+T-T) = 观察推导过程，可以看 到：一旦产生式选择错 了，会导致失败！ =i*(i+i-i) L(G) = x | Z x , x VT* = + 合法的算术表达式是指： 文法有两种基本运算：推导和归约 v星推导( ): 2.3 各种语法成分的定义 1. 直接推导( = ) : xAy = xy 即：指用产生式的右部符号串替换左部非终结符。 加推导 算符 v 加推导( ): 设 x, y(VN+VT)*， A - P = * = * （当且仅当 = 1 = 2 = = ） 即：指一步或一步以上的直接推导运算 。 （当且仅当=或=1=2=) 即：指零步或零步以上的直接推导运算 。 直接推导 算符 星推导 算符 = + = + 2.3.1 文法的运算 = . + = . + 2. 直接归约( ) : xy xAy = . = . （当且仅当 1 2 ） = . = . = . = . v 星归约( ): = . * = . * （当且仅当 =或 1 2 ) = . = . = . = . 即：直接归约是直接推导的逆运算，用产生式的左 部非终结符替换右部符号串。 即：指零步或零步以上的直接归约运算。 即：指一步或一步以上的直接归约运算。 直接归约 算符 加归约 算符 星归约 算符 v 加归约( ): 2.3.1 文法的运算 规范推导和规范归约 实用中最常见的两种运算： 最左推导( )每次推导皆最左非终结符优先； 最左归约( )每次归约皆最左可归约串优先。 = + = . + 最右推导也称为规范推导 最左归约也称为规范归约 同一个句子可以通过不同的推导序列推导出来 通常只考虑两种特殊推导，即最左推导和最右推导 N1=N=ND=N2=D2=12 12 D2 N2 ND N N1 N1 - N N - ND|D D - 0|1|2 = . =. =. = . = . 最左归约是最右推导的逆过程！ i + i*i l 给定一个符号串 i+i*i ： T-F|T*F|T/F F-i |( E ) G(E): E-T|E+T|E-T 文法运算示例 ： 【例 2.11】 算术表达式文法： = . = . = . = . = . =. = . = . 2. 最左归约(从符号串出发)过程： E = E +T= T +T= F+T= i+ T= i+T*F = i+ F *F = i+i*F = i+i*i E = + i + i * i F+i*iT+i*iE+ i *iE+F*i E+T*iE+T*FE+T E i + i * i = . + E 1. 最左推导(从开始符号出发)过程： 最左非终结符 最左可归约串 即：句型是由文法开始符号加推导出的任一符号串。 2.3.2 句型、句子和语法树 若有 且VT*，则是句子； Z = + 若有 , 则是句型； Z = + 2. 句子 即：句子是由开始符号加推导出的任一终结符号串。 1. 句型 设有文法 G(Z)=(VN, VT, Z, P)，则： 3.语法树 句型(句子)产生过程的一种树结构表示； 树根开始符号；树叶给定的句型(句子)。 A x1 x2 xn 重复步骤，直到推导过程结束为止。 置树根为开始符号； 【语法树的构造算法】 若推导采用了产生式：A - x1x2xn，则有子树 ： 如此构造的语法树，其全体树叶(自左至右) 恰好是给定的句型(句子)。 E = T = T*F =F*F =(E)*F =(E+T)*F =(T+T)*F =(T/F+T)*F =(T/F+F)*F =(T/F+F)*i 句型、句子和语法树示例 【例2.12】 算术表达式文法： (1) 证明 (T/F+F)*i 是一个句型(表达式型)； (2) 画出该句型的语法树。 E - T | E + T | E - T T - F | T * F | T / F F - i | ( E ) 【证】 即：E (T/F+F)*i = + 句型(T/F+F)*i的语法树构造： E T T * F F ( E ) E + T T T / F F i E - T | E+T | E-T T - F | T*F | T/F F - i | ( E ) 【注】关于语法树： 子树：由某一结点 连同所有分支组成 的部分。 简单子树 ：仅具有 单层分支的子树。 3. 句柄 - 一个句型的最左简单短语称为该句型的句柄。 2.3.3 短语、简单短语和句柄 设文法G(Z),xy是一个句型，则: 则 是句型 xy 关于A的短语(A是的名字)； = + = + 1.短语 若 Z xAy xy Z x A y 任一子树的树叶全体(具有共同祖先的叶节点符号串) 皆为短语； = + 2. 简单短语 若 Z xAy = xy 则 是句型 xy 关于A的简单短语(A是的名字) ； 任一简单子树的树叶全体(具有共同父亲的叶节点符 号串)皆为简单短语； (他) (哥哥) (喜欢) (看) 图2.2 他哥哥喜欢看书的语法树 (书) 2.3.3 短语、简单短语和句柄 【例2.13】图2.2为一个中文句型的语法树： 短 语 - 他哥哥,喜欢看,书， 喜欢看书，他哥哥喜欢看书 简单短语 - 他哥哥，喜欢看，书 句 柄 - 他哥哥（最左边的简单短语!） 【例2.14】图2.3为一个算术表达式(型)的语法树： 句型： E+F-T/F*i 短语: E+F-T/F*i，E+F，F，T/F*i，T/F，i 简单短语: F，T/F，i 句柄: F E E - T E + T T * F F T / F i 图2.3 E+F-T/F*i 的语法树 2.3.3 短语、简单短语和句柄 一类典型的综合例题： 【例2.15】G(S): S-aAcBe ; A-Ab|b ; B- d 给定符号串：aAbcde 证明 = aAbcde 是一个句型； 画出句型 的语法树； 指出中的短语、简单短语和句柄。 【题解】 S=aAcBe=aAbcBe= aAbcde 语法树如右图： 短语、简单短语和句柄: S a A c B e A b d 短语: aAbcde ,Ab , d 简单短语: Ab , d 句柄：Ab G2(S): S - b S | a - 直接右递归文法。 2.4 两种特性文法 2.4.1 递归文法 设有文法：G(Z)=(VN,VT,Z,P) 【定义】 设 AVN，x, y(VN+VT)*，则; 若 A xAy，称文法具有递归性; = + 特别地： 若 A - A ，称文法具有直接左递归性； A - A ，称文法具有直接右递归性。 递归文法是定义无限语言的工具 递归文法定义的语言有无限个句子 如：G1(S): S - S b | a - 直接左递归文法； 递归文法示例 【例2.16】G(Z)： Z - aAbB | cZ A - bBc | B - BbAc |a Z - cZ 直接右递归性； B - BbAc 直接左递归性； A =bBc = bBbAcc 即 A A 具有递归性 ( 且 又称为A具有自嵌套性) 可以统称文法G(Z)具有递归性。 = + 2.4.2 二义性文法 【定义】 若文法中存在这样的句型，它具有两棵 不同的语法树，则称该文法是二义性文法。 【例2.17】 算术表达式的另一种文法： 句型 i+i*i 有两棵不 同的语法树(右图)： G(E) 是二义性文法。 G(E)：E - E+E | E*E | (E) | i ; i (变量或常数) E E E + E E * E i E * E E + E i i i i i 二义性文法会引起歧义 ，应尽量避免之！ 文法二义性的消除 【方法1】不改变文法的原有规则,加进一些非形 式的规定。 【方法2】构造一个等价的无二义性文法，将排除 二义性的规则合并到文法中 加进运算符的优先顺序和结合规则 对G(E)，规定*优于+，*和+服从左结合 G(E) - G(E) : E - E+T | T T - T*F | F F - (E) | i ; 2.5.1 文法的等价性 2.5 文法的等价变换 即：文法的等价性是指它们所定义的语言是一样的。 【定义】 设G1、G2是两个文法，若L(G1)=L(G2)， 则称G1与G2等价，记作G1G2。 【例2.18】 G1：S - aS|a G2：S - Sa|a L(G1)=a, aa, aaa, =an | n1 L(G2)=a, aa, aaa, =an | n1 L(G1)=L(G2) 即 G1G2 【结论】一个语言，其描述文法并不唯一。 2.5.2 文法变换方法 在实际工作中，人们总是希望定义一种语言的 文法尽可能地简单。 另外，某些常用的语法分析技术也会对文法提 出一定的要求或限制。 因此，有时需要对文法进行必要的改写。改写 后的文法要与原文法等价通常称为文法变换。 这里重点介绍三类变换： BNF（巴科斯范式）表示法： 删除产生式； 必选项法； 可选项法； 重复可选项法。 删除无用的产生式（文法的化简）； 文法的化简是指消除如下无用产生式： 1. A-A 形式的产生式(自定己)； 2. 不能从其推导出终结符号串的产生式(不终结)； 3. 在推导中永不使用的产生式(不可用)。 文法的化简 删除不终结产生式算法： (1) 构造能推导出终结符号串的非终结符集VVT: 若有 A- 且 VT* ;则令 AVVT ； 若有 B- 且 (VT+ VVT)* ;则令 BVVT ; 重复步骤，直到VVT不再扩大为止。 (2) 删除不在VVT中的所有非终结符(连同其产生式)。 删除不可用产生式算法： (1) 构造可用的非终结符集 VUS: 首先令 ZVUS ; (Z 为文法开始符号) = + (2) 删除不在VUS中的所有非终结符(连同其产生式)。 【例2.19】化简下述文法： G(S): S - Be | Ec A - Ae | e | A B - C e | Af C - Cf ; D - f ; G - b 若有 Z A ，则 令 AVUS ; 重复步骤，直到VUS不再扩大为止。 = + 文法的化简 文法化简示例 l 化简步骤 ： G(S): S - Be | Ec A - Ae | e | A B - C e | Af C - Cf ; D - f ; G - b 删除 A - A ; 2. 删除不终结产生式: VVT= A,D,G,B,S ; 应删除 C,E(连同其产生式) 得： G(S): S - Be ; A - Ae | e ; B - Af ; D - f ; G - b ; 3. 删除不可用产生式: VUS= S,B,A ; 应删除 D,G(连同其产生式) 整理后得：G(S): A - Ae | e B - Af S - Be 删除产生式 【算法】 1. 首先构造可以推出空串的非终结符集：V 若有 A-; 则 令 AV ; 若有 B-A1 An 且全部 AiV ;则令 BV ; 重复步骤，直到V不再扩大为止。 2. 删除 G(Z)中的 A - 形式的产生式； 假定文法G(Z); L(G) 3. 依次改写G(Z)中的产生式 B - X1 X2 Xn : 若有 Xi V 则用 (Xi|) 替换之(一个分裂为两个)； 若有 j 个 Xi V ，则一个产生式将分裂为2j个! 删除产生式示例： (1) 求解 V = A,B (2) 删除 产生式 得： S-aAbc|bS ；A-dABe ； B-A|b (3) 改写 右部含有 V 中元素的产生式： S-a(A|)bc S-aAbc|abc A-d(A|)(B|)e A-dABe|dBe|dAe|de B-(A|) B-A 含有V元素 的产生式 综合 G(S) ： S-aAbc|abc|bS A-dABe|dBe|dAe|de B-A|b 【例2.20】G(S): S-aAbc|bS A-dABe| ; B-A|b 令 ( | ) = 或者 1.必选项法（圆括号法） BNF（巴科斯范式）表示法 必选其中之一！ 例如：有 A - a|a 也可写成： A - aA；A- | 【注】此法又称提公因子法，利用此法可以解决： 具有相同左部的各产生式首符号不同！ 基本思想：扩展文法，引进新的描述符号： ( ) 圆括号； 方括号； 花括号 可变换成: A - a(|) 也可写成： S - S; S - | 令 = 或者 2. 可选项法（方括号法） 例如： S - | 可选也可不选！ 例如 条件语句文法： S - if (B) S 可变换成： S - S - if (B) S else S 可变换成： S - if (B) S else S S(语句)，B(布 尔表达式) 或： S - if (B) S S ; S- else S| BNF（巴科斯范式）表示法 3. 重复可选项法（花括号法） 例如： A - A| 令 = 或 或 或 可变换为： A - 通过递推方法，可得： A= A= A= A= * 有 A - 或 A A ; A -A| 也可写成： A A ; A -A| 验证： 【注】此方法常用来消除文法的直接左递归！ BNF（巴科斯范式）表示法 产生式形式为： A -u 2.6 形式语言的分类 Chomsky 把形式语言分为四类，分别由四类 文法定义；四类文法的区别在于产生式的形式不 同： (2) 1 型语言 由 1型文法定义 (1) 0 型语言 由 0型文法定义 又称 无限制文法