文档介绍：第3章 80x86微处理器
语法分析的若干问题
上下文无关文法(Context Free Grammar, CFG)
语言与文法简介
自上而下语法分析
自下而上语法分析
本章小结
80x86微处理器简介
语法分析器的作用
语法分析器是编译器前端的重要组成部分,许多编译器,特别是由自动生成工具构造的编译器,往往其前端的中心部件就是语法分析器。,它的主要作用有两点:
(1) 根据词法分析器提供的记号流,为语法正确的输入构造分析树(或语法树)。这是本章的重点,在以后各节中详细讨论;
(2) 检查输入中的语法(可能包括词法)错误,并调用出错处理器进行适当处理。下边简单介绍语法错误处理的基本原则,而在以后的讨论中忽略此问题。
语法分析器在编译器中的位置与作用
语法错误的处理原则

源程序中可能出现的错误可以分为两类:语法错误和语义错误。其中,语法错误又包括词法错误和语法错误。词法错误指出现非法字符或关键字、标识符拼写错误等;语法错误是指语法结构出错,如少分号、begin/end不配对等。语义错误包括静态语义错误和动态语义错误。静态语义错误涉及的是编译时可检查出来的错误,如类型不一致、参数不匹配等;动态语义错误一般是指程序运行时的逻辑错误,如无穷递归、变量为零时作除数等。
大多数错误的诊断和恢复集中在语法分析阶段,一个原因是大多数错误是语法错误,另一个原因是语法分析方法的准确性,它们能以非常有效的方法诊断语法错误。在编译的时候,想要准确地诊断语义或逻辑错误有时是很困难的。

对语法错误的处理,一般希望达到以下基本目标:
①清楚而准确地报告错误的出现,地点正确、不漏报、不错报也不多报;
②迅速地从每个错误中恢复过来,以便分析继续进行;
③对语法正确源程序的分析速度不应降低太多。
这些目标看起来容易,但是实现起来并不简单。幸好常见的错误是简单的,直接了当的出错处理机制一般就足以应付。但有些时候,错误的实际位置远远前于发现它的位置,并且这种错误的准确性也难以推断。在某些场合,出错处理程序可能需要猜测程序员的本意。
有些分析方法,如LL和LR方法,可以尽可能快地检测语法错误。更准确地说,它们具有“活前缀”(viable-prefix property)性质,这指的是,它们一看见输入的前缀不是该语言任何串的前缀时,就能报告错误。出错处理的关键是如何从错误中恢复,使分析可以进行下去,而不是遇到第一个错误就停止分析。

若希望编译器的语法分析方式是每次对输入源程序完整地扫描一遍,而不是遇到第一个语法错误就停止的话,就需要采取某种恢复策略,使得分析在遇到错误时还能够继续进行。以下是一些可能的恢复策略。
(1) 紧急方式恢复(Panic-mode recovery):这是最简单的方法,适用于大多数分析方法。发现错误时,分析器每次抛弃一个输入记号,一直向前搜索,直到输入记号属于某个指定的合法记号(称为同步记号)集合为止。同步记号一般是定界符,如分号或end等,它们在源程序中的作用很清楚。当然,设计编译器时必须选择适当的同步记号。这种处理方法最简单,但是也最容易造成错报,特别是漏报和多报语法错误的现象。
(2) 短语级恢复(Phrase-level recovery):发现错误时,分析器采用串替换的方式对剩余输入进行局部纠正,它用可以使分析器继续的输入串来代替剩余输入的前缀。典型的局部纠正是用分号代替逗号,删除多余的分号,或插入遗漏的分号等。设计编译器时必须仔细选择替换的串,以免引起死循环,例如,若总是在当前输入符号的前面插入一些东西就会造成死循环。这种方式建立在产生式(用于规定上下文无关文法的一种形式化描述)的基础之上,以短语为基本分析单元,同时也便于进行语法制导翻译,恢复得比紧急方式要精确,因此被认为是一种较为理想的恢复方式。
(3) 出错产生式(Error-productions):预测被分析语言可能出现的错误,用出错产生式捕捉错误。采用的方式,它基本上可以被认为是一种预置型的短语级恢复方式。
(4) 全局纠正(Global correction):对有语法错误的输入序列x,根据文法G构造相近序列y的语法树,使得x变换成y所需的修改、插入、删除次数最少。由于这种方法的代价太大,因此目前只具有理论价值。
下述两条是有语法错误的语句,其中第一条赋值句结束时忘记加分号,采用紧急恢复方式和短语级恢复方式的可能结果分别如下所示。
x := a + b
y := c + d;
紧急方式: x