编译原理第二章

1、编译原理电子教案第二章第二章高级语言及其语法描述高级语言及其语法描述上一页下一页2本章的主要内容本章的主要内容 高级语言的一般特性 语法、文法和语义 上下文无关的文法 分析树与二义性 形式语言的概况及分类上一页下一页3本章要求本章要求 知识点：文法和语言的形式定义，分析树和二义性，形式语言概观。 深刻理解：上下文无关文法，推导，语言，最左推导，最右推导，分析树和二义性。 熟练掌握：（1）已知上下文无关文法G和句型w，构造出w的推导，最左推导，最右推导，分析树； （2）判定上下文无关文法G是二义性的。（3）已知上下文无关文法G，求出L，使得L=L（G）； 已知上下文无关语言 L，求出 G，使得

2、L（G）=L。上一页下一页4本章教学线索本章教学线索1 高级语言的一般特性高级语言的一般特性 1.1 程序语言的定义 1.2 程序语言的分类 1.3 数据类型与操作 1.4 高级语言常见的语句2 字符串字符串3 文法和语言文法和语言 4 语法分析树与二义性问题语法分析树与二义性问题 5 文法的分类（逐渐对产生式施加限制）文法的分类（逐渐对产生式施加限制）上一页下一页51.1 程序语言的定义程序语言的定义 高级程序语言都可看成是一个字符集上的字符串。程序语言主要是由语法和语义两方面定义。 语言的语法是用来形成一个合法程序的一组规则，这些规则一部分称为词法规则，另一部分称为语法规则。词法规则定义了

3、单词符号的形成规则，而语法规则定义了语法单位的形成规则。 语法单位：表达式、语句、函数、过程和程序等。 语义规则定义了语言的意义，语义规则定义语言的单词符号和语法单位的意义。 程序语言的语法规则是用文法来描述的，目前的程序语言一般用上下文无关的文法来描述。上一页下一页61.2 程序语言的分类程序语言的分类（1）强制式语言（过程式语言）：命令驱动，面向语句，一个强制式语言程序由一系列语句组成，如：FORTRAN、C、PASCAL等；（2）应用式语言（函数式语言）：注重程序的表示功能，程序的开发过程就是从前面已有的函数出发构造更复杂的函数，如：LISP。（3）基于规则的语言（逻辑设计语言）：检查一

4、定的条件，当它满足值，则执行适当的操作，如：Prolog。（4）面向对象的语言：封装性、继承性、多态性，如：C+，Java，Smalltalk。上一页下一页71.3 数据类型与操作数据类型与操作 一个数据类型通常包括3种要素：（1）用于区别这种类型数据对象的属性（2）这种类型的数据对象可以具有的值（3）可以作用于这种类型的数据对象的操作 常见的数据类型：（1）数值数据（2）逻辑数据（3）字符数据（4）指针类型（5）数组（6）记录（7）字符串、栈、队列（8）抽象数据类型（类）上一页下一页81.4 高级语言常见的语句高级语言常见的语句 说明语句 赋值语句 控制语句（无条件转移语句、条件语句、循环语

5、句、过程调用语句、返回语句）上一页下一页9本章教学线索本章教学线索1 高级语言的一般特性高级语言的一般特性2 字符串字符串 2.1 字母表 2.2 符号串定义、术语及运算3 文法和语言文法和语言 4 语法分析树与二义性问题语法分析树与二义性问题5 文法的分类（逐渐对产生式施加限制）文法的分类（逐渐对产生式施加限制） 上一页下一页102.1 字母表字母表 字母表是符号的非空有穷集合。任何程序语言都有自己的字母表，一个程序语言只使用一个有限字符集作为字母表。用表示。例如:计算机语言：由符号“0”和“1”组成的字母表，=0，1 ASCII字符集；Pascal字母表为： = AZ, az, 09, +

6、, -, *, /, , :, , ; ，.， , (, ), , , , 上一页下一页112.2 符号串定义、术语及运算符号串定义、术语及运算 符号串的定义符号串的定义 设是一个有穷字母表，它的每个元素称为一个符号。上的一个符号串是指由中的符号所构成的一个有穷序列。(1) 空字是上的一个符号串。空字是不包含任何符号的序列不包含任何符号的序列。(2) 若x是上的符号串，而a是的元素, 则xa是上的符号串。(3) y是上的符号串,当且仅当它由(1)和(2)导出。 由字母表中的符号所组成的任何有穷序列称之为该字母表上的符号串,也称作“字”。*(Kleene闭包)：表示上的所有字符串的全体，也在其中

7、。表示不含任何元素的空集。例如：若=a，b，则*=，a，b ，aa，ab，ba，bb，aaa， 上一页下一页12 符号串的术语符号串的术语设s是符号串前缀：移走s的尾部的零个或多于零个符号后缀：删去s的头部的零个或多于零个符号子串：从s中删去一个前缀和一个后缀子序列：从s中删去零个或多于零个符号(这些符号不要求是连续的）逆转：将S中的符号按相反次序写出而得到的符号串。长度：是该符号串中的符号的数目。例如|aab|=3,|=0。真前缀，真后缀，真子串: xsx 例子：符号串s=banana前缀：,b,ba,ban,bana,banan,banana后缀：banana,anana,nana,ana

8、,na,a, 子串：banana,anana,banan,anan, 子序列: baa(这些符号不要求是连续的）逆转（用SR表示）：ananab长度：banana=6上一页下一页13 符号串的运算符号串的运算（1）连接：设x和y是符号串，它们的连接 xy是把y的符号写在x的符号之后得到的符号串。例如：x = ba，y = nana，xy = banana。（2）方幂：x0 = ；x1 = x；x2 = xx ；xn=xn-1x ； 例如： x = ba，x1= ba， x2=baba，x3=bababa，上一页下一页14 符号串集合符号串集合(语言）的运算语言）的运算设*的子集U和V是两个符号

9、串集合，则合并：UV |U orV（或表示为：U+V）连接：UV |U and V方幂： V0=， V1V，V2VV，VnVn-1V 语言V的闭包，记作V*： V*Vi（i=0） = V0V1V2V3 语言V的正则闭包，记作V+（V+V V*） V+Vi（i =1） = V1V2V3 上一页下一页15本章教学线索本章教学线索1 高级语言的一般特性高级语言的一般特性2 字符串字符串3 文法和语言文法和语言 3.1 文法的定义（上下文无关的文法） 3.2 直接推导和推导的定义 3.3 最左推导与最右推导 3.4 语言的定义4 语法分析树与二义性问题语法分析树与二义性问题 5 文法的分类（逐渐对产生

10、式施加限制）文法的分类（逐渐对产生式施加限制）上一页下一页163 文法和语言文法和语言 例子：He gave me a book Hegavemebooka语法树语法树上一页下一页17语法规则语法规则 He me a gave book上一页下一页18 注意：其中He,me,book,gave,a等称为终结符；、等称为非终结符号；这种书写形式称为产生式。 产生式（规则，重写规则或生成式）： Uu （或U:=u） 且UV+，uV* ，U是符号,称为规则左部，u是有穷非空符号串，为规则右部。 非终结符号：需要进一步定义的符号，不会出现在程序中。 终结符号：不需要再定义，会出现在程序中。上一页下一页

11、193.1 文法的定义（上下文无关的文法）文法的定义（上下文无关的文法）一个上下文无关的文法G可以表示成一个四元式(VT，VN，S，P)，其中： VT是一个非空有限集，它的每个元素称为终结符； VN是一个非空有限集，它的每个元素称为非终结符，且有VTVN= S是一个非终结符，称为开始符号； P是一个产生式集合（有限），每个产生式的形式是A，其中AVN，（VTVN）*。S至少必须在某个产生式的左部出现一次。可以将左部相同的产生式缩写成：A1|2|3|n 上一页下一页20（注意：终结符号是组成语言的基本符号，比如关键字、标志符、常数、算符和界符等；非终结符用来代表语法范畴，比如算术表达式、赋值语句

12、、程序等；开始符号是一个特殊的非终结符，代表了我们最终有用的语法范畴。） 例2.1：一个简单的算术表达式的文法：G = ( i，+，*，(，)，P )P： * （） i可以简单表示为：E E+TTT T*F FF ( E ) i 上一页下一页21巴科斯范式（BNF：Backus-Naur Form）： “”：表示定义为，“ ”：表示或另一种表示法： := i := + * 将非终结符用括起来表示，用“:=”表示“定义为”，用“ ”表示“或”，这种方法不够简洁。 上一页下一页22令G=（VT，VN，S，P），若AP，且，（VTVN）*，则称A直接推出，表示成A ，我们称：A直接推出 ，反之称直接

13、归约到A； 如果存在一个直接推导序列： 1 2 3 n（n0），我们称这个序列是从 1到n 的一个推导。 1 n：表示从1经过一步或若干步可以推导出n。 1 n：表示从1经过0步或若干步可以推导出n。（ 意味着=，或者 ）。3.2 直接推导和推导的定义直接推导和推导的定义+*上一页下一页23例：E E+T T+T F+Ti+T i+F i+i A产生式E E+TE E+T E+T T+TE T+TT+T F+TT F+TF+Ti+TF i+Ti+Ti+FT Fi+i+Fi+iF ii+上一页下一页243.3 最左推导与最右推导最左推导与最右推导 对于推导，如果每一步都是对中的最左非终结符最左非

14、终结符进行替换的，则我们称这种推导为最左推导，如果每一步都是对中的最最右非终结符右非终结符进行替换的，则我们称这种替换为最右推导。 例2-2：对于文法：EE+ E|E*E|(E)|i 我们看对于（i*i+i）的推导最左推导：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) 上一页下一页25 例2-3:文法GS: SAB AA0|1B B0|S1 请给出句子101001的最左和最右推导。 最左推导： S AB 1B B10B 10S1 10AB1 101BB1 101

15、0B1 101001 最右推导： S AB AS1AAB1 AA01 A1B01 A1001 1B1001 101001 上一页下一页26 假定G是一个文法，S是它的开始符号。如果S ，则称是一个句型。仅含终结符的句型是一个句子。文法G所产生句子的全体是一个语言，将它记为：L（G）， 则L（G）=|S & VT* 例2-4：考虑文法 G(a,b,S,S，P）其中P：SaSb abSaSb aaSbb a3Sb3 an-1Sbn-1 anbn这里文法可以表示为：L(G) = anbn|n1注意：1)句型与句子的区别和联系 2)文法和语言之间并不存在一一对应关系，对于一给定的文法，唯一地确

16、定它所产生的语言；但对于一个给定的语言往往可用若干个不同的文法来产生。3.4 语言的定义语言的定义+*上一页下一页27本章教学线索本章教学线索1 高级语言的一般特性高级语言的一般特性2 字符串字符串3 文法和语言文法和语言4 语法分析树与二义性问题语法分析树与二义性问题 4.1 语法分析树的定义 4.2 文法的二义性问题 4.3 压缩过的文法（化简了的文法）5 文法的分类（逐渐对产生式施加限制）文法的分类（逐渐对产生式施加限制）上一页下一页284.1 语法分析树的定义语法分析树的定义设G=（VT，VN，S，P），G的一棵分析树满足如下条件： 每一结点有一标记，此标记是VTVN中的符号。 根的标

17、记是S。 如果一个结点是内部结点，且标记A，那么A必在VN中。 如果编号为n的结点有标记A，结点n1，n2，nk是点n的从左到右的儿子，并分别有标记X1，X2，Xk，则AX1X2Xk必须是P中的产生式。 若结点n有标记，那么结点n是叶子，且是它父亲唯一的儿子。 上一页下一页29画语法树的两种方法：自顶向下：根据推导序列，对每步推导画相应分枝自底向上：根据归约序列，对每步归约画相应分枝 有关分析树要注意的几点： 一个句型推导或分析用一棵树结构图示出来，它反应了一个句子的语法结构层次。 对于一个句子的多种推导（若文法是无二义性的），采用各种推导过程，画出的分析树是一样的。分析树并未描述推导过程。

18、在书中，用画分析树的过程解释语法分析过程，用分析树图解语法结构。分析树是推导的图形表示。上一页下一页30E（树根）（E）E+EE*Eiii12345E（E）（E+E）（E*E+E）（i*E+E）（i*i+E）（i*i+i）对于（i*i+i）的语法分析树上一页下一页314.2 文法的二义性问题文法的二义性问题 描述一个句子的文法不是唯一的； 对于一个句子的分析应是唯一的。 考虑文法：EE+ E|E*E|（E）|i， 句子 （i*i+i）推导一：E (E) (E+E) (E*E+E) (i*E+E) (i*i+E) (i*i+i)推导二：E (E) (E*E) (i*E) (i*E+E) (i*i

19、+E) (i*i+i)上一页下一页32推导一对应的语法树推导二对应的语法树E（树根）（E）E*EE+Eiii12345E（树根）（E）E+EE*Eiii12345上一页下一页33 如果一个文法的句子存在两棵不同的分析树，那么该句子是二义性的。如果一个文法包含二义性的句子，则称这个文法是二义性的；否则，该文法是无二义性的。 上一页下一页34几点说明：1）一般来说，程序语言要求无二义性文法，对于条件语句，经常使用二义性文法描述它：S if 条件 then 语句 if 条件 then 语句 else 语句 其它语句二义性的句子：if e1 then if e2 then s1 else s2 2）在

20、能驾驭的情况下，使用二义性文法。3）对于任意一个上下文无关文法，不存在一个算法，能够在有限的步骤内判定它是无二义性的；但能给出一组充分条件，满足这组充分条件的文法是无二义性的。上一页下一页354.3 压缩过的文法（化简了的文法）压缩过的文法（化简了的文法）1）文法中不含有任何形如 PP的产生式；2）每个非终结符号P必须都有用处。即： S P 且P ，VT* （两层含义：一方面意味着，必须存在含P的句型，另一方面方面意味着对于P不存在永不终结的回路）*+上一页下一页36本章教学线索本章教学线索1 高级语言的一般特性高级语言的一般特性2 字符串字符串3 文法和语言文法和语言4 语法分析树与二义性问

21、题语法分析树与二义性问题 5 文法的分类（逐渐对产生式施加限制）文法的分类（逐渐对产生式施加限制） 5.1 乔姆斯基文法（Chomsky） 5.2 上下文有关的语法结构 5.3 自嵌套的文法 5.4 文法的递归性 5.5 文法与语言的典型题目上一页下一页375.1 乔姆斯基文法（Chomsky）乔姆斯基文法（Chomsky）：四种类型：0型，1型，2型，3型0型：G =（VT，VN，S，P） 规则形式： ， (VTVN)*， 推导： 例如：GS = （S，A，B，C，D，E，a，P，S），其中P由如下产生式组成：SACaB CaaaC CBDB CBE aDDa ADAC aEEa AE 上一

22、页下一页381型（上下文有关）：对于产生式均满足，仅仅S除外，但S不得出现在任何产生式的右部。例如：GS = （S，A，B，C，A ，a，b，c，P，S） 其中P： SaSBA SabB BABA BA AA AA AB bAbb bBbc cBcc L（G）=aibici|i1 上一页下一页392型（上下文无关）：G的任何产生式为A A VN， (VN VT)* 例如：GS = （S，a，b，SaSb，Sab，S） L（G）= aibi|i13型（右线性）：G的任何产生式为A B或A ， VT*，A、BVN （左线性）：G的任何产生式为A B或A ， VT*，A、BVN3型文法等价于正规式，

23、因此又称为正规文法。上一页下一页40四种文法之间的关系 由于四种文法是按照将产生式做进一步限制而定义的，所以它们之间是逐级“包含”的关系，由四种文法产生的语言也是逐级“包含”的关系。 即： 3型语言类 2型语言类 1型语言类 0型语言类注：0型语言除外，从其中删去或往其中添加一个空串并不改变其语言类。语言层正规语言3上下文无关语言2上下文有关语言1递归可枚举语言0图灵机TM线性界限自动机LBA下推自动机PDA有穷自动机FA上一页下一页415.2 上下文有关的语法结构上下文有关的语法结构 现在使用的程序语言中,有些语言结构并不是总能用上下文无关文法描述的。 例例2.9 L1=wcw|wa,b+。例如,aabcaab就是L1的一个句子。这个语言是检查程序中标识符的声明应先于引用的抽象。 例例2.10 L2=anbmcndm|n,m0，它是检查过程声明的形参个数和过程引用的参数个数一致问题的抽象。 语言中过程定义