高级语言及其语法描述

高级语言及其语法描述2.2.4语句与控制结构第2页,共86页，2024年2月25日，星期天一表达式概念一个表达式是由运算量（亦称操作数，即数据引用或函数调用）和算符组成的。X+Y二元算符左运算量右运算量2.2.4语句与控制结构第3页,共86页，2024年2月25日，星期天运算符一元算符前缀:一元算符写在运算量的前面例子:-X,ヮB后缀:一元算符写在运算量的后面例子:P↑既是一元算符又是二元算符“-”二元算符中缀:二元算符写在两个运算量之间例子:X+Y前缀:二元算符写在两个运算量之前例子:+XY后缀:二元算符写在两个运算量之后例子:XY+2.2.4语句与控制结构第4页,共86页，2024年2月25日，星期天表达式的形成规则（1）变量（包括下标变量）、常数是表达式；（2）若E1、E2为表达式，θ为二元算符，则E1θE2为表达式(一般用中缀形式)；（3）若E为表达式，θ为一元算符，则θE(或Eθ)为表达式；（4）若E为表达式，则（E)是表达式。例子2.2.4语句与控制结构第5页,共86页，2024年2月25日，星期天例子1X1+x(1+x)-(1+x)2.2.4语句与控制结构第6页,共86页，2024年2月25日，星期天表达式的运算顺序和结合性与通常的数学习惯一致例如:先乘除后加减,乘幂更优先结合性对于同级算符,先左后右(左结合)或先右后左(右结合)2.2.4语句与控制结构第7页,共86页，2024年2月25日，星期天练习X+Y*ZX-Y-ZX-Y+ZX**Y**ZX+++Y2.2.4语句与控制结构第8页,共86页，2024年2月25日，星期天

在多数语言中算术算符和逻辑算符的优先顺序一般规定如下：乘幂（**或↑）一元负（-）乘、除（*，/，÷）加、减（+，-）关系符（<,=,>,<=,<>,>=)非（﹁，not,或.NOT.)与（∧，&,and或.AND.)或（∨，∣，or或.OR.)隐含（

或imp)等值（≡,～或equi)2.2.4语句与控制结构第9页,共86页，2024年2月25日，星期天讨论:不同语言对算符优先级和结合性的差异APL:右结合X-Y+ZX-(Y+Z)ALGOL:左结合X-Y+Z(X-Y)+ZFORTRAN:对于满足左或右结合的算符,任取其一;对于满足交换率的算符，左右运算量的计算顺序不加限制2.2.4语句与控制结构第10页,共86页，2024年2月25日，星期天

算符的代数性质（交换率、结合率和分配率）常常可用来优化目标程序的质量。但是必须注意两点：（1）代数性质引用到什么程度视具体语言的不同而不同。如在ALGOL中把

A*B+C*D处理成C*D+A*B,则至少是对ALGOL不够忠实。（2）数学上成立的代数性质在计算机上未必完全成立。如：(A+B)+C=A+(B+C)在计算机上并不普遍成立。2.2.4语句与控制结构第11页,共86页，2024年2月25日，星期天不同类型的数据运算0.5+3ALGOL允许FORTRAN禁止C++允许,但要做类型转换2.2.4语句与控制结构第12页,共86页，2024年2月25日，星期天二语句不同程序语言含有不同形式和功能的各种语句。从功能上说语句大体可分:执行性语句执行性语句旨在描述程序的动作。执行性语句又可分赋值语句控制语句输入/输出语句.说明性语句说明性语句旨在定义不同数据类型的变量或运算。从形式上说，语句还可分为简单句、复合句和分程序等。2.2.4语句与控制结构第13页,共86页，2024年2月25日，星期天1赋值语句

我们知道，每个名字有两方面的特征：一方面它代表一定的存储单元，另一方面它又以该单元的内容作为值。70weight0100Normal=(height-100)*weightWeight=802.2.4语句与控制结构第14页,共86页，2024年2月25日，星期天赋值语句的意义赋值语句A:=B的意义是：“把B的值送入A所代表的单元”也就是说：在赋值句中，赋值号‘：=’左右两边的变量名扮演着两种不同的角色。对赋值号右边的B我们需要的是它的值；对于左边的A我们需要的是它们的所代表的存储单元（的地址）。7001001000900ABA:=B2.2.4语句与控制结构第15页,共86页，2024年2月25日，星期天左值与右值为了区分一个名字的这两种特征，我们把一个名字所代表的那个存储单元（地址）称为该名字的左值；把一个名字的值称为该名字的右值。回顾C++的左值和右值概念2.2.4语句与控制结构第16页,共86页，2024年2月25日，星期天进一步讨论变量既可持有左值又持有右值常数和带有算符的表达式一般持有右值指示器变量P,P↑既持有左值有持有右值出现在赋值号左边的表达式必须持有左值出现在赋值号右边的表达式只需持有右值对于出现在赋值号右边表达式中的变量,我们要其右值(a=4)=28++(++a)++(a++)2.2.4语句与控制结构第17页,共86页，2024年2月25日，星期天(a=4)=28++(++a)++(a++)2.2.4语句与控制结构第18页,共86页，2024年2月25日，星期天2控制语句多数语言中所含的控制语句有：无条件转移语句:gotoL条件语句：ifBthenSifBthenS1elseS2循环与句：whileBdoSrepeatSuntilBfori:=E1stepE2untilE3doS过程调用语句：callP(X1,X2,…,Xn)返回语句：return(E)

重要的是我们必须了解这些语句在不同语言中的不同含义。2.2.4语句与控制结构第19页,共86页，2024年2月25日，星期天3说明语句

说明语句旨在定义名字的性质。编译程序把这些性质登记在符号表中，并检查程序中名字的引用和说明是否相一致。许多说明语句没有相应的代码。但有些语句，如过程说明语句，和可变数组说明语句则有相应的目标代码。2.2.4语句与控制结构第20页,共86页，2024年2月25日，星期天4简单句和复合句简单句是指那些不含其它语句成分的基本句例如赋值句、goto句等。复合句则指那些句中有句的语句。例如:if(xeqy)got152.2.4语句与控制结构第21页,共86页，2024年2月25日，星期天2.3程序语言的语法描述本节内容是对高级语言中为编译原理课程所关心特性的总结对于高级程序语言及编译程序而言，语言的语法定义是非常重要的。本节将介绍语法结构的形式描述问题。第22页,共86页，2024年2月25日，星期天首先引入几个概念设是一个有穷字母表，它的每个元素称为一个符号。上的一个符号串是指由中的符号所构成的有穷序列。不包含符号的序列称为空字，记为

。用

*表示上的所有符号串的全体，空字也包括在其中。如：若={a,b}则*={,a,b,aa,ab,bb,aaa,…}。

表示不含任何元素的空集{}。这里要注意、{}和{}的区别。2.3程序语言的语法描述第23页,共86页，2024年2月25日，星期天

*的子集U和V中的（连接）积定义为:UV={∣U&V}

即集合UV中的符号串是由U和V的符号串连接而成的。注意，一般UVVU，但（UV)W=U(VW).V自身的n次（连接）积记为：

Vn=VV…V(n个V)规定V0={}.

令：V*=V0V1V2

…

称V*是V的闭包。记V+=VV*,称V+是V的正则包。闭包V*中的每个符号都是由V中的符号串经有限次连接而成的。2.3程序语言的语法描述第24页,共86页，2024年2月25日，星期天课堂练习已知

={a,b}，*={,a,b,aa,ab,bb,aaa,…}U={aa,ab}V={ba,bb}则UV＝｛aaba,aabb,abba,abbb｝U2＝UU=｛aaaa,aaab,abaa,abab｝U3＝UUU=(UU)U=｛aaaa,aaab,abaa,abab｝U=U*＝｛,aa,ab,aaaa,aaab,abaa,abab,aaaaaa…｝U+＝｛｝2.3程序语言的语法描述第25页,共86页，2024年2月25日，星期天2.3.1上下文无关文法文法是描述语言的语法结构的形式规则（即语法规则）。要求：强描述能力，足以描述各种不同结构，有利于句子分析和翻译，可自动产生有效的语法分析程序所谓上下文无关文法是这样一种文法，它所定义的语法范畴（或语法单位)是完全独立于这种范畴可能出现的环境的。例如：在程序语言中，当碰到一个算术表达式，我们完全可以对它“就事论事”处理，而不必考虑它所处的上下文．例如：自然语言的字词句与上下文密切关系上下文无关文法不能描述自然语言，但足以描述程序语言2.3程序语言的语法描述第26页,共86页，2024年2月25日，星期天例子有的句子还必须结合上下文的关系才能获得正确的分析结果。例如，知道了上文是“狼来了”，理解下文“咬死了猎人的狗”时，就不会再有歧义；或者上文是“我爷爷年纪大了”，下文是“他只能算一个半劳力”，联系上下文一起分析，“一个半劳力”便只剩下一种含义。

“狼来了”“我爷爷年纪大了”2.3.1上下文无关文法第27页,共86页，2024年2月25日，星期天例子例如：“乒乓球拍卖完了”，可以切分成“乒乓球拍卖完了”“乒乓球拍卖完了”如果没有上下文其他的句子，恐怕谁也不知道“拍卖”在这里算不算一个词。“乒乓球拍卖完了”“乒乓球拍卖完了”2.3.1上下文无关文法第28页,共86页，2024年2月25日，星期天例子：一个具体的英文例句分析请仔细阅读课本P27页的英文分析的例句，2.3.1上下文无关文法第29页,共86页，2024年2月25日，星期天直接宾语间接宾语谓语主语Hegavemeabook思考：如果你是英语老师，学生写了这样一个英语句子，你如何判断该句子是对的？2.3.1上下文无关文法第30页,共86页，2024年2月25日，星期天句型：主语谓语间接宾语直接宾语思考：假定有以下句型，如何判断“Hegavemaabook”符合该句型如果“Hegavemaabook”符合该句型，则“Hegavemaabook”是一个正确的句子例子：常见英语句型2.3.1上下文无关文法第31页,共86页，2024年2月25日，星期天思考：如何判断一个程序的语句是否正确？赋值语句变量：＝表达式X:=3.14*r*r2.3.1上下文无关文法第32页,共86页，2024年2月25日，星期天思考能不能将判断一个句子是否符合一个句型的过程自动化，使得今后可以通过编写程序来完成这一过程？方法：建立语法规则，用程序自动推导2.3.1上下文无关文法第33页,共86页，2024年2月25日，星期天解决方法规则推导2.3.1上下文无关文法第34页,共86页，2024年2月25日，星期天结论

定义英文句子的规则可以说是一个上下文无关文法。其中He,me,book,gave,a等，称为终结符号；<句子>、<主语>、<谓语>等为非终结符号；这个文法最终是要定义<句子>的语法结构，所以<句子>在这里成为开始符号；<间接宾语>→<冠词><名词>这种书写形式称为产生式。2.3.1上下文无关文法第35页,共86页，2024年2月25日，星期天归纳一个上下文无关文法G包括四个组成部分：一组终结符号，一组非终结符，一个开始符号，以及一组产生式。所谓终结符号乃是组成语言的基本符号，即在程序语言中以前屡次提到的单词符号，如基本字，标识符，常数，算符和界符等所谓非终结符号（也称语法变量）用来代表语法范畴。如“算术表达式”、“布尔表达式”、“过程”等。一个非终结符代表一个一定的语法概念。因此非终结符是一个类（或集合）记号，而不是个体记号。2.3.1上下文无关文法第36页,共86页，2024年2月25日，星期天开始符号是一个特殊的非终结符号，它代表所定义的语言中我们最感兴趣的语法范畴，这个语法范畴通常称为“句子”。但在程序语言中我们最终感兴趣的是“程序”这个语法范畴，而其他的语法范畴都只不过是构造“程序”的一块块砖石。产生式（也称为产生规则或简称规则）是定义语法范畴的一种书写规则。一个产生式的形式是A→α,其中箭头左边的A是一个终结符，称为产生式的左部符号；箭头右边的α是终结符号或与非终结符号组成的一符号串，称为产生式的右部。2.3.1上下文无关文法第37页,共86页，2024年2月25日，星期天产生式是定义语法范畴的。例如：对于表达式的形成规则：“变量（包括下标变量）、常数是表达式“可用产生式定义为：算术表达式→变量或算术表达式→i可用巴科斯范式表示为算术表达式：＝变量2.3.1上下文无关文法第38页,共86页，2024年2月25日，星期天有时需要多个产生式规则定义一个语法范畴例如：要定义一类含+、*的算术表达式，这个定义可以这样给出：定义“变量是一个算术表达式；若E1和E2是算术表达式，则E1+E2、E1*E2和(E1)也是算术表达式。用产生式描述：E→iＥ→Ｅ＋ＥＥ→Ｅ＊ＥＥ→（Ｅ）其中Ｅ代表“算术表达式”，ｉ代表“变量”递归定义2.3.1上下文无关文法第39页,共86页，2024年2月25日，星期天上下文无关文法Ｇ的形式定义上下文无关文法是一个四元式（ＶＴ，ＶＮ，Ｓ，P）其中ＶＴ是一个非空有限集，它的每一个元素称为终结符号；ＶＮ是一个非空有限集，它的每一个元素称为非终结符号，ＶＴ∩ＶＮ＝；Ｓ是一个非终结符号，称为开始符号；P是一个产生式（有限）集合，每个产生式形式是Ｐ→，其中，Ｐ∈ＶＮ，

∈（ＶＴ∪ＶＮ）＊开始符号S至少必须在某一产生式的左部出现一次。2.3.1上下文无关文法第40页,共86页，2024年2月25日，星期天进一步讨论产生式缩写若干个左部相同的产生式，如：Ｐ－＞ａ１Ｐ－＞ａ２．．．．．Ｐ－＞ａｎ可合并为：Ｐ－＞ａ１｜ａ２｜．．．｜ａｎ其中ai称为侯选式箭头读为“定义为”直竖读为“或”元语言符号：－＞｜2.3.1上下文无关文法第41页,共86页，2024年2月25日，星期天书写约定非终结符号：大写字母终结符号：小写字母符号串：αβγ例子Ｅ－＞ｉ｜ＥＡＥＡ－＞＋｜＊2.3.1上下文无关文法第42页,共86页，2024年2月25日，星期天如何用上下文无关文法定义语言？中心思想：从文法的开始符号出发，反复连续使用产生式，对非终结符施行替换和展开例如：Ｅ－＞Ｅ＋Ｅ｜Ｅ＊Ｅ｜（Ｅ）｜ｉＥ－＞（Ｅ）从Ｅ可直接（一步）推出（Ｅ）用＝＞表示Ｅ＝＞（Ｅ）2.3.1上下文无关文法第43页,共86页，2024年2月25日，星期天例子从Ｅ推出（ｉ＋ｉ）Ｅ＝＞（Ｅ）＝＞（Ｅ＋Ｅ）＝＞（ｉ＋Ｅ）＝＞（ｉ＋ｉ）概念：将以上一系列替换序列称为“推导“推导提供了一个证明推导每前进一步必引用一条产生式（规则）＝＞表示仅推导一步2.3.1上下文无关文法第44页,共86页，2024年2月25日，星期天推导称αＡβ=>

αγ

β（αＡβ直接推出αγ

β），当且仅当Ａ->γ是一个产生式，且α，β∈（ＶＴ∪ＶＮ）*定义推导如果α1=>α2=>…=>αn，则我们称这个序列是从α1到αn的一个推导．如果存在a1至an的一个推导,则称a1推导出an。记a1=>an，表示从a1出发，经过１步或若干步，可推导出an记a1＝＞an，表示从a1出发，经过０步或若干步，可推导出an如果α＝＞β，或者α＝β，或者α＝＞β+*+*2.3.1上下文无关文法第45页,共86页，2024年2月25日，星期天例子（Ｅ＋Ｅ）＝＞（ｉ＋Ｅ）称αＡβ＝＞αγ

β（αＡβ直接推出αγ

β），当且仅当Ａ－＞γ是一个产生式，且α，β∈（ＶＴ∪ＶＮ）*（Ｅ＋Ｅ）->（ｉ＋Ｅ）Ｅ->ｉ2.3.1上下文无关文法第46页,共86页，2024年2月25日，星期天例子Ｅ＝＞（Ｅ）＝＞（Ｅ＋Ｅ）＝＞（ｉ＋Ｅ）＝＞（ｉ＋ｉ）因为所以有：Ｅ＝＞（ｉ＋ｉ）+2.3.1上下文无关文法第47页,共86页，2024年2月25日，星期天语言的定义假定G是一个文法，S是它的开始符号。如果S

*(表示从S出发，经0步或若干步可推出），则称是一个句型。仅含终结符号的句型是一个句子。文法G所产生的句子的全体是一个语言，将它记为L(G).L(G)={|S+&∈VT*}

2.3.1上下文无关文法第48页,共86页，2024年2月25日，星期天例子例如：终结符号串（i*i+i)是文法E→E+E|E*E|(E)|ｉ(2.1)的一个句子。是因为有E(E)(E+E)(E*E+E)(i*E+E)(i*i+E)(i*i+i)从开始符号E至（i*i+i)的一个推导。而E,(E),(E*E+E)等是文法的句型。2.3.1上下文无关文法第49页,共86页，2024年2月25日，星期天

例考虑一个文法G1:S→bAA→aA|a它定义了一个什么语言呢？从开始符S出发，我们可以推出如下句子：

SbAbaSbAbaAbaaSbAbaA…baa…a可以写为：L(G1)={ban|n≥1}几个简单文法的例子2.3.1上下文无关文法第50页,共86页，2024年2月25日，星期天例考虑文法Ｇ２ Ｓ－＞ＡＢ Ａ－＞ａＡ｜a

Ｂ－＞ｂＢ｜ｂ解：L(G2)={ambn|m,n>=1}思考如何归纳出Ｌ（Ｇ２）2.3.1上下文无关文法第51页,共86页，2024年2月25日，星期天例构造一个文法G3使

L(G3)={anbn|n≥1}

解;S→aSb|ab区别L(G2)={ambn|m,n>=1}与L(G3)={anbn|n≥1}2.3.1上下文无关文法第52页,共86页，2024年2月25日，星期天课堂练习例设有文法GS→P|aPPbP→ba|bQaQ→ab

求语言L(G).

解：

L(G)={ba,baba,abab,ababab…}2.3.1上下文无关文法第53页,共86页，2024年2月25日，星期天例子观察下面的文法存在什么问题：文法1S→ABA→aA|aC→cB文法2S→ABA→aAB→Sb2.3.1上下文无关文法写文法时注意不要犯错！第54页,共86页，2024年2月25日，星期天讨论从一个句型到另一个句型的推导过程是不唯一的，例如：Ｅ＋Ｅ＝＞ｉ＋ｉ，而言，有两个推导１Ｅ＋Ｅ＝＞Ｅ＋ｉ＝＞ｉ＋ｉ２Ｅ＋Ｅ＝＞ｉ＋Ｅ＝＞ｉ＋ｉ原因：对非终结符号的替换顺序不同2.3.1上下文无关文法第55页,共86页，2024年2月25日，星期天最左推导和最右推导

为了对句子结构进行确定性分析，我们往往只考虑最左推导或最右推导。所谓最左推导是指：任何一步都是对中的最左非终结符进行替换的。同样，可定义最右推导。Ｅ＋Ｅ＝＞Ｅ＋ｉ＝＞ｉ＋ｉＥ＋Ｅ＝＞ｉ＋Ｅ＝＞ｉ＋ｉ最右推导最左推导2.3.1上下文无关文法第56页,共86页，2024年2月25日，星期天2.3.2语法分析树与二义性

前面我们提到过可以用一张图表示一个句型的推导，这种表示称为语法分析树，或简称语法树。语法树的根结由开始符号所标记。随着推导的展开，当某个非终结符被它的某个候选式所替换时，这个非终结符的相应结就产生了下一代新结。每个新结和其父亲结间都有一条连线。在一棵语法树生长过程中的任何时刻，所有那些没有后代的端末结自左至右排列起来就是一个句型。第57页,共86页，2024年2月25日，星期天

例如对于文法（2.1)关于（i*i+i)的推导形成语法树如图2.2

图2.2语法树E(E)(E+E)(E*E+E)(i*E+E)(i*i+E)(i*i+i)黑板演示过程E(E)(E+E)(E+i)=>(E*E+i)=>(E*i+i)=>(i*i+i)

2.3.2语法分析树与二义性第58页,共86页，2024年2月25日，星期天语法树的意义语法树表示了一个句型种种的可能的（但未必是所有的）不同推导过程，包括最左推倒和最右推导．一个语法树是这些不同推导过程的共性抽象，是它们的代表．如果我们坚持使用最左（最右）推导，这种等价性包括树的步步成长和推导的步步展开之间的完全一致．2.3.2语法分析树与二义性第59页,共86页，2024年2月25日，星期天讨论

一个句型是否只对应唯一的一棵语法树呢？也就是说它是否只有唯一的一个最左（最右)推导呢？不尽然。2.3.2语法分析树与二义性第60页,共86页，2024年2月25日，星期天例子(文法2.1)E→E+E|E*E|(E)|ｉ（i*i+i)〔推导1〕E(E)(E+E)(E*E+E)(i*E+E)(i*i+E)(i*i+i)〔推导2〕E(E)(E*E)(i*E)(i*E+E)(i*i+E)(i*i+i)2.3.2语法分析树与二义性第61页,共86页，2024年2月25日，星期天

图2.2与图2.3的不同之处在于从第二代三代过渡开始。对于前者，我们选用规则E→E+E,而后者我们选用E→E*E。这里不是同代兄弟生儿子的先后次序的不同而是生什么儿子的不同，后面的这个不同是本质上的的差异。这意味着我们可以用两种完全不同的办法产生同一个句子。E(E)(E*E)(i*E)(i*E+E)(i*i+E)(i*i+i)问题所在：在推导过程中选择产生式的顺序不同2.3.2语法分析树与二义性第62页,共86页，2024年2月25日，星期天二义性如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。也就是说，若一个文法存在某个句子，它有两个不同的最左（最右)推导，则这个文法是法是二义的。2.3.2语法分析树与二义性第63页,共86页，2024年2月25日，星期天文法二义性和语言的联系可能存在两个不同的文法Ｇ和Ｇ‘，其中一个是二义的另一个是无二义的．但可能存在Ｌ（Ｇ）＝Ｌ（Ｇ’），即两个文法产生的语言是相同的．对于程序语言来说，我们希望它的文法是无二义的．这样对其每个语句的分析是唯一的．如果我们能国控制和驾驭文法的二义性，文法的二义性的存在不一定是坏事．二义性是不可判定的（已证明），即不存在一个算法在有限步骤内，确切地判定一个文法是否为二义的．2.3.2语法分析树与二义性第64页,共86页，2024年2月25日，星期天图示GG’L二义无二义文法语言2.3.2语法分析树与二义性第65页,共86页，2024年2月25日，星期天思考：如何处理二义性？EE+EE*EEE+EE*E2.3.2语法分析树与二义性第66页,共86页，2024年2月25日，星期天解决二义性的方法为无二义性寻找一组充分条件例如：假如规定文法２．１中的运算符＋和＊的优先顺序和结合顺序，就可构造出无二义性文法2.3.2语法分析树与二义性第67页,共86页，2024年2月25日，星期天例子Ｅ－＞Ｅ＋ＥＥ－＞Ｅ＊ＥＥ－＞（Ｅ）Ｅ－＞ｉＥ－＞T|Ｅ＋TT－＞F|T＊FF－＞（Ｅ）|i表达式－＞项｜表达式＋项项－＞因子｜项＊因子因子－＞（表达式）｜iＥ表达式Ｔ项Ｆ因子改变2.3.2语法分析树与二义性第68页,共86页，2024年2月25日，星期天Ｅ－＞T|Ｅ＋TT－＞F|T＊FF－＞（Ｅ）|iＥ＝＞Ｔ＝＞F＝＞（Ｅ）＝＞（E+T）＝＞（T+T）＝＞（T*F＋T）＝＞（F*F＋T）＝＞（i*F＋T）＝＞（i*i＋T）＝＞（i*i＋F）＝＞（i*i＋i）例子2.3.2语法分析树与二义性E→F|E+FE→F|E*FF→(E)|iＥ＝＞F＝＞（Ｅ）＝＞（E+F）＝＞（E*F+F）＝＞（F*F＋F）＝＞（i*F＋F）＝＞（i*i＋F）＝＞（i*i＋i）第69页,共86页，2024年2月25日，星期天E→F|E+FE→F|E*FF→(E)|iＥ＝＞F＝＞（Ｅ）＝＞（E+F）＝＞（E*F+F）＝＞（F*F＋F）＝＞（i*F＋F）＝＞（i*i＋F）＝＞（i*i＋i）Ｅ＝＞F＝＞（Ｅ）＝＞（E*F）＝＞（E+F*F）＝＞第70页,共86页，2024年2月25日，星期天对描述程序语言的上下文无关文法的限制最后，作为描述程序语言的上下文无关文法，我们对它有几点限制。（1）文法中不含任何下面形式的产生式：P→P因为这种产生式除了产生二义性外没有任何用处。有害规则2.3.2语法分析树与二义性第71页,共86页，2024年2月25日，星期天

（2）每个非终结符P必须有用处。这一方面意味着，必须存在含P的句型；也就是，从开始符号出发，存在推导S

*P.

另一方面意味着，必须存在终结符串

VT*,使得P

+

；也就是，对于P不存在永不终结的回路。我们以后所讨论的文法均假定满足上述两条件。多余规则：用不着的规则。2.3.2语法分析树与二义性第72页,共86页，2024年2月25日，星期天例子：找多余规则和有害规则例：文法G[S]:SBeBCe|AfAAe|eCCfDf其中Df是多余规则（用不到），CCf也是多余的（C永远推不到终结符）。同样BCe也是多余的。2.3.2语法分析树与二义性第73页,共86页，2024年2月25日，星期天例子观察下列文法的错误S→aABA→abB→baP→S2.3.2语法分析树与二义性第74页,共86页，2024年2月25日，星期天例子观察下列文法的错误S→aABPA→abB→ba2.3.2语法分析树与二义性第75页,共86页，2024年2月25日，星期天2.3.3形式语言鸟瞰乔姆斯基把文法分为四种类型即0型、1型、2型、3型。0行强于1型，1行强于2型，2型强于3型。这几文法的差别在于对产生式施加不同的限制。第76页,共86页，2024年2月25日，星期天0型文法我们说G=(VT,VN,S,

)是一个0型文法，如果它的每个产生式是这样的结构

(VNVT)*且至少有一个非终结符，而(VNVT)*。0型文法也称短语文法。0型文法的能力相当于图灵机，是递归可枚举的2.3.3形式语言鸟瞰第77页,共86页，2024年2月25日，星期天0型文法例子G={Vn,Vt,S,P}Vn={S,A,B,C,D,E}Vt={a}P={S→ACaBCa→aaCCB→DBCB→EaD→DaAD→ACaE→EaAE→ε}对于程序设计语言来，0型文法有