高级语言及其语法描述课件.ppt-得力文库

资源描述

《高级语言及其语法描述课件.ppt》由会员分享，可在线阅读，更多相关《高级语言及其语法描述课件.ppt（86页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、高级语言及其语法描述第1页，此课件共86页哦2.2.4 2.2.4 语句与控制结构语句与控制结构第2页，此课件共86页哦一一表达式表达式概念概念一个表达式是由运算量（亦称操作一个表达式是由运算量（亦称操作数，即数据引用或函数调用）和算符组数，即数据引用或函数调用）和算符组成的。成的。X+Y二元算符左运算量右运算量2.2.4 语句与控制结构语句与控制结构第3页，此课件共86页哦运算符一元算符前缀:一元算符写在运算量的前面例子:-X,B后缀:一元算符写在运算量的后面例子:P既是一元算符又是二元算符“-”二元算符中缀:二元算符写在两个运算量之间例子:X+Y前缀:二元算符写在两个运算量之前例子:+

2、XY后缀:二元算符写在两个运算量之后例子:XY+2.2.4 语句与控制结构语句与控制结构第4页，此课件共86页哦表达式的形成规则表达式的形成规则（1 1）变量（包括下标变量）、常数是表达）变量（包括下标变量）、常数是表达式；式；（2 2）若）若E1E1、E2E2为表达式，为表达式，为二元算符，为二元算符，则则 E1 E2E1 E2为表达式为表达式(一般用中缀形式一般用中缀形式)；（3 3）若）若E E为表达式，为表达式，为一元算符，则为一元算符，则E(E(或或E)E)为表达式；为表达式；（4 4）若）若E E为表达式，则（为表达式，则（E)E)是表达式。是表达式。例子例子2.2.4 语句与控制

3、结构语句与控制结构第5页，此课件共86页哦例子1X1+x(1+x)-(1+x)2.2.4 语句与控制结构语句与控制结构第6页，此课件共86页哦表达式的运算顺序和结合性与通常的数学习惯一致例如:先乘除后加减,乘幂更优先结合性对于同级算符,先左后右(左结合)或先右后左(右结合)2.2.4 语句与控制结构语句与控制结构第7页，此课件共86页哦练习X+Y*ZX-Y-ZX-Y+ZX*Y*ZX+Y2.2.4 语句与控制结构语句与控制结构第8页，此课件共86页哦在多数语言中算术算符和逻辑算符的优先顺序一般规在多数语言中算术算符和逻辑算符的优先顺序一般规定如下：定如下：乘幂乘幂（*或或）一元负一元负（

4、-）乘、除乘、除（*，/，）加、减加、减（+，-）关系符关系符（,=,=),=,=)非非（，not,not,或或 .NOT.).NOT.)与与（，&,and&,and 或或 .AND.).AND.)或或（，or or 或或 .OR.).OR.)隐含隐含（或或 imp)imp)等值等值（,或或 equi )equi )2.2.4 语句与控制结构语句与控制结构第9页，此课件共86页哦讨论:不同语言对算符优先级和结合性的差异APL:右结合X-Y+ZX-(Y+Z)ALGOL:左结合X-Y+Z(X-Y)+ZFORTRAN:对于满足左或右结合的算符,任取其一;对于满足交换率的算符，左右运算

5、量的计算顺序不加限制2.2.4 语句与控制结构语句与控制结构第10页，此课件共86页哦算符的代数性质（交换率、结合率和算符的代数性质（交换率、结合率和分配率）常常可用来优化目标程序的质分配率）常常可用来优化目标程序的质量量。但是必须注意两点：但是必须注意两点：（1 1）代数性质引用到什么程度视具代数性质引用到什么程度视具体语言的不同而不同。如在体语言的不同而不同。如在ALGOLALGOL中把中把 A*B+C*D A*B+C*D 处理成处理成C*D+A*B,C*D+A*B,则至少是对则至少是对ALGOLALGOL不够忠实。不够忠实。（2 2）数学上成立的代数性质在计算机）数学上成立的代数性质在

6、计算机上未必完全成立。如：上未必完全成立。如：(A+B)+C=A+(B+C)(A+B)+C=A+(B+C)在计算机上并不普遍成立。在计算机上并不普遍成立。2.2.4 语句与控制结构语句与控制结构第11页，此课件共86页哦不同类型的数据运算0.5+3ALGOL允许FORTRAN禁止C+允许,但要做类型转换2.2.4 语句与控制结构语句与控制结构第12页，此课件共86页哦二二语句语句不同程序语言含有不同形式和功能的各种语句。从不同程序语言含有不同形式和功能的各种语句。从功能上说语句大体可分功能上说语句大体可分:执行性语句执行性语句执行性语句旨在描述程序的动作。执行性语句又可分执行性语句旨在描述程

7、序的动作。执行性语句又可分赋值语句赋值语句控制语句控制语句输入输入/输出语句输出语句.说明性语句说明性语句说明性语句旨在定义不同数据类型的变量或运算。说明性语句旨在定义不同数据类型的变量或运算。从形式上说，语句还可分为简单句、复合句和分程从形式上说，语句还可分为简单句、复合句和分程序等。序等。2.2.4 语句与控制结构语句与控制结构第13页，此课件共86页哦1 1 赋值语句赋值语句我们知道，每个名字有两方面的特征：我们知道，每个名字有两方面的特征：一方面它代表一定的存储单元，另一方一方面它代表一定的存储单元，另一方面它又以该单元的内容作为面它又以该单元的内容作为值值。70weight0100

8、Normal=(height-100)*weightWeight=802.2.4 语句与控制结构语句与控制结构第14页，此课件共86页哦赋值语句的意义赋值语句赋值语句A:=BA:=B的意义是：的意义是：“把把B B的值送入的值送入A A所代表的所代表的单元单元”也就是说：在赋值也就是说：在赋值句中，赋值号句中，赋值号：=左右左右两边的变量名扮演着两种两边的变量名扮演着两种不同的角色。对赋值号右不同的角色。对赋值号右边的边的B B我们需要的是它的值；我们需要的是它的值；对于左边的对于左边的A A我们需要的我们需要的是它们的所代表的存储是它们的所代表的存储单元（的地址）。单元（的地址）。70010

9、01000900ABA:=B2.2.4 语句与控制结构语句与控制结构第15页，此课件共86页哦左值与右值为了区分一个名字的这两种特征，我们把为了区分一个名字的这两种特征，我们把一个名字所代表的那个存储单元（地址）一个名字所代表的那个存储单元（地址）称为该名字的称为该名字的左值左值；把一个名字的值称为；把一个名字的值称为该名字的该名字的右值右值。回顾C+的左值和右值概念2.2.4 语句与控制结构语句与控制结构第16页，此课件共86页哦进一步讨论变量既可持有左值又持有右值常数和带有算符的表达式一般持有右值指示器变量P,P既持有左值有持有右值出现在赋值号左边的表达式必须持有左值出现在赋值号右边的表达

10、式只需持有右值对于出现在赋值号右边表达式中的变量,我们要其右值(a=4)=28+(+a)+(a+)2.2.4 语句与控制结构语句与控制结构第17页，此课件共86页哦(a=4)=28+(+a)+(a+)2.2.4 语句与控制结构语句与控制结构第18页，此课件共86页哦2 2 控制语句控制语句多数语言中所含的控制语句有：多数语言中所含的控制语句有：无条件转移语句无条件转移语句:goto L:goto L条件语句：条件语句：if B then Sif B then S if B then S1 else S2 if B then S1 else S2循环与句：循环与句：while B do Swhi

11、le B do S repeat S until B repeat S until B for i:=E1 step E2 until E3 do S for i:=E1 step E2 until E3 do S过程调用语句：过程调用语句：call P(X1,X2,call P(X1,X2,Xn),Xn)返回语句：返回语句：return(E)return(E)重要的是我们必须了解这些语句在不同语言中的不重要的是我们必须了解这些语句在不同语言中的不同含义。同含义。2.2.4 语句与控制结构语句与控制结构第19页，此课件共86页哦3 3 说明语句说明语句说明语句旨在定义名字的性质。编译程说明语

12、句旨在定义名字的性质。编译程序把这些性质登记在符号表中，并检查程序把这些性质登记在符号表中，并检查程序中名字的引用和说明是否相一致。许多序中名字的引用和说明是否相一致。许多说明语句没有相应的代码。但有些语句，说明语句没有相应的代码。但有些语句，如过程说明语句，和可变数组说明语句则如过程说明语句，和可变数组说明语句则有相应的目标代码。有相应的目标代码。2.2.4 语句与控制结构语句与控制结构第20页，此课件共86页哦4 4 简单句和复合句简单句和复合句简单句是指那些不含其它语句成分的基本简单句是指那些不含其它语句成分的基本句句例如例如赋值句、赋值句、gotogoto句等。句等。复合句则指那些句

13、中有句的语句。复合句则指那些句中有句的语句。例如例如:if(x eq y)got 15:if(x eq y)got 152.2.4 语句与控制结构语句与控制结构第21页，此课件共86页哦2.3 2.3 程序语言的语法描述程序语言的语法描述本节内容是对高级语言中为编译原理课程本节内容是对高级语言中为编译原理课程所关心特性的总结所关心特性的总结对于高级程序语言及编译程序而言，语言对于高级程序语言及编译程序而言，语言的语法定义是非常重要的。本节将介绍语的语法定义是非常重要的。本节将介绍语法结构的形式描述问题。法结构的形式描述问题。第22页，此课件共86页哦首先引入几个概念首先引入几个概念设设是一个

14、是一个有穷字母表有穷字母表，它的每个元素称为一个，它的每个元素称为一个符号符号。上的一个上的一个符号串符号串是指由是指由中的符号所构成的有穷序列。中的符号所构成的有穷序列。不包含符号的序列称为不包含符号的序列称为空字空字，记为，记为。用。用*表示表示上的上的所有符号串的全体，空字也包括在其中。如：所有符号串的全体，空字也包括在其中。如：若若=a,b=a,b则则*=,a,b,aa,ab,bb,aaa,a,b,aa,ab,bb,aaa,。表示不含任何元素的表示不含任何元素的空集空集。这里要注意。这里要注意、和和的区别。的区别。2.3 程序语言的语法描述程序语言的语法描述第23页，此课件共86

15、页哦*的子集的子集U U和和V V中的中的（连接）积（连接）积定义为定义为:UV=UV=U&U&V V 即集合即集合UVUV中的符号串是由中的符号串是由U U和和V V的符号串连接而成的。的符号串连接而成的。注意，一般注意，一般UVUV VUVU，但（，但（UV)W=U(VW).UV)W=U(VW).V V自身的自身的n n次（连接）积记为：次（连接）积记为：V Vn n=V V=V VV (nV (n个个V)V)规定规定 V V0 0=.令：令：V V*=V=V0 0 V V1 1 V V2 2 称称 V V*是是V V的的闭包闭包。记记V V+=VV=VV*,称称 V V+是是V V的的正

16、则包正则包。闭包闭包V V*中的每个符号都是由中的每个符号都是由V V中的符号串经有限次连中的符号串经有限次连接而成的。接而成的。2.3 程序语言的语法描述程序语言的语法描述第24页，此课件共86页哦课堂练习已知已知=a,b=a,b，*=,a,b,aa,ab,bb,aaa,a,b,aa,ab,bb,aaa,U=U=aa,abaa,abV=V=ba,bbba,bb则则UVUVaaba,aabb,abba,abbbaaba,aabb,abba,abbbU U2 2 UU=UU=aaaa,aaab,abaa,ababaaaa,aaab,abaa,ababU U3 3 UUU=(UU)U=UUU=(U

17、U)U=aaaa,aaab,abaa,ababaaaa,aaab,abaa,ababU=U=U U*,aa,ab,aaaa,aaab,abaa,abab,aaaaaa,aa,ab,aaaa,aaab,abaa,abab,aaaaaaU U+2.3 程序语言的语法描述程序语言的语法描述第25页，此课件共86页哦2.3.1 2.3.1 上下文无关文法上下文无关文法文法是描述语言的语法结构的形式规则（即语法规则）。文法是描述语言的语法结构的形式规则（即语法规则）。要求：强描述能力，足以描述各种不同结构，有利于句子分析和翻译，可自要求：强描述能力，足以描述各种不同结构，有利于句子分析和翻译，可自动产生

18、有效的语法分析程序动产生有效的语法分析程序所谓所谓上下文无关文法上下文无关文法是这样一种文法，它所定义的语法范畴是这样一种文法，它所定义的语法范畴（或语法单位（或语法单位)是完全独立于这种范畴可能出现的环境的。是完全独立于这种范畴可能出现的环境的。例如：在程序语言中，当碰到一个算术表达式，我们完全可以对它例如：在程序语言中，当碰到一个算术表达式，我们完全可以对它“就事论事就事论事”处理，而不必考虑它所处的上下文处理，而不必考虑它所处的上下文例如：自然语言的字词句与上下文密切关系例如：自然语言的字词句与上下文密切关系上下文无关文法不能描述自然语言，但足以描述程序语言上下文无关文法不能描述自然语言

19、，但足以描述程序语言2.3 程序语言的语法描述程序语言的语法描述第26页，此课件共86页哦例子有的句子还必须结合上下文的关系才能获得正确的分析结果。例如，知道了上文是“狼来了”，理解下文“咬死了猎人的狗”时，就不会再有歧义；或者上文是“我爷爷年纪大了”，下文是“他只能算一个半劳力”，联系上下文一起分析，“一个半劳力”便只剩下一种含义。“狼来了”“我爷爷年纪大了”2.3.1 上下文无关文法上下文无关文法第27页，此课件共86页哦例子例如：“乒乓球拍卖完了”，可以切分成“乒乓球拍卖完了”“乒乓球拍卖完了”如果没有上下文其他的句子，恐怕谁也不知道“拍卖”在这里算不算一个词。“乒乓球拍卖完了”“乒乓球

20、拍卖完了”2.3.1 上下文无关文法上下文无关文法第28页，此课件共86页哦例子：一个具体的英文例句分析请仔细阅读课本请仔细阅读课本P27P27页的英文分析的例句，页的英文分析的例句，2.3.1 上下文无关文法上下文无关文法第29页，此课件共86页哦直接宾语间接宾语谓语主语Hegavemeabook思考：如果你是英语老师，学生写了这样一个英语句子，你如何判断该句子是对的？2.3.1 上下文无关文法上下文无关文法第30页，此课件共86页哦句型：句型：主语主语谓语谓语间接宾语间接宾语直接宾语直接宾语思考：假定有以下句型，如何判断“Hegavemaabook”符合该句型如果“Hegavemaa

21、book”符合该句型，则“Hegavemaabook”是一个正确的句子例子：常见英语句型2.3.1 上下文无关文法上下文无关文法第31页，此课件共86页哦思考：如何判断一个程序的语句是否正确？赋值语句赋值语句变量：表达式变量：表达式X:=3.14*r*r2.3.1 上下文无关文法上下文无关文法第32页，此课件共86页哦思考能不能将判断一个句子是否符合一个句型的过程自动化，使得今后可以通过编写程序来完成这一过程？方法：建立语法规则，用程序自动推导2.3.1 上下文无关文法上下文无关文法第33页，此课件共86页哦解决方法规则推导2.3.1 上下文无关文法上下文无关文法第34页，此课件共86页哦结论

22、结论定义英文句子的规则可以说是一个上下文无关文法。定义英文句子的规则可以说是一个上下文无关文法。其中其中He,me,book,gave,a He,me,book,gave,a 等，称为等，称为终结符号终结符号；、等为等为非终结符号非终结符号；这个文法最终是要定义这个文法最终是要定义的的语法结构语法结构，所以所以在这里成为在这里成为开始符号开始符号；这种书写形式称为这种书写形式称为产生式产生式。2.3.1 上下文无关文法上下文无关文法第35页，此课件共86页哦归纳归纳一个一个上下文无关文法上下文无关文法G包括四个组成部分：一组包括四个组成部分：一组终终结符号结符号，一组，一组非终结符非终结符

23、，一个，一个开始符号开始符号，以及一，以及一组组产生式产生式。所谓所谓终结符号终结符号乃是组成语言的基本符号，即在程序乃是组成语言的基本符号，即在程序语言中以前屡次提到的单词符号，如基本字，标语言中以前屡次提到的单词符号，如基本字，标识符，常数，算符和界符等识符，常数，算符和界符等所谓所谓非终结符号非终结符号（也称语法变量）用来代表语法（也称语法变量）用来代表语法范畴。如范畴。如“算术表达式算术表达式”、“布尔表达式布尔表达式”、“过程过程”等。一个非终结符代表一个一定的语法概等。一个非终结符代表一个一定的语法概念。因此非终结符是一个类（或集合）记号，而念。因此非终结符是一个类（或集合）记号，

24、而不是个体记号。不是个体记号。2.3.1 上下文无关文法上下文无关文法第36页，此课件共86页哦开始符号开始符号是一个特殊的非终结符号，它代表所定是一个特殊的非终结符号，它代表所定义的语言中我们最感兴趣的语法范畴，这个语法义的语言中我们最感兴趣的语法范畴，这个语法范畴通常称为范畴通常称为“句子句子”。但在程序语言中我们最。但在程序语言中我们最终感兴趣的是终感兴趣的是“程序程序”这个语法范畴，而其他的语这个语法范畴，而其他的语法范畴都只不过是构造法范畴都只不过是构造“程序程序”的一块块砖石。的一块块砖石。产生式产生式（也称为产生规则或简称（也称为产生规则或简称规则规则）是定义语法）是定义语法范畴

25、的一种书写规则。一个产生式的形式是范畴的一种书写规则。一个产生式的形式是 A ,其中箭头左边的其中箭头左边的A是一个终结符，称为产生式的是一个终结符，称为产生式的左左部部符号；箭头右边的符号；箭头右边的是终结符号或与非终结符号是终结符号或与非终结符号组成的一符号串，称为产生式的组成的一符号串，称为产生式的右部右部。2.3.1 上下文无关文法上下文无关文法第37页，此课件共86页哦产生式是定义语法范畴的。产生式是定义语法范畴的。例如：对于表达式的形成规则：例如：对于表达式的形成规则：“变量（包括下标变量）、常数是表达式变量（包括下标变量）、常数是表达式“可用产生式定义为：可用产生式定义为：算术表

26、达式算术表达式变量变量或或算术表达式算术表达式i可用巴科斯范式表示为可用巴科斯范式表示为算术表达式：变量算术表达式：变量2.3.1 上下文无关文法上下文无关文法第38页，此课件共86页哦有时需要多个产生式规则定义一个语法范畴有时需要多个产生式规则定义一个语法范畴例如：要定义一类含例如：要定义一类含+、*的算术表达式，这个定义可以这的算术表达式，这个定义可以这样给出：样给出：定义定义“变量是一个算术表达式；变量是一个算术表达式；若若E1和和E2是算术表达式，则是算术表达式，则E1+E2、E1*E2和和(E1)也是算术表达式。也是算术表达式。用产生式描述：用产生式描述：Ei（）其中代表（）其中代

27、表“算术表达式算术表达式”，代表，代表“变量变量”递归定义2.3.1 上下文无关文法上下文无关文法第39页，此课件共86页哦上下文无关文法的形式定义上下文无关文法的形式定义n上下文无关文法上下文无关文法是一个四元式（是一个四元式（，P）其中其中n是一个非空有限集，它的每一个元素是一个非空有限集，它的每一个元素称为终结符号；称为终结符号；n是一个非空有限集，它的每一个元素称为非终结符号，是一个非空有限集，它的每一个元素称为非终结符号，；n是一个非终结符号，称为开始符号；是一个非终结符号，称为开始符号；nP是一个产生式（有限）集合，每个产生式形式是是一个产生式（有限）集合，每个产生式形式是，其中

28、，其中，（）开始符号开始符号S S至至少必须在某一产生式的左部出现一次。少必须在某一产生式的左部出现一次。2.3.1 上下文无关文法上下文无关文法第40页，此课件共86页哦进一步讨论产生式缩写若干个左部相同的产生式，如：可合并为：其中ai称为侯选式箭头读为“定义为”直竖读为“或”元语言符号：2.3.1 上下文无关文法上下文无关文法第41页，此课件共86页哦书写约定非终结符号：大写字母终结符号：小写字母符号串：例子例子2.3.1 上下文无关文法上下文无关文法第42页，此课件共86页哦如何用上下文无关文法定义语言？中心思想：从文法的开始符号出发，反复连续使用产生式，对非终结符施行替换和展开例如：（

29、）（）从可直接（一步）推出（）用表示（）2.3.1 上下文无关文法上下文无关文法第43页，此课件共86页哦例子从推出（）（）（）（）（）概念：将以上一系列替换序列称为“推导推导“推导提供了一个证明证明推导每前进一步必引用一条产生式（规则）表示仅推导一步2.3.1 上下文无关文法上下文无关文法第44页，此课件共86页哦推导称=（直接推出），当且仅当-是一个产生式，且，（）*定义推导定义推导如果1=2=n，则我们称这个序列是从1到n的一个推导如果存在a1至an的一个推导,则称a1推导出an。记a1=an，表示从a1出发，经过步或若干步，可推导出an记a1an，表示从a1出发，经过步或若干步，可推导

30、出an如果，或者，或者+*+*2.3.1 上下文无关文法上下文无关文法第45页，此课件共86页哦例子（）（）（）（）称（直接推出），当且仅当是一个产生式，且，（）*（）（）-（）（）-2.3.1 上下文无关文法上下文无关文法第46页，此课件共86页哦例子（）（）（）（）（）（）（）（）因为所以有：（）（）+2.3.1 上下文无关文法上下文无关文法第47页，此课件共86页哦语言的定义假定假定G G是一个是一个文法文法，S S是它的开始符号。如果是它的开始符号。如果S S*(表表示从示从S S出发，经出发，经0 0步或若干步可推出步或若干步可推出），则称），则称是是一个一个句型句型。仅含终结符号

31、的句型是一个。仅含终结符号的句型是一个句子句子。文。文法法G G所产生的句子的全体是一个所产生的句子的全体是一个语言语言，将它记为，将它记为L(G).L(G).L(G)=L(G)=|S|S+&VVT T*2.3.1 上下文无关文法上下文无关文法第48页，此课件共86页哦例子n例如：例如：n终结符号串终结符号串（i*i+i)i*i+i)是文法是文法nEE+E|E*E|(E)|EE+E|E*E|(E)|(2.1)(2.1)n的一个的一个句子句子。是因为有。是因为有nE E(E)(E)(E+E)(E+E)(E*E+E)(E*E+E)(i*E+E)(i*E+E)(i*i+E)(i*i+E)(i*i+i

32、)(i*i+i)n从开始符号从开始符号E E至（至（i*i+i)i*i+i)的一个推导。的一个推导。n而而E,(E),(E*E+E)E,(E),(E*E+E)等是文法的等是文法的句型句型。2.3.1 上下文无关文法上下文无关文法第49页，此课件共86页哦例考虑一个文法例考虑一个文法G1:G1:SbA SbA AaA|a AaA|a 它定义了一个什么语言呢？它定义了一个什么语言呢？从开始符从开始符S S出发，我们可以推出如下句子：出发，我们可以推出如下句子：S SbA bA baba S SbA bA baA baA baabaa S SbA bA baA baA baa baaa a可以写为

33、：可以写为：L(G1)=baL(G1)=ban n|n1|n1几个简单文法的例子几个简单文法的例子2.3.1 上下文无关文法上下文无关文法第50页，此课件共86页哦例考虑文法例考虑文法a a解：解：L(G2)=aL(G2)=am mb bn n|m,n=1|m,n=1思考如何归纳出（）2.3.1 上下文无关文法上下文无关文法第51页，此课件共86页哦例例构造一个文法构造一个文法G3G3使使 L(G3)=aL(G3)=an nb bn n|n1|n1 解解;SaSb|ab;SaSb|ab区别区别区别区别L(G2)=ammb bn n|m,n=1与与L(G3)=an nb bn|n1|n12.3

34、.1 上下文无关文法上下文无关文法第52页，此课件共86页哦课堂练习例例设有文法设有文法G G SP|aPPb SP|aPPb P ba|bQa P ba|bQa Q ab Q ab 求语言求语言L(G).L(G).解：解：L(G)=ba,baba,abab,abababL(G)=ba,baba,abab,ababab 2.3.1 上下文无关文法上下文无关文法第53页，此课件共86页哦例子观察下面的文法存在什么问题：文法1SABABAaA|aAaA|aCcBCcB文法文法2 2SABABAaAAaABSb BSb 2.3.1 上下文无关文法上下文无关文法写文法时注意不要犯错！第54页，此课件

35、共86页哦讨论从一个句型到另一个句型的推导过程是不唯一的，例如：，而言，有两个推导原因：对非终结符号的替换顺序不同原因：对非终结符号的替换顺序不同原因：对非终结符号的替换顺序不同原因：对非终结符号的替换顺序不同原因：对非终结符号的替换顺序不同原因：对非终结符号的替换顺序不同2.3.1 上下文无关文法上下文无关文法第55页，此课件共86页哦最左推导和最右推导为了对句子结构进行确定性分析，我们往往只考为了对句子结构进行确定性分析，我们往往只考虑最左推导或最右推导。所谓最左推导是指：任何虑最左推导或最右推导。所谓最左推导是指：任何一步一步都是对都是对中的最左非终结符进行替换的。中的最左非终结符进

36、行替换的。同样，可定义最右推导。同样，可定义最右推导。最右推导最右推导最左推导最左推导2.3.1 上下文无关文法上下文无关文法第56页，此课件共86页哦2.3.2 2.3.2 语法分析树与二义性语法分析树与二义性前面我们提到过可以用一张图表示一个句型的推前面我们提到过可以用一张图表示一个句型的推导，这种表示称为导，这种表示称为语法分析树语法分析树，或简称，或简称语法树语法树。语法树的语法树的根结根结由由开始符号开始符号所标记。随着推导的展开，所标记。随着推导的展开，当某个非终结符被它的某个候选式所替换时，这个非终当某个非终结符被它的某个候选式所替换时，这个非终结符的相应结就产生了下一代新结。

37、每个新结和其父亲结符的相应结就产生了下一代新结。每个新结和其父亲结间都有一条连线。在一棵语法树生长过程中的任何时结间都有一条连线。在一棵语法树生长过程中的任何时刻，所有那些没有后代的端末结刻，所有那些没有后代的端末结自左至右自左至右排列起来就是排列起来就是一个一个句型句型。第57页，此课件共86页哦例如对于文法（例如对于文法（2.1)2.1)关于（关于（i*i+i)i*i+i)的推的推导形成语法树如图导形成语法树如图2.2 2.2 图图 2.2 2.2 语法树语法树E E(E)(E)(E+E)(E+E)(E*E+E)(E*E+E)(i*E+E)(i*i+E)(i*i+i)(i*i+i)黑板演

38、示过程E(E)(E+E)(E+i)=(E*E+i)=(E*E+i)=(E*i+i)=(i*i+i)=(i*i+i)2.3.2 语法分析树与二义性语法分析树与二义性第58页，此课件共86页哦语法树的意义语法树表示了一个句型种种的可能的（但未必是所有的）不同推导过程，包括最左推倒和最右推导一个语法树是这些不同推导过程的共性抽象，是它们的代表如果我们坚持使用最左（最右）推导，这种等价性包括树的步步成长和推导的步步展开之间的完全一致2.3.2 语法分析树与二义性语法分析树与二义性第59页，此课件共86页哦讨论一个句型是否只对应唯一的一棵语法树呢？一个句型是否只对应唯一的一棵语法树呢？也就是说它是否只有

39、唯一的一个最左也就是说它是否只有唯一的一个最左（最右（最右)推导呢？推导呢？不尽然。不尽然。2.3.2 语法分析树与二义性语法分析树与二义性第60页，此课件共86页哦例子(文法文法2.1)EE+E|E*E|(E)|（i*i+i)推导推导推导推导1 1E E(E)(E)(E+E)(E+E)(E*E+E)(E*E+E)(i*E+E)(i*E+E)(i*i+E)(i*i+E)(i*i+i)(i*i+i)推导推导2E(E)(E*E)(i*E)(i*E+E)(i*i+E)(i*i+i)2.3.2 语法分析树与二义性语法分析树与二义性第61页，此课件共86页哦图图图图2.22.22.22.2与图与图与图

40、与图2.32.32.32.3的不同之处在于从第二代三代过渡开始。对于前者，的不同之处在于从第二代三代过渡开始。对于前者，的不同之处在于从第二代三代过渡开始。对于前者，的不同之处在于从第二代三代过渡开始。对于前者，我们选用规则我们选用规则我们选用规则我们选用规则EE+EEE+EEE+EEE+E,而后者我们选用而后者我们选用而后者我们选用而后者我们选用EE*EEE*EEE*EEE*E。这里不是同代兄弟生儿。这里不是同代兄弟生儿。这里不是同代兄弟生儿。这里不是同代兄弟生儿子的先后次序的不同而是生什么儿子的不同，后面的这个不同是本质上子的先后次序的不同而是生什么儿子的不同，后面的这个不同是本质上子的先

41、后次序的不同而是生什么儿子的不同，后面的这个不同是本质上子的先后次序的不同而是生什么儿子的不同，后面的这个不同是本质上的的差异。这意味着我们可以用两种完全不同的办法产生同一个句子。的的差异。这意味着我们可以用两种完全不同的办法产生同一个句子。的的差异。这意味着我们可以用两种完全不同的办法产生同一个句子。的的差异。这意味着我们可以用两种完全不同的办法产生同一个句子。E E(E)(E)(E*E)(E*E)(i*E)(i*E)(i*E+E)(i*E+E)(i*i+E)(i*i+E)(i*i+i)(i*i+i)问题所在：在推导过程中选择产生式的顺序不同问题所在：在推导过程中选择产生式的顺序不同2.3.

42、2 语法分析树与二义性语法分析树与二义性第62页，此课件共86页哦二义性n如果一个文法存在某个句子对应两棵不如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是同的语法树，则称这个文法是二义的二义的。也就是说，若一个文法存在某个句子，也就是说，若一个文法存在某个句子，它有两个不同的最左（最右它有两个不同的最左（最右)推导，则这推导，则这个文法是法是个文法是法是二义的二义的。2.3.2 语法分析树与二义性语法分析树与二义性第63页，此课件共86页哦文法二义性和语言的联系可能存在两个不同的文法和，其中一个是二义的另一个是无二义的但可能存在（）（），即两个文法产生的语言是相同的对于程序语言来

43、说，我们希望它的文法是无二义的这样对其每个语句的分析是唯一的如果我们能国控制和驾驭文法的二义性，文法的二义性的存在不一定是坏事二义性是不可判定的（已证明），即不存在一个算法在有限步骤内，确切地判定一个文法是否为二义的2.3.2 语法分析树与二义性语法分析树与二义性第64页，此课件共86页哦图示GGL二义无二义文法语言2.3.2 语法分析树与二义性语法分析树与二义性第65页，此课件共86页哦思考：如何处理二义性？EE+EE*EEE+EE*E2.3.2 语法分析树与二义性语法分析树与二义性第66页，此课件共86页哦解决二义性的方法为无二义性寻找一组充分条件例如：假如规定文法中的运算符和的优先顺序和

45、F+F）（F*FF）（i*FF）（i*iF）（i*ii）第69页，此课件共86页哦EF|E+FE+FEEF|E*FF(E)|iF（）（E+F）（E*F+F）（F*FF）（i*FF）（i*iF）（i*ii）F（）（E*F）（E+F*F）第70页，此课件共86页哦对描述程序语言的上下文无关文法的限制最后，作为描述程序语言的上下文无关文法，最后，作为描述程序语言的上下文无关文法，我们对它有几点限制。我们对它有几点限制。（1 1）文法中不含任何下面形式的产生式：）文法中不含任何下面形式的产生式：PPPP因为这种产生式除了产生二义性外没因为这种产生式除了产生二义性外没有任何用处。有任何用处。有害规则2.

46、3.2 语法分析树与二义性语法分析树与二义性第71页，此课件共86页哦（2）每个非终结符每个非终结符P P必须有用处。这一方必须有用处。这一方面意味着，必须存在含面意味着，必须存在含P P的句型；也就是，的句型；也就是，从开始符号出发，存在推导从开始符号出发，存在推导 S S*P P.另一方面意味着，必须存在终结符串另一方面意味着，必须存在终结符串V VT T*,使得使得P P+；也就是，对于；也就是，对于P P不存在不存在永不终结的回路。永不终结的回路。我们以后所讨论的文法均假定满足上我们以后所讨论的文法均假定满足上述两条件。述两条件。多余规则：用不着的规则。2.3.2 语法分析树与二义性语

47、法分析树与二义性第72页，此课件共86页哦例子：找多余规则和有害规则例：文法GS:S BeB Ce|AfA Ae|eC CfD f其中Df是多余规则（用不到），CCf也是多余的（C永远推不到终结符）。同样BCe也是多余的。2.3.2 语法分析树与二义性语法分析树与二义性第73页，此课件共86页哦例子观察下列文法的错误SaABAabBbaPS2.3.2 语法分析树与二义性语法分析树与二义性第74页，此课件共86页哦例子观察下列文法的错误SaABPAabBba2.3.2 语法分析树与二义性语法分析树与二义性第75页，此课件共86页哦2.3.3 2.3.3 形式语言鸟瞰形式语言鸟瞰乔姆斯基把文法分为

48、四种类型即乔姆斯基把文法分为四种类型即0 0型、型、1 1型、型、2 2型、型、3 3型。型。0 0行强于行强于1 1型，型，1 1行强于行强于2 2型，型，2 2型强于型强于3 3型。这几文法的型。这几文法的差别差别在于在于对产生式施加不同的限制。对产生式施加不同的限制。第76页，此课件共86页哦0 0型文法型文法我们说我们说G=(VG=(VT T,V,VN N,S,S,)是一个是一个0 0型文法型文法，如果它的每个产生式如果它的每个产生式是这样的结构是这样的结构 (V(VN N V VT T)*且至少有一个非终结符，而且至少有一个非终结符，而(V(VN N V VT T)*。0 0型文法

49、也称型文法也称短语文法短语文法。0 0型文法的能力相当于图灵机，是递归可枚举型文法的能力相当于图灵机，是递归可枚举的的2.3.3 形式语言鸟瞰形式语言鸟瞰第77页，此课件共86页哦0型文法型文法例子nG=Vn,Vt,S,PnVn=S,A,B,C,D,En Vt=anP=SACaBnCaaaCnCBDBnCBEnaDDanADACnaEEanAE 对于程序设计语言来，对于程序设计语言来，0型型文法文法有很大的随意性有很大的随意性，还，还须加以限制须加以限制第78页，此课件共86页哦1型文法n如果对如果对0 0型文法分别施加以下的第型文法分别施加以下的第i i条限制，则我们就条限制，则我们就得到第

50、得到第i i型文法型文法:n(1)G(1)G的任何产生式的任何产生式均满足均满足n|（其中（其中|和和|分别为分别为和和的长度；仅的长度；仅S S例外，但例外，但S S不得出现在任何产生式的右部。不得出现在任何产生式的右部。n1 1型文法也称型文法也称上下文有关文法上下文有关文法。这种文法意味着，对非终。这种文法意味着，对非终结符进行替换式务必考虑上下文并且一般不允许替换成结符进行替换式务必考虑上下文并且一般不允许替换成空串空串。第79页，此课件共86页哦1型文法例子型文法例子G=Vn,Vt,S,P 其中：其中：Vn=S,B,C,D Vt=a,b,c P=SaSBC|aBC CBDB D

展开阅读全文