编译原理及实现技术：第三章 语法分析

1、语法分析概述语法分析的对象文法语法分析的功能语法错误的分类语法错误处理语法分析方法概述21.1 语法分析的功能3TokenToken ListList语法分析器语法分析器语法树语法树 / / 语法错误信息语法错误信息1.2 语法错误类别程序的开始符，语句（表达式）的开始符（后继符）错标识符（常量）错：该出现时未出现括号类错误：不匹配分隔符错：赋值语句41.3 语法错误处理要求：报告错误出现的位置修复错误并继续检查后续部分执行开销不应太大处理策略：紧急方式恢复；短语级恢复；出错产生式；全局纠正。52.4 语法分析方法概述自顶向下LL（1）递归下降自底向上简单优先方法LR族方法6文法概述文法相关的

2、概念文法等价变换72.1 文法概述文法能清晰地描述程序设计语言的语法构成，易于理解。文法能构造有效的语法分析器，检查源程序是否符合语言规定的语法形式。文法定义可以了解程序设计语言的结构，有利于将源程序转化为目标代码及检查出语法错误。基于文法实现的语言易于扩展。82.1.1 文法的形式化定义文法G定义为四元组(VT,VN,S,P) VT是有限的终极符集合 VN是有限的非终极符集合 S是开始符，S VN P是产生式的集合，且具有下面的形式：，其中，(VTVN)*92.1.2 文法分类O型文法：也称为短语文法，其产生式具有形式: ，其中,(VTVN)*，并且至少含一个非终极符 。1型文法：也称为上下

3、文相关文法。它是0型文法的特例，要求| | (S例外，但S不得出现于产生式右部)。2型文法：也称为上下文无关文法。它是1型文法的特例，即要求产生式左部是一个非终极符: A 。3型文法：也称为正则文法。它是2型文法的特例，即产生式的右部至多有两个符号，而且具有下面形式之一: A a ，A a B 其中A,BVN ，aVT 。 102.1.3 上下文无关文法定义为四元组(VT,VN,S,P) VT是有限的终极符集合 VN是有限的非终极符集合 S是开始符，S VN P是产生式的集合，且具有下面的形式：AX1X2Xn 其中AVN，Xi(VTVN) ，右部可空。112.2 文法相关概念推导（直接推导）：

4、如果A是一个产生式，则有A ,其中表示一步推导。这时称是由A直接推导的。 /*的含义是，使用一条规则，代替左边的某个符号，产生右端的符号串。*/ + :表示通过一步或多步可推导出 * :表示通过零步或多步可推导出 12句型：如果有S* ，则称符号串为CFG的句型 。我们用SF(G)表示文法G的所有句型的集合。句子：如果只包含终极符，则称为CFG的句子。语言：L(G)= u| S + u ,u VT* 文法G所定义的语言是其开始符所能推导的所有终极符号串(句子)的集合。 13最左（右）推导：如果进行推导时选择的是句型中的最左(右）非终极符，则称这种推导为最左(右)推导，并用符号lm（rm）表示最

5、左（右）推导。左（右）句型：用最左推导方式导出的句型，称为左句型，而用最右推导方式导出的句型，称为右句型(也称为规范句型)。14短语：设S是文法的开始符，是句型(即有S *），如果满足条件：S* AA+ VT+ 则称是句型的一个短语。直接短语（简单短语）：如果满足条件：S* AA VT+ 则称是句型的一个简单短语。句柄：一个句型可能有多个简单短语，其中最左的简单短语称之为句柄。 15语法分析树(简称分析树)用来描述句型的结构，是句型推导的一种树型表示。给定文法 G=(VN,VT,S,P)，则称满足下面条件的树为G的一棵语法分析树：1.每个结点都有G的一个文法符号，并且根结点标有初始符S，非叶结

6、点标有非终极符，叶结点标有终极符或非终极符或。2.如果一个非叶结点A有n个儿子结点(从左到右）为 X1,X2,.,Xn，则G一定有产生式 AX1X2 .Xn 。16线性推导：称用符号进行的推导为线性推导 。树型推导与线性推导的不同：线性推导指明了推导的顺序，而树型推导则没有指明推导的顺序。因此，句型一般只有一棵分析树(如果无二义性)，而线性推导则可以有很多棵分析树。二义性文法：如果一个文法的某个句型有两棵不同的语法分析树，则称该文法二义性为二义性文法。17思考给定分析树的任一子树的树叶全体(具有共同祖先的叶节点符号串)皆为短语？任一简单子树的树叶全体(具有共同父亲的叶节点符号串)皆为简单短语？

7、每个句子都有相应的最右和最左推导吗？每个句型呢？18二义性文法实例例：文法G=( +,*,i,(,), E, E, P),其中P为：E iE E + EE E * EE ( E )19句型句型i*i+i 可能的推导可能的推导:推导推导1: E E + E E * E + E i * E + E i * i + E i * i + i推导推导2: E E * E i * E i * E + E i * i + E i * i + i推导推导1的语法树的语法树E+EEE*EiiiEE*EE+Eii推导推导2的语法树的语法树i202.3 文法的等价变换增加拓广产生式消除空产生式消除不可达产生式消除特

8、型产生式消除公共前缀消除左递归消除二义性21增加拓广产生式定理：对任一文法G1都可以构造文法G2，使得L(G1)=L(G2)，且G2的开始符唯一且不出现于任何产生式的右部。证明：假设S是G1的开始符，则只要在G1中扩充一条新产生式ZS即可，其中Z是新的开始符。另这样扩充后的文法为G2，则它显然满足定理的要求。22消除空产生式定理：对任一文法G1，可构造文法G2，使得L(G1)=L(G2)，且G2中无空产生式。证明：根据G1，构造G2的方法如下：1.令G2=G1；2.令=A | A，=A | A +, +；对于文法中任意产生式AX1X2Xi-1XiXi+1Xn,若Xi，补充规则A X1X2Xi-

9、1Xi+1Xn；重复2，直到不补充新的产生式。3.从G2.P中删除所有形如A的产生式。4.从G2.VN删除只能导出空串的非终极符。例： AaBcD Bb | DBB | d23消除不可达产生式定理：对任一文法G1都可以构造文法G2，使得L(G1)=L(G2)，且G2中的每个非终极符必出现在它的某个句型中。证明：根据G1，构造文法G2的方法如下：1.令G2=G1。2.令=S | S是文法的开始符，递归扩充 =B | AxByG1, BVN, A。3.若A，则删除以A为左部的所有产生式。24消除特型产生式定理：对任一文法G1，可以构造文法G2，使得L(G1)=L(G2)，且在G2中没有特型产生式。

10、证明：构造无特型产生式的文法G2的方法如下：1.对文法G1中任意非终极符A，求集合 A=B | A+B, BVN。2.若BA，且B是文法G中的一个非特型产生式，则补充如下规则A。3.去掉文法G1中的所有的特型产生式。4.去掉新的文法中的无用产生式。例：AB|D|aBBC|bCcDB|d25消除公共前缀某个非终极符A有如下的两个产生式：A，A 称这两个产生式有公共前缀。方法：对于产生式：A1|2| |n| ，其中表示不以开头的字符串，引进非终极符A，使产生式替换为：A A | A 1|2 | n26消除左递归一个文法含有下列形式的产生式时（1） AA |其中AVN；, (VNVT)*（2） AB|BA| 其中A,B VN； , (VNVT)*（1）称为直接左递归，（2）称为间接左递归，即文法中只要有A+A，则称文法为左递归的。对于不含回路或空产生式，消除做递归方法为27（1）对直接左递归形如：AA|消除左递归得：AAAA|（2）间接左递归形如：AB|BA|消除左递归得：转为直接左递归形式：AA| 或者 BB|按照直接左递归方式消除。去