东南大学编译原理.ppt

2语言与文法,翟玉庆周晓宇,字母表和符号,字母表：符号的非空有穷集合符号:语言中不可再分的单位字母表：，V或其它大写字母V1=a,b,cV2=+,-,0,1,9=x|xASCII字符,符号串（字符串）,某字母表上的符号的有穷序列a,b,c,abc,bc,：V1上的符号串1250,+2,-1835,：V2上的符号串空串（）：不含任何符号的串,语句,字母表上符合某种构成规则的符号串序列Heisagoodstudent.Peanuteatsmonkey.我们约定，用a,b,c,表示符号;用,表示符号串;用A,B,C,表示符号或符号串的集合,语言,某字母表上的句子的集合。,符号串集合的积,设A=1,2,，B=1,2,.，二者的笛卡尔积AB=A,B若A=a,b,B=c,e,d，那么AB=ac,ae,ad,bc,be,bd,字符串集合的幂,A0=，An=AAn-1=?若|A|=m，那么，|A0|=1，|A1|=m，|An|=mn,Kleene闭包和正闭包,Kleene闭包：A*=A0A1A2a,b*=?正闭包:A+=A1A2=A*-a,b+=?一个语言是其字母表上闭包的子集.,文法（grammar）,表达语言构成规则的形式化方法,自然语言文法示例,产生式,yongpopmenmusiclike,产生式文法的组成,非终结符（VN）终结符（VT）开始符号产生式,推导与规约,推导：使用产生式的右部取代左部的过程规约：推导的逆过程，用产生式的左部取代右部的过程,推导及规约的顺序,推导及规约的顺序,最左归约和最右归约称为规范归约。,句型、句子与语言,句型：从文法开始符号S开始，每步推导（包括0步推导）所得到的字符串S，其中(VNVT)*句子：仅含终结符的句型语言：由S推导所得的句子的集合L(G)=|S，且VT*，G为文法,文法规则的递归定义,非终结符的定义中包含了非终结符自身设=0,1|0|1使用递归定义时要谨慎，要有递归出口，否则，可能永远产生不出句子,扩充的BNF表示,()提因子Uax|ay|az改写为Ua(x|y|z)重复次数的指定|05任选符号+|-,元语言符号,用来说明文法符号之间关系的符号|,文法与语言的形式定义,Chomsky0型文法,G：四元组(VN,VT,P,S)0型文法（短语文法或无限制文法）P：，其中V+并至少含有一个非终结符,V*.是对产生式限制最少的文法；识别0型语言的自动机称为图灵机(TM)；对0型文法的产生式作某些限制，可以得到其他类型的文法。,Chomsky1型文法,长度增加文法（上下文有关文法）P：，除可能有S外均有|=|；若有S，规定S不得出现在产生式右部。或P中产生式，除可能有S外均有A，其中,V*，AVN，V+。,Chomsky1型文法（续）,1型文法对非终结符进行替换时必须考虑上下文。除文法开始符号外不允许将其它的非终结符替换成。识别1型语言的自动机称为线性界限自动机(LBA)。,Chomsky2型文法,P：A，其中AVN，V*。产生式左部一定是非终结符，产生式右部可以是VN、VT或。非终结符的替换不必考虑上下文，故也称作上下文无关文法。识别2型语言的自动机称为下推自动机(PDA)。,Chomsky3型文法,P中产生式具有形式AB，A，或者AB，A，其中A，BVN，VT*。也称为正规文法RG、线性文法：若所有产生式均是左线性，则称为左线性文法；若所有产生式均是右线性，则称为右线性文法。,Chomsky3型文法（续）,产生式要么均是右线性产生式，要么是左线性产生式，不能既有左线性产生式，又有右线性产生式。识别3型语言的自动机称为有限状态自动机。,由文法产生语言,例：设文法G1(S,a,b,P,S)，其中P为:(0)SaS(1)Sa(2)Sb,答：L(G1)=ai(a|b)|i=0,由文法产生语言,例：设文法G2(S,a,b,P,S)，其中P为:(0)SaSb(1)Sab,答：L(G2)=anbn|n=1,由语言构造文法,例：设L1=a2nbn|n=1且a,bVT，试构造生成L1的文法G1。解：n=1，L1=aabn=2，L1=aaaabbn=3，L1=aaaaaabbb得：SaaSbSaab,由语言构造文法-题型,构造形如amibni的语言的文法aibj,(i2j,j1),由语言构造文法（续）,例：设L2=aibjck|i,j,k=1且a,b,cVT试构造生成L2的文法G2。答：SaSSaBBbBBbCCcCCc,由语言构造文法（续）,sa,b*,a的数目为奇数，b的数目为偶数（电路图法）Sa,b*,以a开始，以b结尾，a的数目为奇数，b的数目为偶数sa,b,c*,a和c的数目为奇数，b的数目为偶数,由语言构造文法（续）,例：设L3=|(a,b)*且中含有相同个数的a和b试构造生成L3的文法G3。答：SSbBB(a,b)*,且B中b的数目比a的数目少1,由语言构造文法（续）,SaAA(a,b)*,且A中a的数目比b的数目少1AbS|b,AaAABaS|a,BbBB,由语言构造文法（续）,例：设L4=|(0,1)*且中1的个数为偶数试构造生成L4的文法G4答：SS0SS1AA0AA1S,文法的简化,由于同一语言可以用不同的文法来描述，显然应当选择产生式的个数最少，最符合语言特征的来描述。,文法简化的步骤,（1）删除形如PP的产生式（2）删除永不被使用的产生式，即由文法的开始符号无法推导出其左部。（3）删除不能从中导出终结符串的产生式。（4）整理产生式,文法简化示例,文法简化示例（续）,答：,构造无产生式的上下文无关文法,无产生式的上下文无关文法要满足条件若P中含S，则S不出现在任何产生式右部，其中S为文法的开始符号；P中不再含有其它任何产生式。,变换算法,G=(VN,VT,P,S)G=(VN,VT,P,S)（1）由文法G满足如下定义的非终结符集合。V0=A|AVN,A（V0怎么求？）（2）再按下述步骤构造G产生式集合P,构造P的步骤,（a）若产生式B0B11B2Bkk属于P，其中jV*(0jk)，BiV0，那么将这些Bi分别以和Bi本身这两种形式替代，然后将有关B的所有产生式扣除产生式后加入到P中。（b）其它产生式扣除产生式后（原来就有，或者由步骤a产生）也投入到P中。,构造P的步骤（续）,（C）如果P中有产生式S（原来就有，或者由步骤a产生），且S出现在产生式的右部，则将它扣除并增加如下产生式：S|S将S加入VN，文法开始符号变为S。,例题,设G1=(S,a,b,P,S),其中P:(0)S(1)SaSbS(2)SbSaS答案：(1)V0=S(2)P:SabS|aSbS|aSb|abSbaS|bSaS|bSa|baS|S(3)G1=(S,S,a,b,P,S),语法树,S,基本术语,子树：除叶子结点之外的任意结点连同它的所有子孙结点构成子树。修剪子树：剪去子树树根的所有子孙节点，对应于规约（一步或多步）。句型：由树的末端符（叶结点）从左至右连成的串是文法的一个句型。,基本术语（续）,短语：子树的末端符号自左到右连成串，相对于子树树根而言称为短语。简单短语(直接短语)：若短语是某子树根经过1步推导得到的，则称之为该子树根的简单短语。句型的短语：某句型中的短语（属于某子树）。,基本术语（续）,句柄：句型中的最左简单短语。是最左归约时要寻找的简单短语。例：语法树,文法的二义性,如果文法的一个句子存在对应的两棵或两棵以上的语法树，则该句子是二义的。包含二义性句子的文法是二义文法。,示例,例如：文法G=(E，+,*,(,),i，P，E)其中：EE+E|E*E|(E)|i对于句子（i*i+i)有几种最左推导（1）E(E)(E+E)(E*E+E)(I*E+E)(i*i+E)(i*I+i)（2）E(E)(E*E)(i*E)(i*E+E)(i*i+E)(i*i+i),示例（图示）,示例（等价的非二义文法）,ET|E+TTF|T*FF(E)|i,示例（非二义文法的语法树）,二义的IF语句文法,SifCthenSelseSSifCthenSS,一个IF语句对应的不同语法树,评论,二义性会给语法分析带来不确定性。文法的二义性是不可判定的，即不存在算法，能够在有限步数内确切判定一个文法是否为二义文法。若要证明是二义性，只要举出一例。可以采用BNF范式以外的手段消除语法的二义性。二义文法并非绝对必需去除的。,作业,2.2.1,2.2.2,2.2.4,