《西安电子科技大学编译原理课件》由会员分享，可在线阅读，更多相关《西安电子科技大学编译原理课件（32页珍藏版）》请在金锄头文库上搜索。
1、第三章 语法分析 词法分析：元素是字母表，组成字符串，线性结构，单词的集合语法分析：元素是终结符，组成句子，树结构， 句子的集合语法的双重含意： 语法规则：上下文无关文法（子集LL文法或LR文法） 语法分析：下推自动机（LL或LR分析器），自上而下和自下而上分析 本章主要内容： 与语法分析有关的基本概念和相关问题 上下文无关文法 自上而下分析 自下而上分析 上机作业第二部分：函数绘图语言的语法分析器1西安电子科技大学编译原理3.1 语法分析的若干问题 3.1.1 语法分析器的作用 语法分析器是编译器前端的重要组成部分，许多编译器，特别是由自动生成工具构造的编译器，往往其前端的中心部件就是语法分
2、析器。语法分析器在编译器中的位置和作用下：它的主要作用有两点： 根据词法分析器提供的记号流，为语法正确的输入构造分析树（或语法树），这是本章的重点，在以后各节中详细讨论； 检查输入中的语法（可能包括词法）错误，并调用出错处理器进行适当处理，下边简单介绍语法错误处理的基本原则，而在以后的讨论中忽略此问题。 2西安电子科技大学编译原理3.1.2 语法错误的处理原则 源程序中可能出现的错误 两类：语法错误和语义错误。 词法错误如非法字符或拼写错关键字、标识符等； intege20times 语法错误是指语法结构出错，如少分号、begin/end不配对等。beginx:=a+by:=x; 静态语义错误
3、：如类型不一致、参数不匹配等；a,b:integer;x:array1.10 of integer;x:=a+b; 动态语义错误（逻辑错误）：如无穷递归、变量为零时作除数等。while (t) .;a:=a/b; 大多数错误的诊断和恢复集中在语法分析阶段。一个原因是大多数错误是语法错误，另一个原因是语法分析方法的准确性，它们能以非常有效的方法诊断语法错误。 在编译的时侯，想要准确诊断语义或逻辑错误有时是很困难的。 3西安电子科技大学编译原理3.1.2 语法错误的处理原则（续1） 语法错误处理的目标 对语法错误的处理，一般希望达到以下基本目标： 清楚而准确地报告错误的出现，地点正确、不漏报、不错
4、报也不多报； 迅速地从每个错误中恢复过来（以便分析继续进行）； 不应使对语法正确源程序的分析速度降低太多。4西安电子科技大学编译原理3.1.2 语法错误的处理原则（续2） 语法错误的基本恢复策略 紧急方式恢复：抛弃若干输入，直到遇到同步记号。 短语级恢复：采用串替换的方式对剩余输入进行局部纠正（抛弃插入）。 出错产生式：用出错产生式捕捉错误（预测错误）。预置型的短语级恢复方式。 全局纠正：对错误输入序列x，找相近序列y，使得x变换成y所需的修改、插入、删除次数最少。 例3.1 下述两条是有语法错误的语句，其中第一条赋值句结束时忘记加分号，采用紧急恢复方式和短语级恢复方式的可能结果分别如下所示。
5、 x := a + b y := c + d;紧急方式： x := a + b + d; - 丢弃b之后的若干记号，直到遇到同步记号+为止。短语级恢复：x := a + b; - 加入分号，使之成为一个赋值句 y := c + d; 5西安电子科技大学编译原理3.2 上下文无关文法(Context Free Grammar, CFG)3.2.1 CFG的定义与表示 定义3.1 CFG是一个四元组G =（N，T，P，S），其中（1） N是非终结符（Nonterminals）的有限集合；（2） T是终结符（Terminals）的有限集合，且NT=；（3） P是产生式（Productions）的有限
6、集合， A，其中AN（左部），(NT)*（右部）， 若=，则称A为空产生式（也可以记为A ）；（4） S是非终结符，称为文法的开始符号（Start symbol）。例3.2 简单算术表达式的上下文无关文法可表示如下： N=E T=+，*，(，)，-，id S=E P: E E + E （1） E E * E （2） E （E） （3） (G3.1) E -E （4） E id （5） 6西安电子科技大学编译原理 由产生式集表示CFG 3.2.1 CFG的定义与表示（续1）前提：若文法正确，第一个产生式的左部是文法开始符号S则： N是仅出现在产生式左边符号的集合， T是所有不出现在产生式左边符号
7、的集合（记号）P: E E + E （1） E E * E （2） E （E） （3） E -E （4） E id （5） 产生式的一般读法 可以将产生式中的记号读作“定义为”或者“可导出”。 更一般的，“E E + E”可用自然语言表述为“算术表达式定义为两个算术表达式相加”， 或者“一个算术表达式加上另一个算术表达式，仍然是一个算术表达式”。 终结符与非终结符书写上的区分 (a) 用大小写区分： E id (b) 用“”区分： E id E E + E (c) 用区分： + 约定：大写英文字母A、B、C表示非终结符； 小写英文字母a、b、c表示终结符； 小写希腊字母、表示任意文法符号序列。
8、 S=EN=ET=+，*，(， )，-，id7西安电子科技大学编译原理 产生式的缩写形式 3.2.1 CFG的定义与表示（续2） 当若干个产生式具有相同的左部非终结符时，可以将它们合并为一个产生式。 该产生式的左部是此非终结符， 右部是所有原来右部的或运算（并集合）， 产生式也以非终结符命名。例3.3 G3.1可以重写为如下形式： E E + E （1） | E * E （2） |（E） （3） (G3.2) | -E （4） | id （5）P: E E + E （1） E E * E （2） E （E） （3） E -E （4） E id （5） 我们可以称它为E产生式。 用“|”连接的每
9、个右部称为一个候选项，它们具有平等的权利。 即id是一个表达式，-E也是一个表达式。8西安电子科技大学编译原理3.2.2 CFG产生语言的基本方法推导 CFG（产生式）通过推导的方法产生语言。 通俗地讲，产生式产生语言的过程是从开始符号S开始， 对产生式左部的非终结符反复地使用产生式： 将产生式左部的非终结符替换为右部的文法符号序列（展开产生式，用标记=表示），直到得到一个终结符序列。 例3.4 用(G3.2)产生终结符序列-(id+id)可如下：E = -E by(4) = -(E) by(3) = -(E+E) by(1) = -(id+E) by(5) = -(id+id) by(5)E
10、 E + E （1） | E * E （2） |（E） （3） (G3.2) | -E （4） | id （5）9西安电子科技大学编译原理3.2.2 CFG产生语言的基本方法推导（续1）定义3.2 利用产生式产生句子的过程中，将产生式A的右部代替文法符号序列A中的A得到的过程，称为A直直接接推推导导出，记作：A=。 若 对 于 任 意 文 法 符 号 序 列 1， 2， .n， 均 有1=2=.=n，则称此过程为零步或多步推导零步或多步推导，记为：1=*n，其中1=n的情况为零步推导零步推导。 若1n，即推导过程中至少使用一次产生式，则称此过程为至少一步推导至少一步推导，记为：1=+n。 定义
11、3.2强调了两点： ，有=*，即推导具有自反性； 若=*，=*，则=*，即推导具有传递性。定义3.3 由CFG G所产生的语言L(G)被定义为: L(G) = S=+ and T* ， L(G)称为上下文无关语言（Context Free Language, CFL），称为句子。若S=*，(NT)*，则称为G的一个句型。 10西安电子科技大学编译原理3.2.2 CFG产生语言的基本方法推导（续2）定义3.4 在推导过程中，若每次直接推导均替换句型中最左边的非终结符，则称为最左推导最左推导，由最左推导产生的句型被称为左句型左句型。 类似的可以定义最右推导与右句型，最右推导也被称为规范推导规范推导
12、。 再考察-(id+id)的推导过程（这是一个最左推导）： E = -E = -(E) = -(E+E) = -(id+E) = -(id+id) 1 2 3 4 5 6 其中，1是文法开始符号，6是句子，其他i(i=2、3、4、5)均是句型。句型是一个相当广泛的概念，根据定义3.3可知，1和6同样也是句型。 11西安电子科技大学编译原理3.2.3 推导、分析树与语法树 对于推导：E = -E = -(E) = -(E+E) = -(id+E) = -(id+id) 它产生句子的方式很不直观，看起来十分困难。 分析树是推导的图形表示，它的表示很直观，并且同时反映语言结构的实质和推导过程。 定义
13、3.5 对CFG G的句型，分析树被定义为具有下述性质的一棵树。 （1） 根由开始符号所标记； （2） 每个叶子由一个终结符、非终结符、或标记； （3） 每个内部结点由一个非终结符标记； （4） 若A是某内部节点的标记，且X1，X2，.，Xn是该节点从左到右所有孩子的标记，则AX1X2.Xn是一个产生式。若A，则标记为A的结点可以仅有一个标记为的孩子。 分析树与语言和文法的关系： 每一直接推导（每个产生式），对应一棵仅有父子关系的子树，即产生式左部非终结符“长出”右部的孩子； 分析树的叶子，从左到右构成G的一个句型。若叶子仅由终结符标记，则构成一个句子。12西安电子科技大学编译原理3.2.3
14、推导、分析树与语法树（续1）例3.5 再考察-(id+id)的推导过程。E = -E = -(E) = -(E+E) = -(id+E) = -(id+id) 用分析树的方式如下：E -EE ( E )E E + EE id 最左推导和最右推导的中间过程对应的分析树可能不同，因为句型不同： -(id+E) 或 -(E+id) 但是最终的分析树相同，因为最终是同一个句子： -(id+id) 分析树既反映了产生句型的推导过程，又反映了句型的结构。13西安电子科技大学编译原理3.2.3 推导、分析树与语法树（续2） 更多的情况下，仅关注句型结构，而忽略推导过程。 定义3.6 对CFG G的句型，表达
15、式的语法树被定义为具有下述性质的一棵树: （1） 根与内部节点由表达式中的操作符标记； （2） 叶子由表达式中的操作数标记； （3）用于改变运算优先级和结合性的括弧，被隐含在语法树的结构中。 14西安电子科技大学编译原理3.2.3 推导、分析树与语法树（续3）例3.6 句子-(id+id)和句型if C then s1 else s2 ：S if C then S1 else S2分析树：左部非终结符“产生”右部文法符号序列；语法树：操作符（运算）“作用于”操作数（运算对象）；习惯上：分析树和语法树被分别称为具体语法树和抽象语法树。 15西安电子科技大学编译原理3.2.4 二义性与二义性的消除
16、3.2.4.1 二义性（歧义，Ambiguity） 问题：一个句子可能对应多于一棵分析树例3.7 句子id+id*id和id+id+id可能的分析树：G3.2：E E + E （1） | E * E （2） |（E） （3） | -E （4） | id （5）定义3.7 若G对同一句子产生不止一棵分析树，则称G是二义的。 原因：在产生句子的过程中某些直接推导有多于一种选择 一个句子有多于一棵分析树，仅与文法和句子有关，与采用的推导方法无关； 文法中缺少对文法符号优先级和结合性的规定。16西安电子科技大学编译原理“悬空（dangling）else”问题 3.2.4.1 二义性（续1）S if C
17、 then S (1) | if C then S else S (2) | id := E (3)(G3.3)C E = E | E E (4).(6)E E + E | - E | id | n (7).(10)例3.8 条件语句 if x0 then x:=5 else x:=-5 if x0 then x:=5 else x:=-5if x0 then x:=5 else x:=-517西安电子科技大学编译原理3.2.4.2 二义性的消除 文法二义不能说明程序设计语言是二义。程序设计语言不能二义。消除语言二义的两种方法： 改写二义文法为非二义文法； 规定二义文法中符号的优先级和结合性，
18、使仅产生一棵分析树。 改写二义文法为非二义文法再分析id+id*id和id+id+id：例3.9 与G3.2等价的非二义文法: E E + T | T T T * F | F (G3.4) F （E） | -F | id问题：如何将二义文法改写为非二义文法？18西安电子科技大学编译原理可以看出： 改写二义文法为非二义文法（续1） 新引入的非终结符，限制了每一步直接推导均有唯一选择； 最终分析树的形状，仅与文法有关，而与推导方法无关； 非终结符的引入，增加了推导步骤（分析树增高）； 越接近S的文法符号的优先级越低。（如EE+T）。 对于AA，若A在终结符左边出现（即终结符在中），则A产生式具有左
19、结合性质。 改写二义文法的关键步骤：(a) 引入一个新的非终结符，增加一个子结构并提高一级优先级；(b) 递归非终结符在终结符左边，运算具有左结合性，否则具有右结合性。 例3.10 改写二义文法G3.2为G3.4 ： E E + E （1） | E * E （2） |（E） （3） | -E （4） | id （5）E E + T | TT T * F | FF (E) | -F | id19西安电子科技大学编译原理再讨论“悬空else”问题 改写二义文法为非二义文法（续2） if-then-else和if-then：在一个复合if语句中，可能then多于else，使得else不知与哪个the
20、n结合。 一般原则是右结合，即else与其左边最靠近的then结合。 改写文法的根据是将S分为完全匹配（MS）和不完全匹配（UMS）两类，且在UMS中规定else右结合。 S if C then S | if C then S else S | id := EC E = E | E EE E + E | - E | id | nS MS (1) | UMS(2)MS if C then MS else MS (3) | id := E(4)UMS if C then S(5) | if C then MS else UMS(6)(G3.5)C E = E | E E(7).(9)E E + T
21、 | T(10).(11)T T * F | F(12).(13)F （E） | -F | id | n(14).(17)20西安电子科技大学编译原理 改写二义文法为非二义文法（续3）if x0 then x:=5 else x:=-5if x0 then x:=5 else x:=-5S MS (1) | UMS(2)MS if C then MS else MS (3) | id := E(4)UMS if C then S(5) | if C then MS else UMS(6)C E = E | E E(7).(9)E E + T | T(10).(11)(G3.5)T T * F
22、| F(12).(13)F （E） | -F | id | n(14).(17)21西安电子科技大学编译原理 为文法符号规定优先级和结合性二义文法的优点： 比非二义文法容易理解； 分析效率高（分析树低，直接推导步骤少）。对于：id+id*id 为二义文法规定优先级和结合性（YACC的方法）： %left +%left *%right -E : E + E | E * E | - E | ( E ) | idE E + E | E * E | - E | ( E ) | idEE+T|TTT*F|FF(E)|-F|id22西安电子科技大学编译原理 修改语言的语法（表现形式被改变） Ada中用en
23、d if结束条件语句，于是有：if x3 if x0 then if x0then x:=5; then x:=5;end if;else x:=-5;else x:=-5;end if;end if;end if; 给表达式加括号，如Pascal中逻辑和算术运算：(a+b)(c*d) 23西安电子科技大学编译原理3.3 语言与文法简介 文法的重要作用： 给出精确、易于理解的语言结构说明； 以文法为基础的语言，便于加入新的、或修改、删除旧的语言结构； 有些类别的文法，可以自动生成高效的分析器。 本节从理论的角度对文法进行简单地讨论。讨论建立在形式语言与自动机的理论之上，且仅引用结论而忽略数学的
24、证明，有兴趣的同学可以参阅相关文献。 希望通过本节的讨论，对文法的分类和它们在编译器构造中的作用有一定的了解。 （证明技术.ppt：语言与问题、证明技术等简单介绍）24西安电子科技大学编译原理3.3.1 正规式与上下文无关文法 正规式到CFG的转换推论3.1 正规式所描述的语言结构均可用CFG描述，反之不一定。 从正规式到CFG的对应关系： 构造正规式的NFA； 若0为初态，则A0为开始符号； 对于move(i,a)=j，引入产生式AiaAj； 对于move(i,)=j，引入产生式 AiAj； 若i是终态，则引入产生式Ai 。例3.11 从正规式r=(a|b)*abb的NFA构造CFG： A0
25、 aA0|bA0|aA1A1 bA2A2 bA3A3 经验的方法：A HTH | Ha | HbT abb分别产生abb的分析树：25西安电子科技大学编译原理 为什么用正规式而不用CFG描述词法 词法规则简单，用正规式描述已足够； 正规式的表示比CFG更直观、简洁、易于理解； 有限自动机的构造比下推自动机简单，且分析效率高； 区分词法和语法，为编译器前端的模块划分提供方便。 贯穿词法分析和语法分析始终的思想： 语言的描述和语言的识别是表示一个语言的两个不同侧面，二者缺一不可；（语言、文法、自动机） 用正规式和CFG描述的语言，对应的识别方法（自动机）不同； 一般情况下，正规式适合描述线性结构，
26、如标识符、关键字、注释等； CFG适合描述具有嵌套（层次）性质的非线性结构，如不同结构的句子if-then-else、while-do等。 26西安电子科技大学编译原理3.3.2 上下文有关语言（Context Sensitive Language, CSL） 程序设计语言中除了CFG可以描述的结构之外，还有一些是CFG无法描述的所谓上下文有关的结构。 典型的这类语言结构包括：变量的声明与引用、过程调用时形参与实参的一致性检查等。 描述它们的文法被称为上下文有关文法（Context Sensitive Grammar, CSG）。 例3.12 不能用CFG描述的语言： L1=c|(a|b)*（
27、 标识符声明与引用一致性的抽象）L2=anbmcndm|n1和m1 （形参与实参一致性的抽象）L3=anbncn|n1 （计数问题的抽象） 相近的CFL：L1=cr|(a|b)* （SaSa|bSb|c）L2=anbmcmdn|n1, m1 （SaSd|aAd AbAc|bc）L2=anbncmdm|n1, m1 （SAB AaAb|abBcBd|cd）L3=ambmcn|m, n1 （AAC AaAb|ab CcC|c）27西安电子科技大学编译原理计数问题L3=anbncn|n1 CSLL3=ambmcn|m,n1 CFL（AAC AaAb|ab CcC|c）命题：L3不是正规集，因为构造不
28、出可以识别L3的DFA。 证明：（反证） 假设L3是正规集，则可构造n个状态的DFA D，它接受L3； 考察D读完，a，aa，.，an，分别到达S0，S1，.，Sn，共有n+1个状态。根据鸽巢原理，序列中至少有两个状态相同，设Si=Sj（ji），因为aibick L3所以存在路径aibick。但是D中也有路径ajbick，矛盾。故L3不是正规集。 L3=akbmcn|k，m，n1 （a+b+c+ ）28西安电子科技大学编译原理3.3.3 形式语言与自动机简介 定义3.8 若文法G=(N，T，P，S)的每个产生式中，均有(NT)*，且至少含有一个非终结符，(NT)*，则称G为0型文法。 对0型文
29、法施加以下第i条限制，即得到i型文法。 1. G的任何产生式（S除外）满足|； 2. G的任何产生式形如A，其中AN，(NT)*； 3. G的任何产生式形如Aa或者AaB(或者ABa)，其中A，BN，aT。 文法、语言与自动机文 法语 言自 动 机短语文法 (0型)短语结构语言图灵机CSG (1型)CSL线性界线自动机CFG (2型)CFL下推自动机正规文法 (3型)正规集有限自动机29西安电子科技大学编译原理再考察L3： 3.3.3 形式语言与自动机简介（续）L3=anbncn|n1L3=ambmcn|m,n1 （AAC AaAb|ab CcC|c）L3=akbmcn|k，m，n1 （a+b
30、+c+ ）例3.15 L3可以用下述CSG描述： SaSBC (1) SaBC (2) CBBC (3) aBab (4) bBbb(5) bCbc(6) cCcc(7)句子akbkck 的推导：S =.= ak-1S(BC)k-1 (1) = ak(BC)k (2) =.= akBkCk (3) = akbBk-1Ck (4) =.= akbkCk (5) = akbkcCk-1 (6) =.= akbkck (7)结论：CSG、CFG、正规式能力递减（看教材）但是：能力越强的文法，其文法的设计和自动机的构造越困难因此：语法分析仅用到CFG（除特别指出，文法即指CFG ）30西安电子科技大学
31、编译原理结 束31西安电子科技大学编译原理改写二义文法：(a) 引入一个新的非终结符，增加一个子结构并提高一级优先级；(b) 递归非终结符在终结符左边，运算具有左结合性，否则具有右结合性。 E E + E （1） | E * E （2） |（E） （3） | -E （4） | id （5）1. 优先级：+*( ), -, id2. 结合性：左结合+, *右结合-无结合id3. 非终结符与运算：E:+（E产生式，左递归）T:*，（T产生式，左递归）F:-,( ), id（F产生式，右递归）E E + T | TT T * F | FF (E) | -F | id问题： 如何看待( )？ 返回32西安电子科技大学编译原理
