编译原理第03章-文法和语言

1、2021/3/111 编译原理编译原理 文法和语言文法和语言 华东交通大学华东交通大学 软件学院网络工程教研室软件学院网络工程教研室 万仲保万仲保 Tel:7046821E-mail: 2021/3/112 第三章 文法和语言 v本章目的本章目的 为语言的语法描述寻求工具为语言的语法描述寻求工具 w工具要对程序设计语言给出精确无二义的语法描述。（严工具要对程序设计语言给出精确无二义的语法描述。（严 谨、简洁、易读）谨、简洁、易读） v形式工具形式工具-形式语言抽象地定义为一个数学形式语言抽象地定义为一个数学 系统。系统。“形式形式”是指这样的事实：语言的是指这样的事实

2、：语言的 所有规则只以什麽符号串能出现的方式来所有规则只以什麽符号串能出现的方式来 陈述。陈述。 2021/3/113 v3.1 文法的直观概念 v3.2 符号和符号串 v3.3 文法和语言的形式定义 v3.4 文法的类型 v3.5 上下文无关文法及其语法树 v3.6 句型分析 v3.7 实用说明 第三章第三章 文法和语言文法和语言 2021/3/114 文法的直观概念文法的直观概念 v一个程序设计语言是一个记号系统，如同自然语言 一样，它的完整的定义应包括语法和语义两个方面。 所谓一个语言的语法是指一组规则，用它可以形成 和产生一个合适的程序。目前广泛使用的手段是上 下文无关文法，即用上下文

3、无关文法作为程序设计 语言语法的描述工具。语法只是定义什么样的符号 序列是合法的，与这些符号的含义毫无关系 v阐明语法的一个工具是文法，这是形式语言理论的 基本概念之一。 v示例：汉语句子的描述 v语言概述 2021/3/115 汉语句子的描述汉语句子的描述 v语法规则定义 v字符串的判断 2021/3/116 语法规则定义语法规则定义 句子 =主语谓语 主语 =代词名词 代词 =我你他 名词 =王明大学生工人英语 谓语 =动词直接宾语 动词 =是学习 直接宾语 =代词名词 2021/3/117 字符串的判断字符串的判断 v 有了一组规则以后，按照如下方式用它们导出句子：开始去找 = 左端的带

4、有句子的规则并把它由 =右端的符号串代替，这个 动作表示成： 句子 主语谓语， v 然后在得到的串主语谓语中，选取主语或谓语， 再用相应规则的 =右端代替之。比如，选取了主语，并采用 规则主语 =代词， v 那么得到：主语谓语 代词谓语， 重复做下去。 v 句子：“我是大学生”的全部动作过程是： 句子主语谓语 代词谓语 我谓语我动词直接宾语 我是直接宾语我是名词我是大学生 2021/3/118 字符串的判断字符串的判断 v“我是大学生”的构成符合上述规则，而“我大 学生是”不符合上述规则，我们说它不是句 子。这些规则成为我们判别句子结构合法与 否的依据，换句话说，这些规则看成是一种 元语言，用

5、它描述汉语。这里仅仅涉及汉语 句子的结构描述。其中一种描述元语言称为 文法。 2021/3/119 符号和符号串 v定义： 符号：可以相互区别的记号（元素）。 字母表（）：符号（元素）的非空有穷集合。 符号串：由字母表中的符号组成的任何有穷序列称为 该字母表上的符号串。 1.空符号串(没有符号的符号串)是上的符号串 2.若x是上的符号串,a是的元素,则xa是上的符号串 3. y是上的符号串,当且仅当它可以由1和2导出。 例如： =a,b ,a,b,aa,ab,aabba都是上的符号串 v符号串的运算 2021/3/1110 符号串的运算符号串的运算 v既然将语言定义为一个集合，那么有关集合 的

6、运算也适合语言。即：设L是（上的）一 个语言,M是（上的）一个语言，则语言L 和M的并，交，差，补是一个语言。 符号串的头、尾、子串 符号串的长度 符号串的连接 符号串的方幂 符号串的集合 2021/3/1111 符号串的头、尾、子串符号串的头、尾、子串 v符号串s的头（前缀）：移走符号串s尾部的零个或多于零 个符号得到的符号串。 如： b是符号串banana的一个前缀. v符号串s的尾（后缀）：删去符号串s头部的零个或多于零 个符号得到的符号串。 如:nana是符号串banana的一个后缀. v符号串s的子串：从s中删去一个前缀和一个后缀得到的符 号串。 如:ana是符号串banana的一个

7、子串. v对于每个符号串s， s和两者都是符号串s的前缀，后缀和 子串。 v符号串s的真前缀，真后缀，真子串：任何非空符号串 x,相 应地，是s的前缀，后缀或子串，并且 s x。 2021/3/1112 v符号串中符号的个数。符号串中符号的个数。 v符号串符号串s的长度记为的长度记为|s|。 v的长度为的长度为0 符号串的长度符号串的长度 2021/3/1113 符号串的连接符号串的连接 v设设x x、y y是符号串，则是符号串，则x x、y y的连接是把的连接是把y y的符的符 号写在号写在x x的符号之后得到的符号串的符号之后得到的符号串xyxy 如如 x=ab,y=cd x=ab,y=c

8、d 则则 xy=abcdxy=abcd 有有a = aa = a 2021/3/1114 符号串的方幂符号串的方幂 v方幂：设x是符号串，把x自身连接n次得到 的符号串z，即z=aaaa称为符号串x的方幂。 写作z=an v示例： a1=a, a2=aa a0= 2021/3/1115 符号串集合符号串集合 v 若集合A中所有元素都是某字母表上的符号串，则称A为 字母表上的符号串集合。 v 两个符号串集合A和B的乘积定义为： AB =xy|xA且yB 若 集合A=ab,cde B = 0,1，则 AB =ab1,ab0,cde0,cde1 v 使用 * 表示上的所有有穷长符号串（包括）组成的集

9、 合。*称为的闭包。 v 上的除外的所有符号串组成的集合记为+ 。 +称为 的正闭包。 * = 012 n + = 12 n * = + + =* = * 2021/3/1116 文法和语言的形式定义 v文法和语言的形式定义 文法的定义 推导的定义 句型（子）的定义 语言的定义 文法等价的定义 2021/3/1117 语言概述语言概述 v 语言是由句子组成的集合，是由一组符号所构成的集合。语言是由句子组成的集合，是由一组符号所构成的集合。 v 汉语汉语-所有符合汉语语法的句子的全体所有符合汉语语法的句子的全体 v 英语英语-所有符合英语语法的句子的全体所有符合英语语法的句子的全体 v 每个句子

10、构成的规律每个句子构成的规律 v 语言研究语言研究 每个句子的含义每个句子的含义 v 每个句子和使用者的关系每个句子和使用者的关系 每个程序构成的规律每个程序构成的规律 v 研究程序设计语言研究程序设计语言 每个程序的含义每个程序的含义 每个程序和使用者的关系每个程序和使用者的关系 语法语法 Syntax v 语言研究的三个方面语言研究的三个方面 语义语义 Semantics 语用语用 Pragmatics 2021/3/1118 程序设计语言程序设计语言 v研究程序设计语言研究程序设计语言 每个程序构成的规律每个程序构成的规律 每个程序的含义每个程序的含义 每个程序和使用者的关系每个程序和使

11、用者的关系 v语言研究的三个方面语言研究的三个方面 语法语法 Syntax 语义语义 Semantics 语用语用 Pragmatics 2021/3/1119 语言研究的三个方面 v 语法 - 表示构成语言句子的各个记号之间的组合规律 v 语义 - 表示各个记号的特定含义。（各个记号和记号所表 示的对象之间的关系） v 语用 -表示在各个记号所出现的行为中，它们的来源、使 用和影响。 v 每种语言具有两个可识别的特性，即语言的形式和该形式 相关联的意义。 v 语言的实例若在语法上是正确的，其相关联的意义可以从 两个观点来看，其一是该句子的创立者所想要表示的意义， 另一是接收者所检验到的意义。

12、这两个意义并非总是一样 的，前者称为语言的语义，后者是其语用意义。幽默、双 关语和谜语就是利用这两方面意义间的差异。 2021/3/1120 文法的定义文法的定义 v 文法G定义为四元组(VN，VT，P，S )其中VN为非终结符号 (或语法实体，或变量)集；VT为终结符号集；P为产生式 (也称规则)的集合；VN，VT和P是非空有穷集。S称作识别 符号或开始符号，它是一个非终结符，至少要在一条产生 式中作为左部出现。 v VN和VT不含公共的元素，即VN VT = v 通常用V表示VN VT ，称为文法G的字母表或字汇表。 v 规则规则，也称重写规则重写规则、产生式产生式或生成式生成式，是形如或

13、 =的(，)有序对，其中是字母表V的正闭包V+中的 一个符号，是V*中的一个符号。称为规则的左部，称 作规则的右部。 v 示例： 例3.1 例3.2 2021/3/1121 例例3.1 v文法G=（VN，VT，P，S），VN = S , VT = 0, 1 ，P= S0S1, S01 。这里，非 终结符集中只含一个元素S；终结符集由两 个元素0和1组成；有两条产生式；开始符号 是S。 2021/3/1122 例例3.2 v 文法G=(VN，VT，P，S) v 其中VN=标识符，字母，数字VT=a,b,c,，x,y,z,0,1,，9 v P =标识符字母 标识符标识符字母 标识符标识符数字 字母

14、a 字母b 字母z 数字0 数字1 数字9 S =标识符 这里，使用尖括号和括起非终结符。 2021/3/1123 推导的定义 v 直接推导“”： 如是文法G=(Vn，VT，P，S)的规则(或说是P中的一产生式)， 和是 V*中的任意符号，若有符号串v，w满足：v= ，w= 则说v(应用规则)直接产生w，或者说，w是v的直接推导直接推导，也可以说， w直接归约直接归约到v，记作v w。 v 如果存在直接推导的序列： v 示例： 直接推导 多步推导 2021/3/1124 直接推导的示例 v 对于例3.1的文法G，可以给出直接推导的一些例子如下： v=0S1,w=0011， 直接推导：0S100

15、11，使用的规则：S01，这里 =0，=1。 v=S,w=0S1， 直接推导：S0S1使用的规则：S0S1，这里 =，= v=0S1,w=00S11， 直接推导：0S100S11，使用的规则：S0S1，这里 =0，=1。 v 对于例3.2的文法G，直接推导的例子有： v v=标识符，w=标识符字母， 直接推导：标识符 标识符字母， 使用的规则：标识符标识符字母，这里 = v v=标识符字母数字，w=字母字母数字， 直接推导：标识符字母数字 字母字母数字， 使用的规则：标识符字母。这里 =， 字母数字。 v v=abc数字，w=abc5， 直接推导：abc数字 abc5, 使用的规则：数字5，这

16、里 =abc,=。 2021/3/1125 多步推导的示例多步推导的示例 v对例3.1的文法，存在直接推导序列 v=0S100S11000S11100001111=w， 即0S1 00001111，也可记作0S1 00001111 v对例3.2的文法，存在直接推导序列 v=标识符标识符数字字母 数字x数字x1=w， 即 x1，也可记作 x1。 2021/3/1126 句型(子)的定义 v设GS 是一文法，如果符号串x是从识别符 号推导出来的，即有S x，则称x是文法 GS的句型句型。若x仅由终结符号组成， 即S x，xVT*，则称x为GS的句子句子。 v例： S，0S1，000111都是例3.

17、1的文法G的句型，其 中000111是G的句子。 标识符字母，字母数字，a1等 都是例3.2文法G的句型，其中a1是G的句子。 2021/3/1127 语言的定义 v文法G所产生的语言定义为集合x|S x，其中S为 文法识别符号，且xVT*。可用L(G)表示该集合。 v从定义可以看出两点： 第一，符号串x可从识别符号推出，也即x是句型。 第二，x仅由终结符号组成，即x是文法G的句子。也就 是说，文法描述的语言是该文法一切句子的集合。 v例： 例3.1 G： S0S1， S01 L(G)=0n1n|n1 例3.3 2021/3/1128 例例3.3 v设G=(VN，VT，P，S)， VN=S,B

18、,E， VT=a,b,e，P由下列产生式组成： (1) SaSBE (2) SaBE (3) EBBE (4) aBab (5) bBbb (6) bEbe (7) eEee v则L（G）= anbnen | n1 2021/3/1129 文法的等价 v若L（G1）=L（G2），则称文法G1和G2是等 价的。 v示例：文法G1A：A0R A01 RA1与 G2S：S0S1 S01等价。 2021/3/1130 文法的类型 v乔姆斯基分类 v 示例： 例3.4 例3.5 v乔姆斯基分类文法之间关系 v对应于乔姆斯基分类文法的语言 v文法和语言之间的关系 2021/3/1131 乔姆斯基对文法的分

19、类乔姆斯基对文法的分类 v 通过对产生式施加不同的限制，Chomsky（乔姆斯基）将 文法分为四种类型： 0型文法：对文法G=(VN，VT，P，S)的任一产生式，都有 (VNVT)*且至少含有一个非终结符，(VNVT)*。 1型文法（上下文有关文法）上下文有关文法） ：对文法G=(VN，VT，P，S)的任一 产生式，都有|， 仅仅 S除外。 2型文法（上下文无关文法）上下文无关文法）：对文法G=(VN，VT，P，S)的任一产 生式，都有VN ， (VNVT)* 。 3型文法（正规文法正规文法）：设G=(VN，VT，P，S)，若P中的每一个产生 式的形式都是AaB或Aa，其中A和B都是非终结符，

20、a是终结符。 3型文法G=(VN，VT，P，S)的P中的规则有两种形式：一种是前面定义的 形式，即：AaB或Aa其中A，BVN ，aVT*，另一种形式是：ABa 或Aa，前者称为右线性文法，后者称为左线性文法。正规文法所描述 的是VT*上的正规集。 2021/3/1132 例例3.43.4 vG=(S,A,B,a,b,P,S)，其中P由下列产生 式组成： SaB AbAA SbA Bb Aa BbS AaS BaBB 或将P改写为： SaB|bA AbA|a Aa|AaS BbS|BaB|b v则G是正规文法或3型文法。 2021/3/1133 例例3.53.5 v文法G=(S,A,B,0,1

21、,P,S)，其中P由下列 产生式组成： S0A A1B S1B B1B S0 B1 A0A B0 A0S 或将P改写为： S0A|1B|0 A0S|1B|0A B1B|1|0 v则G是正规文法或3型文法。 2021/3/1134 乔姆斯基分类文法之间关系乔姆斯基分类文法之间关系 2型文法型文法 1型文法型文法 0型文法型文法 四种四种文法文法之间之间的的逐级逐级“包含包含”关系关系 3型文法型文法 2021/3/1135 对应乔姆斯基分类文法的对应乔姆斯基分类文法的语言 v0型文法产生的语言称为0型语言。 v1型文法或上下文有关文法（ CSG ）产生的语言 称为1型语言或上下文有关语言（CSL

22、）。 v2型文法或上下文无关文法（ CFG ）产生的语言 称为2型语言或上下文无关语言（ CF L ）。 v3型文法或正则（正规）文法（ RG ）产生的语言 称为3型语言正则（正规）语言（ RL ）。 2021/3/1136 文法和语言之间的关系文法和语言之间的关系 v四种文法之间的关系是将产生式做进一步限 制而定义的。 v语言之间的关系依次：有不是上下文有关语 言的0型语言，有不是上下文无关语言的1型 语言，有不是正则语言的上下文无关语言。 2021/3/1137 上下文无关文法及其语法树 v语法树 句型能够构造关联语法树的条件 示例：例3.7 v最左（右）推导 v二义性文法 判断依据 示例

23、：例3.8 二义性文法与二义性语言的区别 2021/3/1138 句型能够构造关联语法树的条件句型能够构造关联语法树的条件 v给定文法G=(VN，VT，P，S)，对于G的任何句型 都能构造与之关联的语法树(推导树)。这棵树满足 下列4个条件： 每个结点都有一个标记，此标记是V的一个符号。 根的标记是S。 若一结点n至少有一个它自己除外的子孙（子结点）， 并且有标记A，则A肯定在VN中。 如果结点n的直接子孙，从左到右的次序是结点n1， n2，nk，其标记分别为A1，A2，Ak，那么 AA1A2Ak一定是P中的一个产生式。 2021/3/1139 例例3.7 G=(S,A,a,b,P,S)，其中

24、P为： SaAS ASbA ASS Sa Aba 右图是G（aabbaa）的一棵推导树。 2021/3/1140 最左（右）推导最左（右）推导 v如果在推导的任何一步，其中，是句型， 都是对中的最左(最右)非终结符进行替换，则称 这种推导为最左(最右)推导。 v在形式语言中，最右推导常被称为规范推导。由 规范推导所得的句型称为规范句型。 v最左推导示例 SaASaSbASaabASaabbaSaabbaa v最右推导示例 SaASaAaaSbAaaSbbaaaabbaa 2021/3/1141 二义文法的判断依据判断依据 v若一个文法存在某个句子对应两棵不同的语法树， 则称这个文法是二义的。

25、或者，若一个文法存在某个句子有两个不同的最左 （右）推导，则称这个文法是二义的。 v如果产生上下文无关语言的每一个文法都是二义的， 则说此语言是先天二义的。 v判定任给的一个上下文无关文法是否二义，或它是 否产生一个先天二义的上下文无关语言，这两个问 题是递归不可解的，即，不存在一个算法，它能在 有限步骤内，确切判定任给的一个文法是否为二义 的。我们所能做的事是为无二义性寻找一组充分条 件(当然它们未必都是必要的)。 2021/3/1142 例例3.8 v文法G=(E,+,*,i,(,),P,E)其中P= EiEE+EEE*EE(E) 是二义性的， 假若规定了运算符“+”与“*”的优先顺序和结

26、合 规则，即按惯例，让“*”的优先性高于“+”，且 它们都服从左结合，那么就可以构造出一个无二义 文法。 v定义表达式的无二义文法GE： ET|E+T TF|T*F F(E)|i 它和上述文法产生的语言是相同的。即它们是等价 的。 2021/3/1143 二义性文法与二义性语言的区别二义性文法与二义性语言的区别 v文法的二义性和语言的二义性是两个 不同的概念。因为可能有两个不同的文 法G和G，其中G是二义的，但是却有 L(G)=L(G)，也就是说，这两个文法 所产生的语言是相同的。 2021/3/1144 句型的分析 v 句型分析句型分析是识别一个输入符号串是否为语法上正确的程序 的过程。在语

27、言的编译实现中，把完成句型分析的程序称 为分析程序分析程序或识别程序识别程序，分析算法又称识别算法。 v 从左到右的分析算法，即总是从左到右地识别输入符号串， 首先识别符号串中的最左符号，进而依次识别右边的一个 符号，直到分析结束。 v 句型的分析算法分类 v 句型的分析算法反映语法树的构造过程 v 句型分析的有关定义 v 句型分析的有关问题 2021/3/1145 句型的分析算法分类 v自上而下分析法： 是从文法的开始符号出发，反复使用各种产生 式，寻找“匹配”于输入符号串的推导。 示例：例3.9 v自下而上分析法： 从输入符号串开始，逐步进行“归约”，直至 归约到文法的开始符号。 示例 2

28、021/3/1146 两种方法反映语法树的构造过程 v自上而下方法： 自上而下方法是从文法符号开始，将它做为语 法树的根，向下逐步建立语法树，使语法树的 末端结点符号串正好是输入符号串。 v自下而上方法： 自下而上方法是从输入符号串开始，以它做为 语法树的末端结点符号串，自底向上地构造语 法树。 2021/3/1147 例例3.9：自上而下分析：自上而下分析 例：考虑文法GS； ScAd Aab Aa 识别输入串w=cabd是否该文法的句子。 推导过程：推导过程：ScAd cabd 2021/3/1148 示例：自下而上分析示例：自下而上分析 例：例：考虑文法GS； ScAd Aab Aa 识

29、别输入串w=cabd是否该文法的句子。 S AA c a b d c a b d c a b d 规约规约过程构造的推导：过程构造的推导： cAd cabd S cAd 2021/3/1149 句型分析的有关定义句型分析的有关定义 v令G是一文法，S是文法的开始符号，是 文法G的一个句型。如果有： S A且A 则称是句型相对于非终结符 A的短语短语。特别，如有A 则称是句型相 对于规则A的直接短语直接短语(也称简单短语简单短语)。一个 句型的最左直接短语称为该句型的句柄句柄。 v示例 v从句型的推导树中查找方法 2021/3/1150 示例示例 v 文法GE的一个句型i*i+i。为了叙述方便，

30、将句型改写为i1*i2+i3。因为 有： E F* i2+i3 且Fi1则称i1是句型i1*i2+i3的相对于非终结符F的短语，也是相 对于规则Fi的直接短语。又有： E i1*F+i3 且Fi2则i2是句型i1*i2+i3的相对于F的短语，也是相对于规则 Fi的直接短语，还有： E i1*i2+F 且Fi3则i3也是句型i1*i2+i3的相对于F的短语，也是相对于规则 Fi的直接短语。 E T*i2+i3，且T i1则i1是句型i*i2+i3的相对于T的短语。 E i1*i2+T 且T i3则i3是句型i1*i2+i3的相对于T的短语。 E E+i3 且E i1*i2则i1*i2是句型i1*

31、i2+i3的相对于E的短语。 E E 且E i1*i2+i3则i1*i2+i3是句型i1*i2+i3相对于E的短语。 即i1，i2，i3，i1*i2和i1*i2+i3都是句型i1*i2+i3的短语，而且i1，i2，i3均为直接 短语，其中i1是最左直接短语，即句柄。 v 虽然i2+i3是句型i1*i2+i3的一部分，并不是它的短语，因为尽管有E i2+i3，但不存在从文法开始符号E到i1*E的推导。 2021/3/1151 从句型的推导树中查找方法从句型的推导树中查找方法 v从句型的推导树上很容易找出句型的短语和直接 短语。 v设A是句型的某一子树的根，其中是形成此 子树的末端结点的符号串，则

32、其中是句型的 相对于A的短语。若这个子树只有一层分支，则 是句型的直接短语。 v示例 2021/3/1152 示例：推导树中找短语示例：推导树中找短语 2021/3/1153 句型分析的有关问题 v在自上而下的分析方法中如何选择使用哪个产生 式进行推导？ 假定要被代换的最左非终结符号是B，且有n条规则： BA1|A2|An，那么如何确定用哪个右部去替代B？ v在自下而上的分析方法中如何识别可归约的串？ 在分析程序工作的每一步，都是从当前串中选择一个 子串，将它归约到某个非终结符号，该子串称为“可 归约串”。 v存在确定和不确定分析。 2021/3/1154 实用说明实用说明 v有关文法的实用限

33、制有关文法的实用限制 v上下文无关文法中的上下文无关文法中的规则规则 v无用符号和无用产生式的消除无用符号和无用产生式的消除 v -产生式的消除产生式的消除 v单产生式的消除单产生式的消除 2021/3/1155 有关文法的实用限制 v 在实用中，我们将限制文法中不得含有有害规则和多余规 则： 有害规则，是指形为UU的产生式。它对描述语言显然是没有必 要的。说它有害，是说它只会引起文法的二义性。 多余规则，是指文法中那些连一个句子的推导都用不到的规则，这 类规则在文法中以两种形式出现。一种是文法中某些非终结符不在 任何规则的右部出现，所以任何句子的推导中不可能用到它。 v 对文法G=(VN，V

34、T，P，S)来说，为了保证其任一非终结符 A在句子推导中出现，必须满足如下两个条件： A必须在某句型中出现。即有S A，其中，属于(VTVN)* 。 必须能够从A推出终结符号串t来。即A t，其中tVT 。 v 若程序设计语言的文法包含有多余规则时，其中必定有错 误存在，因此检查文法是否包含多余规则是很有必要的。 2021/3/1156 上下文无关文法中的规则 v上下文无关文法中某些规则可具有形式 A，称这种规则为规则。 v规则会使得有关文法的一些讨论和证明变 得复杂,有时会限制这种规则的出现。 v上下文无关文法的相关定理 定理3.1 定理3.2 2021/3/1157 定理3.1 v若L是由

35、文法G=(VN，VT，P，S)产生的语言，P 中的每一个产生式的形式均为A，其中 AVN，(VN VT)*(即可能为)， 则L能由这样一种文法产生：每一个产生式 或者为A形式，其中AVN， (VN VT)+(即)，或者 S且 S不出现 在任何产生式右边。 2021/3/1158 定理3.2 v如果如果G=G=(VN，VT，P，S)是一个上下文有关文法，是一个上下文有关文法， 则存在另一个上下文有关文法则存在另一个上下文有关文法G G1 1，它所产生，它所产生 的语言与的语言与G G产生的相同，即产生的相同，即L(G)=L(GL(G)=L(G1 1) )，其，其 中中G G1 1的开始符号不出现

36、在的开始符号不出现在G G1 1的任何产生式的的任何产生式的 右边。右边。 v若若G G为上下文无关文法或正规文法，类似结为上下文无关文法或正规文法，类似结 论成立。论成立。 2021/3/1159 无用符号和无用产生式的消除无用符号和无用产生式的消除 v定义：设G=(VN，VT，P，S)是一文法，我们说G 中的一个符号x(VNVT)是有用的指x至少出现在 一个句子的推导过程中。即x必须同时满足以下两 个条件： 存在、V*，有S*x 存在wVT*,x*w 否则就说x是无用的。如果一个产生式的左部或右部含 有无用符号，则此产生式称之为无用产生式。 v消除算法 算法1 算法2 v示例 2021/3

37、/1160 算法算法1 v1、分别置VN(1)和P(1) 为； v2、对于P中的每一产生式A ，若 VT* ，则将 A置于VN(1) 中； v3、对于P中的每一产生式A x1x2xm若每个xi都属 于VN(1) 或VT ，则将A置于VN(1) ； v4、重复步骤3，直到VN(1)不再增大为止； v5、对于P中的每一产生式B y1y2yn ，若B及每一 个yi都属于VN(1) VT ，则将此产生 式B y1y2yn 置于P (1)。 2021/3/1161 算法算法2 v1、分别置VN 、VT和P 为； v2、将文法的开始符号S置入VN中； v3、对于G (1)中任何形如A x1|x2 | |

38、xm的产生式， 若A VN ，则将符号串x1，x2 ， ， xm中的全部 非终结符号置于VN中，而将其中的全部终结符号 置于VT中； v4、重复步骤3，直到VN和VT都不再增大为止； v5、将P中左右部仅含VN VT中符号的所有产生式 置P 。 2021/3/1162 示例示例 v文法的定义 已知文法G=（S,U,V,W，a,b,c，P，S），产 生式P的组成如下： SaS SW SU Ua VbV Vac WaW v执行算法1 v执行算法2 2021/3/1163 执行算法执行算法1 v第一步，由于产生式Ua、 Vac的右部均 为终结符号串，故置VN(1) =U，V； v第二步，对于产生式S

39、U ，由于U VN(1) ， 故将S置于中，所以VN(1) =S，U，V； v于是得到以下文法G1： vG1=（S,U,V,a,b,c,P (1),S），其中P (1)由如 下产生式组成： SaS SU Ua VbV Vac 2021/3/1164 执行算法执行算法2 v第一步，置VN =S； v第二步，因为G1中含有产生式SU、Ua ， 故应将U、a分别置于，即VN =S，U VT =a; v因此得到等价的且不含无用符号和无用产生 式的文法为G2=（S，U，a，P，S）， 其中，P由如下产生式组成： SaS SU Ua 2021/3/1165 -产生式的消除 v算法3 v算法4（ 不属于文法所产生的语言） v算法5 （属于文法所产生的语言） v示例： 不属于文法