第四章文法与语法分析
主要内容：
? 语法分析概述
? 文法
? 进行语法分析的几种方法
? 语法错误处理
语法分析概述
? 语法分析器和识别器
? 语法分析的功能
? 语法错误类别
? 语法错误的处理
? 语法分析器和识别器
? 语法分析器的功能：
? 语法错误类别
程序的开始符，语句（表达式）的开始符
（后继符）错
标识符（常量）错：该出现时未出现
括号类错误：不匹配
分隔符错,assignment;
Token/TokenList Parser 语法树 /语法错误信息
? 语法错误处理
要求,报告错误出现的位置
修复错误并继续检查后续部分
执行开销不应太大
修改策略：
插入 /删除 /修改
应急方式恢复,
定义同步符号集合 (分隔符, end,某些
语句头符, else等 )
发现错误时, 跳过一些 Token,直到找
到某个同步符号, 再继续进行分析 。
同步符号保证接下来的分析是从正确的
头位置开始 。
文法
? 文法能清晰地描述程序设计语言的语法构成
易于理解。
? 文法能自动地构造有效的语法分析器，检
查源程序是否符合语言规定的语法形式。
? 文法定义可以了解程序设计语言的结构，有
利于将源程序转化为目标代码，以及检查出
语法错误。
? 基于文法实现的语言易于扩展
小语言 Micro的定义
? P ? begin VDL;SL end.
? VDL ? VD | VD ; VDL
? VD ? var id, T
? SL ? S | S ; SL
? S ? id:= E | write(E) | read(id)
? T ? integer | real
? E ? id | num
| E + E
| E * E
|(E)
文法的定义
?文法 G定义为四元组 (VT,VN,S,P)
? VT是有限的终极符集合
? VN是有限的非终极符集合
? S是开始符,S? VN
? P是产生式的集合，且具有下面的形式：
? ??，其中 ?,??(VT?VN )*
文法的分类
? O型文法, 也称为短语文法, 其产生式具有形式,
?→ ?,其中 ?,??(VT?VN)*,并且 ?至少含一个非
终极符 。
? 1型文法, 也称为上下文有关文法 。 它是 0型文法
的特例, 要求 |?| ? |?| (S→ ?例外, 但 S不得出
现于产生式右部 )。
? 2型文法, 也称为上下文无关文法 。 它是 1型文法
的特例, 即要求产生式左部是一个非终极符,
A→ ? 。
? 3型文法, 也称为正则文法 。 它是 2型文法的特例,
即产生式的右部至多有两个符号, 而且具有下面
形式之一, A →a, A →a B
其中 A,B?VN, a?VT 。
上下文无关文法（ CFG）
?定义为四元组 (VT,VN,S,P)
? VT是有限的终极符集合
? VN是有限的非终极符集合
? S是开始符,S? VN
? P是产生式的集合，且具有下面的形式：
A?X1X2… Xn
其中 A?VN,Xi? (VT?VN), 右部可空。
? 推导,如果 A??是一个产生式，则有
?A?????,其中 ?表示一步推导 (用 A → ?)。
这时称 ???是由 ?A?直接推导的。 ?的含义是，
使用一条规则，代替 ?左边的某个符号，产
生 ?右端的符号串
? ? ?+ ?,表示 ?通过一步或多步可推导出 ?
? ? ?* ?, 表示 ?通过 0步或多步可推导出 ?
? 句型：
如果有 S?* ?, 则称符号串 ?为 CFG的
句型 。我们用 SF(G)表示文法 G的所有句
型的集合
? 句子：
如果 ?只包含终极符，则称 ?为 CFG的句
子，其中 S是文法的开始符
? 语言：
L(G)={ u| S ?+ u,u ? VT* }。
文法 G所定义的语言是其开始符所能推导
的所有终极符号串 (句子 )的集合。
? 最左（右）推导：
如果进行推导时选择的是句型中的最左 (右）
非终极符，则称这种推导为最左 (右 )推导，
并用符号 ?lm（ ?rm） 表示最左（右）推导。
? 左（右）句型：
用最左推导方式导出的句型，称为左句型，
而用最右推导方式导出的句型，称为右句型
(规范句型 )。
? 结论：
每个句子都有相应的最右和最左推导（但对
句型此结论不成立）
语法分析树与二义性
? 语法分析树 (简称分析树 )用来描述句型的结构，是句
型推导的一种树型表示。文法 G=(VN,VT,S,P),则称
满足下面条件的树为 G的一棵分析树：
1,每个结点都有 G的一个文法符号，并且根结点标
有初始符 S,非叶结点标有非终极符，叶结点标有
终极符或非终极符或 ?。
2.如果一个非叶结点 A有 n个儿子结点 (从左到右）为
X1,X2,...,Xn,则 G一定有产生式 A→X1X2,..Xn 。
? 线性推导,我们称用 ?符号进行的推导为线性推导 。
? 树型推导与线性推导的不同,线性推导指明了推导的
顺序，而树型推导则没有指明推导的顺序。因此，句
型一般只有一棵分析树 (如果无二义性 )，而线性推导
则可很多。
二义性文法
?文法 G=( {+,*,I,(,)},{E},E,P),其中 P为：
? E ? i
? E ? E + E
? E ? E * E
? E ? ( E )
句型 i*i+i:
推导 1,E ? E + E ? E * E + E ? i * E + E
? i * i + E ? i * i + i
推导 1,E ? E * E ? i * E
? i * E + E ? i * i + E ? i * i + i
推导 1的语法树
E + E
E
E * E
i i
i
E
E * E
E + E
i i
推导 2的语法树
i
主要内容：
? 语法分析概述
? 文法
? 进行语法分析的几种方法
? 语法错误处理
语法分析概述
? 语法分析器和识别器
? 语法分析的功能
? 语法错误类别
? 语法错误的处理
? 语法分析器和识别器
? 语法分析器的功能：
? 语法错误类别
程序的开始符，语句（表达式）的开始符
（后继符）错
标识符（常量）错：该出现时未出现
括号类错误：不匹配
分隔符错,assignment;
Token/TokenList Parser 语法树 /语法错误信息
? 语法错误处理
要求,报告错误出现的位置
修复错误并继续检查后续部分
执行开销不应太大
修改策略：
插入 /删除 /修改
应急方式恢复,
定义同步符号集合 (分隔符, end,某些
语句头符, else等 )
发现错误时, 跳过一些 Token,直到找
到某个同步符号, 再继续进行分析 。
同步符号保证接下来的分析是从正确的
头位置开始 。
文法
? 文法能清晰地描述程序设计语言的语法构成
易于理解。
? 文法能自动地构造有效的语法分析器，检
查源程序是否符合语言规定的语法形式。
? 文法定义可以了解程序设计语言的结构，有
利于将源程序转化为目标代码，以及检查出
语法错误。
? 基于文法实现的语言易于扩展
小语言 Micro的定义
? P ? begin VDL;SL end.
? VDL ? VD | VD ; VDL
? VD ? var id, T
? SL ? S | S ; SL
? S ? id:= E | write(E) | read(id)
? T ? integer | real
? E ? id | num
| E + E
| E * E
|(E)
文法的定义
?文法 G定义为四元组 (VT,VN,S,P)
? VT是有限的终极符集合
? VN是有限的非终极符集合
? S是开始符,S? VN
? P是产生式的集合，且具有下面的形式：
? ??，其中 ?,??(VT?VN )*
文法的分类
? O型文法, 也称为短语文法, 其产生式具有形式,
?→ ?,其中 ?,??(VT?VN)*,并且 ?至少含一个非
终极符 。
? 1型文法, 也称为上下文有关文法 。 它是 0型文法
的特例, 要求 |?| ? |?| (S→ ?例外, 但 S不得出
现于产生式右部 )。
? 2型文法, 也称为上下文无关文法 。 它是 1型文法
的特例, 即要求产生式左部是一个非终极符,
A→ ? 。
? 3型文法, 也称为正则文法 。 它是 2型文法的特例,
即产生式的右部至多有两个符号, 而且具有下面
形式之一, A →a, A →a B
其中 A,B?VN, a?VT 。
上下文无关文法（ CFG）
?定义为四元组 (VT,VN,S,P)
? VT是有限的终极符集合
? VN是有限的非终极符集合
? S是开始符,S? VN
? P是产生式的集合，且具有下面的形式：
A?X1X2… Xn
其中 A?VN,Xi? (VT?VN), 右部可空。
? 推导,如果 A??是一个产生式，则有
?A?????,其中 ?表示一步推导 (用 A → ?)。
这时称 ???是由 ?A?直接推导的。 ?的含义是，
使用一条规则，代替 ?左边的某个符号，产
生 ?右端的符号串
? ? ?+ ?,表示 ?通过一步或多步可推导出 ?
? ? ?* ?, 表示 ?通过 0步或多步可推导出 ?
? 句型：
如果有 S?* ?, 则称符号串 ?为 CFG的
句型 。我们用 SF(G)表示文法 G的所有句
型的集合
? 句子：
如果 ?只包含终极符，则称 ?为 CFG的句
子，其中 S是文法的开始符
? 语言：
L(G)={ u| S ?+ u,u ? VT* }。
文法 G所定义的语言是其开始符所能推导
的所有终极符号串 (句子 )的集合。
? 最左（右）推导：
如果进行推导时选择的是句型中的最左 (右）
非终极符，则称这种推导为最左 (右 )推导，
并用符号 ?lm（ ?rm） 表示最左（右）推导。
? 左（右）句型：
用最左推导方式导出的句型，称为左句型，
而用最右推导方式导出的句型，称为右句型
(规范句型 )。
? 结论：
每个句子都有相应的最右和最左推导（但对
句型此结论不成立）
语法分析树与二义性
? 语法分析树 (简称分析树 )用来描述句型的结构，是句
型推导的一种树型表示。文法 G=(VN,VT,S,P),则称
满足下面条件的树为 G的一棵分析树：
1,每个结点都有 G的一个文法符号，并且根结点标
有初始符 S,非叶结点标有非终极符，叶结点标有
终极符或非终极符或 ?。
2.如果一个非叶结点 A有 n个儿子结点 (从左到右）为
X1,X2,...,Xn,则 G一定有产生式 A→X1X2,..Xn 。
? 线性推导,我们称用 ?符号进行的推导为线性推导 。
? 树型推导与线性推导的不同,线性推导指明了推导的
顺序，而树型推导则没有指明推导的顺序。因此，句
型一般只有一棵分析树 (如果无二义性 )，而线性推导
则可很多。
二义性文法
?文法 G=( {+,*,I,(,)},{E},E,P),其中 P为：
? E ? i
? E ? E + E
? E ? E * E
? E ? ( E )
句型 i*i+i:
推导 1,E ? E + E ? E * E + E ? i * E + E
? i * i + E ? i * i + i
推导 1,E ? E * E ? i * E
? i * E + E ? i * i + E ? i * i + i
推导 1的语法树
E + E
E
E * E
i i
i
E
E * E
E + E
i i
推导 2的语法树
i
