《编译原理3文法和语言》由会员分享，可在线阅读，更多相关《编译原理3文法和语言（61页珍藏版）》请在金锄头文库上搜索。
1、编译原理 计算机学院 李金厚第三章 文法和语言3.1 文法的直观概念 3.2 符号和符号串 3.3 文法和语言的形式定义 3.4 文法的类型 3.5 上下文无关文法及其语法树 3.6 句型分析编译原理 计算机学院 李金厚语言和文法为什么关心文法问题？为语言的描述寻求一种工具(以确定什么样 的句子属于该语言)。穷举法是不合适的(原因？) 。提供有限的描述语言特性的法则文法要对程序设计语言给出精确无二义的语法描 述，严谨、简洁、易读形式化工具“形式化”是指这样的事实：语言的所有规则只以 什麽符号串能出现的方式来陈述，形式化很像是 数学的符号化编译原理 计算机学院 李金厚文法的直观概念以自然语言为例
2、，人们罗列出所有的句子是不 现实的，但人们可以给出一些规则，用它们来 说明或定义句子合理的组成结构 这里采用前面介绍过的EBNF来如下简单地表示 自然语言中句子的构成规则：:=:=|:=我|你|他编译原理 计算机学院 李金厚文法的直观概念:=王明|大学生|工人|英语|:=:=是|学习:=|编译原理 计算机学院 李金厚符号和符号串语言离不开符号的使用 字母表：字母表是符号的非空有穷集合，因此，字母 表也可称为符号集不同的语言可以有不同的字母表 符号串：由字母表中的符号组成的任何有穷的符号序 列称为符号串编译原理 计算机学院 李金厚符号串及若干相关运算符号串的头尾，固有头和固有尾：如果z=xy是一
3、个符号串，那么称x是z的头，y是z的 尾；如果x是非空的，那么y称为固有尾；同样，如果y 非空，那么称x是固有头例，对于z=abc，那么z的头是, a, ab, abc，除abc外 ，其他都是固有头；z的尾是, c, bc, abc，z的固有尾是 , c, bc 求符号串长度：如果某符号串x中有m个符号，则称其长度为m，并 表示为|x|=m例，|001110|=6编译原理 计算机学院 李金厚符号串上的运算符号串的连接：设x和y是符号串，它们的连接xy是把y放在x之后得 到的符号串显然，x=x=x；|xy|=|x|+|y| 符号串的方幂：把x连接n次得到的符号串，如z=xx，写作z=xn例，x0
4、=，x1=x等等；如果x=AB，则x2=ABAB字符串集合：如果集合A中的元素都是某字母表上的符号串(符 号串的集合)，则称A为该字母表上的符号串集合编译原理 计算机学院 李金厚符号串上的运算符号串集合A和B的乘积：AB=xy|xA, yB 对字母表，以*表示上所有有穷长的串 的集合；它称为集合的闭包；+称为的 正闭包例，设=0, 1，则*=, 0, 1, 00, 01, 10, 11, ，它也可表示为：*= 0 1 n编译原理 计算机学院 李金厚文法定义 定义：文法G为四元组(VN, VT, P, S)其中，VN，VT和P都是非空有穷集。具体地，VN是非终 结符号(或语法实体，或语法变量)集
5、；VT终结符号集； P是规则的集合S是称作识别符号或开始符号的一个非终结符，它 至少要在一条产生式中作为左部出现VN和VT不含公共的元素，即VNVT = 用V表示VN VT ，称为文法G的字母表或字汇表规则，也称重写规则、产生式或生成式，是形如 或:=的(, )有序对，其中是字母表V的正闭包 V+中的一个符号且至少含一个非终结符，是V*中的一 个符号。 称为规则的左部， 称作规则的右部编译原理 计算机学院 李金厚文法定义例，文法G=(VN, VT, P, S） VN = S, VT =0, 1 P= S0S1, S01 S为开始符号编译原理 计算机学院 李金厚文法的写法元符号: := | 习惯
6、: 大写字母表示非终结符, 小写字母表示终结 符 (1) G: SaAb Aab AaAb A(2) GS: Aab AaAb A SaSb(3) GS: Aab |aAb | SaSb编译原理 计算机学院 李金厚推导的定义直接推导“”是文法G的产生式，若有v,w满足：v= ，w= ，其中, V*则称v直接推导到w,记作 vw也称w直接归约到v 例，有文法G：S0S1，S01，可有下 面一些推导0S1 00S1100S11 000S111000S111 00001111S 0S1编译原理 计算机学院 李金厚推导 例，有下面的推导，括号里是相应的文法：. ( . ). . ( ) VAR; BE
7、GIN READ()END. VAR A;BEGIN READ( ) END.( A)VAR A; BEGIN READ( ) END. VAR A;BEGIN READ( A) END.( A)编译原理 计算机学院 李金厚推导若存在v =w0 w1 . wn=w,(n0)，则 记为v =+ w，称作v推导出w，或w归约 到v 若有v =+ w 或 v=w， 则记为v =* w编译原理 计算机学院 李金厚例，有文法G： S0S1， S01，则可确定存 在下面一些推导0S1 00S1100S11 000S111000S111 00001111 S 0S1 00S11 000S111 000011
8、11 于是，S + 00001111S * S 00S11 * 00S11编译原理 计算机学院 李金厚句子和句型句子句型 对文法G，若S * x，则称x是文法G的句型 句子 对文法G，若S * x，且xVT*，则称x是文法 G的句子 例，设有文法G：S0S1，S01S 0S1 00S11 000S111 00001111G的句型S，0S1，00S11，000S111， 00001111G的句子00001111, 01，等等编译原理 计算机学院 李金厚句子和句型例，设有文法GE：EE+T|TTT*F|FF(E)|a有推导EE+T T+T F+T a+T a+T*Fa+F*F a+a*F a+a*
9、a，等等通过观察可以知道，上述文法定义的句子是用 符号a，+，*， 以及 ( )构成的算术表达式编译原理 计算机学院 李金厚语言、文法和句子例，由文法G生成的语言记为L(G),它是文 法G的一切句子的集合: L(G)=x|S * x，其中S为文法的开始符号 ，且x VT*例：G：S0S1，S01L(G)= 0n1n|n1集合表示形式编译原理 计算机学院 李金厚文法、语言和句子 例 文法GS： （1）SaSBE （2）SaBE （3）EBBE （4）aBab （5）bBbb （6）bEbe （7）eEeeL(G)= anbnen | n1 G生成的每个串都在L(G)中L(G)中的每个串确实能被G
10、生成编译原理 计算机学院 李金厚文法等价的概念定义：若L(G1)=L(G2)，则称文法G1和G2是等价的。也就是说，如果 两个文法所产生句子集合相同，那么就称它们是等价的 例，下面两个文法就因为产生的句子集合相同 而等价：G1A：ADB 与 G2S：S0S1 等价ADE S01 EABD0B1编译原理 计算机学院 李金厚文法的类型通过对产生式施加不同的限制，学者Chomsky 将文法分为四种类型： 0型文法：对任一产生式，都有 (VNVT)+， (VNVT)* 1型文法：对任一产生式，都有|， 仅 仅S除外 2型文法：对任一产生式，都有VN 3型文法：任一产生式的形式都为AaB或 Aa，其中A
11、VN ，BVN ，aVT *编译原理 计算机学院 李金厚文法的类型例，下面是1型(上下文有关)文法文法GS： SCDAbbACaCABaaBCbCBBbbBADaDCaBDbDDbAabD编译原理 计算机学院 李金厚文法与类型例，下面是2型(上下文无关)文法文法GS： SAB ABS|0 BSA|1编译原理 计算机学院 李金厚文法与类型例，下面是3型文法的两个例子GS：S0A|1B|0A0A|1B|0SB1B|1|0GI：I lTI lT lTT dTT lT d编译原理 计算机学院 李金厚不同类型文法之间的关系四类文法之间存在逐级包含的关系2型文法1型文法3型文法0型文法编译原理 计算机学院
12、 李金厚文法和语言文法和它所产生的语言之间存在对应关系0型文法产生的语言称为0型语言1型文法或上下文有关文法(CSG)产生的语言称为1型语 言或上下文有关语言(CSL)2型文法或上下文无关文法(CFG)产生的语言称为2型语 言或上下文无关语言(CFL) 3型文法或正则(正规)文法(RG)产生的语言称为3型语言 正则(正规)语言(RL)编译原理 计算机学院 李金厚文法和语言怎样理解四种文法之间的关系？四种文法之间的关系是对产生式逐步做更 多的限制而定义的。为此，它们所定义语言之 间的关系依次是：有不是上下文有关语言的0型 语言，有不是上下文无关语言的1型语言，有不 是正则语言的上下文无关语言编译
13、原理 计算机学院 李金厚几个理论共识结论1：0型文法(短语结构文法)的能力相 当于图灵机，可以表征任何递归可枚举集 ，而且任何0型语言都是递归可枚举的结论2：1型文法(上下文有关文法)：产生 式的形式为1A212，即只有A出现 在1和2的上下文中时，才允许取代A。 其识别系统是线性界限自动机编译原理 计算机学院 李金厚几个理论共识结论3：任何能用图灵机描述的计算都能 机械实现，任何能在现代计算机上实现的 计算都能用图灵机描述带 a0 a1 a2 a3 a4 a5 a6 a7 a8 an-1 an 有限控制器磁头编译原理 计算机学院 李金厚几个理论共识结论4：2型文法产生式的形式为A， 取代A时
14、与A的上下文无关。其识别系统 是不确定的下推自动机结论5：3型文法(正规文法RG) 产生的语 言是有穷自动机(FA)所接受的集合编译原理 计算机学院 李金厚3型文法与有穷自动机定理：设G=(VN, VT, P, S)是3型文法，则存在一个有穷自动 机 M=(K, , f, A, Z)，使得L(M)=L(G) 可以从文法直接构造相应的自动机： =VT Z=N，N是新增加的一个状态 A=S K=VNN f的设置需视情况来定a, 对G中的形如 DtB的产生式,t为终结符或，有f(D,t)=Bb, 对G中形如Dt的产生式， t为终结符或,有f(D,t)=Nc, 对VT中的每一个a ,有f(N, a)=编译原理 计算机学院 李金厚从3型文法到有穷自动机从3型文法按前述方法可直接构造相应的 有穷自动机GS：SaA|bBAbB|aD|aBaA|bD|bDaD|bD|a|bASaabbb a,bZaba bBD编译原理 计算机学院 李金厚从有穷自动机到3型文法定理：已知一有穷自动机M= (K, , f, A, Z)，那么存在一个3型文法G = (VN, VT, P, S)，使得L(G)=L(M) 3型文法的构造方法： VT= VN= K S=A 对转换函数a, 若 f(D,t)=B ，则DtB在
