第三章 文法和语言

1、盛威网：专业的计算机学习网站1指导教师指导教师:杨建国杨建国二零零七年十一月二零零七年十一月盛威网：专业的计算机学习网站2第三章文法和语言v第一节第一节 文法的直观概念文法的直观概念v第二节第二节 符号和符号串符号和符号串v第三节第三节 文法和语言的形式定义文法和语言的形式定义v第四节第四节 文法的类型文法的类型v第五节第五节 上下文无关文法及其语法树上下文无关文法及其语法树v第六节第六节 句型分析句型分析v第八节第八节 典型例题及解答典型例题及解答v第七节第七节 有关文法实用中的一些说明有关文法实用中的一些说明盛威网：专业的计算机学习网站3知识结构知识结构盛威网：专业的计算机学习网站43.1

2、 文法的直观概念 第三章 文法和语言v所谓一个语言的所谓一个语言的语法语法是指一组是指一组规则规则，用它可，用它可以形成和产生一个合适的程序以形成和产生一个合适的程序v目前广泛使用的手段是目前广泛使用的手段是上下文无关文法上下文无关文法，即，即用上下文无关文法作为程序设计语言语法的描用上下文无关文法作为程序设计语言语法的描述工具述工具盛威网：专业的计算机学习网站5v程序设计语言的描述：程序设计语言的描述：语法：语法：语义：语义：语用：语用：程序的程序的结构或形式结构或形式语言所代表的语言所代表的含义含义语言的实际语言的实际应用应用盛威网：专业的计算机学习网站6例如，对于赋值语句例如，对于赋值语

3、句x : = a + b x : = a + b * * c c的非形式描的非形式描述是：述是：语法：赋值语句语法：赋值语句变量变量:=:=表达式表达式语义：先求右部，然后把结果给左部变量语义：先求右部，然后把结果给左部变量语用：赋值语句可用来计算和保存表达式的值语用：赋值语句可用来计算和保存表达式的值形式化方法：用一整套带有严格规定的符号体系形式化方法：用一整套带有严格规定的符号体系来描述问题的理论和方法来描述问题的理论和方法形式语言：一种不考虑含义的符号语言形式语言：一种不考虑含义的符号语言盛威网：专业的计算机学习网站7v程序设计语言的语义分成：程序设计语言的语义分成：静态语义静态语义：是

4、一系列：是一系列限定规则限定规则，并确定哪些合乎，并确定哪些合乎语法的程序是合适的语法的程序是合适的动态语义动态语义（运行语义、执行语义）：表明程序要（运行语义、执行语义）：表明程序要做什么做什么，要计算什么，要计算什么盛威网：专业的计算机学习网站8v以自然语言为例，人们无法列出全部句子，以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说但是人们可以给出一些规则，用这些规则来说明（或者定义）句子的组成结构：明（或者定义）句子的组成结构：盛威网：专业的计算机学习网站9v例如例如, , 有一组规则有一组规则: : : = : = : = : = : = the : =

5、the : = a : = a : = big : = big : = : = : = ate : = ate : = : = : = cat : = cat : = mouse : = mouse 显然显然, , 由这一组规则可以产生句子由这一组规则可以产生句子: :The big cat / mouse ate a mouse / cat The big cat / mouse ate a mouse / cat 盛威网：专业的计算机学习网站10v 这样的语言描述称为文法这样的语言描述称为文法v 使用文法作为工具，不仅为了严格地定义句使用文法作为工具，不仅为了严格地定义句子的结构，也是为了

6、用适当条数的规则把语子的结构，也是为了用适当条数的规则把语言的全部句子描述出来，可以说言的全部句子描述出来，可以说文法文法是是以有以有穷的集合刻画无穷的集合的一个穷的集合刻画无穷的集合的一个工具工具。盛威网：专业的计算机学习网站113.2 符号和符号串一一. .字母表和符号串字母表和符号串1.1.语言语言可以看成在一个基本符号集上定义的，按一定规可以看成在一个基本符号集上定义的，按一定规则构成的一切基本符号串组成的则构成的一切基本符号串组成的集合集合2.2.字母表字母表（符号集）：是一个（符号集）：是一个非空非空有穷集合有穷集合3.3.符号符号（字符）：字母表中的元素（字符）：字母表中的元素4

7、.4.符号串符号串：符号的有穷：符号的有穷序列序列。注意：。注意： 表示空符号串！表示空符号串！5.5.符号串集合符号串集合：字母表：字母表 上若干个符号串组成的集合上若干个符号串组成的集合盛威网：专业的计算机学习网站12v 重要约定：重要约定： 小写字母小写字母 a, b, c, a, b, c, , r , r 表示符号表示符号 小写字母小写字母 s, t, u, s, t, u, , z , z 表示符号串表示符号串 大写字母大写字母 A, B, C, A, B, C, , Z , Z 表示符号串集合表示符号串集合盛威网：专业的计算机学习网站13二二. .符号串的运算符号串的运算1.1.

8、符号串相等符号串相等 设设x x、y y是字母表是字母表 上的两个符号串，若上的两个符号串，若x x与与y y的诸符号依次相等，则该两符号串相等，记为的诸符号依次相等，则该两符号串相等，记为x=yx=y。盛威网：专业的计算机学习网站142.2.符号串长度符号串长度 设设x x是字母表是字母表 上的符号串，符号串中包含符号上的符号串，符号串中包含符号的个数称为符号串的个数称为符号串x x的长度，用的长度，用 x x 表示表示例例: :（1 1） | | |= 0 ; |= 0 ; （2 2） |ax|=|xa|=|x| + 1(a)|ax|=|xa|=|x| + 1(a)【注】【注】对于字母表A

9、=begin,if,real,end【1】符号串beginif的长度是多少？ 2【2】 begini或eginif是不是A上的符号串盛威网：专业的计算机学习网站153.3.符号串的连结符号串的连结 设设x x与与y y是字母表是字母表 上的两个符号串，把上的两个符号串，把y y的所的所 有符号相继写在有符号相继写在x x的符号之后所得到的符号串称为的符号之后所得到的符号串称为 x x与与y y的连结，用的连结，用xyxy表示表示注意注意: : |xy|=|x|+|y| |xy|=|x|+|y| x = xx = x = x = x xy yx ( xy yx ( 一般说来一般说来 ) )盛威网

10、：专业的计算机学习网站164.4.符号串的逆符号串的逆X(1)(1)若若x=abcd,x=abcd,则则 = dcba = dcba (2) = (2) = X 设设x x是字母表是字母表 上的符号串，其逆为符号串上的符号串，其逆为符号串x x的的倒置，记为倒置，记为 。盛威网：专业的计算机学习网站175.5.符号串的前缀、后缀和子串符号串的前缀、后缀和子串 设设x x、y y、z z是字母表是字母表 上的符号串，则称上的符号串，则称x x为为符号串符号串xyxy的前缀，的前缀，y y是符号串是符号串xyxy的后缀，的后缀，x x、y y、z z、xyxy、yz yz 是符号串是符号串xyzx

11、yz的子串的子串例例: : 字母表字母表A=a,b,cA=a,b,c上的符号串上的符号串x=abcx=abc，则，则x x的的 前缀前缀有有 ,a,ab,abc,a,ab,abc；后缀后缀有有 ,c,bc,abc,c,bc,abc；真真 前缀前缀有有 ,a,ab,a,ab；真后缀真后缀有有 ,c,bc,c,bc。盛威网：专业的计算机学习网站186.6.符号串集合的乘积符号串集合的乘积设设A A、B B为两个符号串集合，其乘积为为两个符号串集合，其乘积为AB=xy|xAB=xy|x A,yA,y BB例例: (1): (1)若若A = ab, cd ,B = ef, gh A = ab, cd

12、,B = ef, gh 则则AB = abef, abgh, cdef, cdgh AB = abef, abgh, cdef, cdgh (2) (2) x = x x = x = x = x A = A A = A = A = A盛威网：专业的计算机学习网站197.7.空集空集 不含任何元素的集合，记为不含任何元素的集合，记为 注意注意: (1) : (1) A = A A = A = = ; ; (2) (2) 盛威网：专业的计算机学习网站208.8.符号串的幂符号串的幂 设设x x是字母表是字母表 上的符号串，则上的符号串，则x x的幂运算的幂运算为为x x0 0= = x x1 1=

13、x x=x x2 2=xx =xx x xn n=x=xn-1n-1x(xxx(xxn-1n-1) )例例: :若若x=ab,x=ab,则则x x0 0= = ,x,x1 1=ab,x=ab,x2 2=abab,=abab, , x xn n=abab=abababab盛威网：专业的计算机学习网站219.9.符号串集合的幂符号串集合的幂 设设A A是符号串集合，则符号串是符号串集合，则符号串A A的幂运算为：的幂运算为： A A0 0= A A1 1=A A=A A2 2=AA =AA A An n=A=An-1n-1A (AAA (AAn-1n-1) ) 例例: :若若A=ab,cd A=a

14、b,cd 则则:A:A0 0 = ,A,A1 1=ab,cd, =ab,cd, A A2 2=abab,abcd,cdab,cdcd,=abab,abcd,cdab,cdcd,盛威网：专业的计算机学习网站22注意注意: :A A* *=A=A0 0AA+ + A A+ +=AA=AA* *= =A A* *A A 若若A=a,b A=a,b 则则:A:A* *= ,a,b,aa,ab,ba,bb,aaa,a,b,aa,ab,ba,bb,aaa, A A+ +=a,b,aa,ab,ba,bb,aaa,=a,b,aa,ab,ba,bb,aaa, 10.10.集合集合A A的闭包与正闭包的闭包与正闭

15、包正闭包表示为正闭包表示为 A+ ，集合集合A A的闭包表示为的闭包表示为 A* ， A UA UA UA A K1K32 1U A UA UA UUA A A K0K32 10*U盛威网：专业的计算机学习网站233.3 文法和语言的形式定义一一. .如何来描述一种语言如何来描述一种语言 如果语言是如果语言是有穷有穷的（只含有的（只含有有穷有穷多个句子），可以多个句子），可以将句子逐一列出来表示将句子逐一列出来表示 如果语言是如果语言是无穷无穷的，找出语言的有穷表示。语言的的，找出语言的有穷表示。语言的有穷表示有两个途经：有穷表示有两个途经： 生成方式生成方式 （文法）：（文法）：语言中的每个

16、句子可以用严语言中的每个句子可以用严格定义的规则来构造。格定义的规则来构造。 识别方式（自动机）：识别方式（自动机）：用一个过程，当输入的一任用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止意串属于语言时，该过程经有限次计算后就会停止并回答并回答“是是”，若不属于，要么能停止并回答，若不属于，要么能停止并回答“不不是是”，（要么永远继续下去），（要么永远继续下去） 盛威网：专业的计算机学习网站24二二. .相关概念相关概念1.1.规则规则（重写规则、产生式、生成式）（重写规则、产生式、生成式） 一个规则是一个二元组一个规则是一个二元组, ,通常写作通常写作:=:= 或或称为

17、规则的称为规则的左部左部，是字母表是字母表V V的正闭包的正闭包V+中的一个中的一个符号；符号；称为规则的称为规则的右部右部，是是V V*中的一个符号；中的一个符号；(:=)(:=)读作读作“定义为定义为”，这是一条关于，这是一条关于的规则（产的规则（产生式）生式）盛威网：专业的计算机学习网站252.2.文法文法定义定义3.13.1：文法文法G G定义为四元组（定义为四元组（V VN N，V VT T，P P，S S）V VN N ：非终结符（语法实体、变量）集非终结符（语法实体、变量）集V VT T ：终结符集终结符集P P：产生式产生式（ ）集合，）集合，(V(VN NV VT T) )*

18、 *且至少且至少包含一个非终结符，包含一个非终结符，(V(VN NV VT T) )* *V VN N、V VT T、P P是非空有穷集是非空有穷集出现在规则的左部、用出现在规则的左部、用括起来、表示一定语括起来、表示一定语法概念的词。法概念的词。 语言中不可再分割的字语言中不可再分割的字符串符串( (包括单个字符组成包括单个字符组成的串的串) )。注：终结符是组。注：终结符是组成句子的基本单位。成句子的基本单位。 用来定义符号串之间关系用来定义符号串之间关系的一组的一组( (语法语法) )规则规则 盛威网：专业的计算机学习网站26S S：开始符开始符（识别符），它是一个非终结符，至（识别符）

19、，它是一个非终结符，至少要在一条规则中作为左部出现少要在一条规则中作为左部出现V VN NVVT T= = V=VV=VN NVVT T，称为文法，称为文法G G的字母表（字汇表）的字母表（字汇表）盛威网：专业的计算机学习网站27v例例3.13.1 文法文法G=G=（V VN N，V VT T，P P，S S），其中），其中V VN N = S = S ，V VT T = 0, 1 = 0, 1 ，P = SP = S0S1, S0S1, S 01 01 盛威网：专业的计算机学习网站28v例例3.23.2文法文法G=G=（V VN N，V VT T，P P，S S），其中），其中V VN N

20、= =标识符，字母，数字标识符，字母，数字 V VT T =a,b,c,x,y,z,0,1,9 =a,b,c,x,y,z,0,1,9P P a a z z 0 0 9 9 S=S= 盛威网：专业的计算机学习网站29v很多时候，不用将文法很多时候，不用将文法G G的四元组显的四元组显式地表示出来，而只将产生式写出式地表示出来，而只将产生式写出盛威网：专业的计算机学习网站30v一般约定：一般约定：第一条产生式的左部是识别符第一条产生式的左部是识别符用尖括号括起来的是非终结符（或者用大写字母用尖括号括起来的是非终结符（或者用大写字母表示）表示）不用尖括号括起来的是终结符（或者用小写字母不用尖括号括起

21、来的是终结符（或者用小写字母表示）表示）将将G G也写成也写成GSGS，其中，其中S S是识别符是识别符盛威网：专业的计算机学习网站31v推导：推导：定义定义V V* *中的符号之间的关系：中的符号之间的关系：直接推导：直接推导：长度为长度为n(n1)n(n1)的推导：的推导：长度为长度为n(n0)n(n0)的推导：的推导：*+盛威网：专业的计算机学习网站32v定义定义3.23.2：文法文法G G（V VN N，V VT T，P P，S S），）， 是是一条规则，一条规则，和和是是V V* *中的任意符号，若有符号串中的任意符号，若有符号串v v、w w满足：满足：v=v=，w= w= ，则称

22、则称v v直接推导到直接推导到w w，v v w w，或或w w直接归约到直接归约到v vv例：例：G G： S S0S10S1， S S0101 S S0S1 0S1 00S1100S11 000S111 000S111 0000111100001111盛威网：专业的计算机学习网站33v定义定义3.33.3：如果存在直接推导的序列：如果存在直接推导的序列：v=wv=w0 0w w1 1w w2 2w wn n=w (n0)=w (n0)则称则称v v推导出推导出w w（推导长度为（推导长度为n n），或称），或称w w归约到归约到v v，记作记作+盛威网：专业的计算机学习网站34v定义定义3

23、.53.5：若有若有S Sx x，则称，则称x x是文法是文法GSGS的的句句型型，若，若x x仅由终结符组成，则称仅由终结符组成，则称x x为为GSGS的的句子句子*v定义定义3.43.4：若有若有v vw w，或，或v=wv=w，则记作：，则记作：v wv w+*盛威网：专业的计算机学习网站35v定义定义3.63.6：文法文法G G所产生的语言定义为集合所产生的语言定义为集合L(G)=L(G)=x|Sx|Sx x，其中，其中S S为文法识别符号，且为文法识别符号，且xVxVT T* *v文法描述的语言是该文法一切句子的集合文法描述的语言是该文法一切句子的集合v例：例：G G：S S0S10

24、S1， S S0101L(G)=0L(G)=0n n1 1n n|n1|n1*盛威网：专业的计算机学习网站36例例3.33.3文法文法文法文法GSGS：（1 1）S SaSBEaSBE（2 2）S SaBEaBE（3 3）EBEBBEBE（4 4）aBaBabab（5 5）bBbBbbbb（6 6）bEbEbebe（7 7）eEeEeeeeL L（G G）= a= an nb bn ne en n | n1 | n1 思考：思考：a a4 4b b4 4e e4 4怎么推导？怎么推导？盛威网：专业的计算机学习网站37v定义定义3.73.7：若若L(GL(G1 1) )L(GL(G2 2) )，

25、则称文法，则称文法G G1 1和和G G2 2是等是等价的价的v例如文法例如文法GAGA：A A0R0RA A0101R RA1A1和文法和文法GSGS：S S0S10S1S S0101等价等价L(G)=0L(G)=0n n1 1n n|n1|n1盛威网：专业的计算机学习网站383.4 文法的类型v乔姆斯基乔姆斯基(Chomsky)(Chomsky)于于19561956年建立形式语言的描述年建立形式语言的描述v他把文法分成：他把文法分成：0 0型、型、1 1型、型、2 2型、型、3 3型型v设设G G（V VN N，V VT T，P P，S S），如果它的），如果它的每个每个产生式产生式 是这

26、样一种结构：是这样一种结构：(V(VN NVVT T) )* *且且至少包含一个至少包含一个非终结符，非终结符， (V(VN NVVT T) )* *，则，则G G是是一个一个0 0型文法型文法（短语结构文法、无限制文法短语结构文法、无限制文法），），简称简称PSGPSG。盛威网：专业的计算机学习网站39 设设G G（V VN N，V VT T，P P，S S），如果它的），如果它的每个每个产产生式生式 是这样一种结构：是这样一种结构：(V(VN NVVT T) )+ +，(V(VN NVVT T) )* *，则，则G G是一个是一个0 0型文法型文法v思考：这样定义可以吗？思考：这样定义可以

27、吗？盛威网：专业的计算机学习网站40v设设G G（V VN N，V VT T，P P，S S），如果它的），如果它的每个每个产生式产生式均满足：均满足：| | | | |，仅仅，仅仅S S 除外，则文法除外，则文法G G是是1 1型文法型文法（上下文有关文法，上下文有关文法，上下文敏感文法上下文敏感文法），简称），简称CSGCSG。例例3.13.1、3.23.2、3.33.3盛威网：专业的计算机学习网站41例：例：文法文法GSGS： S SCDCDAbAbbAbA C CaCAaCABaBaaBaB C CbCBbCBBbBbbBbB AD ADaDaDC C BD BDbDbDD D Aa

28、AabDbDL(G)=w|wa,bL(G)=w|wa,b* * 盛威网：专业的计算机学习网站42v有些定义中，将上下文有关文法的产生式的形有些定义中，将上下文有关文法的产生式的形式描述为式描述为1 1AA2 21 12 2，其中，其中1 1、2 2和和都在都在V V* *中，中，A A在在V VN N中中盛威网：专业的计算机学习网站43v设设G G（V VN N，V VT T，P P，S S），如果它的），如果它的每个每个产生式产生式 均满足：均满足：是是一个一个非终结符，非终结符，V V* *， 则文法则文法G G是是2 2型文法型文法（上下文无关文法上下文无关文法），简称），简称CFGCF

29、G。盛威网：专业的计算机学习网站44v有时将有时将2 2型文法的产生式表示为型文法的产生式表示为A A的形式，的形式，其中其中AAV VN N，也就是用，也就是用取代非终结符取代非终结符A A时，与时，与A A所在的上下文无关，因此取名为所在的上下文无关，因此取名为上下文无关上下文无关。例例3.13.1、3.23.2盛威网：专业的计算机学习网站45例例3.43.4：文法：文法GSGS：S SaB|bAaB|bA A Aa|aS|bAAa|aS|bAA B Bb|bS|aBBb|bS|aBB盛威网：专业的计算机学习网站46v设设G G（V VN N，V VT T，P P，S S），如果它的），如

30、果它的每个每个产生产生式式A A B B或或A A （A A B B或或A A ），其中，其中A A和和B B都是非终结符，都是非终结符，V VT T* *，则文法，则文法G G是是3 3型文型文法法（正规文法，正则文法，有穷状态文法正规文法，正则文法，有穷状态文法），简），简称称RGRG。 例例3.5-13.5-1：文法：文法GSGS：S S0A|1B|00A|1B|0 A A0A|1B|0S0A|1B|0S B B1B|1|01B|1|0若文法中所有的产生式均为若文法中所有的产生式均为A A BB或或A A 形式，则此文法为右线性的形式，则此文法为右线性的若文法中所有的产生式均为若文法中所

31、有的产生式均为A A BB或或A A 形式，则此文法为左线性的形式，则此文法为左线性的盛威网：专业的计算机学习网站47例例3.5-23.5-2：文法：文法GSGS：S S0A|1B|00A|1B|0 A AA0|B1|0SA0|B1|0S B BB1|1|0B1|1|0第一，左边有非终结符，所以此文法是第一，左边有非终结符，所以此文法是0 0型文法型文法；第二，左边符号串长度不大于右边，所以此文法是第二，左边符号串长度不大于右边，所以此文法是1 1型文法型文法；第三，左边只有一个非终结符，所以此文法是第三，左边只有一个非终结符，所以此文法是2 2型文法型文法；第四，由于文法中既有左线性文法又有

32、右线性文法，所以此第四，由于文法中既有左线性文法又有右线性文法，所以此文法文法不是不是3 3型文法型文法；综上所述，此文法是综上所述，此文法是2 2型文法。型文法。盛威网：专业的计算机学习网站48v四个文法类的定义是四个文法类的定义是逐渐增加限制逐渐增加限制的的0 0型型1 1型型2 2型型3 3型型 因此，每一种正规文法（因此，每一种正规文法（3 3型）都是上下文无关型）都是上下文无关的，每一种上下文无关文法（的，每一种上下文无关文法（2 2型）都是上下文有关型）都是上下文有关的，而每一种上下文有关文法（的，而每一种上下文有关文法（1 1型）都是型）都是0 0型文法。型文法。各类文法对应的语

33、言叫各类文法语言。各类文法对应的语言叫各类文法语言。盛威网：专业的计算机学习网站490 0型语言型语言-图灵机图灵机p四类语言与自动机四类语言与自动机1 1型语言型语言-线性界限自动机线性界限自动机2 2型语言型语言-下推自动机下推自动机3 3型语言型语言-有穷状态自动机有穷状态自动机盛威网：专业的计算机学习网站50 通常自然语言是通常自然语言是上下文有关上下文有关的，程序设计语的，程序设计语言也不例外。言也不例外。p四类语言与程序设计语言四类语言与程序设计语言例例1 1 语言语言wcwwcww w (a,b)(a,b)* * 表示一个句子中出现有第二表示一个句子中出现有第二个个w w时必须同

34、时出现有第一个时必须同时出现有第一个w w，如果让，如果让w w表示标识符，且表示标识符，且第一个第一个w w代表说明部分，第二个代表说明部分，第二个w w代表语句部分，则表明标代表语句部分，则表明标识符识符w w可以任意长，且标识符可以任意长，且标识符w w必须先说明后使用。这类语必须先说明后使用。这类语言是上下文有关的。言是上下文有关的。盛威网：专业的计算机学习网站51例例2 2 设有语言设有语言 a an nb bm mc cn nd dm mn,m1,n,m1,其中其中a an n与与b bm m可以表示两个可以表示两个过程中的形参表，分别有过程中的形参表，分别有n n个和个和m m个

35、参数，而个参数，而c cn n与与d dm m则分别表则分别表示调用这两个过程的实参表。示调用这两个过程的实参表。a an n与与c cn n中及中及b bm m与与d dm m中分别具有相中分别具有相同的指数，表示实参与形参的个数必须相同。这类语言也是同的指数，表示实参与形参的个数必须相同。这类语言也是上下文有关的。上下文有关的。u与与词法词法有关的规则属于有关的规则属于正则文法正则文法u与与局部语法局部语法有关的规则属于有关的规则属于上下文无关文法上下文无关文法u与与全局语法和语义全局语法和语义有关的规则属于有关的规则属于上下文有关文法上下文有关文法盛威网：专业的计算机学习网站523.5

36、上下文无关文法及其语法树【注】上下文无关文法所定义的语法范畴是完全独立【注】上下文无关文法所定义的语法范畴是完全独立于这种范畴可能出现的环境的，即是和其上下于这种范畴可能出现的环境的，即是和其上下文无关的，不同于自然语言。文无关的，不同于自然语言。一一. .上下文无关文法上下文无关文法Context-Free GrammarContext-Free Grammar （2 2型文法型文法CFGCFG）v设设G G（V VN N，V VT T，P P，S S），如果它的），如果它的每个每个产生式产生式均满足：均满足：是是一个一个非终结符，非终结符，V V* *，则文法，则文法G G是是上下文无关文

37、法上下文无关文法。1.1.定义定义盛威网：专业的计算机学习网站53u上下文无关上下文无关文法文法有足够的能力描述现今程序设计语有足够的能力描述现今程序设计语言的语法结构。言的语法结构。 算术表达式算术表达式 语句语句 赋值语句赋值语句 条件语句条件语句 读语句读语句 2.2.描述对象描述对象盛威网：专业的计算机学习网站54算术表达式文法表示算术表达式文法表示例例3.63.6 文法文法G=(E, +,G=(E, +,* *,i,(,), P, E,i,(,), P, E P:E i P:E i E E+E E E+E E E E E* *E E E (E) E (E)u赋值语句文法表示赋值语句文

38、法表示 i = Ei = Eu条件语句文法表示条件语句文法表示 ififthenthen | | ififthenthenelse else 注：注：无特殊说明，无特殊说明，“文法文法”均指上下文无关文均指上下文无关文法法盛威网：专业的计算机学习网站55一一. .语法树语法树( (推导树推导树Parse Tree)Parse Tree)1.1.定义定义 语法树是这样的一个语法结构，它的结点由符语法树是这样的一个语法结构，它的结点由符号组成。号组成。根结点根结点对应于对应于识别符号识别符号。只有。只有非终结符号非终结符号对应的结点有对应的结点有子结点子结点。并且，一个结点和它的子结。并且，一个结

39、点和它的子结点分别对应于文法中的一个规则的左部和右部。点分别对应于文法中的一个规则的左部和右部。盛威网：专业的计算机学习网站56 语法树语法树：句子结构的图示表示法，它是一种有向图，由：句子结构的图示表示法，它是一种有向图，由结点和有向边组成。结点和有向边组成。 结点结点：符号：符号 根结点根结点：识别符号识别符号 中间结点中间结点：非终结符非终结符 叶结点叶结点：终结符或非终结符终结符或非终结符 有向边有向边：表示结点间的派生关系：表示结点间的派生关系盛威网：专业的计算机学习网站572.2.引入语法树的意义引入语法树的意义 作为识别句子的辅助工具，语法树可以表示句作为识别句子的辅助工具，语法

40、树可以表示句子的结构。这一点对于其后的语义分析有非常重要子的结构。这一点对于其后的语义分析有非常重要的意义。的意义。3.3.作用作用 直观地描述上下文无关文法的句型推导过程。直观地描述上下文无关文法的句型推导过程。给定文法给定文法G=(VG=(VN N,V,VT T,P,S),P,S)，对于，对于G G的任何句型都能的任何句型都能构造与之关联的语法树。构造与之关联的语法树。盛威网：专业的计算机学习网站584.4.语法树的相关概念语法树的相关概念结点结点：每棵树的结点对应于一个符号。结点的名字就是该符号。边边：两个结点之间的连线。根结点根结点：没有边进入的结点。分支分支：某个结点向下射出的边和其

41、结点称为分支。（父子结点，兄弟结点）子树子树：语法树的某个结点和它向下射出的部分末端结点末端结点：没有向下射出的边的结点成为末端结点。在相对于句型的语法树中，末端结点可能是非终结符号。盛威网：专业的计算机学习网站594.4.语法树的特征语法树的特征u给定文法给定文法G G，G=(VG=(VN N,V,VT T,P,S),P,S)，对于，对于G G的任何句型都能构的任何句型都能构造与之关联的语法树（推导树）。这棵树具有下列造与之关联的语法树（推导树）。这棵树具有下列特征特征：1 1、根结点的标记是、根结点的标记是开始符号开始符号S S；2 2、每个结点的标记都是、每个结点的标记都是V V中的一个

42、符号；中的一个符号；3 3、若一棵子树的根结点为、若一棵子树的根结点为A A，且其所有直接子孙的标记，且其所有直接子孙的标记 从左向右的排列次序为从左向右的排列次序为A A1 1A A2 2AAR R ，那么，那么 AAAA1 1A A2 2AAR R一定是一定是P P中的一条规则；中的一条规则；盛威网：专业的计算机学习网站604 4、若一标记为、若一标记为A A的结点至少有一个除它以外的子的结点至少有一个除它以外的子孙，则孙，则AVAVN N5 5、若树的所有叶结点上的标记从左到右排列为、若树的所有叶结点上的标记从左到右排列为字符串字符串w w，则，则w w是文法是文法G G的的句型句型；若

43、；若w w中仅含中仅含终结终结符号符号，则，则w w为文法为文法G G所产生的所产生的句子句子。盛威网：专业的计算机学习网站61线性推导：线性推导：我们称用我们称用符号进行的推导为线符号进行的推导为线性推导。性推导。树型推导与线性推导的不同：树型推导与线性推导的不同：线性推导指明线性推导指明了推导的顺序，而树型推导则没有指明推导的了推导的顺序，而树型推导则没有指明推导的顺序。因此，句型一般只有一棵语法树顺序。因此，句型一般只有一棵语法树( (如果如果无二义性无二义性) )，而线性推导则可很多。，而线性推导则可很多。句型推导过程句型推导过程句型语法树的生长过程句型语法树的生长过程盛威网：专业的计

44、算机学习网站62从推导构造语法树从推导构造语法树l方法：方法：把识别符号做为根结点，对每一个把识别符号做为根结点，对每一个直接推导画一个分支，分支的名字是直接直接推导画一个分支，分支的名字是直接推导中被替换的非终结符号，直到再无分推导中被替换的非终结符号，直到再无分支可画结束。支可画结束。从从识别符号识别符号开始，开始，逐步逐步建立建立推导推导序列。序列。由由根结点根结点开始，开始，自上而下自上而下建立建立语法树语法树。盛威网：专业的计算机学习网站63 例如：推导例如：推导SBBdbaAcdcA AB B AcAcB Bd dA Accddccdd abccddabccddS S盛威网：专业的

45、计算机学习网站64从语法树构造推导自下而上自下而上地修剪子树的末端结点，直至把整棵地修剪子树的末端结点，直至把整棵树剪掉（留根），每剪一次对应一次树剪掉（留根），每剪一次对应一次归约归约。从句型开始，从句型开始，自右向左自右向左地逐步进行地逐步进行归约归约，建立推，建立推导序列。导序列。盛威网：专业的计算机学习网站65 方法：方法：从分支建立直接推导，然后从语法从分支建立直接推导，然后从语法树中剪去这个分支，直到无分支可剪。树中剪去这个分支，直到无分支可剪。 语法树表明了在推导过程中使用了哪条规语法树表明了在推导过程中使用了哪条规则和使用在哪个非终结符号上，但它并没则和使用在哪个非终结符号上，

46、但它并没有表明使用规则的顺序。有表明使用规则的顺序。 一棵语法树可能对应不止一种推导。一棵语法树可能对应不止一种推导。盛威网：专业的计算机学习网站66从语法树构造推导的过程SBBdbaAcdc(1)(2)(3)(4) S ABABababBabcBdcBd abccdcdd 对于同一个句型或句子，可以通过不同的推导序列推对于同一个句型或句子，可以通过不同的推导序列推导出来，这是因为在推导过程中所选择的非终结符的次序导出来，这是因为在推导过程中所选择的非终结符的次序不同。不同。 abccdd(1)SAB AaAb|ab BcBd|cd Accdd(2)AcBd(3)存在下面的推导可能：AB(4)

47、S例如文法例如文法GS：盛威网：专业的计算机学习网站67例例3.73.7 句型句型aabbaaaabbaa的可能的可能推导序列和语法树推导序列和语法树GS:GS:SSa aASASASASb bA AASSASSSSa aAAbaba S a A S S b A a a b aSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa盛威网：专业的计算机学习网站68二二. .规范推导与规范归约规范推导与规范归约 最左最左( (右右) )推导指对于一个推导序列中的每一直推导指对于一个推导序列中的每一直接推

48、导，被替换的总是当前符号串中的最左接推导，被替换的总是当前符号串中的最左( (右右) )非非终结符号。最右推导也称为终结符号。最右推导也称为规范推导规范推导。规范推导的逆过程，称为最左归约，也称为规范推导的逆过程，称为最左归约，也称为规范归约规范归约。用最左推导所推导出的句型称为用最左推导所推导出的句型称为最左句型最左句型用最右推导所推导出的句型称为用最右推导所推导出的句型称为最右句型最右句型，通常称为，通常称为规范句型规范句型盛威网：专业的计算机学习网站69【例】【例】 给出了下列文法给出了下列文法G G（1 1） （2 2） | | （3 3） 0|1|2|3|4|5|6|7|8|9 0|

49、1|2|3|4|5|6|7|8|9 V VT T =0,1,2,3,4,5,6,7,8,9 =0,1,2,3,4,5,6,7,8,9 V VN N= , , , 判断数据判断数据26342634是否是是否是C C语言合法的数据。语言合法的数据。【解】【解】（1 1）用最右推导，每次用产生式的规则替换最右边）用最右推导，每次用产生式的规则替换最右边的非终结符，推导过程如下：的非终结符，推导过程如下： 4 4 4 4 3434 3434 63463426342634盛威网：专业的计算机学习网站70（2 2）用最左推导，每次直接推导都替换最左边的非）用最左推导，每次直接推导都替换最左边的非终结符，推

50、导过程如下：终结符，推导过程如下： 2 2 2626 263263 26342634盛威网：专业的计算机学习网站71疑问疑问 一个句型是否只对应唯一的一棵语法树？一个句型是否只对应唯一的一棵语法树？一个句型是否只有唯一的一个最左（最右）推导？一个句型是否只有唯一的一个最左（最右）推导？不是不是课堂练习：课堂练习：GEGE：EE+E|EEE+E|E* *E|(E)|iE|(E)|i对于句子对于句子i ii i* *i i，给出两种不同的，给出两种不同的规范推导，并画出语法树。规范推导，并画出语法树。盛威网：专业的计算机学习网站72EEE+EE*iiiEEE*EE+iii这两种不同的推导对应了两种

51、不同的语法树这两种不同的推导对应了两种不同的语法树(1) E=E+E=E+E*E =E+E*i =E+i*i = ii * i(2) E= E*E = E*i = E+E*i = E+i*i = ii * i盛威网：专业的计算机学习网站73 我我没说她偷了我的钱。（可是有人这么说）没说她偷了我的钱。（可是有人这么说） 我我没没说她偷了我的钱。（我确实没这么说）说她偷了我的钱。（我确实没这么说） 我没我没说说她偷了我的钱。她偷了我的钱。( (可是我是这么暗示的）可是我是这么暗示的） 我没说我没说她她偷了我的钱。（可是有人偷了）偷了我的钱。（可是有人偷了） 我没说她我没说她偷偷了我的钱。了我的钱。

52、( (但她用这钱做了某事但她用这钱做了某事) ) 我没说她偷了我没说她偷了我我的钱。（她偷了别人的钱）的钱。（她偷了别人的钱） 我没说她偷了我的我没说她偷了我的钱钱。（她偷了别的东西）。（她偷了别的东西） 二义性盛威网：专业的计算机学习网站74三三. .二义性文法二义性文法1.1.定义定义（1 1）文法二义性）文法二义性 若一个文法存在某个句子对应两棵不同的语若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是法树，则称这个文法是二义二义的。（或者，若一个的。（或者，若一个文法存在某个句子有两个不同的最左（右）推文法存在某个句子有两个不同的最左（右）推导）。导）。（2 2）语言先天二义）

53、语言先天二义 产生某上下文无关语言的每一个文法都是二产生某上下文无关语言的每一个文法都是二义的。义的。盛威网：专业的计算机学习网站752.2.二义性文法的证明二义性文法的证明u要判定一个文法是否是二义性文法，或它是否产生一要判定一个文法是否是二义性文法，或它是否产生一个先天二义性的上下文无关语言，是个递归不可解的。个先天二义性的上下文无关语言，是个递归不可解的。即不存在一个算法，它能在有限的步骤内，确切地判即不存在一个算法，它能在有限的步骤内，确切地判断出某个给定的文法是否是一个二义性文法。断出某个给定的文法是否是一个二义性文法。u我们要证明一个文法是否是一个二义性文法，就是找我们要证明一个文

54、法是否是一个二义性文法，就是找到该文法的一个句型特例，能够画出这个句型的两棵到该文法的一个句型特例，能够画出这个句型的两棵语法树，该文法就是二义性文法。语法树，该文法就是二义性文法。盛威网：专业的计算机学习网站763.3.为什么要避免文法有二义性为什么要避免文法有二义性 二义性的文法将给编译程序的执行带来问题。当编译程序对二义性文法生成的句子结构进行语法分析时，就会产生两种甚至更多种不同的理解。语法结构上的不确定性，必将导致语义处理上的不确定性。因此，希望描述语言的文法是无二义性的。盛威网：专业的计算机学习网站774.4.解决途径解决途径可以采用两种途径来解决文法的二义性问题可以采用两种途径来

55、解决文法的二义性问题 1不改变文法中原有的规则，仅加进一些语法的非形式规定。不改变文法中原有的规则，仅加进一些语法的非形式规定。如如1 1：对于文法对于文法 GE: Ei EE+E EEGE: Ei EE+E EE* *E E(E) E E(E) 规定运算符优先顺序和结合律，即规定运算符优先顺序和结合律，即* *优先于优先于+ +，+ +、* *服从左结合。服从左结合。 如如2 2：C C语言中二义性的消除是通过约定，在符合语言中二义性的消除是通过约定，在符合if if 语句中，语句中，elseelse子句总是属于最近的尚无子句总是属于最近的尚无elseelse子句的子句的那个那个ifif语句

56、。语句。盛威网：专业的计算机学习网站78SifB thenSifB thenelseSSSifBthenelseSSifBthenS设文法设文法GSGS：Sif B then S|if B then S else S|iSif B then S|if B then S else S|i：=E=E给出符号串给出符号串if B then if B then S else Sif B then if B then S else S的语法树。的语法树。盛威网：专业的计算机学习网站79改写文法，把排除二义性的规则合并到原有文法中。改写文法，把排除二义性的规则合并到原有文法中。2EiET+TF*iFTFi

57、例例: :算术表达式的文法算术表达式的文法 E:= E+T | T T := T*F | F F := (E) | iGE：EE+E|E*E|(E)|i 盛威网：专业的计算机学习网站803.6 句型的分析u任务: 句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。对于程序设计语言来说，句型分析就是一个识别输入符号串是否为语法上正确的程序的过程。盛威网：专业的计算机学习网站81q在语言的编译实现中，把完成句型分析的程序称为在语言的编译实现中，把完成句型分析的程序称为分析程序分析程序或或识别程序识别程序。分析算法分析算法又称又称识别算法识别算法。q从左到右的分析算法从左到右的分析

58、算法，即总是从左到右地识别输入，即总是从左到右地识别输入符号串。句型分析算法采用从左到右的分析算法。符号串。句型分析算法采用从左到右的分析算法。q句型的分析算法句型的分析算法分类分类 自上而下分析法自上而下分析法 (Top-Down parsing)(Top-Down parsing) 从文法的开始符号出发，反复使用各种产生从文法的开始符号出发，反复使用各种产生式，寻找与输入符号串匹配的式，寻找与输入符号串匹配的推导推导。 自下而上分析法自下而上分析法 (Bottom-Up parsing)(Bottom-Up parsing) 从输入符号串开始，逐步进行从输入符号串开始，逐步进行归约归约，直

59、至归，直至归 约到文法的开始符号。约到文法的开始符号。 盛威网：专业的计算机学习网站82 两种方法反映了两种两种方法反映了两种语法树语法树的构造过程：的构造过程：l自上而下方法自上而下方法是从文法符号开始，将它做为语是从文法符号开始，将它做为语法树的根，向下逐步建立语法树，使语法树的法树的根，向下逐步建立语法树，使语法树的结果正好是输入符号串结果正好是输入符号串l自下而上方法自下而上方法则是从输入符号串开始，以它做则是从输入符号串开始，以它做为语法树的结果，自底向上地构造语法树为语法树的结果，自底向上地构造语法树盛威网：专业的计算机学习网站83一一. .基本思想基本思想 自上而下的分析方法就是

60、从识别符号出发，看是自上而下的分析方法就是从识别符号出发，看是否能推导出待检查的符号串，如果能推导出这个符号否能推导出待检查的符号串，如果能推导出这个符号串，则表明此符号串是该文法的句型或句子，否则就串，则表明此符号串是该文法的句型或句子，否则就不是。不是。或者说或者说，以文法的识别符号作为根结点，看是，以文法的识别符号作为根结点，看是否能构造出一棵语法树，而且此语法树所有叶子结点否能构造出一棵语法树，而且此语法树所有叶子结点从左到右所构成的符号串恰好是待检查的符号串。如从左到右所构成的符号串恰好是待检查的符号串。如果能生成这样的语法树，则表明待检查的符号串是该果能生成这样的语法树，则表明待检