编 译 原 理 指导教师:杨建国 二零一零年三月.

Presentation on theme: "编 译 原 理 指导教师:杨建国 二零一零年三月."— Presentation transcript:

1 编 译 原 理 指导教师:杨建国 二零一零年三月

2 第三章 文法和语言 第一节 文法的直观概念 第二节 符号和符号串 第三节 文法和语言的形式定义 第四节 文法的类型
第三章　文法和语言 第一节 文法的直观概念 第二节 符号和符号串 第三节 文法和语言的形式定义 第四节 文法的类型 第五节 上下文无关文法及其语法树 第六节 句型分析 第七节 有关文法实用中的一些说明 第八节 典型例题及解答

3 知识结构

4 第三章 文法和语言 3.1 文法的直观概念 所谓一个语言的语法是指一组规则，用它可以形成和产生 一个合适的程序
　一个合适的程序 目前广泛使用的手段是上下文无关文法，即用上下文无关 　文法作为程序设计语言语法的描述工具

5 程序设计语言的描述： 语法：程序的结构或形式 语义：语言所代表的含义 语用：语言的实际应用

6 例如，对于赋值语句 x : = a + b * c 的非形式描述是：
语法：赋值语句＝变量＋:=＋表达式 语义：先求右部，然后把结果给左部变量 语用：赋值语句可用来计算和保存表达式的值 形式化方法：用一整套带有严格规定的符号体系来描述问 　题的理论和方法 形式语言：一种不考虑含义的符号语言

7 程序设计语言的语义分成： 静态语义：是一系列限定规则，并确定哪些合乎语法的程 　序是合适的 动态语义（运行语义、执行语义）：表明程序要做什么， 　要计算什么

8 以自然语言为例，人们无法列出全部句子，但是人们可以
　给出一些规则，用这些规则来说明（或者定义）句子的组 　成结构：

9 例如, 有一组规则: < 句子 > :: = < 主语 > < 谓语 > < 主语 > :: = < 冠词 > < 形容词 > < 名词 > < 冠词 > :: = the < 冠词 > :: = a < 形容词 > :: = big < 谓语 > :: = < 动词 > < 直接宾语 > 　　 < 动词 > :: = ate < 直接宾语 > :: = < 冠词 > < 名词 > < 名词 > :: = cat < 名词 > :: = mouse 　　显然, 由这一组规则可以产生句子: 　　The big cat / mouse ate a mouse / cat

10 这样的语言描述称为文法 使用文法作为工具，不仅为了严格地定义句子的结构， 　 也是为了适当条数的规则把语言的全部句子描述出来， 可以说文法是以有穷的集合刻画无穷的集合的一个工具

11 3.2 符号和符号串 一.字母表和符号串 1.语言可以看成在一个基本符号集上定义的，按一定规则 构成的一切基本符号串组成的集合
　构成的一切基本符号串组成的集合 2.字母表（符号集）：是一个非空有穷集合 3.符号（字符）：字母表中的元素 4.符号串：符号的有穷序列。注意： 表示空符号串！ 5.符号串集合：字母表上若干个符号串组成的集合

12 重要约定： 小写字母 a, b, c, ••• , r 表示符号 小写字母 s, t, u, ••• , z 表示符号串 大写字母 A, B, C, ••• , Z 表示符号串集合

13 二.符号串的运算 1.符号串相等：设 x 、y 是字母表  上的两个符号串，若 x 　与 y 的诸符号依次相等，则该两符号串相等，记为 x = y 　例：x=ab, y=ba, x=y?

14 2.符号串长度：设 x 是字母表上的符号串，符号串中包含
　符号的个数称为符号串 x 的长度，用 x 表示 例: (1). | abc | = ? (2). |  | = ? (3). | a x | = | x a | = | x | ( a ∈∑ )

15 3. 符号串的连结：设 x 与 y 是字母表  上的两个符号串，
　把 y 的所有符号相继写在 x 的符号之后所得到的符号串 　称为x 与 y 的连结，用 x y 表示 　注意: | x y | = | x | + | y |  x = x  = x x y ≠ y x ( 一般说来 )

16 4 .符号串的逆：设 x 是字母表  上的符号串，其逆为符号串 x
　的倒置，记为 。 . 若 x = abcd , 则 = ? (2) = 

17 5.符号串的前缀、后缀和子串：设 x、y、z 是字母表  上的
　符号串，则称 x 为符号串 x y 的前缀，y 是符号 串 x y 的 　后缀， x、y 、 z 、xy 、yz 是符号串 x y z 的子串 　例: abcd前缀、后缀、子串是什么？

18 6.符号串集合的乘积：设A、B为两个符号串集合，其乘积为
AB={xy|xA,y B} 例: (1). 若 A = { ab, cd }, B = { ef, gh } ，AB＝？ (2). ∵  x = x  = x ∴ {  } A = A {  } = A

19 7.空集：不含任何元素的集合，记为 Ø 注意: (1). Ø A = A Ø = Ø (2).   Ø

20 8.符号串的幂：设 x 是字母表  上的符号串，则 x 的幂运算
　为x 0 =  x 1=x x 2=xx •••••• x n=x n-1x (xx n-1) 　例: 若 x = ab 则: x 0 = ?, x 1 = ?, x 2 = ?, ••••••, 　　　x n = ?

21 9.符号串集合的幂：设 A 是符号串集合，则符号串 A 的幂运
　算为： A0={} A1=A A2=AA •••••• An=A n-1A (AA n-1) 　例: 若 A = { ab, cd } ,则: A 0 = ?, A 1 = ?, A 2 = ?, ••••••

22 则: A*= {, a, b, aa, ab, ba, bb, aaa, ••• }
注意: A*=A0∪A+ A+=AA*=A*A 若 A = { a, b } 则: A*= {, a, b, aa, ab, ba, bb, aaa, ••• } A+= {a, b, aa, ab, ba, bb, aaa, ••• }

23 3.3 文法和语言的形式定义 规则（重写规则、产生式、生成式）： 一个规则是一个二元组,通常写作α::= β 或 α β
　一个规则是一个二元组,通常写作α::= β 或 α β α称为规则的左部，β称为规则的右部， (::=)读作 　“定义为”，这是一条关于α的规则（产生式）

24 定义3.1：文法G定义为四元组（VN，VT，P，S）
P：规则（α　 β）集合，α∈(VN∪VT)*且至少包含 　一个非终结符，β ∈(VN∪VT)* VN、VT、P是非空有穷集 S：开始符（识别符），它是一个非终结符，至少要在一 　条规则中作为左部出现 VN∩VT= Ø V=VN∪VT，称为文法G的字母表（字汇表）

25 例3.1 文法G=（VN，VT，P，S），其中 　VN = { S }， 　VT ={ 0, 1 }， 　P={ S　　0S1, S　　01 } 思考：S＝？

26 例3.2　文法G=（VN，VT，P，S），其中 VN ={标识符，字母，数字} ，S=<标识符> VT ={a,b,c,…x,y,z,0,1,…,9} P＝{<标识符>　　<字母> 　 <标识符>　　<标识符><字母> <标识符>　　<标识符><数字> 　 <字母>　　a 　　　　……　　　 　　　 <字母>　　z 　　 <数字>　　0 　　　　 …… 　　　 <数字>　　9 } 思考：S＝？

27 很多时候，不用将文法G的四元组显式地表示出来，而
　只将产生式写出

28 一般约定： 第一条产生式的左部是识别符 用尖括号括起来的是非终结符（或者用大写字母表示） 不用尖括号括起来的是终结符（或者用小写字母表示） 将G也写成G[S]，其中S是识别符

29 推导： 　定义V*中的符号之间的关系： 直接推导： 长度为n(n≥1)的推导： 长度为n(n ≥0)的推导： + *

30 定义3.2：文法G＝（VN，VT，P，S），α　 β是一条
　规则，γ和δ是V*中的任意符号，若有符号串v，w满 　足：v=γαδ，w= γβδ，则称v直接推导到w， 　 v　  w，或w直接归约到v 例：G： S　　0S1， S　　01 　S 　0S1 　00S11 　000S111 　

31 定义3.3：如果存在直接推导的序列： 　v=w0　　w1　　w2…　　wn=w (n>0) 　则称v推导出w（推导长度为n），或称w归约到V， 　记作 +

32 + * 定义3.4：若有v　　w，或v=w，则记作：

33 * 定义3.5：若有S　　x，则称x是文法G[S]的句型，若x仅 　由终结符组成，则称x为G[S]的句子

34 定义3.6：文法G所产生的语言定义为集合 　L(G)=｛x|S　　x，其中S为文法识别符号，且x∈VT*｝ 文法描述的语言是该文法一切句子的集合 例：G： S　　0S1， S　　01 　　　L(G)={0n1n|n≥1} *

35 例3.3　文法文法G[S]： （1）S　　aSBE （2）S　　aBE （3）EB　　BE （4）aB　　ab （5）bB　　bb （6）bE　　be （7）eE　　ee L（G）={ anbnen | n≥1 } 思考：a4b4e4怎么推导？

36 定义3.7：若L(G1)＝L(G2)，则称文法G1和G2是等价的
例如文法G[A]： A　　0R A　　01 R　　A1 　和文法G[S]： S　　0S1 S　　01 等价　L(G)={0n1n|n≥1}

37 3.4 文法的类型 乔姆斯基(Chomsky)于1956年建立形式语言的描述 他把文法分成：0型、1型、2型、3型
四个文法类的定义是逐渐增加限制的 0型 1型 2型 3型

38 设G＝（VN，VT，P，S），如果它的每个产生式
　含一个非终结符， β∈(VN∪VT)*，则G是一个0型文法 　（短语文法、无限制文法）

39 思考：这样定义可以吗？ 设G＝（VN，VT，P，S），如果它的每个产生式 　α　　β是这样一种结构：α∈(VN∪VT)+， β∈(VN∪VT)*，则G是一个0型文法

40 重要的理论结果： 0型文法的能力相当于图灵机（Turing） 或者说，任何0型语言都是递归可枚举的 反之，递归可枚举集必定是一个0型语言

41 设G＝（VN，VT，P，S），如果它的每个产生式
例3.1、3.2、3.3

42 例：文法G[S]： 　　　　　　 S　　CD Ab　　bA C　　aCA Ba　　aB C　　bCB Bb　　bB AD　　aD C　　ε BD　　bD D　　ε Aa　　bD L(G)={w|w∈{a,b}*}

43 有些定义中，将上下文有关文法的产生式的形式描述为
　α1Aα2　　α1βα2，其中α1、α2和β都在V*中， 　β≠ε，A在VN中

44 设G＝（VN，VT，P，S），如果它的每个产生式

45 有时将2型文法的产生式表示为A　　β的形式，其中
　A∈VN，也就是用β取代非终结符A时，与A所在的上下 　文无关，因此取名为上下文无关 例3.1、3.2

46 例3.4：文法G[S]： 　　　　S　　aB|bA 　A　　a|aS|bAA 　B　　b|bS|aBB

47 设G＝（VN，VT，P，S），如果它的每个产生式
　A　　αB或A 　　α，其中A和B都是非终结符， 　α∈VT*，则文法G是3型文法（正规文法） 例3.5：文法G[S]： 　　　　S　　0A|1B|0 　A　　0A|1B|0S 　B　　1B|1|0 你会忘记我吗？

48 例：判断下面文法G[S]是哪一类方法，并说明你的理由？
　　　　S　　B|aB 　B　　D|a 　D　　b|ε

49 4个文法类的定义是逐渐增加限制的，因此，每一种正规
　文法都是上下文无关的，每一种上下文无关文法都是上 　下文有关的，而每一种上下文有关文法都是0型文法 称0型文法产生的语言为0型语言，上下文有关文法、上 　下文无关文法和正规文法产生的语言分别称为上下文有 　关语言、上下文无关语言和正规语言

50 3.5 上下文无关文法及其语法树 上下文无关文法有足够的能力描述现今程序设计语言的 语法结构，比如描述算术表达式、描述各种语句等
　语法结构，比如描述算术表达式、描述各种语句等 例3.6：文法G=({E},{+,*,i,(,)},P,E)其中P为： 　　　　E　　i 　E　　E+E 　E　　E*E E (E) <条件语句>　　if<条件>then<语句>| 　　　　　　　　if<条件>then<语句>else <语句>

51 给定文法G=（VN，VT，P，S），对于G的任何句型都
　能构造与之关联的语法树（推导树、语法分析树、分 　析树）。这棵树满足下列4个条件： （1）每个结点都有一个V中的符号作标记 （2）根的标记是开始符号S （3）若一结点n至少有一个它自己除外的子孙，并且有标记 　　A，则A∈VN （4）如果结点n的直接子孙，从左到右的次序是结点 n1,n2,…,nk，其标记分别为A1,A2,…,Ak，那么 A　　A1A2…Ak一定是P中的一个产生式

52 例3.7：文法G=({S，A},{a,b},P,E)其中P为：
　　　　(1)S　　aAS 　(2)A　　SbA 　(3)A　　SS (4)S a (5)A ba 图3.1的推导树是文法G的 　句型aabbaa的推导过程 把aabbaa叫做推导树的结果， 　把推导树叫做句型 　aabbaa的语法树 图3.1 推导树

53 文法G的句型aabbaa的推导过程： （1）SaASaAaaSbAaaSbbaaaabbaa （2）SaASaSbASaabASaabbaSaabbaa （3）SaASaSbASaSbAaaabAaaabbaa 如果在推导的任何一步α　　 β，其中α、β是句型，都 　是对α中的最左（最右）非终结符进行替换，则称这种推 　导为最左（最右）推导。在形式语言中，最右推导被称为 　规范推导，由规范推导所得的句型称为规范句型 你会忘记我吗？

54 一个句型是否只对应唯一的一棵语法树？一个句型是否只
　有唯一的一个最左（最右）推导？ 不是 例：G[E]: E 　 　i E 　 E+E E 　 E*E E 　 (E) 句型 i*i+i 的两个： 推导1：E  E+E  E*E+E  i*E+E  i*i+E  i*i+i 推导2：E  E*E  i*E  i*E+E  i*i+E i*i+i

55 图3.2　推导1的语法树 图3.3　推导2的语法树

56 若一个文法存在某个句子对应两棵不同的语法树，则称这
　个文法是二义的。或者，若一个文法存在某个句子有两个 　不同的最左（右）推导，则称这个文法是二义的

57 注意，文法的二义性和语言的二义性是两个不同的概念。
　因为可能有两个不同的文法G和G`，其中G是二义的，但 　是却有L(G)=L(G`) 产生某上下文无关语言的每一个文法都是二义的，则称此 　语言是先天二义的 你是怎么理解我的？

58 判定任给的一个上下文无关文法是否二义，或它是否产生
　一个先天二义的上下文无关语言，这两个问题是递归不可 　解的。但可以为无二义性寻找一组充分条件　　

59 解决二义性的基本方法： 设置一个规则，该规则可在每个二义性情况下指出哪一个 　分析树是正确的。这样的好处：不用修改文法就可以消除 　二义性。缺点：语言的语法结构不能由文法单独提供 将文法改变成一个强制正确分析树的构造的格式

60 例：　G[E]： E 　　　E T E | (E) | 6 T |-|* 　　　　　　　　 6-6*6=? 6-6-6=? 　　 规定优先性、结合规则就可以构造出一个无二义文法

61 3.6 句型的分析 句型分析是一个识别输入符号是否为语法上正确的程序的 过程 在语言的编译实现中，把完成句型分析的程序称为分析程
　过程 在语言的编译实现中，把完成句型分析的程序称为分析程 　序（识别程序），分析算法又称为识别算法 介绍的分析算法都称之为从左到右的分析算法 分析算法分为： 自上而下分析法：从文法的开始符号出发，反复使用各种 　产生式，寻找匹配于输入串的推导 自下而上的方法：从输入符号串开始，逐步进行归约，直 　到归约到文法的开始符号

62 一.自上而下分析方法 例3.9　考虑文法G[S] （1）S　　cAd （2）A　　ab （3）A　　a 识别输入串 w=cabd 是否该文法的句子 所构造的推导过程为： 　S　　cAd　　cabd 图3.4　自上而下的分析步骤

63 二.自下而上分析方法 例3.9　考虑文法G[S] （1）S　　cAd （2）A　　ab （3）A　　a 识别输入串 w=cabd 是否该文法的句子 所构造的推导过程为： 　S　　cAd　　cabd 图3.5　自下而上的分析

64 三.句型分析的有关问题 在自上而下的分析中，对于例3.9的文法，在扩展A时，有 　两个选择，如果选择另一个，推导序列为 　S　　cAd　　cad，语法树如图3.6所示 这时，就与w=cabd不符，宣告失败 应该用哪条规则去替换呢？一种解决办法从各种可能的选 　择中随机挑选一种，并希望它是正确的，如果失败，退回 　去，再试另一种，这种方式称为回溯。显然这种方式代价 　极高，效率很低 图3.6 cad的语法树

65 在自下而上的分析中，对于例3.9的文法，在归约的时候，
　也存在选择哪一条规则进行归约的问题，因此需要精确定 　义“可归约串”。事实上，存在种种不同的方法刻画“可归 　约串”。对这个概念的不同定义形成了不同的自下而上分 　析文法。在一种“规范归约”的分析中，这种“可归约串”称 　作“句柄”

66 定义3.8　令G是一文法，S是文法的开始符号，αβδ是文
如果有：S　 αAδ且A　 β则称β是句型αβδ相对 　于非终结符A的短语 如果有A　　 β则称β是句型αAδ相对于规则A　　 β 　的直接短语（简单短语） 一个句型的最左直接短语称为该句型的句柄 * + 你会忘记我吗？

67 E T F * i3 + i1 i2 例G[E]: E 　　T|E+T 　　　　 T 　　F|T*F F 　　（E）|i 　句型i*i+i 短语：i1、i2 、i3 、i1*i2 、i1*i2+i3 直接短语：i1 、i2 、i3 句柄：i1

68 例题：句型aabbab中的短语、简单短语、句柄是谁？

69 3.7 有关文法实用中的一些说明 一.有关文法的实用限制 有害规则：形如U U的产生式 多余规则：文法中那些连一个句子的推导都用不到的规则
某些非终结符不在任何规则的右部出现（不可到达的） 不能够从这些非终结符推出终结符号串（不可终止的）

70 例3.10　文法G[S]： （1） S　　Be （2） B　　Ce （3） B　　Af （4）A　　Ae （5）A　　e （6）C　　Cf （7） D　　f 该文法的有害规则和多余规则是哪些？

71 对文法G=(VN,VT,S,P)来说，为了保证其任一非终结符A在
　句子推导中出现，必须满足如下两个条件： ①A必须在某句型中出现。即S　　αAβ,其中α,β属于V* ②必须能够从A推出终结符号串t。即A　　t,其中t∈VT* * +

72 二.上下文无关文法中的ε规则 ε规则：形如A　　 ε的产生式，其中A∈VN 某些著作和讲义中限制这种规则的出现。因为ε规则会使 　有关文法的一些讨论和证明变得复杂 两种定义的唯一差别是ε句子在不在语言中 如果语言L有一个有穷的描述，则L∪{ε}也同样有一个有 　穷描述。并且可以证明，若L是上下文有关语言、上下文 　无关语言或正规语言，则L∪{ε}和L-{ε}分别是上下文有 　关语言、上下文无关语言和正规语言

73 定理3.1　若L是由文法G=(VN,VT,P,S)产生的语言，P中的
　每一个产生式的形式均为A　　α,其中A∈VN，α∈V*， 　则L能由这样的一种文法产生，即每一个产生式或者为 　A　　β形式，其中A∈VN， β ∈V+,或者 S　　ε形式， 　且 S不出现在任何产生式右边

74 定理3.2　如果G是上下文有关文法，则存在另一个上下文
　有关文法G1，L(G)=L(G1)，且G1的开始符号不出现在G1 　的任何产生式的右边 又如果G是一个上下文无关文法，也能找到这样一个上下 文无关文法G1 如果G是是一个正规文法，则也能找到这样一个正规文法 G1

75 3.8 典型例题及解答 1.证明文法G=({E,O},{(,),+,*,v,d},P,E)是二义的 E EOE|(E)|v|d O +|*
2.给出生成下述语言的正规文法： 　L={ambn|n,m>=1}

76 (2)S aS|aA (1)S AB A bA|b A aA|a B bB|b (3)S aA (4)S aA A aA|B A aA|bB
我家没双胞胎 我是对的 (2)S　 　　aS|aA 　A　　　bA|b (1)S　 　　AB 　A　　　aA|a B bB|b 我家没有a 我家少ab (3)S　 　　aA 　A　　　aA|B B bB|b|ε (4)S　 　　aA 　A　　　aA|bB B bB|b 我是对的 我是对的 (5)S　 　　aA 　A　　　aA|B B bB|b (6)S　 　　aA 　A　　　aA|bB|b B bB|ε

77 (7)S aA A aA|bB B bB|ε (8)S aS|aA A bA|bB B ε (9)S aA A aA|aB|b B bB|b
我是对的 (7)S　 　　aA 　A　　　aA|bB B bB|ε (8)S　 　　aS|aA 　A　　　bA|bB B ε 我是对的 我家少ab2 我是对的 (9)S　 　　aA 　A　　　aA|aB|b B bB|b (10)S　 　aA 　A　　　aA|bB|b B bB|b 我是对的 (12)S　 　aA|aS 　A　　　bB B bB|ε 我是对的 (11)S　 　a(A|S) 　A　　　b(A|ε)

78 【本章小结】 ① 本章出现的概念较多,应重点理解文法,推导,句型句子及语 　言的定义等概念.语法分析有关内容在后面章节会详细讨论 ② 文法作为程序语言的语法的描述工具,它用规则只能陈述 　的是:语言的所有句子以什麽样的符号串能出现.请记住文 　法和语言的形式定义中的 “形式”的含义-只涉及语言的语 　法不涉及语言的语义 ③ 本章内容是形式语言理论的一部分.形式语言理论是对符 　号串集合的表示法、结构及其特性的研究。是程序设计语 　言语法分析研究的基础

79 第3章　作业题 P47： 1. 6.(5)进行最左推导　(6)进行最右推导 8. 9. 11. 13. 14. 16.