3.1
分析器的作用
3
一、语法分析的任务
把单词符号作为基本单位，根据文法，分析源程 序 (字符串)是否为合法的程序.
同时报告语法错误并进行错误的恢复，使后面的 分析能够进行下去。
源程序 词法 分析器
记号 分析器
取下一个
分析树
记号
前端的 其余部分
中间表示
符号表 分析器在编译器模型中的位置
二、语法错误的处理
4
程序的错误有各种不同的性质。例如，错误可能是： (1)詞法错误，如标识符、关键字或算符的拼写错误 (2)语法错误，如算术表达式的括号不配对 (3)语义错误，如算符作用于不相容的运算对象 (4)逻辑错误，如无穷的递归调用。 大多数错误的诊断和恢复集中在语法分析阶段，原因如下： ➢ (1)大多数错误是语法错误 ➢ (2)诊断语法错误比诊断语义错误和逻辑错误容易得多。 分析器出错处理的基本目标是： (1)清楚而准确地报告错误的出现； (2)迅速从每个错误中恢复过来，以便诊断后面的错误 (3)不应使正确程序的处理速度降低太多。
即: α ，β ∈(VT ∪ VN) * . c) 一个文法，可以仅用开始符号及产生式代替。
例如:表达式的文法可以定义如下:
E →E+E|E-E|E*E|E/E|(E)
E 为文法的开始符号， + - * / ( ) 为终结符。 9
例如：考虑一个文法G1:
S→ bA A→ β |a β →aA 它定义了一个什么样的语言呢？ S是开始符号，是非终结符 A是非终结符 β是终结符与非终结符组成的字符串 b是终结符 a是终结符 结论：S→ baa*
stmt→if expr then stmt else stmt
一、 上下文无关文法定义
7
上下文无关文法 G [S]是一个四元组:
G[S] =(VT，VN，S，P) VT ： 是一个非空有限集，每个元素称为终结符。
程序设计语言的文法中记号是终结符的同义词。
例如：if，then，else，while，do，等都是终结符。
返回
二、 文法的几点约定
a) 若 A→ α1 A→ α2
则简写为: A→ α1|α2|...... |αk
A→ αk b) 用英文大写字母表前面的字母、字母S、小写字母串 代表非终结符;
英文小写字母表前面的字母、数字、运算符号、标 点符号、黑体字代表终结符;
希腊字母 α β、大写字母后面的字母、小写字目表后 面的字母串等代表由VT，VN组成的符号串;
10
三、 文法 G 与语言L(G)的关系及术语
11
从文法初始符开始，反复用产生式右部替换左部的非终结符，
直到推出的符号串全部由终结符组成.得到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.
自然语言不是上下文无关文法; 程序语言是上下文无关文法. 程序设计语言的许多结构包含固有的递归性，可用上下文无 关文法定义。 例：如果S1和S2是语句，E是表达式，则
“if E then S1 else S2”是语句。 使用语法变量stmt表示语句类，用expr表示表达式类，上述语 句可用文法产生式方便地表示为：
第三章 语法分析
主讲教师： 杨华莉
语法分析概述
2
语法分析方法
自下而上分析法 自上而下分析法
自下而上是指: 根据文法，对输入字串进行归约，若能正确地归约 为文法的初始符号，则表示输入字串是合法的. 典型方法是算符优先分析法。
自上而下是指: 从文法的初始符号进行推导，若能推导出与输入 字串相同的句子，则表示输入字串是合法的. 典型方法是递归下降分析法。
6
文法：是描述语言的语法结构的形式规则(即语法规则) 形式描述：用一组数学符号和规则来描述语言的方式。 形式语言：形式描述所用的数学符号和规则。 形式：指仅考虑数学符号间的推演，而不涉及符号的具体含义。
上下文无关文法是这样一种文法: 它定义的语法单位，独立于 该语法单位可能出现的环境，不必考虑上下文关系.
VN：是一个非空有限集，每个元素为非终结符，代表了一 种语法单位. 且 VT ∩ VN=φ.
例如:程序，表达式，短语，符号，S ∈ VN。 S 是文法 G 的最高层次的语法单位.
在程序语言中， S代表了程序这一语法概念。
P: 是产生式的有限集合。一条产生式定义了一个非终结
三、错误恢复策略
5
(1)紧急方式恢复：发现错误时，分析器每次抛弃一个输入记号， 直至输入记号属于某个指定的同步记号集合为止。 同步记号一般是定界符，如分号或end。 优点：方法简单，不会陷入死循环。 适用于一个语句中很少出现多个错误的情况。
(2)短语级恢复：发现错误时，分析器对剩余输入作局部纠正， 用可以使分析器继续分析的输入串来代替剩余输入的前缀。 如：用分号代替逗号、删除多余的分号、插入遗漏的分号。 这种替换可用于纠正任何输入串，已经用于几个错误修复编
符，产生式形式如下:
A→ α
称A定义为α。
(A∈ VN ， α∈ (VT ∪ VN ) * ). (‘→’读为“定义为”， 有时也会用::=代替)
8
例1：文法({id，+，-，*，/，↑，(，)}，{expr， op}，expr，P)定义了简单的算术表达式，P是由下 列产生式组成的有限集合： expr→expr op expr expr→(expr) expr→-expr expr→id op→+ op→op→* op→/ op→↑
译器，首先是用于自上而下的分析方法。它的主要缺点是很 难应付实际错误出现在诊断点以前的情况。 (3)出错产生式：如果对经常遇到的错误了解得很清楚 ，就可以 扩充语言的文法，增加产生错误结构的产生式，用此扩充的 方法来构造分析器。 (4)全局纠正： 在处理不正确的输入串时，作尽可能少的修改。
3.2 上下文无关文法