编译原理第2章文法和语言的基本知识课件.ppt

1、编编 译译 原原 理理2022年8月16日第第2 2章文法和语言的基本知识章文法和语言的基本知识1.1.本章是编译原理课程的理论基础，要求掌握形本章是编译原理课程的理论基础，要求掌握形式语言的基本术语和概念式语言的基本术语和概念,重点掌握重点掌握短语、直接短语、直接短语、句柄、素短语、规范推导、规范归约短语、句柄、素短语、规范推导、规范归约。2.2.掌握文法和语言的定义，掌握文法和语言的定义，文法的二义性文法的二义性与递归与递归性的判断方法及句型的分析方法，性的判断方法及句型的分析方法，文法分类文法分类。3.3.熟练使用文法定义程序设计语言的单词和语法熟练使用文法定义程序设计语言的单词和语法成

2、分。成分。4.4.对形式语言的理论有一个初步认识。对形式语言的理论有一个初步认识。教学目标教学目标编编 译译 原原 理理2022年8月16日 2.1 字母表和符号串的基本概念字母表和符号串的基本概念 2.2 文法和语言的形式定义文法和语言的形式定义 2.3 句型的分析句型的分析 2.4 文法和语言的分类文法和语言的分类教学内容教学内容编编 译译 原原 理理2022年8月16日 程序设计语言是一种形式语言，与自然语言既有相程序设计语言是一种形式语言，与自然语言既有相似的性质又有本质的不同。似的性质又有本质的不同。最主要的区别是：形式语言的规则简单、严格、最主要的区别是：形式语言的规则简单、严格、

3、无例外、无二义性。无例外、无二义性。编译程序的正确转换建立在对程序设计语言的精确编译程序的正确转换建立在对程序设计语言的精确定义和描述基础上。定义和描述基础上。语法语法文法是描述语言语法的形式规则文法是描述语言语法的形式规则语义语义语言中各语句的含义语言中各语句的含义语用语用从使用者的角度对语言的描述从使用者的角度对语言的描述编编 译译 原原 理理2022年8月16日字母表字母表：符号的非空有限集：符号的非空有限集 例：例：=00，11 2.12.1字母表和符号串字母表和符号串符号符号：字母表中的元素：字母表中的元素 例：例：0 0，1 1符号串符号串：由字母表中的符号组成的任何有穷序列：由字

4、母表中的符号组成的任何有穷序列 例：例：0,1,0,1,01,1001,10,011,011，.空符号串空符号串：无任何符号的符号串，用：无任何符号的符号串，用表示表示 C语言的字母表 Aa,b,0,1,9,+,_/,(,),=if,else,for.不对不对如如=if,else,for,while符号就是字符，对吗？符号就是字符，对吗？编编 译译 原原 理理2022年8月16日符号串的前缀和后缀符号串的前缀和后缀:从符号串从符号串s s的尾部删去若干个的尾部删去若干个(包括包括0 0个个)符号之后所余下的符号之后所余下的部分称为部分称为s s的前缀的前缀，0 0，0101及及011011都是

5、符号串都是符号串011011的前缀的前缀，1 1，1111及及011011都是符号串都是符号串011011的后缀的后缀符号串集合符号串集合：若集合：若集合A A中的一切元素都是某字母表上的符号中的一切元素都是某字母表上的符号串，则称串，则称A A为该字母表上的符号串集合。为该字母表上的符号串集合。例：例：=aa，b b，c A=a,aa,acc A=a,aa,ac 编编 译译 原原 理理2022年8月16日符号串的运算符号串的运算符号串符号串x x和和y y的的连接连接:是把是把y y的符号写在的符号写在x x的符号之后的符号之后得到的符号串得到的符号串xyxy 例如例如x=00 x=00，y

6、=11y=11，则，则xyxy=0011=0011对于任意一个符号串对于任意一个符号串s s，有，有s=s=s s=s=s 符号串的符号串的连接运算连接运算编编 译译 原原 理理2022年8月16日符号串自身连接符号串自身连接n n次得到的符号串次得到的符号串s sn n 定义为定义为 ssssssss ，包括，包括n n个个s s，称为符号串的，称为符号串的幂运算幂运算 s s0 0=，s s1 1=s=s，s s2 2=ss=ss，设设s=01s=01，则，则s s0 0=s s1 1=01=01s s2 2=0101=0101 符号串的符号串的幂运算幂运算编编 译译 原原 理理2022年

7、8月16日设设A A、B B为符号串集合，则为符号串集合，则A A和和B B的的乘积乘积定义为：定义为：ABAB xy xy|xA,yB|xA,yB例如，例如，A Aa,ba,b，B=c,dB=c,d则则AB=AB=符号串集合的乘积符号串集合的乘积ac,ad,bc,bdac,ad,bc,bd 编编 译译 原原 理理2022年8月16日有符号串集合有符号串集合A，定义，定义A0=,A1=A,A2=AA,A3=AAA,AnAn-1A=AAn-1 ，n0例如，例如，A A0,10,1，则，则A A0 0=A A1 1=A A2 2=A A3 3=符号串集合的幂运算符号串集合的幂运算0,10,100,

8、01,10,1100,01,10,11000,001,010,011,100,101,110,111000,001,010,011,100,101,110,111编编 译译 原原 理理2022年8月16日设设A A是符号串集合，定义是符号串集合，定义 A A1 A2 A3 An 称为集合称为集合A A的的正闭包正闭包。A*A0 A称为集合称为集合A A的的闭包闭包。例：A=x,y A？A*？x,y,xx,xy,yx,yy,xxx,xxy,xyx,xyy,A1 A2 A3,x,y,xx,xy,yx,yy,xxx,xxy,xyx,xyy,A0 A1 A2 A3符号串集合的闭包运算符号串集合的闭包运

9、算编编 译译 原原 理理2022年8月16日的闭包的闭包*表示表示 上的一切符号串（包括上的一切符号串（包括）组成的集合）组成的集合的正闭包的正闭包+表示表示 上的上的除除外的所有符号串组成的集合外的所有符号串组成的集合例：例：=a,b=a,b *=,a,b,aa,ab,ba,bb,aaa,aab=,a,b,aa,ab,ba,bb,aaa,aab,+=a,b,aa,ab,ba,bb,aaa,aab=a,b,aa,ab,ba,bb,aaa,aab,.2*.32*编编 译译 原原 理理2022年8月16日若A为某语言的字母表 Aa,b,0,1,9,+,_/,(,),=if,else,for.B为单

10、词集 B=if,else,for,则B A*。语言的句子是定义在B上的符号串。若令C为句子集合，则C B*,程序 C为什么对符号、符号串、符号串集合以及它们的运算感兴趣？为什么对符号、符号串、符号串集合以及它们的运算感兴趣？编编 译译 原原 理理2022年8月16日语言语言是由句子组成的集合，是由一组符号所构成的集合是由句子组成的集合，是由一组符号所构成的集合字母表字母表 上上的一个语言是的一个语言是 上的一些符号串的集合上的一些符号串的集合字母表字母表 上上的每个语言是的每个语言是*的一个子集的一个子集集合a,aa,aaa,或表示为w|w*且w=an,n1 为字母表上的一个语言 例如：字母表

11、=a,b,*=,a,b,aa,ab,ba,bb,aaa,aab,集合ab,aabb,aaabbb,anbn,或表示为w|w*且w=anbn,n1为字母表上的一个语言编编 译译 原原 理理2022年8月16日2.22.2文法和语言的形式定义文法和语言的形式定义 文法文法是对语言结构的定义与描述。（或称为是对语言结构的定义与描述。（或称为“语法语法”）。）。:=“=”:=“+”|“*”:=“(”“)”|编编 译译 原原 理理2022年8月16日 文法的直观概念文法的直观概念：以汉语中的“我是大学生”为例。n 采用BNF来表示汉语句子的构成规则为：句子：=主语谓语 主语：=代词|名词 代词：=我|你

12、|他 名词：=王明|大学生|工人|英语 谓语：=动词直接宾语 动词：=是|学习 直接宾语：=代词|名词n 根据上述规则，“我是大学生”的构成符合上述规则，而“我大学生是”不符合，我们说它不是句子。这些规则成为我们判别句子结构合法与否的依据。换句话说，这些规则看成是一种元语言，用它描述汉语。这种的语言描述成为文法。文法的四部分一组终结符号一组终结符号（语言的基本符号）一组非终结符号一组非终结符号（语法单位）一个开始符号一个开始符号（一个特殊的非终结符号，最感兴趣的语法单位）一组规则一组规则（也称产生式或产生规则）编编 译译 原原 理理2022年8月16日 文法的形式定义文法的形式定义：P10的定

13、义的定义1.1 例例2-1，文法G=（，P，S）是描述标识符的文法，则其中：=标识符，字母，数字 =a,b,c.x,y,z,0,1,2,39 P=|a|b|c|.|z 0|1|2|.|9 S =VNVTVNVT编编 译译 原原 理理2022年8月16日赋值语句赋值语句标识符标识符表达式表达式表达式表达式表达式表达式表达式表达式标识符标识符整数整数标识符标识符表达式表达式y=x+r*6y =x+r*6编编 译译 原原 理理2022年8月16日 例：有一句子：“我是大学生”。这是一个在语法、语义上都正确定句子，该句子的结构（称为语法结构）是由它的语法决定的。在本例中它为“主谓结构”。如何定义句子的

14、合法性？有穷语言：只需逐一列举句子无穷语言：使用文法定义句子的结构，用适当条数的规 则把语言的全部句子描述出来。文法是以有穷的集 合刻划无穷的集合的工具。文法的非形式定义文法的非形式定义编编 译译 原原 理理2022年8月16日 1.1.语法规则语法规则：我们通过建立一组规则，来描述句子的语法：我们通过建立一组规则，来描述句子的语法结构结构。规定用规定用“:=”:=”表示表示“由由组成组成”。:=:=:=:=|:=:=你你|我我|他他:=:=王民王民|大学生大学生|工人工人|英语英语:=:=:=:=是是|学习学习:=:=|文法的文法的BNF表示表示编编 译译 原原 理理2022年8月16日2.

15、2.由规则推导句子由规则推导句子：有了一组规则之后，可以按照一定的方式：有了一组规则之后，可以按照一定的方式用它们去推导或产生句子。用它们去推导或产生句子。推导方法：从一个要识别的符号开始推导，即用相应规则的推导方法：从一个要识别的符号开始推导，即用相应规则的右部右部来替代规则的来替代规则的左部左部，每次仅用一条规则去进行推导。，每次仅用一条规则去进行推导。=这种推导一直进行下去，直到所有带这种推导一直进行下去，直到所有带的符号都由终结符号的符号都由终结符号替代为止。替代为止。编编 译译 原原 理理2022年8月16日 =我我=我我 =我我是是 =我是我是=我是我是大学生大学生:=:=:=:=

16、|:=:=你你|我我|他他:=:=王民王民|大学生大学生|工人工人|英语英语:=:=:=:=是是|学习学习:=:=|推导方法：推导方法：从一个要识别的符号从一个要识别的符号开始推导，即用相应规则的开始推导，即用相应规则的右部右部来替代规则的来替代规则的左部左部，每次仅用一条规则去进行推导。每次仅用一条规则去进行推导。编编 译译 原原 理理2022年8月16日例：有一英语句子：例：有一英语句子：The big elephant ate the peanut.:=:=:=:=:=:=the:=:=big:=:=elephant:=:=:=:=ate:=:=:=:=peanut编编 译译 原原 理理

17、2022年8月16日 =the =the big =the big elephant =the big elephant =the big elephant ate =the big elephant ate =the big elephant ate the =the big elephant ate the peanut:=:=:=:=:=:=the:=:=big:=:=elephant|peanut:=:=:=:=ate:=:=编编 译译 原原 理理2022年8月16日上述推导可写成=the big elephant ate the peanut+说明：(1)有若干语法成分同时存在时，我

18、们总是从最左的语法成 分进行推导，这称之为最左推导，类似的有最右推导（一般推 导）。(2)从一组规则可推出不同的句子，如以上规则还可推出“大象吃象”、“大花生吃象”、“大花生吃花生”等句子，它们 在语法上都正确，但在语义上都不正确。所谓文法文法是在形式上对句子结构的定义与描述，而未涉及语义问题。编编 译译 原原 理理2022年8月16日例例2-3，利用例2-2中的文法，推导出文法的句子012：最左推导：N=S=SD=SDD=DDD=0DD=01D=012最右推导：N=S=SD=S2=SD2=S12=D12=012在这里，N S为长度为1的推导，N SD为长度为2的推导N 012为长度为7的推导

19、。其中，对于N S来说，S是N的直接推导，或N是S的直接归约。一些规定：=推导 =规范推导 长度大于零的推导 长度可为零的推导 长度为n的推导 172*nN SS SD|DD 0|1|2|9编编 译译 原原 理理2022年8月16日 课堂作业：课堂作业：设有文法设有文法GS：Sa|（T）T T，S|S请给出句子（请给出句子（a,(a,a)的最左、最右推导。的最左、最右推导。其最左推导为：其最左推导为：S S=（T）=（T，S）=（S，S）=（a，（，（T）=（a，（，（T，S）=（a，（，（S，S）=（a，（，（a，S）=（a，（，（a，a）其最右推导为：其最右推导为：S S=（T）=（T，S

20、）=（T，（，（T）=（T，（，（T，S）=（T，（，（T，a）=（T，（，（S，a）=（T，（，（a，a）=（S，（，（a，a）=（a，（，（a，a）=（a，S）编编 译译 原原 理理2022年8月16日文法文法GS=（VN，VT，P，S）VN：非终结符号集：非终结符号集 VT：终结符号集：终结符号集 P：产生式或规则的集合产生式或规则的集合 S：开始符号（识别符号）开始符号（识别符号）S VN，S至少要在至少要在 一条规则中作为左部出现一条规则中作为左部出现VVN VT称为文法的字母表称为文法的字母表补补:规则的定义规则的定义:或或V+且至少有一个非终结符，而且至少有一个非终结符，而(VN

21、 VT)*文法的形式定义文法的形式定义编编 译译 原原 理理2022年8月16日G=(VT,VN,S,P)，其中，其中:VN=表达式表达式VT=+,*,(,),iS=表达式表达式P=表达式表达式表达式表达式+表达式表达式 表达式表达式表达式表达式*表达式表达式 表达式表达式(表达式表达式)表达式表达式i 【例【例2.1】程序语言中只含】程序语言中只含+、*运算的算术表达式，用运算的算术表达式，用i表示变量或常数，其文法可以表示为：表示变量或常数，其文法可以表示为：描述了表达式的描述了表达式的语法规则语法规则 编编 译译 原原 理理2022年8月16日几点说明几点说明：产生式左边符号构成集合产生

22、式左边符号构成集合VN，且，且 S VN给定一个给定一个 文法，实际只需给出产生式集合，并指定识别符号文法，实际只需给出产生式集合，并指定识别符号G表达式表达式:表达式表达式表达式表达式+表达式表达式表达式表达式表达式表达式*表达式表达式表达式表达式(表达式表达式)表达式表达式iVN：代表程序的语法成份，如：代表程序的语法成份，如“表达式表达式”，它不会，它不会 出现在程序中出现在程序中VT：会出现在程序中，如：会出现在程序中，如i+i编编 译译 原原 理理2022年8月16日有些产生式具有相同的左部，可以和在一起有些产生式具有相同的左部，可以和在一起GE：EE+E|E*E|(E)|i 编编

23、译译 原原 理理2022年8月16日GS：SL|SL|SDLa|b|zD0|1|9【例【例2.2】某种语言的标识符是以字母开头的字母数字】某种语言的标识符是以字母开头的字母数字串，如果用串，如果用L表示表示，D表示表示，用，用S表示字表示字母数字串母数字串 描述了标识符的描述了标识符的词法规则词法规则 编编 译译 原原 理理2022年8月16日例：无符号整数的文法：例：无符号整数的文法：G|00|1|2|3|9描述了无符号整描述了无符号整数的词法规则数的词法规则 编编 译译 原原 理理2022年8月16日说明说明：终结符集是输入字符集，它是构成单词的最基本元素终结符集是输入字符集，它是构成单词

24、的最基本元素终结符集是经词法分析识别后的单词集，如变量终结符集是经词法分析识别后的单词集，如变量i,i,运运算符算符+、*和分界符和分界符(、)，它们被视为语法分析中最基，它们被视为语法分析中最基本元素本元素 描述语法规则的文法描述语法规则的文法GE：EE+E|E*E|(E)|i 描述词法规则的文法描述词法规则的文法GS：SL|SL|SDLa|b|zD0|1|9编编 译译 原原 理理2022年8月16日文法的表示方法文法的表示方法3.语法图语法图2.EBNF：扩充的扩充的BNF的元符号：的元符号：,:=,|,(,)字母字母 字母字母 数字数字 数字数字 标识符标识符无符号整数无符号整数1.BN

25、F的元符号：的元符号：,:=,|编编 译译 原原 理理2022年8月16日推导的形式定义推导的形式定义如果如果是文法是文法G=(VT，VN，S，P)的的一个产生式，一个产生式，V*，有符号串，有符号串x，y满足满足x=，y=,x y则称则称y是是x的的直接推导直接推导，也可以说，也可以说，y直接归约直接归约到到x，记作，记作x y。直接推导：用产生式的右部替换产生式的左部直接推导：用产生式的右部替换产生式的左部直接归约：用产生式的左部替换产生式的右部的过程直接归约：用产生式的左部替换产生式的右部的过程 例：例：x S SD LD aD a1=yGS：SL|SL|SDLa|b|zD0|1|9编编

26、 译译 原原 理理2022年8月16日S=SD,使用规则使用规则SSD，其中，其中=；SD=LD,使用规则使用规则SL，其中，其中=,=D；LD=aD,使用规则使用规则La，其中，其中=,=D；aD=a1,使用规则使用规则D1，其中，其中=a,=。GS：SL|SL|SDLa|b|zD0|1|9根据文法和推导的定义，可推出终结符号串根据文法和推导的定义，可推出终结符号串如果如果是文法是文法G=(VT，VN，S，P)的的一个产生式，一个产生式，V*，有符号串，有符号串x，y满足满足x=，y=,x y则称则称y是是x的的直接推导直接推导，也可以说，也可以说，y直接归约直接归约到到x，记作，记作x y

27、。编编 译译 原原 理理2022年8月16日 1 1 0(6)=(1)=(3)(5)=(2)当符号串已没有非终结符号时，推导就必须终止。因为终结符不可能出现在规则左部，所以将在规则左部出现的符号称为非终结符号。例如：例如：G (1)(2)(3)(4)0|1|2|3|9编编 译译 原原 理理2022年8月16日如果存在直接推导序列：如果存在直接推导序列：x y0 y1 y2yn=y则称这个序列是一个从则称这个序列是一个从x至至y的长度为的长度为n（n0）的）的推推导导，或称，或称y归约归约到到x，记作，记作x y。若有若有x y，或，或x=y，则记作，则记作x y。=*=例：例：x S SD L

28、D aD a1=yGS：SL|SL|SDLa|b|zD0|1|9=记作记作x y或记作或记作x y *=例：例：x S SD LD aD a1=yGS：SL|SL|SDLa|b|zD0|1|9=记作记作x y或记作或记作x y *=编编 译译 原原 理理2022年8月16日文法文法GS （1）句型句型：x是句型是句型 S ,且且 V*；（2）句子句子：x是句子是句子 S ,且且,VT*；（3）语言语言：L（GS）=|VT*,S ；+文法GS所产生的所有句子的集合*句子是所有终结符号组成的句型语言的形式定义语言的形式定义GE：EE+E|E*E|(E)|i 句型：句型：E+EE+E*EE+E*iE

29、+i*i句子：句子：i+ii*ii+i*i(i+i)*i 编编 译译 原原 理理2022年8月16日 形式语言理论可以证明以下两点：形式语言理论可以证明以下两点：（1）G L（G）；）；（2）L(G)G1，G2，Gn；已知文法，求语言，通过推导；已知文法，求语言，通过推导；已知语言，构造文法，无形式化方法，更多是凭经验已知语言，构造文法，无形式化方法，更多是凭经验编编 译译 原原 理理2022年8月16日例：例：GS S:=:=aSb|ab求其所产生的语言。求其所产生的语言。若S:=:=aSb|，如何？L(GS)=anbn|n1L(GS)=anbn|n0已知文法，求语言，通过推导课堂练习课堂练

30、习1：GS S:=:=bA A:=:=aA|aL(GS)=ban|n1课堂练习课堂练习2：GS S:=:=AB A:=:=aA|a B:=:=bB|bL(GS)=ambn|m,n1编编 译译 原原 理理2022年8月16日例：abna|n1,构造其文法 定义.G和G是两个不同的文法，若 L(G)=L(G),则G和G为等价文法。若n0，如何？课堂练习3：anbnci|n1,i 0,构造其文法 GS：S AB A aAb|ab BcB|G1S：SaBa,Bb|bBG2S：SaBa,Bb|BbG1S：SaBa,B|bBG2S：SaBa,B|Bb编编 译译 原原 理理2022年8月16日例：构造一个文

31、法，使其描述的语言是无符号整数。例：构造一个文法，使其描述的语言是无符号整数。GS：SSD|DD0|1|2|3|4|5|6|7|8|9G|00|1|2|3|9编编 译译 原原 理理2022年8月16日编译感兴趣的问题是编译感兴趣的问题是:给定x,G,求x L(G)?x算法1算法2x L(G)?Gyn出错处理停机 =编编 译译 原原 理理2022年8月16日1.递归规则递归规则：规则右部有与左部相同的符号：规则右部有与左部相同的符号 左递归规则：左递归规则：AA 右递归规则：右递归规则：AA 自嵌入递归规则：自嵌入递归规则：AA递归文法递归文法2.递归文法递归文法：含有递归规则的含有递归规则的文

32、文法，为法，为直接递归直接递归文文法法ABaBAb GS：SL|SL|SDLa|b|zD0|1|9间接递归间接递归文文法法编编 译译 原原 理理2022年8月16日递归文法的递归文法的优点优点：可用有穷条规则，定义无穷语言：可用有穷条规则，定义无穷语言 例：对于前面给出的无符号整数的文法是有递归文法，用例：对于前面给出的无符号整数的文法是有递归文法，用12条规则就可以定义出所有的无符号整数。若不用递归文法，那条规则就可以定义出所有的无符号整数。若不用递归文法，那将要用多少条规则呢？将要用多少条规则呢？!GS：SSD|DD0|1|2|3|4|5|6|7|8|9编编 译译 原原 理理2022年8月

33、16日左左递归文法的递归文法的缺点缺点：不能用自顶向下的方法来进行语法分析：不能用自顶向下的方法来进行语法分析会造成死循环（后面将详细论述）会造成死循环（后面将详细论述）GE：Ei+i|i*i|(i+i)*i该文法所描述的语言为该文法所描述的语言为L(G)=i+i,iL(G)=i+i,i*i,(i+i)i,(i+i)*ii，无法表示无穷的表达式语言无法表示无穷的表达式语言 编编 译译 原原 理理2022年8月16日2.32.3句型的分析句型的分析句型的分析：句型的分析：是指识别输入的符号串是否为某一文法的是指识别输入的符号串是否为某一文法的 句型句型(或句子或句子)的过程的过程 对于同一个句型

34、或句子，可以通过不同的推导序列推导出来，对于同一个句型或句子，可以通过不同的推导序列推导出来，这是因为在推导过程中所选择的非终结符的次序不同这是因为在推导过程中所选择的非终结符的次序不同 GEGE：EE+E|EEE+E|E*E|(E)|iE|(E)|ii+ii+i*i i的推导序列有哪些？的推导序列有哪些？编编 译译 原原 理理2022年8月16日最左最左(右右)推导指对于一个推导序列中的每一直接推导，被替推导指对于一个推导序列中的每一直接推导，被替换的总是当前符号串中的最左换的总是当前符号串中的最左(右右)非终结符号。最右推导也非终结符号。最右推导也称为称为规范推导规范推导。规范推导的逆过程

35、，称为最左归约，也称为规范推导的逆过程，称为最左归约，也称为规范归约规范归约。用最左推导所推导出的句型称为用最左推导所推导出的句型称为最左句型最左句型用最右推导所推导出的句型称为用最右推导所推导出的句型称为最右句型最右句型，通常称为，通常称为规范句型规范句型规范推导与规范归约规范推导与规范归约编编 译译 原原 理理2022年8月16日赋值语句赋值语句标识符标识符表达式表达式表达式表达式表达式表达式表达式表达式标识符标识符整数整数标识符标识符表达式表达式y=x+r*6语法分析的结果语法分析的结果-语法语法树树语法树与文法的二义性语法树与文法的二义性编编 译译 原原 理理2022年8月16日1.1

36、.语法树语法树：描述一个句子的语法结构：描述一个句子的语法结构Thebigelephantatethepeanut语法成分（非终语法成分（非终结符）结符）单词符号（单词符号（终结符号终结符号)编编 译译 原原 理理2022年8月16日语法树：句子结构的图示表示法，它是一种有向图，由语法树：句子结构的图示表示法，它是一种有向图，由结点和有向边组成。结点和有向边组成。结点结点：符号：符号 根结点：根结点：识别符号识别符号 中间结点：中间结点：非终结符非终结符 叶结点：叶结点：终结符或非终结符终结符或非终结符 有向边有向边：表示结点间的派生关系：表示结点间的派生关系 SUVabcd编编 译译 原原

37、理理2022年8月16日句型推导过程句型推导过程句型语法树的生长过程句型语法树的生长过程 由推导构造语法树由推导构造语法树1从从识别符号识别符号开始，开始，逐步逐步建立建立推导推导序列。序列。由由根结点根结点开始，开始，自上而下自上而下建立建立语法树语法树。编编 译译 原原 理理2022年8月16日例：例：G句型句型10=0 0=0=110=规范推导规范推导编编 译译 原原 理理2022年8月16日 由语法树构造推导由语法树构造推导2自下而上自下而上地修剪子树的末端结点，直至把整棵树剪掉地修剪子树的末端结点，直至把整棵树剪掉（留根），每剪一次对应一次规约。（留根），每剪一次对应一次规约。从句型

38、开始，从句型开始，自右向左自右向左地逐步进行地逐步进行规约规约，建立推导序列。，建立推导序列。编编 译译 原原 理理2022年8月16日01=0=10 0=规范规约与规范推导互为逆过程规范规约与规范推导互为逆过程编编 译译 原原 理理2022年8月16日课堂练习：课堂练习：对于句子对于句子ii *i ，给出两，给出两种不同的规范推导，并画出种不同的规范推导，并画出语法树语法树定义定义:若一个文法的某句子存在两个不同的若一个文法的某句子存在两个不同的最右最右(最左最左)推导推导，则该文法是则该文法是二义性二义性的，否则是无二义性的。的，否则是无二义性的。2.2.文法的二义性文法的二义性GE：EE

39、+E|E*E|(E)|i 编编 译译 原原 理理2022年8月16日EEE+EE*iiiEEE*EE+iii这两种不同的推导对应了两种不同的语法树(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编编 译译 原原 理理2022年8月16日若文法是二义性的，则在编译时就会产生若文法是二义性的，则在编译时就会产生不确定性不确定性文法的二义性是不可判定的文法的二义性是不可判定的，即不可能构造出一个算法，即不可能构造出一个算法，通过有限步骤来判定任一文法是否有二义性。通过有限步骤来判定任一文法是否有二义性。可以采用两种途径来解决文

40、法的二义性问题可以采用两种途径来解决文法的二义性问题 1不改变文法中原有的规则，仅加进一些语法的非形式规定。不改变文法中原有的规则，仅加进一些语法的非形式规定。规定规定“*”运算优先级高于运算优先级高于“+”+”运算，且服从左结合运算，且服从左结合 改写文法，把排除二义性的规则合并到原有文法中改写文法，把排除二义性的规则合并到原有文法中2编编 译译 原原 理理2022年8月16日EiET+TF*iFTFi例例:算术表达式的文法算术表达式的文法 E:=E+T|T T:=T*F|F F:=(E)|iGE：EE+E|E*E|(E)|i 编编 译译 原原 理理2022年8月16日短语与句柄短语与句柄

41、P18P18定义：设定义：设GG是一个文法，并设是一个文法，并设w=xuyw=xuy 是该文法的一个句型。若是该文法的一个句型。若*xyxy且且+u+u，则称，则称u u为句型为句型w=xuyw=xuy对非终结符对非终结符的一个的一个短语短语。若。若*xyxy且且u u，则称则称u u为句型为句型w=xuyw=xuy相对于非终结符相对于非终结符的一的一个简单个简单(直接）短语直接）短语。任何一个句型的最左。任何一个句型的最左简单短语称为柄短语（简单短语称为柄短语（句柄句柄）。）。含有终结符的短语，并且不存在也具有这含有终结符的短语，并且不存在也具有这种性质真子串的短语称为种性质真子串的短语称为

42、素短语素短语。P72P72编编 译译 原原 理理2022年8月16日 例：表达式文法例：表达式文法G G：+|+|*|()|i ()|i对句型对句型i i*()()的推导为：的推导为：*i i*i i*()()编编 译译 原原 理理2022年8月16日 *i ()对应的推导树为：对应的推导树为：表达式文法表达式文法G G：+|+|*|()|i ()|i编编 译译 原原 理理2022年8月16日语法树与短语语法树与短语 使用推导树计算句型（句子）的短语简单、明了使用推导树计算句型（句子）的短语简单、明了推导推导 *xyxy +u+u等价于：等价于：等价于：等价于：xy xy u u编编 译译 原

43、原 理理2022年8月16日因此称因此称u u是句型是句型xuyxuy(对对)的一个短语的一个短语等价于：等价于：xy u以以 为子树根的叶结点的全体为子树根的叶结点的全体编编 译译 原原 理理2022年8月16日 若子树高度为若子树高度为1 1，则，则u u还是直接还是直接 短语，最左直接短语为短语，最左直接短语为句柄句柄。若若u u是含有终结符的最小的短语，是含有终结符的最小的短语，则为则为素短语素短语，句型最左边的素，句型最左边的素短语称为短语称为最左素短语最左素短语（P72P72）。）。例：上例的文法例：上例的文法G G 和句型和句型i i*()()容易从推导树中看出：容易从推导树中看

44、出：短语：短语：i,ii,i*(),(),()()直接短语：直接短语：i i，()()句柄句柄（左直接短语）左直接短语）：i i素短语：素短语：i i，()()最左最左素短语：素短语：i i *i ()编编 译译 原原 理理2022年8月16日 例，例，找出针对左边文法的句型T+T*F+a的所有短语、简单短语(直接短语)、素短语和句柄。此句型对应的分析树为：EE+TE+TTT*FFa短语：直接短语：句柄：E E+TE TT T*FT FF （E）F aTT*FT+T*FT+T*F+aaTT*FaT素短语：T*F a最左素短语：T*F 课堂练习课堂练习设有文法设有文法GE如下：如下：EE+T|E

45、-T|TTT*F|T/F|FF（E）|id 请给出句型（请给出句型（F+id)-T*(E-T)的的所有短语、简单短语和句柄所有短语、简单短语和句柄。E EE E-T TT TF F（E E）E E+T TT TF FF FididT T*F F（E E）E E-T T短语有：短语有：F FididF+idF+id(F+id(F+id)E-TE-T（E-TE-T）T T*（E-TE-T）（F+id)-TF+id)-T*(E-T)(E-T)直接短语有：直接短语有：F F,idid,E-TE-T句柄有：句柄有：F F素短语：id E-T 最左素短语：id编编 译译 原原 理理2022年8月16日2.

46、42.4文法和语言的分类文法和语言的分类 形式语言形式语言(乔姆斯基乔姆斯基)：通过抽象，对语言进行形式化描述：通过抽象，对语言进行形式化描述用一组数学符号和规则来描述的语言称为形式语言用一组数学符号和规则来描述的语言称为形式语言 *的任何子集称作的任何子集称作 上的形式语言上的形式语言L（GS）=|VT*,S +由文法定义语言由文法定义语言 文法和语言分类：文法和语言分类：0型、型、1型、型、2型、型、3型型 这几类文法的差别在于对产生式施加不同的限制。这几类文法的差别在于对产生式施加不同的限制。编编 译译 原原 理理2022年8月16日 0型语言：型语言：L0 0型文法称为型文法称为无约束

47、短语结构文法无约束短语结构文法。规则的左部和右部都可。规则的左部和右部都可以是符号串，一个短语可以产生另一个短语。以是符号串，一个短语可以产生另一个短语。0型：型：P：:=其中其中V*且至少含有一个非终结符，且至少含有一个非终结符，V*编编 译译 原原 理理2022年8月16日0型文法型文法GS:SABS|ABABBAA0B1L(GS)=x|x是由是由n个个01或或10组成的二进制数字串，组成的二进制数字串，n1该文法产生的语言为该文法产生的语言为编编 译译 原原 理理2022年8月16日SACaBSACaBCaaaCCaaaCCBDBCBDBaBBaaBBaCBECBE aDDaaDDaAD

48、ACADACaEEaaEEaAEAE例：例：0 0型型文法文法GSGS：编编 译译 原原 理理2022年8月16日 1型文法型文法：P：A:=其中其中 AVN，V*，V 注意：注意：规则的左边的字符串长度规则的左边的字符串长度右边字符串长度右边字符串长度 1型语言：型语言：L1称为称为上下文敏感上下文敏感或或上下文有关上下文有关。也即只有在。也即只有在、这样的这样的上下文中才能把上下文中才能把A改写为改写为编编 译译 原原 理理2022年8月16日SaSBESaSBESaBESaBEBEbEBEbEaBabaBab bBbbbBbb bEbebEbeeEeeeEee例：例：1 1型（上下文有关

49、）型（上下文有关）文法文法GSGS：SACaBSACaBCaaaCCaaaCCBDBCBDBaBBaaBBaCBECBE aDDaaDDaADACADACaEEaaEEaAEAE例：例：0 0型型文法文法GSGS：编编 译译 原原 理理2022年8月16日 2型：型：P：A:=其中其中 A VN，V*2型语言：型语言：L2 称为称为上下文无关文法上下文无关文法。也即把。也即把A改写为改写为时，不必考虑上下文。时，不必考虑上下文。编编 译译 原原 理理2022年8月16日例：例：2 2型（上下文无关）文法型（上下文无关）文法 文法文法GS：SABABABS|0BS|0BSA|1SA|1 S编编

50、译译 原原 理理2022年8月16日2 2型（上下文无关）文法型（上下文无关）文法 文法文法GS：S0A|1BA1S|1B0S|0该文法产生的语言为：该文法产生的语言为：L(GS)=anbn|n1编编 译译 原原 理理2022年8月16日（右线性）P：A:=a 或 A:=aB 其中 A、B VN a VT3型语言：L3 又称正则语言.3型文法称为正则文法。它是对2型文法进行进一步限制。左线性 和右线性文法是相互等价的 注意：每个产生式右边至少有一个终结符出现注意：每个产生式右边至少有一个终结符出现（左线性）P：A:=a 或 A:=Ba 其中 A、B VN a VT 3型文法：编编 译译 原原