编译原理－金成植--第4章-语法分析.pptVIP

第四章 文法与语法分析 语法分析概述 文法和文法分析 进行语法分析的几种方法 1. 语法分析概述 语法分析器和识别器 语法分析的功能 语法错误类别 语法错误的处理 语法分析器和识别器 语法分析器的功能： 语法错误类别 程序的开始符，语句（表达式）的开始符 （后继符）错 ?? 标识符（常量）错：该出现时未出现 ???? 括号类错误：不匹配 ??分隔符错：assignment; 语法错误处理 要求：报告错误出现的位置 修复错误并继续检查后续部分 执行开销不应太大 修改策略： 插入/删除/修改 应急方式恢复: 定义同步符号集合(分隔符，end,某些 语句头符， else等) 发现错误时，跳过一些Token，直到找 到某个同步符号，再继续进行分析。 同步符号保证接下来的分析是从正确的 头位置开始。 2. 文法和文法分析 文法能清晰地描述程序设计语言的语法构成 易于理解。 文法能自动地构造有效的语法分析器，检 查源程序是否符合语言规定地语法形式。 文法定义可以了解程序设计语言的结构，有 利于将源程序转化为目标代码，以及检查出 语法错误。 基于文法实现的语言易于扩展 文法的定义 文法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（?r m）表示最左（右）推导。 左（右）句型： 用最左推导方式导出的句型，称为左句型，而用最右推导方式导出的句型，称为右句型(规范句型)。 结论： 每个句子都有相应的最右和最左推导（但对句型此结论不成立） 语法分析树与二义性 语法分析树(简称分析树)用来描述句型的结构，是句型推导的一种树型表示。文法 G=(VN,VT,S,P)，则称满足下面条件的树为G的一棵分析树： 1. 每个结点都有G的一个文法符号，并且根结点标 有初始符S，非叶结点标有非终极符，叶结点标有 终极符或非终极符或?。 2.如果一个非叶结点A有n个儿子结点(从左到右）为 X1,X2,...,Xn，则G一定有产生式A→X1X2 ...Xn 。 线性推导：我们称用?符号进行的推导为线性推导