《编译原理简明教程》普通高等教育“十二五”规划计算机教材---太原理工大学---计算机科学与技术学院---冯秀芳、崔冬华、段富等第一章 引言
第二章 形式语言理论基础第三章 自动机理论基础第四章 词法分析第五章 语法分析—自顶向下分析方法第六章 语法分析—自底向上分析方法
第七章 语义分析及中间代码的生成第八章 代码优化第九章 目标代码的生成第十章 符号表第十一章 目标程序运行时的存储组织与分配第十二
章 出错处理第十三章 编译程序自动生成工具简介第十四章 面向对象语言的编译第十五章 并行编译技术目 录第12章 出错处理12
.1 引言 12.2 校正词法错误12.3 校正语法错误12.4 校正语义错误习题1212.1 引言12.1.1 错误
存在的必然性12.1.2 错误的种类12.1.3 错误复原12.1.1 错误存在的必然性 编译程序用来对源程序进行编译
，当程序在语法(包括词法)上正确时，可以得到相应的等价的目标代码。当程序在语义上正确时，以正确的输入数据运行目标代码可以得到预期的
输出结果。然而，一个程序，尤其是大型软件的程序，其中难免包含错误。一个软件开发中所存在的错误分布比例大致为：56%的错误源自需求分
析，27%的错误源自设计，7%的错误源自编码。有人认为“没有一个程序第一次运行就能正确地工作”是计算机程序设计的一个公理。12.1
.1 错误存在的必然性 一个素质较好的程序员，在他交付的程序中错误率为1%，即每100个语句中约含1条错误，而水平低的程序员
编写的程序，在刚开始调试时错误率是很高的。错误产生原因大致是因为问题(算法)的复杂性、程序员素质、输入错误以及对系统环境不够了解等
，概括起来是因为人类自身能力的局限性。12.1.2 错误的种类一个源程序中的错误一般有如下四类。① 词法错误。编译程序在词法分析
阶段发现的源程序错误，例如，字符号(关键字)拼写有错，标点符号有错，等等。② 语法错误。编译程序在语法分析阶段发现的源程序错误，亦
即书写不符合某语法成分的语法规则。例如，作为语句括号的BEGIN与END不匹配，“{”与“}”不匹配，以及IF与ELSE之间缺少T
HEN，等等。另外，变量未说明或重定义等也可看做语法错误。12.1.2 错误的种类③ 语义错误。源程序中的语义错误有两类，一类是
在编译时才可发现的静态语义错误，例如，编译程序语义分析时发现的运算符对运算分量类型而言不合法，或者双目运算符的两个运算分量类型不相
容，等等。另一类是在目标代码运行时刻才能发现的动态语义错误，也就是说，虽然编译程序把源程序翻译成了等价的目标代码，未发现任何错误，
但运行不能正常结束或者运行结果经验证却是不正确的。12.1.2 错误的种类④ 违反环境限制的错误。一个程序设计语言可以有丰富的表
达能力，用以书写各种应用领域的程序，然而由于编译程序的实现问题，一个手头上可用的编译程序往往对它所能接受的源程序加某些限制。例如，
Pascal语言中过程的可调数组参数就不是每个编译程序都可以接受的。另外，如标识符的长度、整数的最大值范围、IF语句的最大嵌套层数
和数组的最大维数等，都可能会有一定的限制。12.1.2 错误的种类对于一个好的编译程序来说，应能具有较强的查错和改错能力。查错，
就是编译程序能在编译时刻，准确而及时地发现源程序中的错误，并能以简明的方式向用户报告这些错误的性质和出现的确切位置。一个编译程序应
在一次编译期间发现源程序中尽可能多的错误，不是发现一个错误便立即停止编译。在编译时刻能够查出的源程序的错误称为静态错误，运行时刻才
能查出的错误称为动态错误。本章讨论的程序错误的检查和校正主要是针对静态错误，即词法错误、语法错误、非逻辑的或算法上的语义错误及违反
环境限制错误。12.1.2 错误的种类改错及校正，指编译程序在其翻译过程中发现源程序的错误时能适当地对源程序进行修正。为了正确地
校正错误，必须十分清楚地了解程序的意图，了解错误的性质，并确切地对错误定位。即使是词法错误，也必须根据上下文，试探性地做出修改。1
2.1.2 错误的种类一般来说，一个编译程序如果能在一次编译时刻查出源程序中几乎所有的错误，指出错误的性质，并给出错误所在的确切
位置，对于源程序的迅速改正将有很大的帮助。12.1.3 错误复原词法分析时，如果发现输入字符串存在一个错误，这表明，该输入字符串
不是相应文法的句子，是否就此不再继续词法分析呢？如果语法分析时，类似地发现中间表示符号串中存在错误，表明不是相应文法的句子，是否也
不再继续语法分析呢？对于一个实用的编译程序来说，它不应只能处理正确的程序，它还必须能处理源程序中出现的错误，使得编译工作能继续正常
进行下去，不是发现一个错误就结束编译，而是继续下去，以便查出全部错误。12.1.3 错误复原由于错误的存在，往往使编译程序不能正
常地继续下去，早期的一些编译程序，例如，ALGOL 60语言的编译程序采用结束编译的办法。如今，几乎所有常用程序设计语言的编译程序
都能在发现源程序中的错误时继续进行编译，以便一次编译能查出尽可能多的错误。在编译的过程中，发现源程序的错误时采取一定的措施，使得能
继续编译下去，这称为错误复原。如果把所给不正确程序变换成正确的程序，则称之为错误校正。显然，如前所述的原因，错误校正是极其困难的。
12.1.3 错误复原在错误复原时，应重视以下两个方面：? 株连信息的遏止。? 重复信息的遏止。株连信息指的是因为源程序中的
某个错误而导致编译程序向用户发出的出错信息，该出错信息往往不是真实的。12.1.3 错误复原 例如，假定过程语句P(a，b)在输
入时成了p(a.b)，编译时，编译程序将发出出错信息：是不合法符号。如果做出的处理是删除，那么，当扫描p之后，将发出出错信息：缺少
运算符，当扫描到“)”时，将再发出出错信息：参数个数少。显然后面两个出错信息是不真实的。有时可能因为源程序中的一个错误而引出一连串
株连信息。应该遏止这种株连信息。为了遏止株连错误，往往需要查看出错处的上下文和取得相关的信息。例如，对于上述例子，可以取得关于过程
p参数个数的信息，标识符a是否记录类型信息，并向前查看到“)”确定参数的个数。这样，甚至可以做出正确的修改：把“· ”改成“，”。
12.1.3 错误复原下面再考虑遏止株连错误的另一个例子。假定对于下标变量A[e1, e2, e3]，发现标识符A不是数组名，扫
描到“[”时发出出错信息：[错。此后显然将发出一连串株连错误信息。究其原因，可能是因为标识符A未被说明。为了遏止株连信息，可以这样
处理：用一个“万能”标识符U去代替有错的标识符A，或者说让A可以与任意类型的数据结构相关联，这时在符号表的相应条目中已加标志，且填
入了数组和维数的信息，只要其后形如[e1, e2, e3]出现，将不再发出出错信息。12.1.3 错误复原重复信息是因为源程序中
的一个错误反映在源程序中多处而产生的。一个典型的例子是标识符未说明。如果一个标识符i未在某个过程说明的过程分程序中说明，那么，在过
程分程序的语句部分中每次引用i时都将发出出错信息：标识符i无定义。12.1.3 错误复原为了遏止重复信息，可事先设立一个出错信息
表，其中给出一切可能的出错信息(性质)和编号，而编译时刻，则建立一个出错信息集合，其元素呈(编号、关联信息)形式。每当发现一个错误
，便把相应的(编号、关联信息)添加入该出错信息集合中。最后，编译结束时，把出错信息集合中的元素按某种次序输出，便得到了无重复的一切
出错信息。12.2 校正词法错误 12.2.1 词法错误的种类12.2.2 词法错误的校正12.2.1 词法错误的种类词法
分析程序的基本任务是读入源程序字符序列，识别出具有独立意义的最小语法单位(单词或符号)，并把它们变换成等价的内部中间表示——属性字
序列。词法分析时发现的词法错误大多是单词拼写错误，这或者是因为书写错误，或者是因为输入错误，假定不会有连续几个字符的错误，从而可以
假定有如下几类词法错误：? 拼错一个字符，如RECORD错写成RCCORD。? 遗漏一个字符，如REPEAT错写成REPET。
? 多拼一个字符，如UNTIL错写成UNTILE。? 相邻两个字符颠倒了次序，如LABEL错写成LABLE。12.2.1 词
法错误的种类对于错误复原问题，自然地涉及下列问题：? 错误的查出。? 错误的定位。? 错误的局部化。? 重复错误信息的遏止
。由于每一类单词可用一个正则表达式来描述，所以在识别单词时，通常采用最长子串匹配策略。12.2.2 词法错误的校正 基于前面对词
法错误的假设，不存在连续几个字符都出错的现象，对词法错误的校正一般地有? 删除一个字符。? 插入一个字符。? 替换一个字符。
? 交换相邻两个字符。12.2.2 词法错误的校正 由于词法分析时，还不能收集到足够的信息，发现错误便立即校正是不太恰当的，只
是在某些场合可以予以校正，下面列举若干。① 知道下一步应处理的字符号(关键字)，而当前所扫视的余留输入字符序列的任何前缀都不能构成
字符号(关键字)，则可查字符号(关键字)表，从其中选择与当前所扫视的输入字符串前缀最接近的字符号(关键字)去代替这个前缀。例如“I
F b THEM…”，对于“THEM”将用最接近的“THEN”去代替。12.2.2 词法错误的校正 ② 如果某个标识符拼写有错，
因此查找符号表时不能查到相应条目，这时可用符号表中与之最接近的标识符去代替它，例如，如果有语句X: = sim(a)，但不能在符号
表中查到标识符sim，则可以用最接近的sin去代替sim。③ 其他拼写错误的情况，例如，源程序中所引用之下标变量的数组标识符因拼写
错误而不能在符号表中查到，控制转移语句的转移目标(标号)因拼写错误而无定义，等等，都可以用与上面类似的办法来校正。一般地，可以用试
探法，试验删除、插入、替换和交换四种情况，以最可能成功的那种修改作为对错误的校正。12.3 校正语法错误 12.3.1 语法错
误的复原 12.3.2 语法错误的校正12.3.1 语法错误的复原对于语法错误的复原，与词法错误的情况一样，自然地涉及下列问题
：? 错误的查出。? 错误的定位。? 错误的局部化。? 重复错误信息的遏止。 12.3.1 语法错误的复原由于程序设计语
言的语法用上下文无关文法描述，源程序可由基于某种分析技术的识别程序精确地识别，源程序中的语法错误总可自动地查出。12.3.1 语
法错误的复原不言而喻，不同的分析技术发现错误的手段和方式是不同的。例如，LL(1)与LR(1)分析技术都是当前栈顶状态与当前输入符
号配对所对应的分析表元素空白时为出错。然而，对于优先技术，则是当前栈顶符号和当前输入符号匹配时，它们之间不存在优先关系而发现错误。
显然，有的分析技术可对所发现的错误准确地定位，采取一定的措施，使语法分析能继续进行下去。12.3.1 语法错误的复原有的编译程序
，对语法错误复原采取的措施是简单地放过相应的语法结构，例如，放过一个语句的后继符号等。这种过于简单的做法往往失去发现更多语法错误的
机会。更合适的是设法进行校正，尽管这种校正不能保证总是成功的，然而，关于校正的信息可供用户(程序书写人员)参考。12.3.2 语
法错误的校正 1．自顶向下分析中错误的校正假定在自顶向下分析过程中的某一时刻，源程序符号串可写为w1Aw2的形式，其中，w1是已扫
描部分，A是当前扫描符号，而w2是输入符号串的其余部分。如果扫描到A时发现错误，分析程序又无法确定下一个合法的分析动作，换言之，已
构造的语法树部分可覆盖w1，但不能继续构造语法树去覆盖A与其余部分w2。12.3.2 语法错误的校正 一般可有如下三种修改措施。
① 删去A，继续进行分析。② 插入终结符号串X成为w1XAw2，从XAw2的首符号开始继续进行分析。③ 修改w1，例如，删去w1尾
部的若干个符号、替换w1尾部的若干个符号或者在w1之后插入若干个符号。12.3.2 语法错误的校正 修改措施③显然是不可取的，因
为w1已经处理过，不可能再次直接取到，且对已处理的部分进行修改，往往要改变语义信息，实现上较为困难，因此不宜采用。例如，假如有源程
序语句：i：=i+)；处理到符号“)”时显然将发现存在错误，一般地，当按自顶向下分析技术构造语法树时，对照语法树和预期展开的符号串
，采用上述修改措施①和②，将把所给语句修改成i：=i+i；2．自底向上分析中错误的校正 自底向上分析技术包括优先分析技术(简单优先
和算符优先)与LR分析技术。这里以LR分析技术为例说明自底向上分析中语法错误的校正。在LR分析技术中，LR分析表的ACTION部分
指明了当前分析栈顶的状态与当前输入符号配对时所应执行的动作。如果是空白元素，表明一个错误，即当前输入符号有错。为了对语法错误校正，
可以对应于每个空白元素，引进一个出错处理子程序，根据出错情况，在各个出错处理子程序中做出相应处理。这里仍以语句：i：=i+)；为例
进行讨论。假定扫描到上述语句中的符号“+”时进入状态Sk，则ACTION[Sk,)]当然为出错(空白元素)。假定引进的响应出错处理
子程序Ei，其功能有二：删去当前输入符号和发出出错信息“不合法的输入符号：……”。那么，执行动作ACTION[Sk,)]将调用子程
序Ei，因而，删去当前输入符号，并发出出错信息：“不合法的输入符号：)”。这时将扫描下一个符号继续分析下去，即读入符号，执行动作A
CTION[Sk, ;]，为出错，类似地引进出错处理子程序Ej，其功能可能如下：将一假想的标识符i及相应状态S1下推入分析栈，并发
出出错信息：运算符分量缺少，然后执行动作ACTION[S1, i]这里，ACTION[Sk,i]=S1因此，最终，上述语句校正为i
：=i+i；其他出错处理子程序可类似地设计。不言而喻，关于每个错误的修改信息应由出错处理子程序提供给用户(程序书写人员)以便参考，
完成真正的校正。其他各类分析技术，可以参照上述实现思想进行源程序语法错误的校正。12.4 校正语义错误12.4.1 语义错误的
种类12.4.2 语义错误检查措施 12.4.1 语义错误的种类如前所述，语义错误有两类，一类是在编译时可以发现的静态语义错误
，另一类是在运行时才能发现的动态语义错误。1．静态语义错误静态语义错误可能由数据结构引起，有运算符不合法和运算分量类型不相容等，例
如，对数组变量进行加法运算，又如两个实型变量X和Y进行MOD运算，该MOD运算对于运算分量X和Y是不合法的；如果X为实型变量，Y为
字符型变量，它们要进行加法运算，那么，对于Pascal语言，该加法运算符的两个运算分量类型是不相容的。这样一些由数据结构引起的静态
语义错误可由语义分析查出。12.4.1 语义错误的种类语义分析程序还进行控制流方面的某些静态语义检查，例如，由循环外控制转移到循
环内，由转向语句把控制转移到一个构造语句(条件语句与情况语句等)内，或者转移到分程序内，等等，发现控制流的某些静态语义错误。显然，
静态语义错误是容易准确地定位和确定错误性质的。 2．动态语义错误 动态语义错误是在运行目标代码时才能发现的源程序错误。最常见的动态
语义错误有以下几类：(1) 除以零；(2) 下标变量的下标表达式的值越界；(3) 存取位置初值或值为NIL的指针变量；(4) 运行
结果与预期的不一致。2．动态语义错误 前三种情况往往导致运行非正常终止而得不到任何结果，然而第四种情况虽然运行正常终止，但依然得不
到预期的结果。这些错误的产生源自与算法有关的逻辑错误以及程序设计错误。当软件开发的设计阶段，甚至需求分析阶段导致与算法有关的逻辑错
误时，这时的错误往往表现为运行结果与预期的不一致，错误的校正必须在设计阶段或需求分析阶段重新考虑数学模型和算法，从根本上解决。2．
动态语义错误 程序设计的错误会导致程序不反应算法，从而使运行结果与预期的不一致。程序设计的错误还常导致程序运行的夭折。与指针变量有
关的语义错误由于可能对地址存储区域赋值，甚至可能造成巨大破坏。下面举例说明与指针变量有关的错误的产生。 设有下列Pascal程序片
段：P：=q；while P↑. next<>NIL dobeginP：= P↑. next; P↑. inf：= …
end;在While循环中的两个赋值语句可能带来致命的错误。原因在于，如果P的值为NIL，或者并未为P所指向的对象分配存储空间，这
两个语句的赋值都是错误的。应该在这个程序片段之前对q置初值NIL，或者通过语句new(q)为q所指向的对象分配存储空间，并且把WH
ILE循环的重复条件 P↑. next<>NIL改写成 (P <>NIL)AND(P↑. next<>NIL)首先P必
须不是空指针才可能对其值不是NIL的域变量next所指向的对象赋值。 12.4.2 语义错误检查措施 由于语义错误往往涉及算法，
而语义通常又是非形式定义的，因此，对照语法错误，语义错误往往难以采用系统而有效的方法来发现和校正。好在语义分析时采用语法制导的翻译
，通过语法制导定义或翻译方案实现类型一致性检查和某些控制流静态语义检查等，可以发现源程序中运算符不合法、运算分量类型不相容以及控制
流方面的静态语义错误。12.4.2 语义错误检查措施 对于未给变量置初值而导致的动态语义错误，可以通过在语义分析时查看变量是否被
赋初值而避免，因为可以利用代码优化时所讨论的“ud”链思想，容易查出赋值之前就引用的错误。为了发现其他的动态语义错误，通常采用以下
两种方式。① 静态模拟检查。由人阅读所写的源程序进行静态模拟，即给定若干组检查用输入数据，模拟计算机执行各个语句，沿着所模拟的执行
路径，进行变量追踪，也就是记录下各个变量值的变化，最终检查结果的正确性。下面给出一个简单的例子。② 利用调试工具。静态模拟检查是静
态地由人模拟计算机的运行，进行变量追踪，同时也进行了控制路径的追踪。采用这种办法可以查出程序中相当比例的错误。然而，一个明显的不足
是工作量大，尤其当变量增多，控制结构又较复杂时，此不足更为突出。利用软件工具将大大减轻人的负担。编译程序可看成这样的软件工具。当发
生下标表达式值越界或对值为NIL的指针变量及其域变量进行存取时发现相应的出错信息，只需在目标代码中增加相应的判别指令。当发生除以零
溢出时也发出相应的出错信息，这可通过中断设施来实现。 然而毕竟目标代码是机器指令级的，用户并不容易找到出错信息与源程序中符号的对应关系。调试程序是为了发现程序中的错误并进行校正而开发的工具软件，尤其是符号调试程序可以在源程序级上进行调试，给用户带来了极大的方便。调试程序的重要特征之一是允许对变量和控制路径进行动态追踪。首先在源程序中需进行追踪检查的语句处设置断点，当程序运行到断点处，便自动暂停，可以查看被追踪的变量值，然后按逐个语句执行的步进方式查看每执行一个语句后变量值的变化，从而检查运行的正确性。目前的编译程序，更确切地说是编译系统，如TURBO Pascal，TURBO C与BORLAND C++等都是作为程序设计语言支持系统而出现的，它们集程序设计语言程序的编辑、编译和调试于一体，大大方便了用户，对提高程序生产率有着重大影响。当然，即使依靠调试工具，程序中错误的发现和校正仍然取决于人的经验。例如，对错误的性质和发生位置做出判断与选择断点都需要经验。然而，采用逐步缩小检查范围的办法，最终总是可以确切定位，找出错误从而校正错误的。 习题12 12.1 源程序中的错误一般有哪几类？请分别叙述。12.2 如何遏止源程序中的重复性错误？12.3 词法分析阶段的错误主要是什么？通过什么办法校正？ |
|
