第三章文法和语言

1、第三章第三章 文法和语言文法和语言学习目标学习目标: : q掌握：自上而下与自下而上的分析方法掌握：自上而下与自下而上的分析方法q理解：文法的形式定义，推导，归约，句理解：文法的形式定义，推导，归约，句型，句子，语言，上下文无关文法，规范型，句子，语言，上下文无关文法，规范句型，语法树，短语，直接短语，句柄句型，语法树，短语，直接短语，句柄q了解：文法的类型，文法使用中的限制，了解：文法的类型，文法使用中的限制，文法的二义性文法的二义性3.1语言和文法的直观概念语言和文法的直观概念3.2符号和符号串符号和符号串3.3文法和语言的形式定义文法和语言的形式定义3.4文法的类型文法的类型3.5上下文

2、无关文法及其语法树上下文无关文法及其语法树3.6句型的分析句型的分析3.7有关文法实用中的一些说明有关文法实用中的一些说明3.1 3.1 语言和文法的直观概念语言和文法的直观概念1. 程序设计语言的定义程序设计语言的定义语言是一个记号系统。语言是一个记号系统。 汉语汉语-所有符合汉语语法的句子的全体所有符合汉语语法的句子的全体 英语英语-所有符合英语语法的句子的全体所有符合英语语法的句子的全体 程序设计语言程序设计语言-所有该语言的程序的全体所有该语言的程序的全体研究程序设计语言包括：研究程序设计语言包括： 每个程序构成的规律每个程序构成的规律 每个程序的含义每个程序的含义程序设计语言包括程序

3、设计语言包括:语法和语义语法和语义q语法语法(syntax)定义定义: 是一组规则，用它可以形成和产生是一组规则，用它可以形成和产生一个合适的程序一个合适的程序描述工具描述工具:文法文法作用作用: 定义什么样的符号序列是合法的，定义什么样的符号序列是合法的，与符号的含义无关。与符号的含义无关。q语义语义(semantics)分类分类:静态语义：一系列限定规则，确定哪些静态语义：一系列限定规则，确定哪些合乎语法的程序是合适的合乎语法的程序是合适的动态语义：表明程序要做什么动态语义：表明程序要做什么描述工具描述工具: 指称语义指称语义,操作语义等操作语义等作用作用: 检查类型匹配，变量作用域等检查

4、类型匹配，变量作用域等2.2. 文法的直观概念文法的直观概念如何来描述一种语言？如何来描述一种语言？如果语言是有穷的（只含有有穷多个句子），可如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示以将句子逐一列出来表示如果语言是无穷的，要找出语言的有穷表示。如果语言是无穷的，要找出语言的有穷表示。 有两个途经：有两个途经：1. 生成方式生成方式 （文法）：语言中的每个句子可以用严（文法）：语言中的每个句子可以用严格定义的规则来构造格定义的规则来构造2. 识别方式（自动机）：用一个过程，当输入的一识别方式（自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会任意串

5、属于语言时，该过程经有限次计算后就会停止并回答停止并回答“是是”，若不属于，要么能停止并回，若不属于，要么能停止并回答答“不是不是”，要么永远继续下去。，要么永远继续下去。q文法：是语言文法：是语言语法语法的描述工具，实现用的描述工具，实现用有穷的规则把语言的无穷句子集描述出有穷的规则把语言的无穷句子集描述出来。来。例例:“我是大学生我是大学生”是汉语的一个句子是汉语的一个句子用用EBNFEBNF来表示汉语句子的构成规则：来表示汉语句子的构成规则：句子句子=主语谓语主语谓语主语主语=代词名词代词名词代词代词= = 我你他我你他名词名词= = 王明大学生工人英语王明大学生工人英语谓语谓语=动词直

6、接宾语动词直接宾语动词动词= = 是学习是学习直接宾语直接宾语=代词名词代词名词q由规则推导句子由规则推导句子方法方法: 用一条规则用一条规则=的右端符号串代的右端符号串代替替:=:=的左端的左端. .表示表示: : 用用“ = = ”表示推导表示推导, ,含义是含义是, ,使使用一条规则用一条规则, ,代替代替=左边的某个符号左边的某个符号, ,产生产生=右端的符号串右端的符号串. .例如例如: :句子句子“我是大学生我是大学生”的推导过程如下：的推导过程如下：句子句子 主语主语谓语谓语 代词代词谓语谓语 我我谓语谓语 我我动词动词直接宾语直接宾语 我是我是直接宾语直接宾语 我是我是名词名词

7、 我是大学生我是大学生q文法的作用文法的作用严格定义句子的结构，是判断句子结构严格定义句子的结构，是判断句子结构合法与否的依据合法与否的依据用有穷的规则把无穷的句子集合描述出用有穷的规则把无穷的句子集合描述出来来3.2 3.2 符号和符号串符号和符号串1.1. 字母表字母表 定义定义: :元素的元素的非空非空有穷有穷集合集合 例：例：=01 =ab,c 元素也称为符号，字母表也称符号集。元素也称为符号，字母表也称符号集。 程序语言的字母表由字母数字和若干专程序语言的字母表由字母数字和若干专用符号组成。用符号组成。2.2. 符号串符号串 定义定义: :由字母表中的符号组成的任何有穷序列由字母表中

8、的符号组成的任何有穷序列例：例： 0,00,10是是字母表字母表=01上的符号串上的符号串 a,ab,aaca是是=ab,c上的符号串上的符号串在符号串中，符号是有顺序的，顺序不同在符号串中，符号是有顺序的，顺序不同,代代表不同的符号串，如表不同的符号串，如:ab和和ba不同不同不含任何符号的符号串称为空串，用不含任何符号的符号串称为空串，用表示表示注意注意: :并不等于空集合并不等于空集合 符号串长度符号串长度: 符号串中含有符号的个数符号串中含有符号的个数如如: |abc|=3| |=0 符号串的头尾：如果符号串的头尾：如果=xy，那么，那么x是是的头，的头，y是是的尾；如果的尾；如果x是

9、非空的，那么是非空的，那么y是是的固的固有尾，如果有尾，如果y是非空的，那么是非空的，那么x是是的固有头的固有头例：例： =abc 的头包括：的头包括： ，a,ab,abc 的固有头包括：的固有头包括： ，a,ab 的尾包括：的尾包括： ，c,bc,abc 的固有尾包括：的固有尾包括： ，c,bc3. 符号串的运算符号串的运算 符号串的连接符号串的连接：设设、是符号串是符号串,它们它们的连接是把的连接是把的符号写在的符号写在 的符号之后的符号之后得到的符号串得到的符号串例如例如 =ST，=abu ，则则 =STabu 显然显然 = = 符号串的方幂符号串的方幂：把：把符号串符号串自身连接自身连

10、接n n次次得到的符号串得到的符号串n n = = 例如例如 1 1= = 2 2= = 0 0=4.4. 符号串集合：符号串集合： 定义定义: : 若集合若集合A A中所有元素都是某字母表中所有元素都是某字母表 上上的符号串，则称的符号串，则称A A为字母表为字母表 上的符号串集合。上的符号串集合。 符号串集合的乘积符号串集合的乘积：符号串集合：符号串集合A和和B的乘积的乘积定义为定义为:AB = xy|xA且且yB ，即即AB是由是由A中的串中的串x和和B中的串中的串y连接而成的串连接而成的串xy组成的集合。组成的集合。若集合若集合A = ab,cdeab,cde B = 0,10,1 则

11、则 AB = abab0 0,ab,ab1 1,cde,cde0 0,cde,cde1 1 显然显然 A = A = A符号串集合的方幂符号串集合的方幂: : 设设A A是符号串的集合，则是符号串的集合，则称称A Ai i为符号串集为符号串集A A的方幂，其中的方幂，其中i i是非负整数。是非负整数。具体定义如下具体定义如下: :A A0 0 = = A A1 1 = A , A= A , A2 2 = A A= A AA AK K = AA.A(k = AA.A(k个个) )5. 集合的闭包集合的闭包 闭包闭包集合集合的闭包的闭包 *定义如下：定义如下： * = 0 1 2 3例：设有字母表

12、例：设有字母表=0，1则则*=012=,0,1,00,01,10,11,000,即即*表示表示上所有有穷长的串的集合。上所有有穷长的串的集合。正闭包正闭包+ = 123称为称为的正闭包。的正闭包。 + 表示字母表表示字母表 上的上的除除外外的所有用穷长串的所有用穷长串的集合的集合闭包和正闭包之间的运算闭包和正闭包之间的运算 * = 0+ = * = * 字母表字母表 上上的一个语言是的一个语言是 上的一些符号串的集合上的一些符号串的集合 即即是是 *的一个子集的一个子集例如：例如：=a,b =a,b * *=,a,b,aa,ab,ba,bb,aaa,aab,=,a,b,aa,ab,ba,bb,

13、aaa,aab, 1.集合集合 ab,aabb,aaabbb,ab,aabb,aaabbb,a,an nb bn n, , 或或 w|ww|w* *且且w=aw=an nb bn n,n1,n1为为字母表字母表 上上的一个语言。的一个语言。2.集合集合 a,aa,aaa,a,aa,aaa, 或或 w|ww|w* *且且w=aw=an n,n1,n1为为字母字母表表 上上的一个语言的一个语言3.3. 是一个语言是一个语言4. 即即 是一个语言。是一个语言。3.3 文法和语言的形式定义文法和语言的形式定义1文法的定义文法的定义2文法的简化表示法文法的简化表示法3推导与归约推导与归约4句型、句子、语

14、言的定义句型、句子、语言的定义5文法的等价文法的等价1文法的定义文法的定义q产生式（规则）产生式（规则）产生式是一个有序对产生式是一个有序对(,)，通常写作，通常写作 （或或:= ） 定义为定义为q文法定义文法定义:文法文法G(Grammar)定义为四元组（定义为四元组（VN，VT，P，S）VN (Nonternimal)：非终结符集非终结符集VT (Terminal)：终结符集终结符集P (Production)： 产生式（规则）集合产生式（规则）集合S： 开始符号或识别符号开始符号或识别符号q 说明说明:V=VNVT，V称为文法称为文法G的字母表的字母表P中产生式形如：中产生式形如：,其中

15、其中V+且至少含一个非终结且至少含一个非终结符，符，V*VN,VT和和P是非空有穷集是非空有穷集VNVT=S是一个非终结符，且至少要在一条产生式的左部出现是一个非终结符，且至少要在一条产生式的左部出现非终结符一般代表一个语言中的语法成分，如非终结符一般代表一个语言中的语法成分，如，它是构成程序的一个语法成分，这个符号，它是构成程序的一个语法成分，这个符号本身不会在程序中出现，而终结符及其组成本身不会在程序中出现，而终结符及其组成的符号串是会在程序中出现的，如一个具体的赋值语的符号串是会在程序中出现的，如一个具体的赋值语句句“i:=x+1”例例1：文法文法G=(VN,VT,P,S)其中其中VN=

16、S，VT=0，1，P=S0S1,S01开始开始符为符为S例例2：文法：文法G=(VN,VT,P,S)VN =标识符，字母，数字标识符，字母，数字，VT =a,b,c,x,y,z,0,1,9P=， ， a, z z， 0,0, ,99 ，S=2文法的简化表示法文法的简化表示法q简化简化:通常不用将文法的四元组表示出来，只写出产通常不用将文法的四元组表示出来，只写出产生式生式q约定：约定：第一条产生式的左部是开始符号或用第一条产生式的左部是开始符号或用GS表示表示S是开始符号是开始符号用大写字母（或用尖括号括起来）表示非终结符用大写字母（或用尖括号括起来）表示非终结符用小写字母表示终结符用小写字母

17、表示终结符左部相同的产生式左部相同的产生式A,A可以记为可以记为A|，其中其中“|”是是“或或”的意思，的意思，,分别称为候选式分别称为候选式q例如例如:文法文法GS： SA|SA|SDAa|b|zD0|1|93. 推导推导(Derivation)与归约与归约(Reduction)q直接推导和直接归约：直接推导和直接归约： 是文法是文法G G的产生式，若有的产生式，若有v v，w w满足：满足：v=v=,w= ,w= , , 其中其中,V,V* * 则称则称v v直接推导直接推导到到w,w,也称也称w w直接归约直接归约到到v,v,记记作作 v v w w直接推导直接推导就是用产生式的右部替换

18、产生式就是用产生式的右部替换产生式的左部的过程的左部的过程直接归约直接归约就是用产生式的左部替换产生式就是用产生式的左部替换产生式的右部的过程的右部的过程例例 文法文法G G： S0S1 S0S1，S01 S01 有直接推导：有直接推导： 0 0S S1 1 0 00S10S11 1（ S0S1S0S1 ） 0000S S11 11 00000S10S11111（ S0S1S0S1 ） 000000S S111 111 0000000101111111（ S01 S01 ） S S 0S10S1（ S0S1S0S1 ）q推导和归约推导和归约若存在若存在v=wv=w0 0 w w1 1 . .

19、w wn n=w ,(n0)=w ,(n0) 则称则称v v推导出推导出w w，或或w w归约到归约到v,v,记为记为v vw w若有若有v v w w，或或v=wv=w，则记作则记作v vw w+* *+例例 文法文法G G： S0S1 S0S1， S01 S01 S S 0 0S S1 1 0 00 0S S1 11 1 00000 0S S1 111 11 0000000101111 111 S S 0000111100001111S S 0000111100001111 S S S S +*4句型、句子、语言的定义句型、句子、语言的定义q句型和句子句型和句子设有文法设有文法GSGS，若

20、符号串若符号串x x是从开始符推导出来的是从开始符推导出来的, ,即即S S x x，则称则称x x是文法是文法G G的的句型句型。若。若x x仅由终结符仅由终结符组成组成, ,即即S S x x，且且xVxVT T* *，则称则称x x是文法是文法G G的的句子句子。例例 文法文法GSGS： S0S1 S0S1， S01 S01S S 0 0S S1 1 0 00 0S S1 11 1 00000 0S S1 111 11 0000000101111111S,S,0S1 ,00S11 ,000S111,000011110S1 ,00S11 ,000S111,00001111都是都是G G的句

21、型的句型0000111100001111是是G G的句子的句子*q语言的定义语言的定义由文法由文法G G生成的语言记为生成的语言记为L(G),L(G),它是文法它是文法G G的一切句的一切句子的集合子的集合, ,即即 L(G)=x|S L(G)=x|S x x，其中其中S S为文法的开始符号，为文法的开始符号，且且x Vx VT T* * 例例 文法文法G G： S0S1 S0S1， S01 S01S0S1 00S11 03S13 0n-1S1n-1 0n1nL(G)=0L(G)=0n n1 1n n|n1|n1q文法和语言的关系：文法和语言的关系：文法文法G G生成的每个串都在生成的每个串都

22、在L(G)L(G)中中L(G)L(G)中的每个串确实能被中的每个串确实能被G G生成生成*根据文法，可以通过推导得到该文法相应的语言；根据文法，可以通过推导得到该文法相应的语言；例：例：GE E：EE+T|TEE+T|TTTTTF|FF|F F(E)|aF(E)|aE E E+T T+T F+T a+T a+TF a+FF a+aF a+aa表示一切能用符号表示一切能用符号a，+，(和和)构成的算术表达式构成的算术表达式有了语言的要求，也可以为该语言设计文法有了语言的要求，也可以为该语言设计文法例：若语言由例：若语言由0、1符号串组成，串中符号串组成，串中0和和1的个数相同，的个数相同，构造其

23、文法为：构造其文法为：A 0B|1CB 1|1A|0BBC 0|0A|1CC5文法的等价文法的等价若若L L（G G1 1）=L=L（G G2 2），），则称文法则称文法G G1 1和和G G2 2是等价是等价的。的。例如例如 文法文法G G1 1AA：A0R A01 RA1A0R A01 RA1 G G2 2SS：S0S1 S01S0S1 S01所定义的语言都是所定义的语言都是0 0n n1 1n n两文法等价两文法等价3.4 3.4 文法的类型文法的类型通过对产生式施加不同的限制，通过对产生式施加不同的限制，ChomskyChomsky将将文法分为四种类型：文法分为四种类型：q0 0型文法

24、型文法( (短语文法短语文法) )：对任一产生式：对任一产生式，都有都有(V(VN NVVT T) )* *且至少含有一个非终结且至少含有一个非终结符符; (V; (VN NVVT T) )* *q1 1型文法型文法( (上下文有关上下文有关) )：它是：它是0型文法的特例，设型文法的特例，设文文法法G=(VN,VT,P,S)，对对P P中的任一产生式中的任一产生式，都都有有| |， 仅仅仅仅 SS除外除外例例 文法文法GSGS： SaSBE SaSBE SaBESaBEEBBEEBBEaBab aBab bBbb bBbb bEbe bEbe eEeeeEee1型文法产生式的一般形式是型文法

25、产生式的一般形式是 A ， , V V* * ，AVAVN N , , VV+ +( (不能是空串不能是空串) ) ，它表示当，它表示当A的上文为的上文为 且下文为且下文为 时可把时可把A替换成替换成 ，因此称，因此称1型文法为上下型文法为上下文有关文法。文有关文法。 q2 2型文法（上下文无关文法）型文法（上下文无关文法） ：它是：它是1型文型文法的特例，对任一产生式法的特例，对任一产生式，都有都有V VN N ， (V(VN NVVT T) )* *例例 文法文法GSGS： SABSABABS|0ABS|0BSA|1BSA|12型文法产生式的一般形式是型文法产生式的一般形式是:A ，它表示

26、它表示不管不管A的上下文如何即可把的上下文如何即可把A替换成替换成 ，因此被，因此被称为上下文无关文法。称为上下文无关文法。通常程序设计语言的文法，可用通常程序设计语言的文法，可用2型文法来型文法来描述，因此我们重点研究描述，因此我们重点研究2型文法。型文法。 q3 3型文法型文法( (正规文法正规文法) )：它是：它是2 2型文法的特例，型文法的特例，任一产生式任一产生式的形式都为的形式都为AaBAaB或或AaAa，其中其中A A ，BVBVN N ，aVaVT T例如例如 文法文法GSGS：S0A|1B|0S0A|1B|0A0A|1B|0SA0A|1B|0SB1B|1|0B1B|1|0在程

27、序设计语言中，在程序设计语言中，3型文法通常用来描述型文法通常用来描述单词的结构。单词的结构。文法类别文法类别产生式形式产生式形式产生的语言产生的语言 说明说明0型文法型文法(短语文法短语文法)VV+ + , ,且至少含一且至少含一个非终结符，个非终结符，VV* *0型语言型语言对产生式对产生式基本无限基本无限制制1型文法型文法(上下文有关文法上下文有关文法)，| |1|1或或 A , , V V* *AVAVN N , , VV1型语言型语言（上下文有（上下文有关语言）关语言）将将A替换替换成成 时，必时，必须考虑须考虑A的上下文的上下文 ， 2型文法型文法(上下文无关文法上下文无关文法)A

28、A，AVAVN N ， VV* *2型语言型语言（上下文无（上下文无关语言）关语言）无需考虑无需考虑A在上下在上下文中的出文中的出现情况现情况3型文法型文法(正规文法正规文法)AaBAaB或或AaAa，A,BVA,BVN N ，aVaVT T3型语言型语言(正规语言正规语言)产生式全产生式全部是规定部是规定的形式的形式四种文法之间的逐级四种文法之间的逐级“包含包含”关系关系2型文法型文法1型文法型文法3型文法型文法0型文法型文法3.5 上下文无关文法及其语法树上下文无关文法及其语法树1上下文无关文法上下文无关文法(Context-Free Grammar)上下文无关文法有足够的能力描述现今程序

29、设计上下文无关文法有足够的能力描述现今程序设计语言的语法结构语言的语法结构例：算术表达式：例：算术表达式：Ei|E+E|E*E|（E）i:=Eif then | if then else 所以我们只关心上下文无关文法形成的语言中所以我们只关心上下文无关文法形成的语言中的句子的分析的句子的分析2. 规范推导和规范句型规范推导和规范句型q如果在推导的任何一步如果在推导的任何一步，其中其中、是句型，都是对是句型，都是对中的最左（最右）非中的最左（最右）非终结符进行替换终结符进行替换, ,则称这种推导为则称这种推导为最左最左( (最最右右) )推导推导q最右推导被称为最右推导被称为规范推导规范推导q由

30、规范推导所得的句型称为由规范推导所得的句型称为规范句型规范句型q例例 文法文法G：EE+T|T TTF|F F（E）|i句子句子i+ii的推导过程如下：的推导过程如下：最左推导：最左推导：E=E+T=T+T=F+T=i+T=i+TF=i+FF =i+iF=i+ii最右推导：最右推导：E=E+T=E+TF=E+Ti=E+Fi=E+ii = T+ii=F+ii=i+ii3.语法树语法树(推导树推导树Parse Tree)q 作用作用:直观地描述上下文无关文法的直观地描述上下文无关文法的句型句型推导过程推导过程。给定文法给定文法G=(VG=(VN N,V,VT T,P,S),P,S)，对于对于G G

31、的任何句型都能构造与之关联的语法树的任何句型都能构造与之关联的语法树q例：文法例：文法G：EE+T|TTTF|F F（E）|i句型句型T+TF的推导过程与语法树的推导过程与语法树EET+TFTE=E+TEET+TFTE=E+T =E+TF=T+TF=T+T=T+TF从语法树中看不出句型中的符号被替代的顺序从语法树中看不出句型中的符号被替代的顺序从左到右读出叶子结从左到右读出叶子结点得到的符号点得到的符号串串，为，为文法文法的的句型。也把该句型。也把该语法树称为该句型的语法树称为该句型的语法树。语法树。q语法树定义语法树定义:给定文法给定文法G=( VG=( VN N,V,VT T,P,S),P

32、,S)，若一棵树满足下列若一棵树满足下列4 4个条个条件，则称此树为件，则称此树为G G的语法树：的语法树：1.1.每个结点都有一个标记，此标记是每个结点都有一个标记，此标记是V V的一个符号的一个符号2.2.根的标记是根的标记是S S（开始符号）（开始符号）3.3.若一结点若一结点n n至少有一个它自己除外的子孙，并且至少有一个它自己除外的子孙，并且有标记有标记A A，则肯定则肯定AVAVN N4.4.如果结点如果结点n n有标记有标记A,A,其直接子孙结点从左到右的其直接子孙结点从左到右的次序是次序是n n1 1，n n2 2，n nk k，其标记分别为其标记分别为A A1 1，A A2

33、2，A Ak k，那么那么AAAA1 1A A2 2A Ak k一定是一定是P P中的一个中的一个产生式产生式文法文法G：EE+E|EE|（E）|i句子句子 ii+i 对应的语法树对应的语法树两个不同的两个不同的最左推导最左推导：推导推导1：E E+E EE+E iE+E ii+E ii+i推导推导2：E EE iE iE+E ii+E ii+iiEE+EEEiiEEEiEE+ii4.文法的二义性文法的二义性(Ambiguity)定义定义:如果一个文法存在某个句子对应两棵不同的语法树，如果一个文法存在某个句子对应两棵不同的语法树，则说这个文法是二义的。则说这个文法是二义的。二义性文法存在某个句

34、子二义性文法存在某个句子, ,它它有两个不同的最左（右）推导有两个不同的最左（右）推导对于一个程序设计语言来说，希望它的文法是无二义对于一个程序设计语言来说，希望它的文法是无二义的，因为希望对它的每个语句的分析是唯一的。的，因为希望对它的每个语句的分析是唯一的。文法文法G：E E+E| EE|（E）| i文法文法G：ET|E+TTF|TFF(E)| i等价的无等价的无二义文法二义文法3.6 句型的分析句型的分析q任务任务: 句型分析就是识别一个符号串是否为句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。某文法的句型，是某个推导的构造过程。对于程序设计语言来说，句型分析就是一

35、对于程序设计语言来说，句型分析就是一个识别输入符号串是否为语法上正确的程个识别输入符号串是否为语法上正确的程序的过程。序的过程。q从左到右的分析算法从左到右的分析算法，即总是从左到右地，即总是从左到右地识别输入符号串识别输入符号串.句型分析算法采用从左到句型分析算法采用从左到右的分析算法右的分析算法q句型的分析算法句型的分析算法分类分类自上而下分析法自上而下分析法 (Top-Down parsing)自下而上分析法自下而上分析法 (Bottom-Up parsing)3.6.1 自上而下的分析方法自上而下的分析方法q定义定义:从文法的开始符号出发，反复使用文法的从文法的开始符号出发，反复使用文

36、法的产生式，寻找与输入符号串匹配的推导。产生式，寻找与输入符号串匹配的推导。语法树的构造：将文法的开始符号作为语语法树的构造：将文法的开始符号作为语法树的根，向下逐步建立语法树，使语法法树的根，向下逐步建立语法树，使语法树的末端结点符号串正好是输入符号串。树的末端结点符号串正好是输入符号串。例例 文法文法G：S cAd A ab A a识别输入串识别输入串w=cabd是否为该文法的句子是否为该文法的句子S推导过程：推导过程：cAdab=cabdS =cAdq自上而下方法的主要问题自上而下方法的主要问题对输入串对输入串cabd自上而下构造语法树的另一过程自上而下构造语法树的另一过程不成功，不成功

37、，不成功的原因不成功的原因是选错产生式是选错产生式Aa自上而下分析的主要问题是选择产生式自上而下分析的主要问题是选择产生式 :假定要被代换的最左非终结符号是假定要被代换的最左非终结符号是B B，且有且有n n条规则：条规则：BABA1 1|A|A2 2| |A|An n，那么如何确定用那么如何确定用哪个右部去替代哪个右部去替代B B？ScA da3.6.2 自下而上的分析方法自下而上的分析方法q定义定义:从输入符号串开始，逐步进行归约，从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。直至归约到文法的开始符号。语法树的构造：从输入符号串开始，以它语法树的构造：从输入符号串开始，以它作为

38、语法树的末端结点符号串，自底向上作为语法树的末端结点符号串，自底向上的构造语法树的构造语法树例例 文法文法G：S cAd A ab A a识别输入串识别输入串w=cabd是否为该文法的句子是否为该文法的句子cabd归约过程：归约过程：用用“|-”表示归表示归约，下划线部分约，下划线部分为被归约符号为被归约符号cabd |-cAd |-SASq自下而上分析的主要问题自下而上分析的主要问题对输入串对输入串cabd的两种归约过程的两种归约过程（1）cabd|-cAd|-S 归约到开始符归约到开始符（2）cabd|-cAbd 不能归约到开始符不能归约到开始符在自下而上的分析方法中，每一步都是在自下而上

39、的分析方法中，每一步都是从当前串中选择一个子串加以归约，该从当前串中选择一个子串加以归约，该子串暂称子串暂称“可归约串可归约串”。如何确定如何确定“可归约串可归约串”是自下而上分析的是自下而上分析的主要问题。主要问题。为了刻划为了刻划“可归约串可归约串”,引入下面的概念引入下面的概念q短语，直接短语和句柄短语，直接短语和句柄定义定义:设设是文法是文法GS中的一个句型，如果中的一个句型，如果有有SA且且A，则称则称是句型是句型相相对于非终结符对于非终结符A的的短语短语特别的如有特别的如有A，则称则称是句型是句型相对相对于规则于规则A的的直接短语直接短语。一个句型的最左直接短语称为该句型的一个句型

40、的最左直接短语称为该句型的句柄句柄(Handle)。句柄就是句柄就是“可归约串可归约串”* *+ 对定义的分析：对定义的分析：在短语的定义中包括了三个条件：在短语的定义中包括了三个条件： 是文法的一个句型；是文法的一个句型； S A; A 。这三个条件都必须满足。这三个条件都必须满足。(1)(2)说明说明 、 A都必须是句型都必须是句型(2)(3)说明，将说明，将中的中的归约归约A后，得到的后，得到的A一定要是句型。假如符号串一定要是句型。假如符号串 ，将其归约将其归约成成A后得到的符号串不能由开始符号推出，后得到的符号串不能由开始符号推出，则则不是短语。不是短语。* *+例：文法例：文法GE

41、: EE+T|T TTF|F F（E）| i 的一个句型是的一个句型是 TF+i，相应的语法树见右图：相应的语法树见右图：EET+TTFFi1 因为因为E T+i 且且 T TF，所所以以TF是句型相对于是句型相对于T的短语，且是的短语，且是相对于相对于TTF的直接短语的直接短语2 因为因为E TF+F 且且 F i，所所以以i是句型相对于是句型相对于F的短语，且是相对的短语，且是相对于于Fi的直接短语的直接短语3 因为因为E E 且且E TF+i，所以所以TF+i是句型相对于是句型相对于E的短语的短语4 TF是最左直接短语，即是最左直接短语，即句柄句柄 * * * *+ +文法文法GE:EE+T|TTTF|FF（E）|i的一个句型的一个句型 是是TF+iEET+TTFFi虽然虽然F+i是句型是句型TF+i的一部分，的一部分，但不是短语，因为尽管有但不是短语，因为尽管有E F+i，但是不存在从文法开始符但是不存在从文法开始符E TE的推导的推导+ +* *q短语与语法树短语与语法树从句型的语法树上很容易找出句型的短语从句型的语法树上很容易找出句型的短语语法树中每棵子树的末端结点构成相对于子树根语法树中每棵子树的末端结点构成相对于子树根的短语的短语 例：文法例：文法GE的句型的句型TF+i语法树：语法树：EET+TTFFi