三、错误恢复策略
(1)紧急方式恢复：发现错误时，分析器每次抛弃一个输入记号， 直至输入记号属于某个指定的同步记号集合为止。 同步记号一般是定界符，如分号或end。 优点：方法简单，不会陷入死循环。 适用于一个语句中很少出现多个错误的情况。 (2)短语级恢复：发现错误时，分析器对剩余输入作局部纠正， 用可以使分析器继续分析的输入串来代替剩余输入的前缀。 如：用分号代替逗号、删除多余的分号、插入遗漏的分号。 这种替换可用于纠正任何输入串，已经用于几个错误修复编 译器，首先是用于自上而下的分析方法。它的主要缺点是很 难应付实际错误出现在诊断点以前的情况。 (3)出错产生式：如果对经常遇到的错误了解得很清楚 ，就可以 扩充语言的文法，增加产生错误结构的产生式，用此扩充的 方法来构造分析器。 (4)全局纠正： 在处理不正确的输入串时，作尽可能少的修改。 5
T
T→F|T*F F→(E)| i
E为表达式, T 为项, F 为因子F FT Nhomakorabea*
i
F i
该文法对于句子i * i + i的各种 推导,对应的语法树是唯一的. 16
i
1、文法的优点： 文法给出了精确的、易于理解的语言语法说明。 某些文法类可以自动产生高效的分析器，分析器的构造过程 可以揭示出语法的二义性和其他难于分析的结构。 设计的漂亮的文法把结构加于程序设计语言，这些结构对于 把源程序翻译成为正确的目标代码和错误诊断都是很有用的 语言也是逐渐完善的，需要补充新的结构和完成附加的任务。 如果存在以文法为基础的语言的实现，这些新结构的加入就 更方便。 但是不是所有的语言都可以用上下文无关文法来描述， 例如：我们变量的使用就要求先定义后使用，后面的使用就 的根据前面的类型和属性来决定。即：程序语言也有一定的 语言环境。因此我们强调语法分析器的输出结果。 本章介绍语法分析，是分析语法结构，使用文法；而前 一节词法分析，是分析我们的词法规则，使用正规式；他们 有什么区别、联系、相似之处。 17
例如：考虑一个文法G1:





S→ bA A→ β |a β →aA 它定义了一个什么样的语言呢？ S是开始符号，是非终结符 A是非终结符 β是终结符与非终结符组成的字符串 b是终结符 a是终结符 结论：S→ baa*
10
3 文法 G 与语言L(G)的关系及术语
从文法初始符开始,反复用产生式右部替换左部的非终结符, 直到推出的符号串全部由终结符组成.得到G所定义的各种句子. 例如:E=>E+E=>E*E +E=>i * E + E=> i * i + E => i * i + i 定义: 若αBβ,经产生式 B→λ替换后得到 αλβ,称αBβ直接 推出αλβ.{α , λ,β ∈(VT ∪ VN) *},用=>表示直接推出. 若存在α1=> α2 => α3........=> αn ,称α1可推出αn; + α1=> αn表示经一步或若干步α1可推出αn. * α 表示经零步或若干步α 可推出α . α1=> n 1 n * {α ∈(VT ∪ VN) *}, 则称 定义:设S 是G的开始符号,若 S=>α,
3.2 上下文无关文法
文法：是描述语言的语法结构的形式规则(即语法规则) 形式描述：用一组数学符号和规则来描述语言的方式。 形式语言：形式描述所用的数学符号和规则。 形式：指仅考虑数学符号间的推演,而不涉及符号的具体含义。 上下文无关文法是这样一种文法: 它定义的语法单位,独立 于该语法单位可能出现的环境,不必考虑上下文关系. 自然语言不是上下文无关文法; 程序语言是上下文无关文法. 程序设计语言的许多结构包含固有的递归性，可用上下文 无关文法定义。 例：如果S1和S2是语句，E是表达式，则 “if E then S1 else S2”是语句。 使用语法变量stmt表示语句类，用expr表示表达式类，上述语 句可用文法产生式方便地表示为： stmt→if expr then stmt else stmt 6
二、语法错误的处理
程序的错误有各种不同的性质。例如，错误可能是： (1)詞法错误，如标识符、关键字或算符的拼写错误 (2)语法错误，如算术表达式的括号不配对 (3)语义错误，如算符作用于不相容的运算对象 (4)逻辑错误，如无穷的递归调用。 大多数错误的诊断和恢复集中在语法分析阶段，原因如下： (1)大多数错误是语法错误 (2)诊断语法错误比诊断语义错误和逻辑错误容易得多。 分析器出错处理的基本目标是： (1)清楚而准确地报告错误的出现； (2)迅速从每个错误中恢复过来，以便诊断后面的错误 (3)不应使正确程序的处理速度降低太多。 4
2
3.1
分析器的作用
一、语法分析的任务: 把单词符号作为基本单位,根据文法,分析源程序 (字 符串)是否为合法的程序. 同时报告语法错误并进行错误的恢复，使后面的分析 能够进行下去。
源程序 词法 分析器 记号 分析器 取下一个 记号 分析树 前端的 中间表示 其余部分
3
符号表 分析器在编译器模型中的位置
α是 G的一个句型;若 α ∈VT *,则称α是 G的一个句子. 如果两个文法产生同样的语言，则这两个文法等价。
11
例如： E=>E+E=>E*E +E=>i * E + E=> i * i + E => i * i + i


E是我们的开始符号，也是非终结符 +、-、*、/是终结符 i是终结符 E+E、E*E +E、i * E + E、 i * i + E是句型 i*i+i是句子 E=>E+E、 E+E =>E*E +E、 E*E +E =>i * E + E、 i * E + E => i * i + E是经一步推导出----直接推导 E => i * i + i是经多步推导出-----可推导出
1. 上下文无关文法定义
7
上下文无关文法 G 是一个四元组: G =(VT,VN,S,P) VT ： 是一个非空有限集,每个元素称为终结符. 程序设计语言的文法中记号是终结符的同义词。 例如：if,then,else,while,do,等都是终结符。 VN：是一个非空有限集,每个元素为非终结符,代表了一种 语法单位. 且 VT ∩ VN=φ. 例如:表达式,短语,语句等。 S: 是一个非终结符，称为开始符号,S ∈ VN. S 是文法G 的最高层次的语法单位. 在程序语言中, S代表了程序这一语法概念. P: 是产生式的有限集合。一条产生式定义了一个非终结 符，产生式形式如下: A→ α (A∈ VN , α∈ (VT ∪ VN ) * ) 称A定义为α . (→ 有时也会用::=代替) α∈ (VT | VN ) *
定义: 若文法 G 的某个句型存在两个不同的语法树表示,称该文法 是二义文法. 因此,文法 E 是二义文法. 二义性导致了i * i + i 的两种不同运 算结果: (i*i)+i 以及 i*(i+i). E 编译中应避免二义文法. E 文法的 二义性是因为没有规定*,+ 运算符的优 E + T 先顺序,改进 E 后,得到: E→T|E+T
例：文法({id,+,-,*,/,↑,(,)},{expr,op},expr,P) 定义了简单的算术表达式，P是由下列产生式组成的有 限集合： expr→expr op expr expr→(expr) expr→-expr expr→id op→+ op→op→* op→/ op→↑
3. 文法的表式及产生的语言
例如 文法：S→(S)S|ε 推导我们的文法产生式，每一次推导得到的终结符为（） 或则ε ，（）成对出现，而ε是空串，所以此文法描述的语 言是所有的配对括号组合。 例如 文法：S →if expr then stml A A →else B|ε B →S|stml stml →S| stml |ε 推导文法产生式，可以得到我们的if语句的语法结构， 包括if的嵌套结构，描述所有的if语句。 例如 文法：S →while expr do { stml } stml →stml |ε 推导文法产生式，得到该文法描述的是我们所有的 while循环语句。 19
例如 设expr和term为非终结符，用以表式不同的优先级，终 结符为id、括号、运算符等，facter为产生表达式的基本单 位。则： 文法一 facter →id|(expr) term →term*facter|term/facter|facter expr →expr+term|expr-term|term 这个表达式文法是无二义性的，句子id+id+id和id+id*id的分 析树如下： expr expr expr + term expr + term facter expr + term term term * facter term facter id facter facter id facter id id id 20 id
第三章 语法分析
语法分析概述
自下而上分析法 自上而下分析法
语法分析方法
自下而上是指: 根据文法,对输入字串进行归约,若能正确地归约
为文法的初始符号,则表示输入字串是合法的. 典型方法是算符优先分析法.
自上而下是指: 从文法的初始符号进行推导,若能推导出与输入
字串相同的句子,则表示输入字串是合法的. 典型方法是递归下降分析法.

8
2 文法的几点约定
a) 若 A→ α1 A→ α2
则简写为: A→ α1|α2|...... |αk
9