《编译原理ppt课件》由会员分享，可在线阅读，更多相关《编译原理ppt课件（52页珍藏版）》请在金锄头文库上搜索。
1、 2010年年9月月.第2章 形式语言概论 （主要介绍形式语言理论中的一些基本概念和基础知识，包括、语言、语法树和分析方法等） 2010年年9月月.2.1 字母表和符号串2.2 文法及其分类2.3 语言和语法树2.4 关于文法和语言的几点说明2.5 分析方法简介2.6 小结 2010年年9月月.2.1 字母表和符号串一、字母表和符号串一、字母表和符号串 字母表字母表：符号的非空有限集 例：=a，b，c 符号符号：字母表中的元素 例： a，b，c 符号串符号串：符号的有穷序列 例：a, aa, ac, abc，. 空符号串空符号串：无任何符号的符号串(） 符号串集合符号串集合：由符号串构成的集合
2、。符号串的形式定义符号串的形式定义 有字母表，定义： （1）是上的符号串； （2）若x是上的符号串，且a ，则ax或xa是上的符号串； （3）y是上的符号串，iff（当且仅当）y可由（1）和（2）产生。 2010年年9月月.二、符号串和符号串集合的运算二、符号串和符号串集合的运算 1.符号串相等符号串相等：若x、y是集合上的两个符号串，则xyiff（当且仅当）组成x的每一个符号和组成y的每一个每一个符号依次相等。 2.符号串的长度符号串的长度：x为符号串，其长度|x|等于组成该符 号串的符号个数。 例： xCCTV ， |x|=4 特别有|0，即空符号串的长度等于零。 2010年年9月月.例：
3、Aa,b,B=c,d, AB= ？ 4. 符号串集合的乘积运算符号串集合的乘积运算：令A、B为符号串集合，定义 AB xy |xA,yB注意：注意：因为xxx，所以A=A=A A=A= 其中，为空集 3. 3.符号串的联接符号串的联接：若x、y是定义在是上的符号串，且xXY，yYX，则x和y的联接 xyXYYX也是上的符号串。 注意：一般xyyx，而xxac，ad，bc，bd 2010年年9月月.5. 5. 符号串的方幂运算符号串的方幂运算 同一符号串的连接可以写成方幂形式。 设x是一符号串，则定义 x0= x1=x x2=xx x3=x2x=xx2=xxx xn=xxn-1= xxx n n
4、 个个例如： x=abc 则 x2=abcabc x3=abcabcabc6. 6. 符号串集合的幂运算符号串集合的幂运算 有符号串集合A，定义 A0 =, A1=A, A2=AA, A3=AAA, AnAn-1A=AAn-1 ，n0例如：A=a,bc 则A2=AA=aa, abc, bca, bcbc A3=A2A=aaa, abca, bcaa, aabc, abcbc, bcabc, bcbca, bcbcbc 2010年年9月月.6.6.符号串集合的闭包运算符号串集合的闭包运算 设A是符号串集合，定义 A A1 A2 A3 An 称为集合A的正闭包。 A* A0 A称为集合A的自反闭包
5、。 显然有 A+=AA*=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 2010年年9月月.为什么对符号、符号串、符号串集合以及它们的运算感兴趣？为什么对符号、符号串、符号串集合以及它们的运算感兴趣？若A为某语言的基本字符集 Aa,b,z,0,1,9, +, /, ( , ), =B为单词集 B =begin, end, if, then,else,for, 则B A* 。语言的句子是定义在B上的符号串。若令C为
6、句子集合，则C B * , 程序 C 2010年年9月月.2.2 文法及其分类文法的非形式讨论文法的非形式讨论 1.什么是文法：文法是对语言结构的定义与描述。即从形式上用于描述和规定语言结构的称为“文法”（或称为“语法”）。 例：有一句子：“我是大学生” 。这是一个在语法、语义上都正确定句子，该句子的结构（称为语法结构）是由它的语法决定的 。在本例中它为“主谓结构”。 2010年年9月月. 2.2.语法规则语法规则：我们通过建立一组规则，来描述句子的语法结构结构。规定用“:=”表示“由组成”或“定义为”。:=:=| :=你|我|他:= 王民|大学生|工人|英语:=:=是|学习:=| 2010年
7、年9月月.3. 由规则推导推导句子：有了一组规则之后，可以按照一定的方式用它们去推导或产生句子。 推导方法：从一个要识别的符号开始推导，即用相应规则的右部来替代规则的左部，每次仅用一条规则去进行推导。 = = 这种推导一直进行下去，直到所有带的符号都由终结符号替代为止。 2010年年9月月. = = = 我 =我 =我是 =我是 =我是大学生:=:= :=:=| := :=你你| |我我| |他他 :=:= 王民王民| |大学生大学生| |工人工人| |英语英语 :=:= :=:=是是| |学习学习 :=:=| 推导方法：推导方法：从一个要识别的符号开始推导，即用相应规则的右部来替代规则的左部
8、，每次仅用一条规则去进行推导。 2010年年9月月.例：有一英语句子：The big elephant ate the peanut.:=:= :=the:=big:=elephant:=:=ate:= :=peanut 2010年年9月月. = = = 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:=:= :=:= := :
9、=the :=:=big :=:=elephant | peanut :=:= :=:=ate :=:= 2010年年9月月.上述推导可写成 = the big elephant ate the peanut+说明： (1) 有若干语法成分同时存在时，我们总是从最左的语法成 分进行推导，这称之为最左推导，类似的有最右推导（一般推 导）。 (2) 从一组规则可推出不同的句子，如以上规则还可推出“大象吃象”、“大花生吃象”、“大花生吃花生”等句子，它们 在语法上都正确，但在语义上都不正确。 所谓文法文法是在形式上对句子结构的定义与描述，而未涉及语义问题。 2010年年9月月.产生式的定义产生式的定
10、义 设VN、 VT分别是非空有限的非终结符号集和终结符号集，V=VNVT ,VNVT=。 一个产生式是一个有序偶对（,）,其中V+,V*，通常表示为或:=。 称为产生式的左部，称为产生式的右部。 产生式又称为重写规则，它意味着能将一个符号串用另一个符号串替换。 2010年年9月月. 文法G =（VN，VT，P，S） VN：非终结符号集 VT：终结符号集 P：产生式或规则的集合 S：开始符号（识别符号） SVN 文法的定义文法的定义规则：U : xU VN, xV*如果产生式集中的产生式有共同的左部，如 :=，:=则可将其简写成:=| 2010年年9月月.P = Z ； ； ； ； 0； 1；
11、9；例：无符号整数的文法：G=（VN，VT，P，E）VN, ,EVT = 0,1,2,3,9 2010年年9月月. 文法和语言分类文法和语言分类 Chomsky将文法分为四类：0型、1型、2型、3型 这几类文法的差别在于对产生式施加不同的限制。 0型： P： := 其中(VNVT)，(VNVT)* 0型语言：L0 这种语言可以用图灵机(Turing)接受. 0型文法称为短语结构文法。规则的左部和右部都可以是符号串，一个短语可以产生另一个短语。 2010年年9月月. 1型： P： 1A2:= 12 其中 1,2(VNVT)*, AVN, (VNVT)+ 1型语言：L1 这种语言可以由一种线性界限
12、自动机接受.称为上下文有关文法或上下文敏感文法。也即只有在1,2这样的上下文中才能把A改写为。 2010年年9月月. 2型： P： A:= 其中 AVN， (VNVT)+ 2型语言：L2 这种语言可以由下推自动机接受. 称为上下文无关文法。也即把A改写为时，不必考虑上下文。 注意：2型文法与BNF表示相等价。 2010年年9月月.（左线性） P： A:=a 或 A:=Ba 其中 A、BVN aVT3型语言：L3 又称正则语言、正则集合 这种语言可以由有穷自动机接受. 3型文法称为正则文法。它是对2型文法进行进一步限制。（右线性） P： A:=a 或 A:=aB 其中 A、BVN aVT 3型文
13、法： 2010年年9月月.根据上述分析，L0 L1 L2 L3 0型文法可以产生L0、L1、L2、L3，但2型文法只能产生L2，不能产生L1。 从0型文法到3型文法，各文法描述语言的能力依次减弱。 2010年年9月月.2.3语言和语法树和推导推导有关的内容 直接推导直接推导 设文法G(VN, VT, P, S) (, )P ，, (VNVT)* 则称符号串为符号串应用产生式:=所得到的直接推导直接推导，记为= 特别有，当时，有= 即每个产生式得右部都是它左部的直接推导。 2010年年9月月. 1 1 0(6)=(1)=(3)(5)=(2) 当符号串已没有非终结符号时，推导就必须终止。因为终结符
14、不可能出现在规则左部，所以将在规则左部出现的符号称为非终结符号。例如：例如：G (1) ； (2) (3) (4) 0;0;(5) 1;1; (13) 9;9; 2010年年9月月. 推导推导 文法G，U0,U1,U2,，Un V+ if v= U0 U1 U2 Unu 则v u = G= G= G= G= G例：= = = =1 =1 0即 10= G 2010年年9月月. 多步推导多步推导 文法G，v，w V+ if v w ,或v=w，则v w *= G= G 规范推导规范推导 有xUy = xuy, if y Vt* ,则此推导为规范的，记为xUy = xuy|直观意义：规范推导最右推
15、导最右推导：若符号串中有两个以上的非终结符时，先推右边的。最左推导：若符号串中有两个以上的非终结符时，先推左边的。 + 若有v=U0=U1=U2=Un=w,则 v=w 。 2010年年9月月. 句型、句子和语言句型、句子和语言文法GZ所产生的所有句子的集合 形式语言理论可以证明以下两点： （1）G L（G）； （2）L(G)G1，G2，Gn； 已知文法，求语言，通过推导； 已知语言，构造文法，无形式化方法，更多是凭经验。 文法GZ （1）句型句型：x是句型 Z x,且xV*；（2）句子句子：x是句子 Z x, 且xVT*；（3）语言语言：L（GZ）=x| xVT*, Z x ；+* 2010年
16、年9月月. G1Z： ZaBa, Bb|bB G2Z： ZaBa, Bb|Bb等价文法等价文法 G和G是两个不同的文法，若 L(G) = L(G) , 则G和G为等价文法。例：abna|n1,构造其文法 2010年年9月月. 推导与语法树推导与语法树（1）语法树：句子结构的图示表示法，它是一种有向图，由结点和有向边组成。 结点：符号 根结点：识别符号识别符号 中间结点：非终结符非终结符 叶结点：终结符或非终结符终结符或非终结符 有向边：表示结点间的派生关系。 ZUVabcd 2010年年9月月. 注意一个重要事实：文法所能产生的句子，可以 用不同的推导原则（使用产生式顺序不同）将其 推导出来。
17、语法树的生成规律不同，但最终生成的语 法树形状完全相同。某些文法有此性质，而某些文法 不具此性质。( 2 ) 句型的推导及语法树的生成（自顶向下）给定GZ，句型w： 可建立推导序列，Z=w 可建立语法树，以Z为树根结点，每步推导生成语法树的一枝，最终可生成句型的语法树。G* 2010年年9月月. 1(1)(2)(3)(5)(4)0一般推导： 2010年年9月月.( 3 ) 树与推导句型推导过程句型语法树的生长过程 由推导构造语法树由推导构造语法树1从识别符号开始，自左向右建立推导序列。由根结点开始，自上而下建立语法树。 2010年年9月月.例：G句型 10= =0 0= 0=110=规范推导
18、2010年年9月月. 由语法树构造推导由语法树构造推导2自上而下地修剪子树的末端结点，直至把整棵树剪掉（留根），每剪一次对应一次规约。从句型开始，自右向左地逐步进行规约，建立推导序列。 注：注： 对句型中最左简单短语（句柄）进行的规约称为 规范规约。 2010年年9月月.01= = 0=10 0=规范规约与规范推导互为逆过程 2010年年9月月.特别有特别有，通过规范推导或规范规约所得到的句型称为规范句型。 在上例中， 就不是规范句型，因为：=不是规范推导 2010年年9月月.2.4关于文法和语言的几点说明1. 1. 无用非终结符号无用非终结符号 如果文法的某个非终结符不出现在文法的任何一个句
19、型中，并且不能从它推导出终结符号串，则称该非终结符为无用非终结符号。设文法GA： A:=aaBbb B:=aBb | ab C:= Cd | c D:=Ef 此文法中的非终结符D与E ，不可能出现在任何一个句型中，而且不能从它们推导出终结符号，所以，D与E是无用非终结符。 2010年年9月月.2. 2. 不可达文法符号不可达文法符号 如果一个非终结符（非识别符号）不出现在文法的任何一条产生式的右部，则称该非终结符号为不可达文法符号。 不可达文法符号和无用非终结符号都不能出现在文法的句型中，也就是说，它们对与生成文法的语言都毫无意义，或者说包含不可达文法符号或无用非终结符号的产生式对于文法来讲都
20、是多余的。 实际上，形如U:=U的产生式也是多余产生式。这种产生式不仅对文法是不必要的，而且还可能引起文法的二义性。 2010年年9月月.3 3. 可空非终结符可空非终结符 2型文法的产生式形如 A:= 其中, AVN, (VNVT)+ 对2型文法进行扩充，令 (VNVT)*，即允许出现如下产生式 A:= 此产生式称为空产生式，A称为可空非终结符。 2型文法添加空产生式之后，文法的语言除了增加一个空串之外，并没有改变文法的类型。空产生式往往会带来方便，如消除左递归。 2010年年9月月.4. 4. 二义性二义性 若对于一个文法的某一句子存在两棵不同的语法树，则该文法是二义性文法，否则是无二义性
21、文法。 换而言之，无二义性文法的句子只有一棵语法树，尽管推导过程可以不同。下面举一个二义性文法的例子： GE: E:= E+E | E*E | (E) | i Vn=EVt= +, * , ( , ) , i 2010年年9月月. 对于句子Sii * i L（GE ），存在不同的规范推导：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 2010年年9月月. 注：注：若一个文法的某句子存在两个不同的规范推导，
22、则该文法是二义性的，否则是无二义性的。 若文法是二义性的，则在编译时就会产生不确定性，遗憾的是在理论上已经证明：文法的二义性是不可判定的，即不可能构造出一个算法，通过有限步骤来判定任一文法是否有二义性。 现在的解决办法是：提出一些限制条件，称为无二义性的充分条件，当文法满足这些条件时，就可以判定文法是无二义性的。 2010年年9月月.例例: :算术表达式的文法算术表达式的文法E:= E+E | E*E | (E) | iE:= E+T | TT := T*F | FF := (E) | i例例:Pascal :Pascal 条件语句的文法条件语句的文法:= If then | If then
23、else := | |. 对该文法可以加以一定的限制，比如限制条件语句then之后不允许再是条件语句，或者从语义解释方面限制条件语句中的else只能与其紧前面的还没有和其它else配对的then 配对。 2010年年9月月.2.5分析方法简介 任务：给定GZ: S Vt*, 判定是否有 S L (GE ) ?这是词法分析和语法分析所要做的工作，将在第三、四、五章中详细介绍。自上而下分析方法自上而下分析方法 自下而上分析方法自下而上分析方法 2010年年9月月. 自上而下分析方法 基本思想：从文法的识别符号出发，看是否能推导出待检查的符号串，如果能推导出这个符号串，则表明此符号串是该文法的一个句
24、型或句子，否则便不是。 或者说，以文法的识别符号作为根节点，看其是否能构造一个语法树，而且此语法树所有叶子节点从左到右所构成的符号串恰好是待检查的符号串。如果能生成这样的语法树，则表明待检查的符号串是该文法的一个句型或句子，否则便不是。 2010年年9月月.例 设文法GS：S:=aAbc|aB A:=ba B:=beB|d采用自上而下分析，对符号串abed进行分析，识别它是不是该文法的一个句子。SaAbcbaaBbeBd带回溯的自上而下分析 2010年年9月月. 带回溯的自上而下分析方法，又称为不确定的自上而下分析方法。这种方法显然花费时间多，效率低。 确定的自上而下分析方法是指在分析的过程中
25、，选择某个非终结符的产生式，是根据待检查符号串的当前符号以及各产生式右部首符号而进行的，因此是确定的。 2010年年9月月.例：设文法GS：S:=aBc|bCd B:=eB|f C:=dC|c 试检查符号串aefc是不是该文法的句子。SaBceBf 2010年年9月月. 自下而上分析方法 基本思想：从待检查的符号串出发，看最终是否能归约（推导的逆过程）到文法的识别符号。如果能归约到文法的识别符号，则表明此待检查的符号串是该文法的一个句型或句子，否则便不是。 从待检查符号串出发，在其中寻找一个称为句柄的子串，此句柄如果与文法中的某一产生式右部相匹配，那么就用此产生式左部（一个非终结符）去替换待检查符号串中的句柄，替换之后得一新符号串，然后对这新符号串作同样处理。这便是一个归约的过程。 这里需解决两个问题，一是满足什么条件的子串为句柄，二是怎样从一个符号串中寻找句柄。 2010年年9月月.本章重点基本概念：文法、句型、句子、语言 、推 导、二义性和分析方法等 文法的分类与设计语法树的应用 2010年年9月月.作业：P33 2.2 2.4 2.5 2.6 2.7 2.8
