new文法和语言

1、1第三章第三章 文法和语言文法和语言 一个程序设计语言是一个记号系统，它的完整定义包括两个方面：一个程序设计语言是一个记号系统，它的完整定义包括两个方面：语法语法是指是指一组规则一组规则，应用这组规则可以形成和产生一个合适的，应用这组规则可以形成和产生一个合适的程序。通常用程序。通常用上下文无关文法上下文无关文法作为描述语法的工具作为描述语法的工具.语义语义：程序设计语言的语义分为两种：程序设计语言的语义分为两种： 1）静态语义是一系列限定规则，并确定哪些合乎语法）静态语义是一系列限定规则，并确定哪些合乎语法的程序是合适的；的程序是合适的； 2）动态语义（运行语义或执行语义）表明程序要做什）动

2、态语义（运行语义或执行语义）表明程序要做什么，要计算什么么，要计算什么. 主要内容：主要内容：文法和语言、上下文无关文法、句型分析等文法和语言、上下文无关文法、句型分析等例如：赋值语句：例如：赋值语句：A=B+C 合法；合法；A=B+ 非法；语义则匹配类型非法；语义则匹配类型2 3.1 3.1 文法的直观概念文法的直观概念文法的直观认识：文法的直观认识：如何给出语言的有穷表示？如何给出语言的有穷表示？ 语言是由句子组成的，因此，可以用一些规则说明或定义句子的语言是由句子组成的，因此，可以用一些规则说明或定义句子的组成结构。组成结构。例如：我是大学生例如：我是大学生:=:=| :=我我|你你|他

3、他:=王明王明|大学生大学生|工人工人|英语英语:=:=是是|学习学习:=这些规则成为判别句这些规则成为判别句子结构合法与否的依子结构合法与否的依据据.这些规则看成是一这些规则看成是一种元语言，这样的语种元语言，这样的语言描述称为文法言描述称为文法.3应用规则推导句子：应用规则推导句子：= = =我我 =我我 =我是我是 =我是我是 =我是大学生我是大学生“=”的含义是使用一条规则代替的含义是使用一条规则代替=左边的某个符号并产生左边的某个符号并产生=右端右端的符号串的符号串.应用这些规则可以产生很多句子应用这些规则可以产生很多句子.这样，使用文法作为工具，不仅这样，使用文法作为工具，不仅定义

4、了句子的结构，而且通过有穷的规则描述出语言的全部句子定义了句子的结构，而且通过有穷的规则描述出语言的全部句子.4字母表是元素的非空有穷集合字母表是元素的非空有穷集合字母表中至少包含一个元素。字母表中至少包含一个元素。字母表中的元素，可以是字母、数字或其他符号。字母表中的元素，可以是字母、数字或其他符号。3.2 符号和符号串符号和符号串一一. .字母表字母表 alphabetalphabet【例如】【例如】 = a,b,c是字母表，由是字母表，由a,b,ca,b,c三个元素组成。三个元素组成。【例如】【例如】 = 0,1是字母表，由是字母表，由0,10,1两个元素组成。两个元素组成。不同的语言有

5、不同的字母表。不同的语言有不同的字母表。英文的字母表是英文的字母表是26个字母、数字和标点符号的集合；个字母、数字和标点符号的集合；C语言的字母表是字母、数字和若干专用符号组成。语言的字母表是字母、数字和若干专用符号组成。任何语言的字母任何语言的字母表指出了该语言表指出了该语言中允许出现的一中允许出现的一切符号。切符号。5二二. .符号（字符）符号（字符）symbolsymbol字母表中的元素称为符号，或称为字符。字母表中的元素称为符号，或称为字符。【例如】【例如】 = a,b,ca,b,c是字母表是字母表中的符号。中的符号。【例如】【例如】 = 0,10,1是字母表是字母表中的符号。中的符号

6、。6三三. .符号串（字）符号串（字）stringstring符号的有穷序列称为字符串。符号的有穷序列称为字符串。【例如】设有字母表【例如】设有字母表 = a,b,c，则有符号串则有符号串 a,b,ab,ba,cba,abc,(a,b,ab,ba,cba,abc等都是字母表等都是字母表上的符号串上的符号串)符号串总是建立在某个特定字母表上的且只能由字母表上符号串总是建立在某个特定字母表上的且只能由字母表上的的多个符号组成。多个符号组成。符号串中符号的顺序是很重要的，符号串中符号的顺序是很重要的，如如 ab 和和 ba 是字母表是字母表上的两个不同的符号串。上的两个不同的符号串。不包含任何符号的

7、符号串，称为空符号串，用不包含任何符号的符号串，称为空符号串，用 (epsilon)表示，即空符号串由表示，即空符号串由 0 个符号组成，其长度个符号组成，其长度| |=07r符号串的头尾符号串的头尾：如果zxy是一符号串，那么x是z的头，y是z的尾。 如果x是非空的，那么y是固有尾；如果y是非空的，那么x是固有头。r符号串集合：符号串集合：若集合若集合A A中的一切元素都是某字母中的一切元素都是某字母表上的符号串，则称表上的符号串，则称A A为该字母表上的为该字母表上的符号串集符号串集合合。四四. .符号串的运算相关概念符号串的运算相关概念例如例如:zabc，那么，那么z的头是的头是 , a

8、, ab, abc.Z的尾是的尾是 , c, bc, abc.8四四. .符号串的运算符号串的运算1.1.符号串的连接符号串的连接 connectionconnection设设 x 和和 y 是符号串，则串是符号串，则串 xy 称为它们的连接。即称为它们的连接。即 xy 是将是将 y 符号串写在符号串写在 x 符号串之后得到的符号串。符号串之后得到的符号串。【例如】设【例如】设 x abc，y = 10a，则则 xy abc10a则则 yx 10aabc特别，对任意一符号串特别，对任意一符号串 x 有：有： x x x92.2.符号串的幂运算符号串的幂运算 powerpower设设 x 是符号

9、串，则是符号串，则 x 的幂运算定义为：的幂运算定义为：x0 x1 xx2 xxxn xxx = xxn-1 (n0) n【例如】设【例如】设 x = abc,则则x0 x1 abcx2 abcabc103.3.集合的乘积集合的乘积 productproduct设设 A 和和 B 是符号串的集合，则是符号串的集合，则 A 和和 B 的乘积定义为：的乘积定义为：AB = xy | x A, y B即集合即集合 AB 中的符号串是由中的符号串是由 A 和和 B 的符号串连接而成的。的符号串连接而成的。【例如】设【例如】设 A = a,b,B = c,d则则 AB ac,ad,bc,bd因为对任意一

10、符号串因为对任意一符号串 x 有：有： x x x所以，对任意集合所以，对任意集合 A，有，有 A = A = A11空集空集 empty setempty set 表示不含任何元素的表示不含任何元素的空集空集 = 注意：注意： 是符号串，不是集合，是符号串，不是集合， 表示由空符号串表示由空符号串 所组成的集合，但这样的集合不是空集所组成的集合，但这样的集合不是空集， 即即不包含空串。不包含空串。 (不属于不属于)对任意集合对任意集合 A，有，有 A = A = 124.4.集合的幂运算集合的幂运算设设 A 是符号串的集合，则集合是符号串的集合，则集合 A 的幂运算定义为：的幂运算定义为：A

11、0 A1 AA2 AAAn AAA = AAn-1 (n0) n【例如】设【例如】设 A = a,b,则则A0 A1 a,bA2 AA = aa,ab,ba,bbA3 AAA = A2A = aaa,aab,aba,abb,baa,bab,bba,bbb135.5.集合集合A A的正闭包的正闭包A A+ +与闭包与闭包A A* *设设 A 是符号串的集合，是符号串的集合，则集合则集合 A 的正闭包的正闭包A+和闭包和闭包A*分别定义为：分别定义为：A+ A1 U A2 U A3 U U An U A* A0 U A1 U A2 U A3 U U An U = U A+【例如】设【例如】设 A

12、= a,b,则则A+ a,b,aa,ab,ba,bb,aaa,aab,A* ,a,b,aa,ab,ba,bb,aaa,aab, 正闭包：正闭包：Positive closure闭包闭包：Star closure（星闭包）（星闭包）14【例如】设【例如】设 A = a,则则A+ a,aa,aaa, = an | n=1A* , a,aa,aaa, = an | n=0A* = A0 A1 A2 A3 ，称，称 A* 是是 A 的的闭包闭包。A+ = AA* ，称，称 A+ 是是A的的正则闭包正则闭包。*表示表示上的上的所有符号串的全体所有符号串的全体153.3 文法和语言的形式定义1、规则、规则

13、规则规则，也称重写规则重写规则、产生式产生式或生成式生成式，是形如或 =的( ，)有序对，其中是字母表V的正闭包V+中的一个符号，是V*中的一个符号。 称为规则的左部， 称作规则的右部。或或 162 、文法定义定义文法G定义为四元组(VN，VT，P，S )其中VN:非终结符号(或语法实体，或变量)集；VT:终结符号集；P: 规则的集合； VN，VT和P是 非空有穷集。 S:称作识别符号或开始符号的一个非终结符，它至少要在一条产生式中作为左部出现。 VN和VT不含公共的元素，即VN VT = 用V表示VN VT ，称为文法G的字母表或字汇表 规则规则，也称重写规则重写规则、产生式产生式或生成式生

14、成式，是形如或 =的( ，)有序对，其中是字母表V的正闭包V+中的一个符号，是V*中的一个符号。 称为规则的左部， 称作规则的右部。17例例 文法文法G=（VN，VT，P，S）VN = S , VT = 0, 1 P= S0S1, S01 S为开始符号为开始符号例例 文法文法G=（VN，VT，P，S）VN =标识符，字母，数字标识符，字母，数字VT =a,b,c,x,y,z,0,1,9P= a zz 00 99 S=19文法的写法文法的写法 元元符号: = | = | 习惯习惯 大写字母表示非终结符大写字母表示非终结符 小写字母表示终结符小写字母表示终结符(1) G(1) G：SaASaAb

15、Aab Aab AaA AaAb A A (2) GS (2) GS： Aab Aab AaA AaAb A A SaS SaSb (3) GS:Aab |aA(3) GS:Aab |aAb | | SaSSaSb20推导的定义推导的定义直接推导直接推导“”是文法是文法G G的产生式，若有的产生式，若有v,wv,w满足：满足：v=,w= , v=,w= , 其中其中VV* *,V,V* * 则称则称v v直接直接推导推导到到w,w,记作记作 v v w w 也称也称w w直接直接归约归约到到v v例：例：G G： S0S1， S01 0S1 00S11 00S11 000S111 000S11

16、1 00001111 S 0S121推导推导. ( . ). . ( ) VAR;BEGIN READ()END. VAR A;BEGIN READ( ) END. ( A)VAR A;BEGIN READ( ) END. VAR A;BEGIN READ( A) END. ( A)22 若存在若存在v =w0 w1 . wn=w,(n0) 则记为则记为v w，称作，称作v推导出推导出w，或，或w归约到归约到v 若有若有v w 或或 v=w， 则记为则记为v w推导的定义推导的定义+=+=*=23例：例：G G： S0S1， S010S1 00S1100S11 000S111000S111 0

17、0001111 S 0S1 00S11 000S111 00001111 S 00001111 S S 00S11 00S11+=*=*=24句型、句子的定义句型、句子的定义z句型句型有文法有文法G，若，若S =* x，则称，则称x是文法是文法G的句型。的句型。z句子句子有文法有文法G，若，若S =* x，且，且xVVT T* *，则称，则称x是文法是文法G的句子。的句子。例：例：G G： S0S1， S01S 0S1 00S11 000S111 00001111G的句型S,0S1 ,00S11 ,000S111,00001111G的句子00001111, 0125句型、句子句型、句子例：例：

18、GE E： EE+T|TEE+T|T TT TT* *F|FF|F F(E)|a F(E)|aE EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a句子：用符号句子：用符号a，+，*，(和和)构成的算术表达式构成的算术表达式26( (文法生成的文法生成的) )语言的定义语言的定义由文法由文法G生成的语言记为生成的语言记为L(G),它是文法它是文法G的的一切句子的集合一切句子的集合: L(G)=x|S =* x，其中，其中S为文法的开始为文法的开始符号，且符号，且x VVT T* * 例：例：G G： S0S1， S01 L(G)=0n1n|n1例例 文法文法GS：

19、（1）SaSBE（2）SaBE（3）EBBE（4）aBab（5）bBbb（6）bEbe（7）eEee L（G）= anbnen | n1 G生成的每个串都在生成的每个串都在L(G)中中L(G)中的每个串确实能被中的每个串确实能被G生成生成根据1式进行n-1次得到an-1 S（BE）n-1 由2式an(BE)n由3式得到anBnEn由4式得anbBn-1En由5式n-1次得到anbnEn由6式1次，7式n-1次得到anbnen28文法的等价文法的等价z若若L（G1）=L（G2），则称文法），则称文法G1和和G2是是等价的。等价的。如文法如文法G G1AA：ADB ADB 与与G G2SS：S0S

20、1 S0S1 等价等价 ADE S01 ADE S01 EAB EAB D0 D0 B1 B129【例】设计一个表示所有标识符的文法【例】设计一个表示所有标识符的文法分析：标识符的定义是字母或以字母开头的字母数字串，分析：标识符的定义是字母或以字母开头的字母数字串，其结构如下：其结构如下：字母字母字母或数字字母或数字串串用用 I 表示标识符，表示标识符，L 代表字母，代表字母，D 代表数字，则定义标代表数字，则定义标识符的文法为：识符的文法为：G =（VN，VT，P，S）其中：其中：VN = I,L,DVT = a,b,x,y,z,0,1,2,9P = IL | IL |ID L a | b

21、| | x | y | z D 0 | 1 | |9 S = I30【例】用文法定义一个含【例】用文法定义一个含+ +、* *的算术表达式。的算术表达式。变量是表达式；变量是表达式；若若 E1 和和 E2 是算术表达式，则是算术表达式，则 E1+E2，E1*E2，(E) 也也是算术表达式。是算术表达式。算术表达式的文法为：算术表达式的文法为：G =（VN，VT，P，S）其中：其中：VN = EVT = i,+,*,(,)P = E i | E+E | E*E |(E) S = E31【例】设字母表【例】设字母表 a,ba,b，设计一个文法，描述，设计一个文法，描述语言语言 L=abL=abn

22、na | na | n 0 0 分析：该语言中符号串的结构特征是：分析：该语言中符号串的结构特征是：当当 n=0L = aa(b0= )当当 n=1L = aba当当 n=2L = abbaL = aa,aba,abba,abbba,语言的文法为：语言的文法为：G =（A,B，a,b，P，A）其中其中P为：为：AaBaB |Bb32【例】描述语言【例】描述语言L=abL=abn na | na | n 0 0 的的等价文法等价文法（1）AaBaB |Bb（2）AaBaB |bB（3）AaBB a |bB（4）ABaB a |Bb33【例】设有文法【例】设有文法GS: GS: S S01 | 0

23、S101 | 0S1求该文法所描述的语言求该文法所描述的语言分析：分析：问题归结为由识别符号问题归结为由识别符号 S 出发，将推导出什么样的句子，出发，将推导出什么样的句子，也就是说也就是说 L(GS)是由一些什么样的符号串所组成的集合，是由一些什么样的符号串所组成的集合，找出其中的规律，用式子或自然语言描述出来。找出其中的规律，用式子或自然语言描述出来。应用第二个规则应用第二个规则 n-1 次，然后再使用第一个规则次，然后再使用第一个规则 1 次，次，有有S=0S1=00S11=000S111=0n1S1n1=0n1n即即S 0n1n所以此文法定义的语言为所以此文法定义的语言为 +=34【例

24、】设有文法【例】设有文法GS: GS: S S0S|1S|0S|1S| 求该文法所定义的语言求该文法所定义的语言该文法所确定的语言为该文法所确定的语言为L(GS) = ,0,1,00,01,10,11, = x | x0,10,1* * 35【例】设有文法【例】设有文法GA: GA: A AyB,BxB|xyB,BxB|x求该文法求该文法所定义的语言所定义的语言从从开始符号开始符号 A 出发，我们可以推出如下句子：出发，我们可以推出如下句子：A = yB = yxA = yB = yxB =yxx A = yB = yxB = = yxx归纳得出从归纳得出从 A 出发可推导出所有以出发可推导出

25、所有以 y 开头后跟一个或任开头后跟一个或任意多个意多个 x 得字符串，即得字符串，即L(GA) = yxn | n 1 36【例】考虑文法【例】考虑文法 G1:S A BA a A | aB b B | b 我们可以分析得出我们可以分析得出 L(G1) = am bn | m, n1【例】构造一个文法【例】构造一个文法 G2 使使L(G2) = an bn | m, n1G2 和和 G1 的区别在于，的区别在于，G2 的每个句子中的每个句子中 a 和和 b 的个的个数必须相同。数必须相同。我们可以写出文法我们可以写出文法 G2:S a S b | a b【例】【例】37【例】设字母表【例】设

26、字母表 a,b,a,b,试设计文法，描述语试设计文法，描述语言言 L=aL=a2n2n,b,b2n2n | n | n 11分析：设计文法来描述一个语言，关键是设计一组规则生分析：设计文法来描述一个语言，关键是设计一组规则生成语言中的符号串。成语言中的符号串。设计语言的文法，必须分析这个语言是由怎样一些符号串设计语言的文法，必须分析这个语言是由怎样一些符号串组成，即首先分析语言中符号串的结构特征：组成，即首先分析语言中符号串的结构特征：当当 n=1L = aa,bb当当 n=2L = aaaa,bbbb当当 n=3L = aaaaaa,bbbbbbL = aa,bb,aaaa,bbbb,aaa

27、aaa,bbbbbb,语言语言 L 是由偶数个是由偶数个 a，偶数个，偶数个 b 这样的符号串组成的这样的符号串组成的集合。集合。383.4 3.4 文法的类型文法的类型通过对产生式施加不同的限制，通过对产生式施加不同的限制，Chomsky将将文法分为四种类型：文法分为四种类型：0型文法：对任一产生式型文法：对任一产生式，都有，都有(V(VN NVVT T) )+ +， (V(VN NVVT T) )* *1 1型文法：型文法：对任一产生式对任一产生式，都有，都有|， 仅仅仅仅 SS除外除外2 2型文法：型文法：对任一产生式对任一产生式，都有，都有VVN N 3 3型文法：型文法：任一产生式任

28、一产生式的形式都为的形式都为AaBAaB或或AaAa，其中，其中AVAVN N ，BVBVN N ，aVaVT T * *39文法的类型文法的类型例：例：1 1型（上下文有关）文法型（上下文有关）文法 文法文法GSGS： SCDSCDAbbAAbbA CaCA CaCABaaBBaaB CbCB CbCBBbbBBbbBADaDADaD Ca CaBDbDBDbD Db DbAabDAabD40文法的类型文法的类型例：例：2 2型（上下文无关）文法型（上下文无关）文法 文法文法GS： SABABABS|0BS|0BSA|1SA|1413 3型文法型文法GS： S0A|1B|00A|1B|0A0

29、A|1B|0S0A|1B|0SB1B|1|01B|1|0GI：I lT lTI l lT lT lTT dT dTT l lT d d42文法的类型文法的类型2型文法型文法1型文法型文法0型文法型文法四类四类文法文法之间之间的的逐级逐级“包含包含”关系关系3型文法型文法43文法和语言文法和语言0型文法产生的语言称为型文法产生的语言称为0型语言型语言1 1型文法或上下文有关文法（型文法或上下文有关文法（ CSG ）产生的语言产生的语言称为称为1 1型语言型语言或上下文有关或上下文有关语言（语言（CSL）2 2型文法或上下文无关文法（型文法或上下文无关文法（ CFG ）产生的语言产生的语言称为称为

30、2型语言型语言或上下文无关或上下文无关语言（语言（ CF L ） 3 3型文法或正则（正规）文法（型文法或正则（正规）文法（ RG ）产生的语言产生的语言称为称为3型语言型语言正则（正规）正则（正规）语言（语言（ RL ） 44文法和语言文法和语言 四种文法之间的关系四种文法之间的关系 是将产生式做进一步是将产生式做进一步限制而定义的。限制而定义的。 语言之间的关系依次：有不是上下文有关语言之间的关系依次：有不是上下文有关语言的语言的0型语言，有不是上下文无关语言的型语言，有不是上下文无关语言的1型语言，有不是正则语言的上下文无关语型语言，有不是正则语言的上下文无关语言。言。45根据形式语言理

31、论根据形式语言理论, ,文法和识别系文法和识别系统间有这样的关系统间有这样的关系 0型文法（短语结构文法）的能力相当于图型文法（短语结构文法）的能力相当于图灵机，可以表征任何递归可枚举集，而且灵机，可以表征任何递归可枚举集，而且任何任何0型语言都是递归可枚举的型语言都是递归可枚举的 1型文法（上下文有关文法）：产生式的形型文法（上下文有关文法）：产生式的形式为式为1 1AA2 21 12 2，即只有，即只有A A出现在出现在1 1和和2 2的上下文中时，才允许的上下文中时，才允许取代取代A A。其。其识别系统是线性界限自动机。识别系统是线性界限自动机。46 带带 a0 a1 a2 a3 a4

32、a5 a6 a7 a8 an-1 an 有限控制器有限控制器磁头磁头任何能用图灵机描述的计算都能机械实现，任何能在现任何能用图灵机描述的计算都能机械实现，任何能在现代计算机上实现的计算都能用图灵机描述代计算机上实现的计算都能用图灵机描述47 2型文法（上下文无关文法型文法（上下文无关文法CFG）：产生式）：产生式的形式为的形式为AA，取代取代A A时与时与A A的上下文无的上下文无关。其识别系统是不确定的下推自动机。关。其识别系统是不确定的下推自动机。 3型文法（正规文法型文法（正规文法RG）：产生的语言是）：产生的语言是有穷自动机（有穷自动机（FA）所接受的集合）所接受的集合48 3 3型文

33、法产生的语言是有穷自动机（型文法产生的语言是有穷自动机（FAFA）所接）所接受的集合受的集合. .定理定理 设设G=（VN，VT，P，S）是3 3型文法，则存在一个有穷自型文法，则存在一个有穷自 动机动机 M=(K, , f, A, Z)M=(K, , f, A, Z)，使得，使得L(M)=L(G)L(M)=L(G)有穷自动机有穷自动机NFA M NFA M 这样构造：这样构造： = = VT K= K= VN N, NN, N为一个新状态为一个新状态, ,它不在它不在VN中 A=S A=S Z=N Z=N 对对G G中的形如中的形如 DtBDtB的产生式的产生式,t,t为终结符或为终结符或,

34、有有f(D,t)=Bf(D,t)=B； 对对G G中形如中形如DtDt的产生式，的产生式， t t为终结符或为终结符或,有有f(D,t)=N;f(D,t)=N; 对对VT中的每一个a ,有有f(N,a)=f(N,a)=493 3型文法型文法 和 有穷自动机（有穷自动机（FAFA）G： SaA|bB AbB|aD|a BaA|bD|b DaD|bD|a|bBASaaabbba,bDZabab503 3型文法型文法 和 有穷自动机（有穷自动机（FAFA）定理定理 已知一有穷自动机M= (K, , f, A, Z),存在有一个3型文法G = （VN，VT，P，S）,使得L(G)=L(M)G 的定义：

35、 VT = VN= K S = A 若 f(D,t)=B ，则DtB在P中 若 f(D,t)=B ，且B在Z中，则Dt在P中513 3型文法型文法 和 有穷自动机（有穷自动机（FAFA）G： SaA|bB AbB|aD|a BaA|bD|b DaD|bD|a|bDBASaaabba,bb52正规文法和正规式 对上的正规式r ,存在一个RG=(VN,VT,P,S)：L(G)=L(r) 初始， VT= ,S VN ，生成正规产生式 Sr (R.1) 对形如 Ar1r2的正规产生式：Ar1B Br2 BVN (R.2)对形如Arr1的正规产生式： ArB Ar1 BrB Br1 BVN (R.3)对

36、形如Ar1r2的正规产生式:Ar1 A r2 不断应用(R.x)做变换，直到每个产生式右端至多有一个VN53例 r=a(ad)(1) Sa(ad)(2) SaA A(ad) z A(ad)B Az B(ad)Bz B Gs: SaA A VT=a,d AaBVN=S,A,B AdB BaB BdB B54正规文法和正规式 对G=(VN,VT,P,S),存在一个 =VT上的正规式r : L(r)=L(G) AxB, By 形成正规式 A=xy AxAy 形成正规式 A=xy Axy 形成正规式 A=xy55正规文法和正规式Gs:SaA|a AaAadAd A(ad)A(ad) A(ad)(ad)

37、 S=a(ad)(ad)a=a(ad)(ad)=a(ad) R=a(ad)563.5 上下文无关文法及其语法树上下文无关文法及其语法树上下文无关文法有足够的能力描述程序设计语言的上下文无关文法有足够的能力描述程序设计语言的语法结构语法结构语法树语法树-句型推导句型推导的的直观表示直观表示57语法树语法树-句型推导句型推导的的直观表示直观表示 ( (句型、推导)GE E： EE+T|TEE+T|T TT TT* *F|FF|F F(E)|a F(E)|aE EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a E EE+T E+T*F E+T*a E+F*a E+a*

38、a T+a*a F+a*a a+a*aE EE+T T+T T+T*F F+T*F F+F*F a+F*F a+F*a a+a*a58语法树语法树设G=( VN,VT,P,S)为一cfg，若一棵树满足下列4个条件，则此树称作G的语法树(推导树)(派生树）：1. 每个结点都有一个标记，此标记是V的一个符号2. 根的标记是S3. 若一结点n至少有一个它自己除外的子孙，并且有标记A，则肯定AVN4. 如果结点n有标记A,其直接子孙结点从左到右的次序是n1，n2，nk，其标记分别为A1，A2，Ak，那么AA1A2，Ak一定是P中的一个产生式语法树的结果：语法树的结果：从左到右读出叶子的标记而构成的行谓

39、之 59上下文无关文法的语法树上下文无关文法的语法树z句型句型aabbaa的可能的可能推导序列和语法树推导序列和语法树 例例: GS:SaASASbAASSSaAba S a A S S b A a a b aSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa60语法树语法树-句型推导句型推导的的直观表示直观表示给定文法给定文法G=(VN,VT,P,S)，对于，对于G的任何句型都能的任何句型都能构造与之关联的语法树构造与之关联的语法树(推导树推导树)定理：定理： G为上下文无关文法，对于，有S

40、=* ，当且仅当文法G有以为结果的一棵语法树(推导树)61规范推导规范推导 规范句型规范句型z最左（最右）推导：在推导的任何一步最左（最右）推导：在推导的任何一步，其中，其中、是句型，都是对是句型，都是对中中的最左（右）非终结符进行替换的最左（右）非终结符进行替换z最右推导被称为规范推导。最右推导被称为规范推导。z由规范推导所得的句型称为规范句型由规范推导所得的句型称为规范句型62z一棵语法树表示了一个句型的种种可能的一棵语法树表示了一个句型的种种可能的( (但未必是所有的但未必是所有的) )不同推导过程，包括最不同推导过程，包括最左左( (最右最右) )推导。推导。z但是，一个句型是否只对应

41、唯一的一棵语但是，一个句型是否只对应唯一的一棵语法树呢法树呢? ?一个句型是否只有唯一的一个最左一个句型是否只有唯一的一个最左( (最右最右) )推导呢推导呢? ?63例：例：GE:GE:E iE iE E+EE E+EE EE E* *E EE (E)E (E) E E E + E E + E E E * * E i E i i i i i E E E E * * E E i E + E i E + E i i i i句型句型 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+

42、E i*i+E i*i+i64二义文法二义文法z若一个文法存在某个句子对应两棵不同的若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是语法树，则称这个文法是二义二义的的z若一个文法存在某个句子有两个不同的最若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是左（右）推导，则称这个文法是二义二义的的z判定任给的一个上下文无关文法是否二义，判定任给的一个上下文无关文法是否二义，或它是否产生一个先天二义的上下文无关或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不可解的，但可语言，这两个问题是递归不可解的，但可以为无二义性寻找一组充分条件以为无二义性寻找一组充分条件 6

43、5文法的二义性和语言的二义性文法的二义性和语言的二义性文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同的文法的文法G G和和GG，其中，其中G G是二义的，但是却有是二义的，但是却有L(G)=L(G)L(G)=L(G)，也就是说，也就是说，这两个文法所产生的语言是相同的。这两个文法所产生的语言是相同的。二义文法改造为无二义文法二义文法改造为无二义文法GE:E i GEGE:E i GE： E T|E+TE T|E+T E E+E T F|T E E+E T F|T* *F F E E E E* *E F E F （E

44、E）|i|i E (E) E (E) 规定算符优先性和结合性规定算符优先性和结合性 如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的。对于一个程序设计语言来说，常常希望它的文法是无二义天二义的。对于一个程序设计语言来说，常常希望它的文法是无二义的，因为希望对它的每个语句的分析是唯一的。的，因为希望对它的每个语句的分析是唯一的。663.6 3.6 句型的分析（句型的分析（上下文无关文法）上下文无关文法）z句型分析句型分析就是就是识别识别一个符号串是否为某文法一个符号串是否为某文法的的句型句型，是某个，是某个推导推导的

45、构造过程。的构造过程。z在语言的编译实现中，把在语言的编译实现中，把完成句型分析完成句型分析的的程程序序称为称为分析程序分析程序或或识别程序识别程序。分析算法又称。分析算法又称识别算法识别算法。z从左到右的分析算法从左到右的分析算法，即，即总是从总是从左左到到右右地地识识别输入符号串别输入符号串，首先识别符号串中的，首先识别符号串中的最左最左符符号，进而号，进而依次识别右边依次识别右边的一个符号，的一个符号，直到分直到分析结束析结束。67句型的句型的分析算法分类分析算法分类分析算法可分为：分析算法可分为：z自上而下分析法自上而下分析法：从文法的开始符号出发从文法的开始符号出发，反复使用文法的，

46、反复使用文法的产生式，产生式，寻找寻找与与输入符号串输入符号串匹配匹配的的推导，推导，或者说，为输入串寻找一个最左推导。或者说，为输入串寻找一个最左推导。z自下而上分析法自下而上分析法：从从输入符号串输入符号串开始开始，逐步进行逐步进行归约归约，直至，直至归约归约到到文法的文法的开始符号开始符号。 68两种方法反映了两种语法树的构造过程。两种方法反映了两种语法树的构造过程。y自上而下方法自上而下方法是从文法符号开始，将它做为语法树的根，向下逐步建立语法树，使语法树的结果正好是输入符号串y自下而上方法自下而上方法则是从输入符号串开始，以它做为语法树的结果，自底向上的构造语法树691 1、自上而下

47、的语法分析、自上而下的语法分析例：文法例：文法G： S cAd A ab A a识别输入串识别输入串w=cabd是否为该文法的是否为该文法的句子句子SSScAdcAd a b推导过程：推导过程：S cAd cAd cabd702 2、自下而上的语法分析、自下而上的语法分析例：文法例：文法G： S cAd A ab A a识别输入串识别输入串w=cabd是否该文法的是否该文法的句子句子SAA c a b d c a b d c a b d 规约规约过程构造的推导：过程构造的推导： cAd cabd S cAd71自上而下的语法分析自上而下的语法分析(1)S cAd (2) A ab (3) A

48、a 识别输入串识别输入串w=cad是否为该文法的是否为该文法的句子句子若S cAd 后选择(2)扩展A，S cAd cabd那将会？ w的第二个符号可以与叶子结点a得以匹配，但第三个符号却不能与下一叶子结点d匹配？宣告分析失败（其意味着，识别程序不能为串cad构造语法树，即cad不是句子）-显然是错误的结论。导致失败的原因是在分析中对A的选择不是正确的。 S c A d a b 这时应该回溯回溯，把A为根的子树剪掉，扫描过的输入串中的a吐出来,再试探用产生式（3）72(1)S cAd (2) A ab (3)A a识别输入串识别输入串w=cabd是否为该文法的是否为该文法的句子句子自下而上的语

49、法分析自下而上的语法分析对串cabd的分析中，如果不是选择ab用产生式(2),而是选择a用产生式(3)将a归约到了A，那么在c A b d中无法找到一个可归约串了，最终就达不到归约到S的结果，因而也无从知道cabd是一个句子c a b d c A b d a733、句型分析的有关问题、句型分析的有关问题1）在自上而下的分析方法中）在自上而下的分析方法中如何如何选择选择使用使用哪个哪个产生式进产生式进行推导行推导？假定要被代换的最左非终结符号是假定要被代换的最左非终结符号是B，且有，且有n条规则：条规则：BA1|A2|An，那么如何确定用哪个右部去替代，那么如何确定用哪个右部去替代B？2）在自下而上的分析方法中）在自下而上的分析方法中如何如何识别可归约的串识别可归约的串？在分析程序工作的每一步，都是从当前串中在分析程序工作的每一步，都是从当前串中选择一个选择一个子子串串，将它，将它归约归约到到某个非终结符号某个非终结符号，该子串称为，该子串称为“可归约可归约串串”743、句型分析的有关问题、句型分析的有关问题z若若G是一文法，是一文法，S是文法的开始符号，是文法的开