《5西安电子科技大学《编译原理》》由会员分享，可在线阅读，更多相关《5西安电子科技大学《编译原理》（32页珍藏版）》请在金锄头文库上搜索。
1、第三章 语法分析 词法分析：元素是字母表，组成字符串，线性结构，单词的集合 语法分析：元素是终结符，组成句子，树结构， 句子的集合 语法的双重含意： 语法规则：上下文无关文法（子集LL文法或LR文法） 语法分析：下推自动机（LL或LR分析器），自上而下和自下而 上分析 本章主要内容：与语法分析有关的基本概念和相关问题上下文无关文法自上而下分析自下而上分析上机作业第二部分：函数绘图语言的语法分析器13.1 语法分析的若干问题 3.1.1 语法分析器的作用 语法分析器是编译器前端的重要组成部分，许多编译器，特别 是由自动生成工具构造的编译器，往往其前端的中心部件就是语法 分析器。语法分析器在编译器
2、中的位置和作用下：它的主要作用有两点：根据词法分析器提供的记号流，为语法正确的输入构造分析树 （或语法树），这是本章的重点，在以后各节中详细讨论；检查输入中的语法（可能包括词法）错误，并调用出错处理器 进行适当处理，下边简单介绍语法错误处理的基本原则，而在以后 的讨论中忽略此问题。 23.1.2 语法错误的处理原则 源程序中可能出现的错误 两类：语法错误和语义错误。 词法错误如非法字符或拼写错关键字、标识符等； intege20times 语法错误是指语法结构出错，如少分号、begin/end不配对等。 beginx:=a+by:=x; 静态语义错误：如类型不一致、参数不匹配等； a,b:in
3、teger;x:array1.10 of integer; x:=a+b; 动态语义错误（逻辑错误）：如无穷递归、变量为零时作除数等 。 while (t) .;a:=a/b;大多数错误的诊断和恢复集中在语法分析阶段。一个原因是大 多数错误是语法错误，另一个原因是语法分析方法的准确性，它们 能以非常有效的方法诊断语法错误。在编译的时侯，想要准确诊断语义或逻辑错误有时是很困难的 。 33.1.2 语法错误的处理原则（续1）语法错误处理的目标 对语法错误的处理，一般希望达到以下基本目标： 清楚而准确地报告错误的出现，地点正确、不漏报、不错报也不 多报； 迅速地从每个错误中恢复过来（以便分析继续进行
4、）； 不应使对语法正确源程序的分析速度降低太多。43.1.2 语法错误的处理原则（续2）语法错误的基本恢复策略 紧急方式恢复：抛弃若干输入，直到遇到同步记号。 短语级恢复：采用串替换的方式对剩余输入进行局部纠正（抛弃 插入）。 出错产生式：用出错产生式捕捉错误（预测错误）。预置型的短 语级恢复方式。 全局纠正：对错误输入序列x，找相近序列y，使得x变换成y所需 的修改、插入、删除次数最少。 例3.1 下述两条是有语法错误的语句，其中第一条赋值句结束时忘 记加分号，采用紧急恢复方式和短语级恢复方式的可能结果分别如 下所示。x := a + by := c + d; 紧急方式： x := a +
5、b + d; - 丢弃b之后的若干记号，直到遇 到同步记号+为止。 短语级恢复：x := a + b; - 加入分号，使之成为一个赋值句y := c + d; 53.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）的有限集合，A，其中AN（左部），(NT)*（右部），若=，则称A为空产生式（也可以记为A ）；
6、 （4） S是非终结符，称为文法的开始符号（Start symbol）。例3.2 简单算术表达式的上下文无关文法可表示如下：N=E T=+，*，(，)，-，id S=EP: 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是所有不出现在产生式左边符号的集合（记号）P: E E + E （1）E E * E （2）E （E） （3）E -E （4）E id （5）产生式的一般读
7、法可以将产生式中的记号读作“定义为” 或者“可导出”。更一般的，“E E + E”可用自然语言表 述为“算术表达式定义为两个算术表达式相加 ”，或者“一个算术表达式加上另一个算术表达 式，仍然是一个算术表达式”。 终结符与非终结符书写上的区分(a) 用大小写区分： E id(b) 用“”区分： E “id“ E E “+“ E(c) 用表示），直到得到一个终结符序列。 例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 E + E （1）|
8、E * E （2）|（E） （3） (G3.2)| -E （4）| id （5）93.2.2 CFG产生语言的基本方法推导（续1）定义3.2 利用产生式产生句子的过程中，将产生式A的右部代 替文法符号序列A中的A得到的过程，称为A直接推 导出，记作：A=。若对于任意文法符号序列1，2，.n，均有 1=2=.=n，则称此过程为零步或多步推导，记为： 1=*n，其中1=n的情况为零步推导。若1n，即推导过程中至少使用一次产生式，则称此过程 为至少一步推导，记为：1=+n。 定义3.2强调了两点： ，有=*，即推导具有自反性； 若=*，=*，则=*，即推导具有传递性。定义3.3 由CFG G所产生的
9、语言L(G)被定义为:L(G) = S=+ and T* ， L(G)称为上下文无关语言（Context Free Language, CFL）， 称为句子。若S=*，(NT)*，则称为G的一个句型。 103.2.2 CFG产生语言的基本方法推导（续2） 定义3.4 在推导过程中，若每次直接推导均替换句型中最左边的非终 结符，则称为最左推导，由最左推导产生的句型被称为左句型。 类似的可以定义最右推导与右句型，最右推导也被称为规范推导 。 再考察-(id+id)的推导过程（这是一个最左推导）：E = -E = -(E) = -(E+E) = -(id+E) = -(id+id) 1 2 3 4
10、5 6 其中，1是文法开始符号，6是句子，其他i(i=2、3、4、 5)均是句型。句型是一个相当广泛的概念，根据定义3.3可知，1 和6同样也是句型。 113.2.3 推导、分析树与语法树 对于推导：E = -E = -(E) = -(E+E) = -(id+E) = -(id+id) 它产生句子的方式很不直观，看起来十分困难。分析树是推导的图形表示，它的表示很直观，并且同时反映语 言结构的实质和推导过程。 定义3.5 对CFG G的句型，分析树被定义为具有下述性质的一棵树。（1） 根由开始符号所标记；（2） 每个叶子由一个终结符、非终结符、或标记；（3） 每个内部结点由一个非终结符标记；（4
11、） 若A是某内部节点的标记，且X1，X2，.，Xn是该节点从左 到右所有孩子的标记，则AX1X2.Xn是一个产生式。若A， 则标记为A的结点可以仅有一个标记为的孩子。 分析树与语言和文法的关系： 每一直接推导（每个产生式），对应一棵仅有父子关系的子树， 即产生式左部非终结符“长出”右部的孩子； 分析树的叶子，从左到右构成G的一个句型。若叶子仅由终结符 标记，则构成一个句子。123.2.3 推导、分析树与语法树（续1） 例3.5 再考察-(id+id)的推导过程。 E = -E = -(E) = -(E+E) = -(id+E) = -(id+id) 用分析树的方式如下：E -EE ( E )E
12、 E + EE id最左推导和最右推导的中间过程对应的分析树可能不同，因为 句型不同： -(id+E) 或 -(E+id) 但是最终的分析树相同，因为最终是同一个句子： -(id+id) 分析树既反映了产生句型的推导过程，又反映了句型的结构。 133.2.3 推导、分析树与语法树（续2）更多的情况下，仅关注句型结构，而忽略推导过程。 定义3.6 对CFG G的句型，表达式的语法树被定义为具有下述性质的 一棵树:（1） 根与内部节点由表达式中的操作符标记；（2） 叶子由表达式中的操作数标记；（3）用于改变运算优先级和结合性的括弧，被隐含在语法树的结 构中。 143.2.3 推导、分析树与语法树（
13、续3）例3.6 句子-(id+id)和句型if C then s1 else s2 ：S if C then S1 else S2分析树：左部非终结符“产生”右部文法符号序列； 语法树：操作符（运算）“作用于”操作数（运算对象）； 习惯上：分析树和语法树被分别称为具体语法树和抽象语法树。 153.2.4 二义性与二义性的消除 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
14、若G对同一句子产生不止一棵分析树，则称G是二义的。 原因：在产生句子的过程中某些直接推导有多于一种选择 一个句子有多于一棵分析树，仅与文法和句子有关，与采用的 推导方法无关； 文法中缺少对文法符号优先级和结合性的规定。16“悬空（dangling）else”问题 3.2.4.1 二义性（续1 ）S if C 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:=-5173.2.4.2 二义性的消除 文法二义不能说明程序设计语言 是二义。程序设计语言不能二义。 消除语言二义的两种方法： 改写二义文法为非二义文法； 规定二义文法中符号的优先级 和结合性，使仅产生一棵分析树。改写二义文法为非二义文法再分析id+id*id和id+id+id：例3.9 与G3.2等价的非二义文法:E E + T | TT T * F | F (G3.4)F （E） | -F | id问题：如何将二义文法改写为非二义文法？18可以看出：
