文法和形式语言.pptx

第二章第二章文法和形式语言文法和形式语言形式化定义，基本概念形式化定义，基本概念文法的写法，文法的写法，BNF表示法表示法规则的推导，语法树及其二义性规则的推导，语法树及其二义性文法变换，文法和语言的分类文法变换，文法和语言的分类2概概述述程序设计语言包含三方面程序设计语言包含三方面如：如：x=a+b*c语法：语言的构成规律语法：语言的构成规律,C语言中赋值语句的写法语言中赋值语句的写法语义：语言所代表的含义，语义：语言所代表的含义，对对=号右边的表达式号右边的表达式进行计算，再赋值给左边的变量进行计算，再赋值给左边的变量语用：语言的实际应用，语用：语言的实际应用，用于计算和保存值用于计算和保存值形式化方法：形式化方法：定义基本符号串和规则，根据定义基本符号串和规则，根据规则规则“造句造句”形式语言：形式语言：只看语法，不考虑含义只看语法，不考虑含义用规定的符号串和规则来书写的语言用规定的符号串和规则来书写的语言32.1符号和符号串符号和符号串组成形式语言的基本要素组成形式语言的基本要素字母表字母表是符号的非空有穷集合是符号的非空有穷集合习惯用大写字母表示习惯用大写字母表示如有字母表如有字母表、V：=a,b,cV=0,1符号符号(字符字符)字母表中的元素字母表中的元素如：如：a，b，c即为符号即为符号不同文种的语言有适用于该语言的字母表不同文种的语言有适用于该语言的字母表4符号串：符号串：字母表中符号组成的有穷序列。字母表中符号组成的有穷序列。如：如：=a,b,c，则可以有符号串，则可以有符号串a,b,c,aa,ab,ac,aaa有序性：若符号串中符号出现的顺序不同，符号串有序性：若符号串中符号出现的顺序不同，符号串也不同，如也不同，如ab和和ba是不同的符号串是不同的符号串空串：不含有任何符号的串称作空串，记作空串：不含有任何符号的串称作空串，记作。符号串集合：符号串集合：字母表字母表上若干个符号串组成的集合上若干个符号串组成的集合如：如：有符号串集合有符号串集合A=ab,bcB=a,ab,abc符号串与符号串集合符号串与符号串集合5句子句子字母表上符合某种规则构成的符号串。字母表上符合某种规则构成的符号串。语言语言字母表上句子的集合。字母表上句子的集合。注：注：用用a,b,c,r表示符号；表示符号；用用s,t,u,z表示符号串；表示符号串；用用A,B,C,Z表示符号串集合。表示符号串集合。如在字母表如在字母表=a,b,c上，有符号串集合上，有符号串集合A=a,ab,aa,abc，s=ab是是A中的符号串，中的符号串，a,b,c都是字母表中的符号都是字母表中的符号句子和语言句子和语言6例如：例如：=a，b，c，有，有x,y符号串符号串二、符号串的运算二、符号串的运算符号串相等符号串相等字母表字母表上的两个符号串上的两个符号串x，y，若，若x，y的各个符的各个符号号依次相等依次相等，则该两符号串相等，记，则该两符号串相等，记x=y x=y若若x=abbc，y=abbc若若x=ab，y=baxy7符号串长度符号串长度符号串中包含符号的个数，符号串中包含符号的个数，用用x表示表示abcd=4=0符号串连接符号串连接设字母表设字母表上的两个符号串上的两个符号串x x，y y，把，把y y的所有的所有符号相继写在符号相继写在x x的符号之后所得到的符号串称的符号之后所得到的符号串称为为x x与与y y的连接，用的连接，用xyxy表示表示若若x=ab，y=ba则则xy=abba且且xy=x+y x=x=xxyyx8符号串的逆符号串的逆符号串符号串x的倒置的倒置例：例：x=abc，符号串符号串x的逆为的逆为cba符号串的前缀、后缀、子串符号串的前缀、后缀、子串后缀：符号串任意尾部，包括空串后缀：符号串任意尾部，包括空串 前缀：符号串任意首部，包括空串前缀：符号串任意首部，包括空串 如：符号串如：符号串abc前缀：前缀：,a,ab,abc后缀：后缀：c,bc,abc,子串：子串：a,b,c,ab,abc,bc,9符号串的幂符号串的幂符号串符号串x自身连接自身连接n次得到的次得到的如：如：x=ab，则有则有x0=x1=abx2=ababxn=ababab(n个个ab相连，而不是相乘相连，而不是相乘)注：用注：用an表示表示n个个a相连接的符号串，而不是相连接的符号串，而不是n个个a相乘相乘10符号串集合的乘积符号串集合的乘积定义：若串集定义：若串集A=1,2,，串集，串集B=1,2,，则乘积，则乘积AB=|Aand B在在A中任取一个符号串与中任取一个符号串与B中任一符号串连接中任一符号串连接例如：例如：A=ab,bc;B=ac,cb则则AB=abac，abcb，bcac，bccb注：注：由于由于 x=x=x所以所以 A=A=A串集的自身乘积称作串集的方幂串集的自身乘积称作串集的方幂空集空集：不包含任何元素：不包含任何元素有有A=A=，但，但11符号串集合的幂符号串集合的幂例如：串集例如：串集A的各次方幂定义为：的各次方幂定义为：A0=A1=AA2=AAAn=AAn-1（=An-1A）(n0)为符号串集合为符号串集合A的自的自身乘积身乘积若若A=ab,bc，则有，则有A0=A1=ab,bcA2=abab,abbc,bcab,bcbc12集合的闭包与正闭包集合的闭包与正闭包正闭包：正闭包：A+=A1A2An，不包含空串，不包含空串 闭包闭包：A*=A0A1A2An可证明：可证明：A*=A0A+A+=AA*=A*A若若A=a,b，则有，则有A*=,a,b,aa,ab,ba,bb,aaa,A+=a,b,aa,ab,ba,bb,aaa,推论：推论：若若A是字母表，则是字母表，则A*包含空串包含空串 和由和由A中符中符号构成的所有可能的符号串号构成的所有可能的符号串132.2文法和语言文法和语言语言的语言的有穷表示有穷表示生成方式（文法）生成方式（文法）识别方式（自动机）识别方式（自动机）类似自然语言由句子构成，句子要符合一定类似自然语言由句子构成，句子要符合一定的规则，称为的规则，称为“文法文法”语言是无穷的，规则确是有限的语言是无穷的，规则确是有限的如何用有限的文法规则推导出无限的句子，如何用有限的文法规则推导出无限的句子，即即“语言的有穷表示语言的有穷表示”14一、文法的概念一、文法的概念文法文法构造句子的规则，用于产生或推导句子构造句子的规则，用于产生或推导句子规则，二元组规则，二元组形如：形如：U:=u或或Uu，即，即“符号符号:=符号串符号串”的形的形式式含义：含义：U定义为定义为u，或者，或者U由由u组成组成规则又叫产生式：规则又叫产生式：U产生出产生出u15例如：自然语言中有下面的句子例如：自然语言中有下面的句子Youngmenlikepopmusic.其语法规则如下：其语法规则如下：句子由主语和谓语构成句子由主语和谓语构成Young|pop：形容词可以是形容词可以是young或或者者popmen|musiclike语法成分或语法类语法成分或语法类单词符号或单词单词符号或单词引引例例16形式化定义形式化定义文法写成文法写成GZ的形式的形式Z为开始符号或识别符号，至少要出现一次在某为开始符号或识别符号，至少要出现一次在某一条规则的左部一条规则的左部规则中出现的所有符号构成字汇表，记为规则中出现的所有符号构成字汇表，记为V该文法中的字汇表该文法中的字汇表V=0,1,9,如文法如文法G中有下列规则：中有下列规则：:=:=:=:=0:=1:=9开始符号为：开始符号为：17规则的组成元素规则的组成元素推论：推论：V=VnVtVnVt=句子是由终结符组成的句子是由终结符组成的符号符号:=符号串符号串“非终结符非终结符”用大写字母书写用大写字母书写其集合记为其集合记为Vn终结符：字汇表终结符：字汇表V中除了中除了Vn以外的其他符号以外的其他符号其集合记为其集合记为Vt由字汇表由字汇表V中的元素组成中的元素组成G中中Vn=,Vt=0,1,918BNF表示法表示法用用“|”表示表示“或或”，用以合并左部相同的规，用以合并左部相同的规则则规则的左部只有单个非终结符规则的左部只有单个非终结符如如G:=:=:=:=0:=1:=9:=|:=0|1|2|919Chomsky对文法的定义对文法的定义文法是四元文法是四元组G=Vn,Vt,P,SVn：非空有：非空有穷的的非非终结符号符号集合集合,即即规则左部符号的集合左部符号的集合Vt：非空有：非空有穷终结符号符号集合；集合；且且VnVt；字；字汇表表V=VnVtS属于属于Vn，称，称为开始符号开始符号或或识别符号。符号。P是一个是一个产生式生式(规则)的的非空有非空有穷集合，每个集合，每个产生式的形生式的形式是式是(或或:=)，其中，其中V+，V*。开始符号开始符号S至少必至少必须在某个在某个产生式的左部出生式的左部出现一次一次如有文法如有文法G=Vn,Vt,P,S其中：其中：Vn=N,DVt=0,1,2,9P=N:=D|ND,D:=0|1|2|9此文法将产生所有的无符号整数此文法将产生所有的无符号整数20二、推导的定义二、推导的定义推导与归约，互为逆过程推导与归约，互为逆过程推导：使用产生式的右部取代左部的过程推导：使用产生式的右部取代左部的过程用于：从开始符号生成符号串的一步步推导过程用于：从开始符号生成符号串的一步步推导过程归约：将左部取代右部的过程归约：将左部取代右部的过程用于：由符号串反过来归约到开始符号的过程用于：由符号串反过来归约到开始符号的过程推导的分类推导的分类直接推导直接推导推导推导广义推导广义推导最左推导最左推导最右推导最右推导(规范推导规范推导)21vw即xuyxUy直接推导与直接归约直接推导与直接归约定义：定义：对于文法对于文法G，字汇表，字汇表V，x，yV*，有规则，有规则U:=u，若，若v=xUy，w=xuy则称则称v直接推导出直接推导出w，记为，记为或或w直接归约到直接归约到v，记为，记为直接推导就是在推导过程中每次只用一个规则直接推导就是在推导过程中每次只用一个规则来进行替换来进行替换即xUyxuywv22直接推导举例直接推导举例EE+TT+TF+T_E:=T例：设有文法例：设有文法GE要从开始符号要从开始符号E推导出符号串推导出符号串F+T，则经过下面步骤：则经过下面步骤：E:=E+T|TT:=T*F|FF:=(E)|i23定义：对文法定义：对文法G，其中存在一直接推导序列，其中存在一直接推导序列即即v经过经过n次直接推导得到次直接推导得到w，n1有多少个有多少个，则推导长度为多长则推导长度为多长v=u0u1u2.un=w(n0)称v推导出wvw或称w归约到vwv推推导导长长度度若v=w则vwwv称为广义推导，称为广义推导，n 0推导与归约推导与归约24EE+T_T+T_F+T_i+T_i+T*F_i+F*F_i+i*F_i+i*i从从开始符号开始符号E进行进行推导推导ETT*F_F*F_i*Fi*(E)i*(E+T)_i*(T+T)_i*(F+T)_i*(i+T)i*(i+F)i*(i+i)n=8n=11例：设有文法例：设有文法GE对对i+i*i和和i*(i+i)进行推导进行推导E:=E+T|TT:=T*F|FF:=(E)|i25对于文法对于文法G，现讨论推导出，现讨论推导出25的过程是的过程是否唯一否唯一规范推导：先替换最右边的每个非终结符的过程，规范推导：先替换最右边的每个非终结符的过程，(替换最左边)2 25(替换最右边)5 525规范推导，最右推导规范推导，最右推导G文法的文法的BNF表示：表示：|0|1|9规范推导规范推导记为：记为：xUyxuy25如上例26课堂练习课堂练习：文法为文法为E:=E+T|TT:=T*F|FF:=(E)|i给出句子给出句子i+i*i的最左推导和最右推导的过程。的最左推导和最右推导的过程。最左推导过程：最左推导过程：EFiiFi F Fi i Fi i i最右推导过程：最右推导过程：EFiF ii ii iF i ii i i27句型、句子、语言句型、句子、语言设设GZ是字汇表是字汇表V上的一个文法上的一个文法则称x是G的一个句型句型，x是由是由Z推导出来的符号串推导出来的符号串Zx，xV*文法GZ产生的所有句子的集合称为文法GZ所定义的语言语言L(GZ)如果Z x，xVt*，即仅含有终结符的句型是一个句子句子+文法和语言文法和语言28例：考虑一个文法例：考虑一个文法G(0,1,S,S,P)，其中其中P=S:=0S1|01最后语言为最后语言为L(GS)=0n1n n129例例1：文法文法GZZ:=aZb abZaZbaaZbban-1Zbn-1an-1abbn-1=anbn可以确定语言可以确定语言L(GZ)=anbn n1文法文法Vs语言语言给定一个文法，能从结构上唯一地确定其语言给定一个文法，能从结构上唯一地确定其语言30例例2：L(GS)=aibjakcjbi i0，j1，k1给出文法给出文法GSS:=aSb PP:=bPc bQcQ:=Qa a生成的语言。生成的语言。S推出的符号串的形式是推出的符号串的形式是aiPbi（i0），而），而P推推出的符号串的形式是出的符号串的形式是bjQcj（j1），），Q推出的符推出的符号串的形式是号串的形式是ak（k1）。）。31给定一种语言，能确定其文法，但这种文法不唯一给定一种语言，能确定其文法，但这种文法不唯一例：L(GZ)=abnan1aba abba abbba .文法文法G1ZZ:=aBaB:=b Bb文法文法G2ZZ:=aBB:=ba bB文法文法G3ZZ:=BaB:=ab Bb等价文法：产生相同语言的文法等价文法：产生相同语言的文法L(G1Z)=L(G2Z)32例例1:写一个文法写一个文法,使其语言是奇数集使其语言是奇数集,且每个奇数不以且每个奇数不以0开头开头D1 3 5 7 9D2 4 6 8 DD0 DAAD DNAD DGN33例例2:写一个文法写一个文法,使其语言使其语言L(G)=anbman|n,m0考查形式抽象能力。应当仔细研究语言的结构特考查形式抽象能力。应当仔细研究语言的结构特点，通常是这些语言具有形式上的对称性和字符点，通常是这些语言具有形式上的对称性和字符数目上的相关性等特点。数目上的相关性等特点。S:=aSa BB:=bB GS34直接递归规则：直接递归规则：某规则的左、右部具有相同的非终结符号某规则的左、右部具有相同的非终结符号例：例：U:=xUy为直接递归规则，简称递归规则为直接递归规则，简称递归规则若若x=，U:=Uy左递归规则左递归规则若若y=，U:=xU右递归规则右递归规则若若x、y，U:=xUy自嵌入规则自嵌入规则递归规则与递归文法递归规则与递归文法35直接递归文法直接递归文法至少含有一条递归规则的文法至少含有一条递归规则的文法文法中使用递归规则后，可以用有限的规则定义无限语言文法中使用递归规则后，可以用有限的规则定义无限语言但不利是对于具有左递归性的文法，不能采用自顶向下的分析算法但不利是对于具有左递归性的文法，不能采用自顶向下的分析算法文法文法GZZ:=aBaB:=b Bb间接递归文法间接递归文法如如U:=VxV:=Uy|z，因，因UVxUyx，是间接递归文法，是间接递归文法UxUy称称U为间接递归为间接递归UUy称称U为间接左递归为间接左递归UxU称称U为间接右递归为间接右递归36定义：设有文法GZ，w=xuy是其一个句型若有ZxUy且Uu则则u是句型是句型w=xuy相对于相对于U的的短语短语若有ZxUy 且Uu则则u是句型是句型w=xuy相对于相对于U的的简单短语或直接短语简单短语或直接短语短语、简单短语、句柄短语、简单短语、句柄短语与简单短语短语与简单短语即即U可以推导出可以推导出u即即U可以直接推导出可以直接推导出u37理解定义理解定义UuxUyxuyZxUyxuy短语须满足两个条件：短语须满足两个条件：A、可以归约B、原句型归约后仍为一个句型简单短语须满足两个条件：简单短语须满足两个条件：A、可以直接归约B、原句型归约后仍为一个句型句柄句柄句型的最左简单短语为该句型的句型的最左简单短语为该句型的句柄句柄Uu短语短语u是句型是句型w中的子串：中的子串：可以由可以由u归约到归约到U，而，而w也可以归约到一个句型也可以归约到一个句型38用定义求用定义求T+i的所有短语、简单短语和句柄的所有短语、简单短语和句柄写出由写出由E到到T+i的所有推导过程，由此求得的所有推导过程，由此求得句型句型T+i的所有可能的子串的所有可能的子串u有三种情况：有三种情况：u=T+i，u=i，u=T每个每个u分别试探出归约到的分别试探出归约到的UEET+iT+i为句型T+i相对于E的短语ET+TT+ii为句型T+i相对于T的短语ET+FT+ii为句型T+i相对于F的短语，且为简单短语T为句型T+i相对于E的短语，且为简单短语，句柄T+iEE+i例：设有文法设有文法GE E:=E+T|TT:=T*F|FF:=(E)|iF:=iE:=TwuUTi+392.3 语法树和二义性一、语法树和推导一、语法树和推导1 1、语法树、语法树定义：定义：、树根是文法的开始符号、树根是文法的开始符号、每个结点都是文法的终结符或非终结符、每个结点都是文法的终结符或非终结符、非终结符结点一定有子结点、非终结符结点一定有子结点、若结点、若结点A有有n个分枝结点为个分枝结点为B1B2Bn，则有则有A:=B1B2Bn为为G的一个规则的一个规则40设有文法设有文法GS:SaBAaBbdSaABabd则下面两棵树都是则下面两棵树都是G的语法树：的语法树：S:=aABA:=Ba|aB:=bd412、语法树的生成反映了一次推导过程、语法树的生成反映了一次推导过程例:文法文法GNN:=ND DD:=0 1 2 9句子25的推导过程和语法树NN DD25NN D5D2最左推导NNDDD2D25最右推导NNDN5D525推导过程不同，语法树的生长过程也不同，但最终生成的语法树完全相同推导过程不同，语法树的生长过程也不同，但最终生成的语法树完全相同423、子树与短语子树与短语子树子树语法树的某一结点连同它向下射出的部分语法树的某一结点连同它向下射出的部分组成了语法树的子树。组成了语法树的子树。简单子树简单子树只含有单层分枝的子树称为简单子树。只含有单层分枝的子树称为简单子树。NNDD52ND2D2D5NND43子树与短语的关系子树与短语的关系子树子树末端结点组成的末端结点组成的符号串符号串是相对于子树是相对于子树根根的的短语短语简单子树简单子树末端结点组成的末端结点组成的符号串符号串是相对于简单是相对于简单子树子树根根的的简单短语简单短语最左简单子树最左简单子树末端结点组成的末端结点组成的符号串符号串是是句柄句柄利用生成树方便求得短语、简单短语和句柄利用生成树方便求得短语、简单短语和句柄先从开始符推导出句型先从开始符推导出句型w，由此写出生成树，由此写出生成树44+EETTFi短语：短语：T+i为语法树的根为语法树的根E的短语的短语T为为E的短语，且为简单短语的短语，且为简单短语i为为T的短语的短语i为为F的短语，且为简单短语的短语，且为简单短语句柄：句柄：T最左的简单子树的末端结点最左的简单子树的末端结点求求T+i的所有短语、简单短语和句柄的所有短语、简单短语和句柄例：例：设有文法设有文法GE E:=E+T|TT:=T*F|FF:=(E)|i步骤：从步骤：从根开始，每棵子树的根作为根开始，每棵子树的根作为U，该子树的末端结，该子树的末端结点连接成的符号串即为点连接成的符号串即为u，u是相对于是相对于U的短语或简单短语的短语或简单短语45EE-TT*FFi短语：短语：E-F*iF*iFi简单短语：简单短语：Fi句柄：句柄：F求求E-F*i的所有短语、简单短语和句柄的所有短语、简单短语和句柄例：设有文法设有文法GE E:=E+T|TT:=T*F|FF:=(E)|i46设有文法设有文法GA求求#C+C*a#的所有短语、简单短语和句柄的所有短语、简单短语和句柄A#B#B+CCC*a短语：短语：#C+C*a#C+C*aCC*a简单短语：简单短语：CC*a句柄：句柄：CA:=#B#B:=B+C|CC:=C*a|a47已知语法树得到推导已知语法树得到推导对已知的语法树，自底向上可以得到句型的归对已知的语法树，自底向上可以得到句型的归约过程，进一步可以得到推导过程约过程，进一步可以得到推导过程步骤：从左到右、由下而上修剪子树末端结点步骤：从左到右、由下而上修剪子树末端结点即从最左边的子树开始依次修剪末端结点即从最左边的子树开始依次修剪末端结点NNDD52如左图中句子如左图中句子25的归约过程为的归约过程为25D5N5NDN(最左归约、规范归约最左归约、规范归约)反过来即推导过程反过来即推导过程NNDN5D525rrrr48例：例：ifBthenifBthenSelseS理解一理解一ifBthenifBthenSelseS理解二理解二ifBthenifBthenSelseS二、文法的二义性49设有文法设有文法GE句子句子i+i*i的按不同推导得到的两棵语法树的按不同推导得到的两棵语法树EE+EiE*EiiEE*EiE+Eii不同E:=E+E E*E (E)i二、文法的二义性最右推导最右推导(先乘先乘)EE+EE+E*Ei+i*i+最左推导最左推导(先加先加)EE*EE+E*Ei+i*i+50SifB thenSifBthen S else SSifBthenSelse SifBthen S二义性文法的定义二义性文法的定义定义：一个文法的某个句子存在两棵不同的语定义：一个文法的某个句子存在两棵不同的语法树，则称该文法是二义性文法。法树，则称该文法是二义性文法。文法文法GS：S:=ifBthenS ifBthenSelseS A句型句型ifBthenifBthenSelseS的语法树的语法树51注意注意文法的二义性和语言的二义性是两个不同的文法的二义性和语言的二义性是两个不同的概念概念对于一个程序语言来说，通常希望它的文法对于一个程序语言来说，通常希望它的文法是无二义的是无二义的可能有两个不同的文法可能有两个不同的文法G和和G，其中一个是二义，其中一个是二义的而另一个是无二义的，但是却有的而另一个是无二义的，但是却有L(G)=L(G)，即这两个文法所产生的语言是相同的。即这两个文法所产生的语言是相同的。二义性问题是不可判定的，即不存在一个算二义性问题是不可判定的，即不存在一个算法，它能在有限步骤内，确切的判定一个文法，它能在有限步骤内，确切的判定一个文法是否为二义的。法是否为二义的。52二义性的解决办法二义性的解决办法修改编译算法修改编译算法此时此时i+i*i只有最右推导，先乘后加只有最右推导，先乘后加GE规定：规定：*/的优先级大于的优先级大于+-，优先级高的先归约，优先级高的先归约优先级相同的，先左后右进行归约优先级相同的，先左后右进行归约GS规定：规定：else与最近的未匹配的与最近的未匹配的then相匹配相匹配句型句型ifBthenifBthenSelseS的语法树也只有一棵的语法树也只有一棵通常不说语言本身的二义性，句子或句型的不确定通常不说语言本身的二义性，句子或句型的不确定性是由文法的二义性带来的。我们不可以改变句子的性是由文法的二义性带来的。我们不可以改变句子的集合，但能改变其二义性文法。集合，但能改变其二义性文法。53尽量避免规则左部的符号在规则右部同时出现尽量避免规则左部的符号在规则右部同时出现两次或两次以上。两次或两次以上。修改文法修改文法修改后为修改后为文法文法GEE:=E+E E*E (E)i如文法如文法GEE:=E+T|E-T|TT:=T*F|T/F|FF:=(E)|i某规则的左部在右部出现一次也可能导致二义性某规则的左部在右部出现一次也可能导致二义性542.4 2.4 文法的实用限制文法的实用限制一、文法的实用限制一、文法的实用限制1、有害规则、有害规则形如形如U:=U的规则为有害规则的规则为有害规则如如GNN:=NN:=ND DD:=0 1 9则句子则句子25的多种语法树的多种语法树552、多余规则、多余规则则称则称U为活的非终结符号，一定会出现在句型中为活的非终结符号，一定会出现在句型中ZxUyUVn，x,yVt*活的非终结符号：活的非终结符号：可推出符号：可推出符号：在某句型中出现的符号称为可推出符号，其中在某句型中出现的符号称为可推出符号，其中包含非终结符和终结符包含非终结符和终结符活的非终结符号亦为可推出符号活的非终结符号亦为可推出符号56例：文法例：文法GSS:=aAB aA:=aAb bB:=dC:=aBfSSaABaaAbBaaAbd可推出符号集：可推出符号集：SaA Bbd活的非终结符号集：活的非终结符号集：S A B57多余规则多余规则某规则的左部符号某规则的左部符号U，若不满足下列条件，则，若不满足下列条件，则该规则为多余规则。该规则为多余规则。U为可推出符号（活的非终结符号）为可推出符号（活的非终结符号）必须能从必须能从U推出句子（终结符号串）推出句子（终结符号串）所谓多余规则是指：所谓多余规则是指：在推导文法的所有句子时，始终用不到的规则在推导文法的所有句子时，始终用不到的规则在推导过程中，一旦用了此规则，则无法推出句在推导过程中，一旦用了此规则，则无法推出句子来子来58例：文法例：文法GZZ:=BeA:=Ae eB:=Ce AfC:=CfD:=fD为不可推出符号为不可推出符号D:=f为多余规则为多余规则不能从不能从C推出句子推出句子C:=Cf为多余规则为多余规则不能从不能从B:=Ce推出句子推出句子 B:=Ce为多余规则为多余规则ZBeAfeefeZBeCeeCfe可推出符号集：可推出符号集：ZBACef59多余规则的危害多余规则的危害在程序设计语言的文法中如果包含有多余规则在程序设计语言的文法中如果包含有多余规则,其中必定有错误存在：其中必定有错误存在：文法文法GZZ:=AbA:=fB:=f在归约时，碰到在归约时，碰到f，若使用，若使用B:=f，则无法，则无法分析下去，就会出错分析下去，就会出错603 3 文法的实用限制文法的实用限制两点：两点：不能有多余规则不能有多余规则不能有有害规则不能有有害规则如果文法如果文法G中所有规则均满足实用限制条件，则中所有规则均满足实用限制条件，则称文法称文法G是压缩或化简过的是压缩或化简过的。61例：文法例：文法GZZ:=BeA:=Ae eB:=Ce AfC:=CfD:=f经过压缩化简后的文法经过压缩化简后的文法GZZ:=BeA:=Ae eB:=Af被删除的多余规则有被删除的多余规则有D:=fC:=CfB:=Ce621文法的开始符号不出现在规则的右部文法的开始符号不出现在规则的右部二、文法的变换二、文法的变换2每个非终结符号均能导出终结符号串每个非终结符号均能导出终结符号串3每个非终结符号都出现在任意句型中每个非终结符号都出现在任意句型中4没有特殊规则，形如没有特殊规则，形如A:=B，A,B Vn文法的六种假定：文法的六种假定：5没有空规则，形如没有空规则，形如A:=6没有直接左递归规则，形如没有直接左递归规则，形如A:=Ay等价变换等价变换631文法的开始符号不出现在规则的右部文法的开始符号不出现在规则的右部引进符号引进符号S，在文法中拓充一条规则，在文法中拓充一条规则SS,以以S为开始符，变为开始符，变GS为为GS例例G1NNND DD0 1 9NN变为变为G2N称称G2为为G1的的拓广文法拓广文法六种文法变换技术六种文法变换技术64即找到推不出句子的非终结符，并删除多余规则即找到推不出句子的非终结符，并删除多余规则算法：算法：(1)(1)构造非终结符号集构造非终结符号集I首先令首先令=A AtG1,tVt+，找到右部只有终结，找到右部只有终结符的规则，将其左部非终结符归入符的规则，将其左部非终结符归入II递归扩充递归扩充=W|WxG1,x(Vt)+，找到右部由终结，找到右部由终结符和原符和原中非终结符组成符号串的规则，其左部归入中非终结符组成符号串的规则，其左部归入(2)从文法从文法G1中删除那些左部或右部含有不属于中删除那些左部或右部含有不属于中的符号的规则中的符号的规则2每个非终结符号均能导出终结符号串每个非终结符号均能导出终结符号串65例例文法文法G1SS:=aABS bDADdA:=bAB dsA dDDB:=bAB dSBD:=dS dI首先令首先令=D|D:=d=DII递归扩充递归扩充=DA|A:=dDD=A,D=A,DS|S:=bDADd=S,A,D等价文法等价文法G2SS:=bDADdA:=dsA dDDD:=ds d仅有仅有D:=d的右部全是终结符的右部全是终结符A:=dDD的右部由的右部由d和和D组成，组成，A入入S:=bDADd的右部由的右部由b、d和和A、D组成，组成，S入入663消除用不到的非终结符消除用不到的非终结符使每个非终结符都能出现在某一句型中使每个非终结符都能出现在某一句型中算法：算法：构造非终结符集合构造非终结符集合(所有活的非终结符所有活的非终结符)从开始符起，将开始符归入从开始符起，将开始符归入=S递归扩充递归扩充，找到由，找到由中非终结符直接推导出的规则中非终结符直接推导出的规则,将将其右部的非终结符归入其右部的非终结符归入，直到，直到中所有非终结符推出中所有非终结符推出的规则都扫描完毕的规则都扫描完毕删除左部不在删除左部不在中的非终结符的规则中的非终结符的规则删除的也是多余规则，结合方法删除的也是多余规则，结合方法2先删除推不先删除推不出句子的非终结符的规则，再用出句子的非终结符的规则，再用3最终最终=U|SxUy,U Vn,x,y V*67先利用先利用2,找出不能推导出句子的非终结符号，并删找出不能推导出句子的非终结符号，并删除相应的规则除相应的规则再利用再利用3,找出不在任意句型中出现的非终结符号找出不在任意句型中出现的非终结符号,并删并删除相应的规则：除相应的规则：从从S开始，开始，=S，考查，考查G2中所有规则，中所有规则，没有变化，所以左部为没有变化，所以左部为D的规则是多余规则。的规则是多余规则。故得等价文法故得等价文法G3SS:=ad例：例：文法文法G1SS:=ad bAA:=dBDB:=asAD:=bD e=S,D，由，由S:=ad，D:=e得到，得到，A、B为推不出句子的非终结符为推不出句子的非终结符得等价文法得等价文法G2SS:=adD:=bD e68算法：算法：1构造非终结符号集构造非终结符号集4 4 没有特殊规则没有特殊规则A:=B，A,BVn对文法中的每一个非终结符号对文法中的每一个非终结符号A，求其，求其AA=B ABG1，BVn，即对每个，即对每个A求由求由其推导出的非终结符其推导出的非终结符B构成的集合构成的集合+2若有若有AB，并且文法中有，并且文法中有B:=x，则在文法，则在文法G2中增加规则中增加规则A:=x，删除，删除AB和无用规则和无用规则+69例：文法例：文法G1AA:=B dEB:=A D bD:=B dE:=Ea eAAdEAABDbdBAdEBBbBDdDAdEDBbDDdA=B=D=A,B,DE=，对，对A中由中由A推出的推出的每个非终结符的规则判断是每个非终结符的规则判断是否为特殊规则和无用规则否为特殊规则和无用规则等价文法等价文法G2AA:=b dE dB:=d dE bD:=dE d bE:=Ea eA:=B特殊规则，删除，增加特殊规则，删除，增加A:=b因因A:=B，删除，删除B:=D，增加，增加A:=dB:=A特殊规则，删除，增加特殊规则，删除，增加B:=dEB:=D特殊规则，删除，增加特殊规则，删除，增加B:=dD:=B特殊规则，删除，增加特殊规则，删除，增加D:=b因因D:=B特殊规则，增加特殊规则，增加D:=dEA:=dE保留保留B:=b保留保留D:=d保留保留70例例G1AA:=aBbDB:=DDD:=b 删除删除D:=，=B,D对对B:=DD和和A:=aBbD进行扩充进行扩充与与G1等价的文法等价的文法G2为为A:=ab abD aBb aBbDB:=D DDD:=b5没有空规则没有空规则算法：算法：构造非终结符构造非终结符所有空规则的左部归入所有空规则的左部归入递归扩充递归扩充：由：由中符号构成的符号串能归约到的非终中符号构成的符号串能归约到的非终结符归入结符归入删除空规则和只能导出空串的非终结符删除空规则和只能导出空串的非终结符扩充新规则扩充新规则对形如对形如A:=xByD，B,D，x,y(V-)*增加下列规则增加下列规则A:=xy|xyD|xBy|xByD71解：解：=D|D:=DB|B:=DD=B,D删除空规则删除空规则D:=后后A:=aBbDB:=DDD:=b对对A:=aBbD和和B:=DD进行扩充进行扩充新规则新规则A:=ab abD aBbB:=D例例G1AA:=aBbDB:=DDD:=b 与与G1等价的文法等价的文法G2为为A:=ab abD aBb aBbDB:=D DDD:=b726 6 消除左递归规则消除左递归规则若文法中有规则若文法中有规则A:=Ay x(x不以不以A开头开头)可用可用A:=xAA:=yA 来代替来代替这两种形式是等价的这两种形式是等价的一般而言一般而言AAy1 Ay2 Ayn x1 x2 xn消除其左递归消除其左递归Ax1Ax2AxnAAy1Ay2AynA 73例：例：文法文法G1EE:=E+T ET TT:=T*F T/F FF:=(E)i消除左递归后的等价文法消除左递归后的等价文法G2EE:=TEE:=+TE|TE T:=FTT:=*FT/FT F:=(E)i742.5 2.5 扩充的扩充的BNFBNF表示法表示法在在BNF表示法中引进表示法中引进6个专用符号个专用符号，(，)(1)花花括号括号t表示表示t可重复多次可重复多次如：如：N:=ND|DD:=0|1|9利用花括号，文法表示为利用花括号，文法表示为N:=DDD:=0|1|975（2）方括号）方括号t表示表示t可有可无（即可以出现可有可无（即可以出现0次次或或1次）次）如：如：E:=T|T+ET:=F|F*TF:=i|（E）利用方括号，文法表示为利用方括号，文法表示为E:=T+ET:=F*TF:=i|（E）76（3）园括号）园括号()()表示提因子表示提因子“提取公因子提取公因子”A:=ax ay awA:=a(x y w)扩充的扩充的BNF表示法的用途表示法的用途如：如：E:=T|E+TT:=F|T*FF:=i|（E）E:=T+TT:=F*FF:=i|（E）扩充的扩充的BNF表示法的最大用途就是消除了文法的左递表示法的最大用途就是消除了文法的左递归，从而使文法在自顶向下的分析方法中能够进行分归，从而使文法在自顶向下的分析方法中能够进行分析处理析处理772.6文法和语言分类文法和语言分类Chomsky对文法的定义对文法的定义从形式上说文法从形式上说文法G是一个四元式是一个四元式(VN,VT,P,S)Chomsky对文法的分类对文法的分类根据对产生式施加的限制，可分为根据对产生式施加的限制，可分为0型文法型文法1型文法型文法2型文法型文法3型文法型文法四种类型的文法分别对应着四种类型的语言四种类型的文法分别对应着四种类型的语言780型文法型文法0型文法型文法(短语文法或无限制文法短语文法或无限制文法)：文法：文法G中中的每个规则若为的每个规则若为:=，V+,V*非空，非空，可为空，可为空，,是用字汇表中任意符号构是用字汇表中任意符号构成的符号串成的符号串0型文法确定的语言为型文法确定的语言为0型语言型语言L0注：注：识别识别0型语言的自动机称为图灵机型语言的自动机称为图灵机(TM).0型文法是对产生式限制最少的文法。型文法是对产生式限制最少的文法。任何任何0型语言都是递归可枚举的。型语言都是递归可枚举的。对对0型文法产生式的形式作某些限制，可得到其他型文法产生式的形式作某些限制，可得到其他类型文法的定义。类型