编译原理第二章课件(续)——张淑艳.ppt

1、2020/7/15,中国科大,程序设计语言编译原理,2020/7/15,中国科大,温故知新,字母表,符号,符号串,语言,集合,组合,集合,区别, 和,符号串的连接：符号串x和y的连接表示为xy,符号串的长度,符号串的幂运算：设x是一个符号串，则： x0=，x1 = x，x2 = xx，xn = xx,2020/7/15,中国科大,温故知新,符号串集合的连接 *的子集U和V的连接（积）定义为 UV = |U & V 指数：Vn= VVV，V0 = 闭包：V* = V0 V1 V2 V3 正闭包：V+ = VV* = V1 V2 V3 练习 U: A, B, , Z, a, b, , z , V:

2、 0, 1, , 9 UV, V6, V*, U(V )*, U+,2020/7/15,中国科大,温故知新,2020/7/15,中国科大,温故知新,定义1：上下文无关文法是四元组G =（VT , VN , S, P ） VT : 终结符集合 VN : 非终结符集合, VT VN = S : 开始符号, SVN P :产生式集合， 产生式形式 : P , P VN , (VN VT)* 例 :变量i是一个算术表达式； 若E1和E2是算术表达式，则E1+E2、E1*E2和(E1)也是算术表达式,E i E E +E E E *E E (E),E i | E + E| E * E|(E),简化表示,

3、( i, +, *, (, ), E, E, P ),2020/7/15,中国科大,E (E) (E + E) (i + E) (i + i),温故知新,上下文无关文法如何定义语言？推导 把产生式看成重写规则，把当前符号串中的非终结符用其产生式右部的串来代替。,E i | E + E| E * E|(E),E (E) EE+E Ei Ei,E E * E E+E * E i + E * E i + (E) * E i + (E + E) * E i + ( i + E) * E i + ( i + i) * E i + ( i + i) * i,E E *E EE+E Ei E(E) EE +

4、 E E i E i E i,2020/7/15,中国科大,温故知新,定义2：符号串的推导与归约：已给文法G=(VN,VT, S, P ） 令,(VNVT)*，且A P ，此时，由符号串A能够直接推出符号串 ，我们称： 符号串是符号串A的直接推导； 符号串A是符号串的直接归约 记作: A 若有1,2,n (VNVT) * 且1 2 n-1 n 则称n是1的推导。 特别约定：若在推导关系1 n中允许1=n， 则称n是1 的广义推导,2020/7/15,中国科大,温故知新,定义3：句型、句子和语言，已给文法G=(VN,VT, S, P ）,若 S, (VNVT)* ，则称为文法G的句型,文法G所对

5、应的语言是句子的集合，记作L(G)=|VT*，且S,i + i 和 i +(i + i) * i 都是,E i | E + E| E * E|(E),的句子,2020/7/15,中国科大,例：考虑文法G1定义的语言。 G1: SbA AaA | a,S bA,ba,S bA,baA,baa,S bA,baA,baA,baa.a,L(G1)=ban|n1,2020/7/15,中国科大,例：考虑文法G2定义的语言。 G2：SAB AaA | a BbB | b,L(G2)=ambn|m,n1,S AB,aB,S AB,aAB,ab,aaB,aab,S AB,aaB,aabbB,aabb,aabB,

6、2020/7/15,中国科大,L(G2)=ambn|m,n1,G2：SAB AaA | a BbB | b,G2 SACB AaA | a C aCb| BbB | b,(1)给定一个文法G，就可以从结构上唯一地确定其语言 GL(G),(2)给定一种语言L，能确定其文法，但这种文法可能不是唯一的：LG1或G2,2020/7/15,中国科大,例：构造一个文法G3使L(G3)=anbn|n1,G3: SaSb | ab,例：有文法G4: SaSb Sab它确定的语言是什么？,L(G4)=anbn | n1,例：已知语言为 L(G)=abna | n1 试给出其文法。,G5: SaBaBbB|b,G

7、5:SaBaBBb|b,例：有文法G6 确定什么语言？ S aB | bB B a | b,L(G6)=aa,ab,ba,bb,2020/7/15,中国科大,2.3.1 上下文无关文法,E E + E | E * E | (E ) | E | id E E (E) (E + E) 最左推导:任何一步 都是对的最左非终结符进行替换的。 E lm E lm (E) lm (E + E) lm (id + E) lm (id + id) 最右推导（规范推导） E rm E rm (E) rm (E + E) rm (E + id) rm (id + id),？,？,2020/7/15,中国科大,2.

8、3.1 上下文无关文法,例：文法G: E i| E+E | E*E | (E) 给出句子 i*i+ i 的最右及最左推导 。,E, E+i, E*E+i, E+E, E*i+i, i*i+i,最右推导：,E, E*E+E, i*E+E, E+E, i*i+E, i*i+i,最左推导：,E, i*E, i*E+E, E*E, i*i+E, i*i+i,2020/7/15,中国科大,2.3.1 上下文无关文法,E lm E lm (E) lm (E + E) lm (id + E) lm (id + id),E rm E rm (E) rm (E + E) rm (E + id) rm (id +

9、 id),E,E,E,E,E,(,),E,E,E,(,),E,E,E,+,E,E,(,),E,E,E,+,id,E,E,(,),E,E,E,+,id,id,E,E,E,E,E,(,),E,E,E,(,),E,E,E,+,E,E,(,),E,E,E,+,id,E,E,(,),E,E,E,+,id,id,2020/7/15,中国科大,2.3.2 语法分析树与二义性,语法分析树：句型推导的图形表示，简称语法树。,E,E, (E), (E + E), (i + E), (i + i),E, (E), (E + E), (E + i), (i + i),E,一棵语法树表示了一个句型种种可能的不同推导过程

10、。,2020/7/15,中国科大,2.3.2 语法分析树与二义性,E E * E i * E i * E + E i * i + E i * i + i,文法的二义性：若一个文法存在某个句子/句型对应两棵不同的语法树，则称此文法是二义性文法。,E i| E+E | E*E | (E),句子：i * i + i,E E + E E * E +E i * E + E i * i + E i * i + i,2020/7/15,中国科大,2.3.2 语法分析树与二义性,消除二义性：,用一种层次观点看待表达式 按照优先集和结合性,2020/7/15,中国科大,2.3.2 语法分析树与二义性,用一种层次

11、观点看待表达式 i * i + i i * (i + i) i * (i * i + i) i * i * (i + i) + i * i + i 取消二义性的文法 表达式 项 |表达式 + 项 项 因子| 项 * 因子 因子 i |（表达式）,表达式,2020/7/15,中国科大,2.3.2 语法分析树与二义性,用一种层次观点看待表达式 i * i + i i * (i + i) i * (i * i + i) i * i * (i + i) + i * i + i 取消二义性的文法 E T | E + T T F | T * F F i |（E）,E,E,E i| E+E | E*E |

12、(E),2020/7/15,中国科大,2.3.2 语法分析树与二义性,例：给出文法G，判断是否为二义文法，如果是，取消二义性 语句 if 条件 then 语句 | if 条件 then 语句 else 语句 | 其它语句 例 推导句型：if 条件 then if 条件 then 语句 else 语句 最左推导： 语句 if 条件 then 语句 if 条件 then if 条件 then 语句 else 语句 语句 if 条件 then 语句 else 语句 if 条件 then if 条件 then 语句 else 语句,2020/7/15,中国科大,2.3.2 语法分析树与二义性,语句 i

13、f 条件 then 语句 | if 条件 then语句else语句 | 其它语句 取消二义性的文法： 语句 匹配句| 非匹配句 匹配句 if 条件 then 匹配句 else 匹配句 | 其它语句 非匹配句 if 条件 then 语句 | if 条件 then 匹配句 else 非匹配句,2020/7/15,中国科大,练习,1、令文法为 E T | E+T | E-T T F | T *F | T/F F ( E ) | i 给出 i*(i+i) 的最右推导及语法树 2、证明下面的文法是二义的 SiSeS | iS | i,2020/7/15,中国科大,E T T *F T *( E ) T

14、*(E+T ) T *(E+F ) T *(E+i ) T *(T+i ) T *(F+i ) T *(i+i ) F *(i+i ) i *(i+i ),E T | E+T | E-T T F | T *F | T/F F ( E ) | i,句子：i*(i+i),句子：iiiei,S iSeS iiSeS iiieS iiiei,SiSeS | iS | i,S iS iiSeS iiieS iiiei,2020/7/15,中国科大,1.不能有形如： PP的产生式；,2.不能有多余产生式，每个非终结符P必须都有用处。,(1)在推导文法的所有句子时，始终都用不到的产生式；如，从开始符号，不存

15、在推导 S P,(2)在推导过程中，一旦使用此产生式，将无法推出任何句子的产生式；如，对于非终结符P，不存在P , VT*,2.3.2 语法分析树与二义性,例：有文法G: Z Be A Ae | e B Ce | Af C Cf D f,Z BeA Ae | eB Af,*,*,上下文无关文法的限制：,2020/7/15,中国科大,上下文无关文法,2.3.3 形式语言鸟瞰,文法 G = (VT , VN, S, P) 乔姆斯基把文法分为四类： 0型文法： ， , (VN VT)*, 至少有一个非终结符 1型文法：| | | |，但S 可以例外 A 是1型文法的一个产生式 2型文法：A ，AVN , (VN VT)* 3型文法：A B或A ，A, BVN , VT*,短语文法,上下文有关文法,右线性文法正规文法,2020/7/15,中国科大,2.3.3 形式语言鸟瞰,例 L= an