《引论及文法》PPT课件.ppt

《《引论及文法》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《引论及文法》PPT课件.ppt（88页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、编译原理编译原理任课教师：周长敏任课教师：周长敏任课教师：周长敏任课教师：周长敏第一章第一章编译程序概论编译程序概论1.1什么是编译程序什么是编译程序1.2编译过程概述编译过程概述1.3编译程序的结构编译程序的结构1.4编译阶段的组合编译阶段的组合1.5编译技术和软件工具编译技术和软件工具1.1什么是编译程序什么是编译程序一个编译程序就是一个语言翻译程序。它把一种语言一个编译程序就是一个语言翻译程序。它把一种语言（称作源程序）书写的程序翻译成另一种语言（称作目（称作源程序）书写的程序翻译成另一种语言（称作目标语言）的等价的程序标语言）的等价的程序 高级语言高级语言程序程序(源程序源程序)编译程

2、序编译程序低级语言程序低级语言程序低级语言程序低级语言程序1.1什么是编译程序什么是编译程序1.2编译过程概述编译过程概述词法分析词法分析语法分析语法分析语义分析语义分析中间代码生成中间代码生成代码优化代码优化目标代码生成目标代码生成编译过程概述编译过程概述词法分析阶段词法分析阶段这个阶段的任务是从左到右一个字符一个这个阶段的任务是从左到右一个字符一个字符地读入源程序对构成源程序的字符流字符地读入源程序对构成源程序的字符流进行扫描和分解。进行扫描和分解。词法分析词法分析一个一个C C源程序片断：源程序片断：int a int a;a=a+2;a=a+2;单词类型单词类型 单词值单词值 保留字保

3、留字 int int标识符标识符(变量名变量名)a a界符界符 ;标识符标识符(变量名变量名)a)a算符算符(赋值赋值)=标识符标识符(变量名变量名)a)a 算符算符(加加)+整数整数 2 2界符界符 ；语法分析语法分析语法分析的任务是在词法分析的基础语法分析的任务是在词法分析的基础依据源程序依据源程序的语法规则把源程序的单词序列组成语法短语的语法规则把源程序的单词序列组成语法短语(表示成语法树或其他的内部码表示成语法树或其他的内部码).).通过语法分析通过语法分析确定整个输入串是否构成一个语法上正确的程序确定整个输入串是否构成一个语法上正确的程序.语义分析阶段语义分析阶段审查源程序有无语义错

4、误，为代码生成阶审查源程序有无语义错误，为代码生成阶段收集类型信息。如类型检查、强制类型段收集类型信息。如类型检查、强制类型转换、检查数组下标等。转换、检查数组下标等。例如：整型数据例如：整型数据+实型数据实型数据中间代码生成中间代码生成在语义分析之后，将源程序表示成一种内在语义分析之后，将源程序表示成一种内部表示形式。部表示形式。“中间代码中间代码”是一种结构简单、含义明确是一种结构简单、含义明确的记号系统。很多编译程序采用了一种近的记号系统。很多编译程序采用了一种近似似“三地址指令三地址指令”的的“四元式四元式”。四元式的形式为四元式的形式为（运算符，运算对象（运算符，运算对象1，运，运算

5、对象算对象2，结果），结果）代码优化代码优化此阶段的任务是对前阶段产生的中间代码此阶段的任务是对前阶段产生的中间代码进行变换或进行改造，目的是使生成的目进行变换或进行改造，目的是使生成的目标代码更为高效。标代码更为高效。目标代码生成目标代码生成这一阶段的任务是把中间代码变换成特定这一阶段的任务是把中间代码变换成特定机器上的绝对指令代码或可重定位的指令机器上的绝对指令代码或可重定位的指令代码或汇编代码。代码或汇编代码。编译程序的结构编译程序的结构词法分析程序词法分析程序语法分析程序语法分析程序语义分析程序语义分析程序中间代码生成程序中间代码生成程序代码优化程序代码优化程序目标代码生成程序目标代码

6、生成程序出错处理程序出错处理程序表格管理程序表格管理程序1.4编译阶段的组合编译阶段的组合编译过程的前端（编译过程的前端（frontend）词法分析、语法分析、语义分析和中间代码生成词法分析、语法分析、语义分析和中间代码生成等等编译过程的后端编译过程的后端（backend）目标代码生成等目标代码生成等1.5编译技术和软件工具编译技术和软件工具语言的结构化编辑器语言的结构化编辑器语言程序的调试工具语言程序的调试工具语言程序测试工具语言程序测试工具高级语言之间的转换工具高级语言之间的转换工具并行编译技术并行编译技术练习题：练习题：1_是两类程序语言处理程序。是两类程序语言处理程序。A高级语言程序和

7、低级语言程序高级语言程序和低级语言程序B解释程序和编译程序解释程序和编译程序C编译程序和操作系统编译程序和操作系统D系统程序和应用程序系统程序和应用程序2、高级语言编写的程序经编译后产生的程序叫、高级语言编写的程序经编译后产生的程序叫_。A源程序源程序B目标程序目标程序C连接程序连接程序D解释程序解释程序3、编译程序是一种常用的、编译程序是一种常用的_软件。软件。A.应用应用B.系统系统C.工具工具D.测试测试4、对编译程序而言，输入数据是、对编译程序而言，输入数据是_,输出结果是输出结果是_。5、画出编译程序的总体结构图，简述各部分的主要功能。、画出编译程序的总体结构图，简述各部分的主要功能

8、。6、课本、课本P11-12页，第一章练习题第页，第一章练习题第1-4题。题。编译程序用来编译程序用来翻译翻译高级语言编写的源程序高级语言编写的源程序正如正如翻译英文翻译英文一样，要先学习英语的一样，要先学习英语的单词单词和和语法语法！语法（文法）语法（文法）：描述句子的构成规则。（例：句子描述句子的构成规则。（例：句子主语主语+谓语谓语）只需要一些）只需要一些简单的规则简单的规则就可以概括就可以概括中文句子的结构。中文句子的结构。那么高级程序语言如何用那么高级程序语言如何用简单的规则简单的规则来表示呢？来表示呢？课前思考：课前思考：描述程序语言的符号系统 第三章第三章 文法和语言文法和语言所

9、谓一个程序语言的文法是指一组规则，所谓一个程序语言的文法是指一组规则，用它可以形成和产生一个合适的程序。用它可以形成和产生一个合适的程序。3.1 3.1 文法的直观概念文法的直观概念3.2 3.2 符号和符号串符号和符号串3.3 3.3 文法和语言的形式定义文法和语言的形式定义3.4 3.4 文法的类型文法的类型3.5 3.5 上下文无关文法及其语法树上下文无关文法及其语法树3.6 3.6 句型的分析句型的分析3.7 3.7 有关文法实用中的一些说明有关文法实用中的一些说明 =|=我我|你你|他他 =王明王明|大学生大学生|工人工人|英语英语 =是是|学习学习 =|3.1文法的直观概念文法的直

10、观概念有了以上规则，即可推导出（产生）句子有了以上规则，即可推导出（产生）句子有了以上规则，即可推导出（产生）句子有了以上规则，即可推导出（产生）句子 寻找寻找=左端的带有左端的带有 的规则并把的规则并把它表示成它表示成=右端的符号串，这个动作表示右端的符号串，这个动作表示成：成：=，然后再得，然后再得到的串到的串 中，选取中，选取 或或 ，再用相应的规则，再用相应的规则=右端代替，重复右端代替，重复下去，得到句子。下去，得到句子。“我是大学生我是大学生”的推导过程的推导过程=我我我我 =我我我我 =我是我是我是我是 =我是我是我是我是 =我是大学生我是大学生我是大学生我是大学生同样，还可以推

11、导出同样，还可以推导出同样，还可以推导出同样，还可以推导出“王明是大学生王明是大学生王明是大学生王明是大学生”，“我学习英我学习英我学习英我学习英语语语语”等无数句子。因此可以说：等无数句子。因此可以说：等无数句子。因此可以说：等无数句子。因此可以说：文法文法文法文法是以是以是以是以有穷集合有穷集合有穷集合有穷集合刻画刻画刻画刻画无穷集合无穷集合无穷集合无穷集合的一种工具。的一种工具。的一种工具。的一种工具。规则集规则集句子集合句子集合C C语言的基本符号有语言的基本符号有if,while,forif,while,for,字母、数字和字母、数字和+、-、（、）、（、）、=等分界符，由这些符号组

12、成的各种等分界符，由这些符号组成的各种可能序列的符号串构成一个无穷的集合，而可能序列的符号串构成一个无穷的集合，而C C语言就语言就是这个集合的子集。是这个集合的子集。英语的基本符号有英语的基本符号有2626个字母和一些标点符号个字母和一些标点符号，由这，由这些基本符号所组成的各种可能序列的符号串构成一个些基本符号所组成的各种可能序列的符号串构成一个无穷的集合，而英语就是这个集合的子集。无穷的集合，而英语就是这个集合的子集。3.2符号和符号串符号和符号串 字母表字母表：元素的非空有穷集合，字母表中的：元素的非空有穷集合，字母表中的元素又称为符号，因此字母表也称为符号表元素又称为符号，因此字母表

13、也称为符号表（语（语言的基本符号集合）言的基本符号集合）符号串符号串：由字母表中的符号组成的任何有穷：由字母表中的符号组成的任何有穷序列称为符号串序列称为符号串（各种句子）（各种句子）=0 =0，1 1 符号串有符号串有01 11 1001 11 10 A=a A=a，b b，c c 符号串有符号串有a a，b b，c c，abab，aacaaaca3.2符号和符号串符号和符号串任何一种语言都是由该语言的任何一种语言都是由该语言的基本符号基本符号所组成的符所组成的符号串集合的子集。号串集合的子集。符号串符号串符号顺序不同，符号串不同符号顺序不同，符号串不同 ab ab和和baba不同不同可以使

14、用字母表示符号串可以使用字母表示符号串 x=STR x=STR符号串的长度：符号串的长度：如果某符号串如果某符号串x x中有中有m m个符号，则个符号，则其长度为其长度为m m，表示为，表示为|x|=m|x|=m 001110 001110的长度为的长度为6 6空符号串：空符号串：即不包含任何符号的符号串，用即不包含任何符号的符号串，用表表示，长度为示，长度为0 0，即，即|=0|=0符号串的运算符号串的运算符号串的头尾，固有头和固有尾：符号串的头尾，固有头和固有尾：如果如果z=xyz=xy是一符号串，那么是一符号串，那么x x是是z z的头，的头，y y是是z z的尾，如果的尾，如果x x是

15、非空是非空的，那么的，那么y y是固有尾；同样如是固有尾；同样如果果y y非空非空，那么，那么x x是固有头是固有头 设设z=abcz=abc，那么，那么 z z的头（前缀）：的头（前缀）：,a a，abab，abcabc 固有头：固有头：,a a，abab 尾（后缀）：尾（后缀）：，c c，bcbc，abcabc 固有尾：固有尾：，c c，bcbcZ=aabb,Z=aabb,求符号串求符号串Z Z的头尾，固有头和固有尾的头尾，固有头和固有尾练习：练习：符号串的省略写法符号串的省略写法省略写法：省略写法：强调头：强调头：z=xz=x 强调某符号在符号串中某处出现：强调某符号在符号串中某处出现：

16、z=xz=x 强调符号是符号串的第一个符号：强调符号是符号串的第一个符号：z=az=a符号串的运算符号串的运算符号串的连接：符号串的连接：设设x x和和y y是符号串，他们的连接是符号串，他们的连接xyxy是把是把y y的符号写在的符号写在x x的符号之后得到的符号串的符号之后得到的符号串 x=ST x=ST，y=abuy=abu xy=STabu xy=STabu|x|=2|x|=2，|y|=3|y|=3，|xy|=5|xy|=5 特殊的连接：特殊的连接：x=x=xx=x=x 符号串的运算符号串的运算符号串的方幂：符号串的方幂：设设x x是符号串，把是符号串，把x x自身连接自身连接n n次

17、得到符号串次得到符号串z z，即，即z=xxxxz=xxxx，称为符号串，称为符号串x x的的方幂方幂，写作，写作z=xz=xn n，即把符号串即把符号串x x相继地重复写相继地重复写n n次次 x x0 0=，x x1 1=x=x，x x2 2=xx=xx，x x3 3=xxx=xxx x=AB x=AB，x x0 0=，x x1 1=AB=AB，x x2 2=ABAB=ABAB，x x3 3=ABABAB=ABABAB 对于对于n0n0，有，有x xn n=xx=xxn-1n-1=x=xn-1n-1x x符号串的运算符号串的运算符号串集合：符号串集合：符号串集合：符号串集合：若集合若集合若

18、集合若集合A A A A中的一切元素都是某字母中的一切元素都是某字母中的一切元素都是某字母中的一切元素都是某字母表上的符号串，则称表上的符号串，则称表上的符号串，则称表上的符号串，则称A A A A为该字母表上的符号串集为该字母表上的符号串集为该字母表上的符号串集为该字母表上的符号串集合合合合（简单说法：由许多符号串组成的集合）（简单说法：由许多符号串组成的集合）（简单说法：由许多符号串组成的集合）（简单说法：由许多符号串组成的集合）例如：两个符号串集合例如：两个符号串集合例如：两个符号串集合例如：两个符号串集合A A A A和和和和B B B B的乘积表示为：的乘积表示为：的乘积表示为：的乘

19、积表示为：AB=xy|xA AB=xy|xA AB=xy|xA AB=xy|xA且且且且yByByByB，即，即，即，即ABABABAB是满足是满足是满足是满足x x x x属于属于属于属于A A A A，y y y y属属属属于于于于B B B B的所有符号串的所有符号串的所有符号串的所有符号串xyxyxyxy所组成的集合所组成的集合所组成的集合所组成的集合符号串的运算符号串的运算例如：例如：例如：例如：A=aA=aA=aA=a，bbbb，B=cB=cB=cB=c，dddd 则集合则集合则集合则集合AB=acAB=acAB=acAB=ac，adadadad，bcbcbcbc，bdbdbdbd

20、对任意符号串对任意符号串对任意符号串对任意符号串x x x x，有，有，有，有x=x=xx=x=xx=x=xx=x=x，所以有，所以有，所以有，所以有A=A=AA=A=AA=A=AA=A=A*：表示字母表表示字母表表示字母表表示字母表上的所有有穷长的串的集合上的所有有穷长的串的集合上的所有有穷长的串的集合上的所有有穷长的串的集合 =0 =0 =0 =0，1111，即，即，即，即*=，0 0 0 0，1 1 1 1，00000000，01010101，10101010，11111111，000000000000，001001001001，010010010010，符号串的运算符号串的运算也可将也

21、可将*表示为字母表表示为字母表的方幂形式：的方幂形式：*=0 01 12 2n n*称为集合称为集合的的闭包闭包 +=1 12 2n n称为集合称为集合的的正闭包正闭包显然显然 有有*=0 0+，+=*=*(试证试证明看？）明看？）集合的正闭包和集合的闭包集合的正闭包和集合的闭包集合集合的闭包比正闭包多个的闭包比正闭包多个!3.3 3.3 文法和语言的形式定义文法和语言的形式定义=|=我我|你你|他他=王明王明|大学生大学生|工人工人|英语英语=是是|学习学习=|=我我=我我=我是我是=我是我是=我是大学生我是大学生非终结符非终结符终结符终结符产生式产生式开始符号开始符号终结符号：终结符号：是

22、一个语言不可再分的基本符号，如：标示是一个语言不可再分的基本符号，如：标示符、常数、算符、界符等。符、常数、算符、界符等。非终结符号：非终结符号：用来代表语法范畴，是由终结符号和非终用来代表语法范畴，是由终结符号和非终结符号组成的符号串，如：表达式、语句、子程序、函结符号组成的符号串，如：表达式、语句、子程序、函数等。数等。开始符号：开始符号：是一个特殊的非终结符号，代表语言中我们是一个特殊的非终结符号，代表语言中我们最感兴趣的语法范畴。最感兴趣的语法范畴。产生式：产生式：也称规则也称规则3.3 3.3 文法和语言的形式定义文法和语言的形式定义文法即是用规则（产生式）来描述语言：文法即是用规则

23、（产生式）来描述语言：语语言中的每个句子可以用严格定义的规则来言中的每个句子可以用严格定义的规则来构造构造文法的定义文法的定义推导的概念推导的概念句型、句子和语言的定义句型、句子和语言的定义3.3 3.3 文法和语言的形式定义文法和语言的形式定义规则：也称为重写规则、产生式或生成式规则：也称为重写规则、产生式或生成式是形如是形如 或或=的的(,)有序对有序对其中其中 称为规则的左部，称为规则的左部，称为规则的右部。称为规则的右部。或或=读作读作“定义为定义为”例如：例如：A Aaa文法文法G G定义为四元组定义为四元组(V(VN N，V VT T，P P，S)S)其中其中 V VN N：非终结

24、符号非终结符号(或语法实体，或变量或语法实体，或变量)集；集；V VT T：终结符号集；构成语言文法的单词，是语法成分的最小单终结符号集；构成语言文法的单词，是语法成分的最小单位。位。P P：规则规则()的集合，的集合，(V VN N VVT T )*，且至少包含一个非，且至少包含一个非终结符，终结符，(V VN N VVT T )*；S S：称作识别符号或开始符号的一个非终结符，它至少要在一称作识别符号或开始符号的一个非终结符，它至少要在一条产生式中作为左部出现。条产生式中作为左部出现。V VN N，V VT T和和P P是非空有穷集。是非空有穷集。V VN N和和V VT T不含公共的元素

25、即不含公共的元素即VN VT=用用V V表示表示V VN N V VT T ，称为文法，称为文法G G的字母表或字汇表的字母表或字汇表文法的定义文法的定义文法的定义文法的定义例例 文法文法G=G=（V VN N，V VT T，P P，S S）V VN N=S,V=S,VT T=0,1 =0,1 P=S0S1,S01 P=S0S1,S01 S S为开始符号为开始符号文法的写法文法的写法(1)G(1)G：SaAb SaAb Aab Aab AaAb AaAb A A(2)GS(2)GS：SaSb SaSb Aab Aab AaAb AaAb A A (3)GS:SaSb(3)GS:SaSb Aab

26、|aAb|Aab|aAb|习惯：习惯：第一条产生式左部是识别符，用第一条产生式左部是识别符，用括起的是括起的是非终结符，不用非终结符，不用的是终结符，或大写字母表示的是终结符，或大写字母表示非终结符，小写字母表示终结符非终结符，小写字母表示终结符直接推导直接推导“”：是文法是文法G的产生式（或规则），若有的产生式（或规则），若有v,w满足：满足：v=,w=,其中其中V*,V*，则称，则称v直接直接推推导导到到w,记作记作 v w，也称，也称w直接直接归约归约到到v例：例：G：S0S1，S01 0S1 00S11 00S11 000S111 000S111 00001111 S 0S1推导的定义

27、推导的定义推导的定义推导的定义 若存在若存在v=wv=w0 0 w w1 1 .w wn n=w,(n0)=w,(n0)则记为则记为v vw w，称作，称作v v推导出推导出w w，或，或w w归约到归约到v v，推导长度为，推导长度为n n 若有若有v vw w或或 v=w v=w，则记为则记为v vw w+*例：例：G：S0S1，S01 0S1 00S11 00S11 000S111 000S111 00001111 S 0S1 00S11 000S111 00001111 S 00001111+句型、句子的定义句型、句子的定义句型句型有文法有文法G G，若，若S S=x x，则称，则称x

28、 x是文法是文法G G的句型。的句型。句子句子有文法有文法G G，若，若S S=x x，且，且xVxVT T*，则称，则称x x是文法是文法G G的的句子。句子。例：例：G G：S0S1 S0S1，S01 S01S S 0S1 0S1 00S11 00S11 000S111 000S111 0000111100001111G G的句型的句型S S，0S10S1，00S1100S11，000S111000S111，0000111100001111G G的句子的句子0000111100001111，0101*句型、句子句型、句子例：例：GEGE：EE+T|T EE+T|T TT*F|F TT*F|

29、F F(E)|a F(E)|aE EE+T E+T T+T T+T F+T F+T a+T a+T a+T*Fa+T*F a+F*F a+F*F a+a*F a+a*F a+a*aa+a*a句子：用符号句子：用符号a a，+，*，(和和)构成的算术表达构成的算术表达式式(文法生成的文法生成的)语言的定义语言的定义 由文法由文法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：S0S1，S01 L(G)=0

30、n1n|n1*例例 文法文法GSGS：（1 1）SaSBESaSBE（2 2）SaBESaBE（3 3）EBBEEBBE（4 4）aBabaBab（5 5）bBbbbBbb（6 6）bEbebEbe（7 7）eEeeeEee L L（G G）=a=an nb bn ne en n|n1|n1 G G生成的每个串都在生成的每个串都在L(G)L(G)中中L(G)L(G)中的每个串确实能被中的每个串确实能被G G生成生成文法的等价文法的等价若若L L（G G1 1）=L=L（G G2 2），则称文法），则称文法G G1 1和和G G2 2是等价的。是等价的。如文法如文法G G1 1AA：A0R A0

31、R 与与G G2 2SS：S0S1 S0S1 等价等价 A01 S01 A01 S01 RA1 RA13.4 3.4 文法的类型文法的类型通过对产生式施加不同的限制，通过对产生式施加不同的限制，ChomskyChomsky将文法分为四种类型：将文法分为四种类型：0 0型文法：型文法：对任一产生式对任一产生式，都有，都有(V(VN NVVT T)*，且至，且至少含有一个非终结符，少含有一个非终结符，(V(VN NVVT T)*1 1型文法（上下文有关）型文法（上下文有关）：对任一产生式：对任一产生式，都有，都有|，仅仅仅仅 S S除外除外2 2型文法（上下文无关）型文法（上下文无关）：对任一产生

32、式对任一产生式，都有，都有VVN N，(V(VN NVVT T)*3 3型文法（正规文法）：型文法（正规文法）：任一产生式任一产生式的形式都为的形式都为AaBAaB或或AaAa，其中，其中AVAVN N ，BVBVN N ，aVaVT T*文法的类型文法的类型例：例：1 1型（上下文有关）文法型（上下文有关）文法 文法文法GSGS：SCD SCDAbbAAbbA CaCA CaCABaaBBaaB CbCB CbCBBbbBBbbBADaDADaD Ca CaBDbDBDbD Db DbAabDAabD文法的类型文法的类型例：例：2 2型（上下文无关）文法型（上下文无关）文法 文法文法GS：S

33、ABABS|0BSA|13 3型文法型文法GS：S0A|1B|0A0A|1B|0SB1B|1|00型文法型文法1型文法型文法文法的类型文法的类型四类文法之间的逐级“包含”关系2型文法型文法3 3型文法型文法 四种文法之间的四种文法之间的关系关系 是将产生式做是将产生式做进一步限制而定义的。进一步限制而定义的。文法和语言文法和语言0 0 0 0型文法型文法型文法型文法产生的语言称为产生的语言称为产生的语言称为产生的语言称为0 0 0 0型语言型语言型语言型语言1 1 1 1型文法型文法型文法型文法或上下文有关文法或上下文有关文法或上下文有关文法或上下文有关文法产生的语言称为产生的语言称为产生的语

34、言称为产生的语言称为1 1 1 1型语言型语言型语言型语言或上下文有关或上下文有关或上下文有关或上下文有关语言语言语言语言2 2 2 2型文法型文法型文法型文法或上下文无关文法或上下文无关文法或上下文无关文法或上下文无关文法产生的语言称为产生的语言称为产生的语言称为产生的语言称为2 2 2 2型语言型语言型语言型语言或上下文无关或上下文无关或上下文无关或上下文无关语言语言语言语言3 3 3 3型文法型文法型文法型文法或正则（正规）文法或正则（正规）文法或正则（正规）文法或正则（正规）文法产生的语言称为产生的语言称为产生的语言称为产生的语言称为3 3 3 3型语型语型语型语言言言言正则（正规）正

35、则（正规）正则（正规）正则（正规）语言语言语言语言说明说明0 0型文法型文法（短语结构文法）的能力相当于图灵机，（短语结构文法）的能力相当于图灵机，可以表征任何递归可枚举集，而且任何可以表征任何递归可枚举集，而且任何0 0型语言型语言都是递归可枚举的都是递归可枚举的1 1型文法型文法（上下文有关文法）：产生式的形式为（上下文有关文法）：产生式的形式为1 1AA2 21 12 2，即只有，即只有A A出现在出现在1 1和和2 2的上的上下文中时，才允许下文中时，才允许取代取代A A。2 2型文法型文法（上下文无关文法（上下文无关文法CFGCFG）：产生式的形式）：产生式的形式为为AA，取代取代A

36、 A时与时与A A的上下文无关。的上下文无关。3.5 3.5 上下文无关文法及其语法树上下文无关文法及其语法树 上下文无关文法有足够的能力描上下文无关文法有足够的能力描述程述程序设计语言的语法结构序设计语言的语法结构。如无特别说明，。如无特别说明，“文法文法”均指上下文无关文法。均指上下文无关文法。语法树语法树-句型推导句型推导的直观表示的直观表示语法树语法树设设G=(VG=(VN N，V VT T，P P，S)S)为一上下文无关文法，若一棵树满足下为一上下文无关文法，若一棵树满足下列列4 4个条件，则此树称作个条件，则此树称作G G的语法树的语法树(推导树推导树)()(派生树）：派生树）：1

37、.1.每个结点都有一个标记，此标记是每个结点都有一个标记，此标记是V V的一个符号的一个符号2.2.根的标记是根的标记是S S3.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 2，A Ak k，那么，那么AAAA1 1A A2 2，A Ak k一定是一定是P P中的一个产生式中的一个产生式语法树的结果：

38、语法树的结果：从左到右读出叶子的标记而构成的行称为句型从左到右读出叶子的标记而构成的行称为句型上下文无关文法的语法树上下文无关文法的语法树句型句型a aa abbaabbaa的可能的可能推导序列和语法树推导序列和语法树 例例:GS:SaASASbAASSSaAbaSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa S a A S S b A a a b a规范推导规范推导 规范句型规范句型 最左（最右）推导：在推导的任何最左（最右）推导：在推导的任何一步一步，其中，其中、是句型，都是对是句型，都

39、是对中的最左（右）非终结符进行替换中的最左（右）非终结符进行替换 最右推导被称为规范推导。最右推导被称为规范推导。由规范推导所得的句型称为规范句型由规范推导所得的句型称为规范句型给定文法给定文法G=(VG=(VN N，V VT T，P P，S)S)，对于，对于G G的任何句型都的任何句型都能构造与之关联的语法树能构造与之关联的语法树(推导树推导树)一棵语法树表示了一个句型的种种可能的一棵语法树表示了一个句型的种种可能的(但未但未必是所有的必是所有的)不同推导过程，包括最左不同推导过程，包括最左(最右最右)推推导。但是，一个句型是否只对应唯一的一棵语法导。但是，一个句型是否只对应唯一的一棵语法树

40、呢树呢?一个句型是否只有唯一的一个最左一个句型是否只有唯一的一个最左(最右最右)推导呢推导呢例：例：例：例：GE:GE:E iE iE E+EE E+EE E*EE E*EE (E)E (E)E E E+E E+E E*E i E*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+E i*i+E i*i+i二义文法二义文法若一个文法存在某个句子对应两棵不同的语法树，若一个文法存在某个句

41、子对应两棵不同的语法树，若一个文法存在某个句子对应两棵不同的语法树，若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是则称这个文法是则称这个文法是则称这个文法是二义二义的，或者，若一个文法存在的，或者，若一个文法存在的，或者，若一个文法存在的，或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这某个句子有两个不同的最左（右）推导，则称这某个句子有两个不同的最左（右）推导，则称这某个句子有两个不同的最左（右）推导，则称这个文法是个文法是个文法是个文法是二义二义的的的的文法的二义性和语言的二义性是两个不同的概念。文法的二义性和语言的二义性是两个不同的概念。文法的二义性和语言的二义

42、性是两个不同的概念。文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同的文法因为可能有两个不同的文法因为可能有两个不同的文法因为可能有两个不同的文法G G G G和和和和GGGG，其中，其中，其中，其中G G G G是二是二是二是二义的，但是却有义的，但是却有义的，但是却有义的，但是却有L(G)=L(G)L(G)=L(G)L(G)=L(G)L(G)=L(G)，也就是说，这两，也就是说，这两，也就是说，这两，也就是说，这两个文法所产生的语言是相同的。个文法所产生的语言是相同的。个文法所产生的语言是相同的。个文法所产生的语言是相同的。如果产生上下文无关语言的每一个文法都是二义的，则说如

43、果产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的。对于一个程序设计语言来说，常常此语言是先天二义的。对于一个程序设计语言来说，常常希望它的文法是无二义的，因为希望对它的每个语句的分希望它的文法是无二义的，因为希望对它的每个语句的分析是唯一的。析是唯一的。判定任给的一个上下文无关文法是否二义，或它是否产生判定任给的一个上下文无关文法是否二义，或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不可一个先天二义的上下文无关语言，这两个问题是递归不可解的，但可以为无二义性寻找一组充分条件解的，但可以为无二义性寻找一组充分条件二义文法改造为无二义文法二义文法改造为无二义文法GE

44、:E i GEGE:E i GE：E T|E+T E T|E+T E E+E T F|T*F E E+E T F|T*F E E*E F E E*E F （E E）|i|i E (E)E (E)规定算符优先性和结合性规定算符优先性和结合性规定算符优先性和结合性规定算符优先性和结合性文法的二义性和语言的二义性文法的二义性和语言的二义性3.6 3.6（上下文无关文法）句型的分析（上下文无关文法）句型的分析句型分析句型分析就是识别一个符号串是否为某文法的句型，就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。是某个推导的构造过程。在语言的编译实现中，把完成句型分析的程序称为在语言的编译实现

45、中，把完成句型分析的程序称为分析程序分析程序或或识别程序识别程序。分析算法又称。分析算法又称识别算法识别算法。从左到右的分析算法从左到右的分析算法，即总是从左到右地识别输入，即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号，直到分析结束。次识别右边的一个符号，直到分析结束。句型的分析算法分类句型的分析算法分类分析算法可分为：分析算法可分为：自上而下分析法自上而下分析法：从文法的开始符号出发，反复使用文法的产生式，从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导，或者说，为输入寻找与输入符号串匹

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

47、语法树的结果，自底向上的构造语法树自上而下的语法分析自上而下的语法分析例：文法例：文法G：S cAd A ab A a识别输入串识别输入串w=cabd是否为该文法的句子是否为该文法的句子SSScAdcAd a b推导过程：推导过程：S cAd cAd cabd自下而上的语法分析自下而上的语法分析例：文法例：文法G G：S cAd S cAd A ab A ab A a A a识别输入串识别输入串w=cabdw=cabd是否该文法的句子是否该文法的句子SAA c a b d c a b d c a b d 规约规约过程构造的推导：过程构造的推导：cAd cabd S cAd自上而下的语法分析自上

48、而下的语法分析(1)S cAd (2)A ab(3)A a 识别输入串识别输入串w=cad是否为该文法的句子是否为该文法的句子若若S S cAd cAd 后选择后选择(2)(2)扩展扩展A A，S S cAd cAd cabd cabd那将会？那将会？w w的第二个符号可以与叶子结的第二个符号可以与叶子结点点a a得以匹配，但第三个符得以匹配，但第三个符号却不能与下一叶子结点号却不能与下一叶子结点d d匹配，宣告分析失败（其匹配，宣告分析失败（其意味着，识别程序不能为意味着，识别程序不能为串串cadcad构造语法树，即构造语法树，即cadcad不是句子）不是句子）-显然是错误的结论。显然是错误

49、的结论。导致失败的原因是在分析中对导致失败的原因是在分析中对A A的选择不是正确的。的选择不是正确的。S c A d a b 这时应该回溯，把这时应该回溯，把A A为根的子为根的子树剪掉，扫描过的输入串中树剪掉，扫描过的输入串中的的A A吐出来，再试探用产生式吐出来，再试探用产生式（3 3）句型分析的有关问题句型分析的有关问题1 1）在自上而下的分析方法中）在自上而下的分析方法中如何如何选择选择使用使用哪个哪个产生式进产生式进行推导行推导？假定要被代换的最左非终结符号是假定要被代换的最左非终结符号是B B，且有，且有n n条规则：条规则：BABA1 1|A|A2 2|A|An n，那么如何确定

50、用哪个右部去替代，那么如何确定用哪个右部去替代B B？2 2）在自下而上的分析方法中）在自下而上的分析方法中如何如何识别可归约的串识别可归约的串？在分析程序工作的每一步，都是从当前串中在分析程序工作的每一步，都是从当前串中选择一个选择一个子子串串，将它，将它归约归约到到某个非终结符号某个非终结符号，该子串称为，该子串称为“可归约可归约串串”短语短语 直接短语直接短语 句柄句柄G G是一文法，是一文法，S S是文法的开始符号，是文法的开始符号，是文是文法法G G的一个句型。如果有的一个句型。如果有S SAA且且 A A 则称则称是句型是句型相对于非终结符相对于非终结符A A的短语。如有的短语。如