《形式语言的基本知识.ppt》由会员分享，可在线阅读，更多相关《形式语言的基本知识.ppt（84页珍藏版）》请在三一办公上搜索。
1、2023/11/13,第2章形式语言的基本知识,本章是编译原理课程的理论基础，要求掌握形式语言的基本术语和概念。掌握文法和语言的定义，文法的二义性与递归性的判断方法及句型的分析方法。熟练使用文法定义程序设计语言的单词和语法成分。对形式语言的理论有一个初步认识。,教学目标,2023/11/13,2.1 字母表和符号串的基本概念2.2 文法和语言的形式定义2.3 句型的分析2.4 文法和语言的分类2.5 PL/0编译程序概述,教学内容,2023/11/13,字母表：符号的非空有限集 例：=0，1,2.1字母表和符号串,符号：字母表中的元素 例：0，1符号串：由字母表中的符号组成的任何有穷序列 例：
2、0,1,01,10,011，.空符号串：无任何符号的符号串，用表示,C语言的字母表 Aa,b,0,1,9,+,_/,(,),=if,else,for.,不对如=if,else,for,while,符号就是字符，对吗？,2023/11/13,符号串的前缀和后缀:从符号串s的尾部删去若干个(包括0个)符号之后所余下的部分称为s的前缀,，0，01及011都是符号串011的前缀，1，11及011都是符号串011的后缀,符号串集合：若集合A中的一切元素都是某字母表上的符号串，则称A为该字母表上的符号串集合。例：=a，b，c A=a,aa,ac,2023/11/13,符号串的运算,符号串x和y的连接:是把
3、y的符号写在x的符号之后得到的符号串xy,例如x=00，y=11，则xy=0011对于任意一个符号串s，有s=s=s,符号串的连接运算,2023/11/13,符号串自身连接n次得到的符号串sn 定义为 ssss，包括n个s，称为符号串的幂运算,s0=，s1=s，s2=ss，设s=01，则s0=s1=01s2=0101,符号串的幂运算,2023/11/13,设A、B为符号串集合，则A和B的乘积定义为：AB xy|xA,yB,例如，Aa,b，B=c,d则AB=,符号串集合的乘积,ac,ad,bc,bd,2023/11/13,有符号串集合A，定义A0=,A1=A,A2=AA,A3=AAA,AnAn-
4、1A=AAn-1，n0,例如，A0,1，则A0=A1=A2=A3=,符号串集合的幂运算,0,100,01,10,11000,001,010,011,100,101,110,111,2023/11/13,设A是符号串集合，定义 A A1 A2 A3 An 称为集合A的正闭包。A*A0 A称为集合A的闭包。,例：A=x,y A？A*？,x,y,xx,xy,yx,yy,xxx,xxy,xyx,xyy,A1 A2 A3,x,y,xx,xy,yx,yy,xxx,xxy,xyx,xyy,A0 A1 A2 A3,符号串集合的闭包运算,2023/11/13,的闭包*表示上的一切符号串（包括）组成的集合的正闭包
5、+表示上的除外的所有符号串组成的集合,例：=a,b*=,a,b,aa,ab,ba,bb,aaa,aab,+=a,b,aa,ab,ba,bb,aaa,aab,2023/11/13,若A为某语言的字母表 Aa,b,0,1,9,+,_/,(,),=if,else,for.B为单词集 B=if,else,for,则B A*。语言的句子是定义在B上的符号串。若令C为句子集合，则C B*,程序 C,为什么对符号、符号串、符号串集合以及它们的运算感兴趣？,2023/11/13,语言是由句子组成的集合，是由一组符号所构成的集合字母表上的一个语言是上的一些符号串的集合字母表上的每个语言是*的一个子集,集合a,a
6、a,aaa,或表示为w|w*且w=an,n1 为字母表上的一个语言,例如：字母表=a,b,*=,a,b,aa,ab,ba,bb,aaa,aab,集合ab,aabb,aaabbb,anbn,或表示为w|w*且w=anbn,n1为字母表上的一个语言,2023/11/13,2.2文法和语言的形式定义,文法是对语言结构的定义与描述。（或称为“语法”）。,:=“=”:=“+”|“*”:=“(”“)”|,2023/11/13,y=x+r*6,2023/11/13,例：有一句子：“我是大学生”。这是一个在语法、语义上都正确定句子，该句子的结构（称为语法结构）是由它的语法决定的。在本例中它为“主谓结构”。,如
7、何定义句子的合法性？有穷语言：只需逐一列举句子无穷语言：使用文法定义句子的结构，用适当条数的规 则把语言的全部句子描述出来。文法是以有穷的集 合刻划无穷的集合的工具。,文法的非形式定义,2023/11/13,1.语法规则：我们通过建立一组规则，来描述句子的语法结构。规定用“:=”表示“由组成”。,:=:=|:=你|我|他:=王民|大学生|工人|英语:=:=是|学习:=|,文法的BNF表示,2023/11/13,2.由规则推导句子：有了一组规则之后，可以按照一定的方式用它们去推导或产生句子。推导方法：从一个要识别的符号开始推导，即用相应规则的右部来替代规则的左部，每次仅用一条规则去进行推导。,=
8、这种推导一直进行下去，直到所有带的符号都由终结符号替代为止。,2023/11/13,=,=,=我,=我,=我是,=我是,=我是大学生,:=:=|:=你|我|他:=王民|大学生|工人|英语:=:=是|学习:=|,推导方法：从一个要识别的符号开始推导，即用相应规则的右部来替代规则的左部，每次仅用一条规则去进行推导。,2023/11/13,例：有一英语句子：The big elephant ate the peanut.:=:=:=the:=big:=elephant:=:=ate:=:=peanut,2023/11/13,=,=,=the,=the big,=the big elephant,=t
9、he big elephant,=the big elephant ate,=the big elephant ate,=the big elephant ate the,=the big elephant ate the peanut,:=:=:=the:=big:=elephant|peanut:=:=ate:=,2023/11/13,说明：(1)有若干语法成分同时存在时，我们总是从最左的语法成 分进行推导，这称之为最左推导，类似的有最右推导（一般推 导）。(2)从一组规则可推出不同的句子，如以上规则还可推出“大象吃象”、“大花生吃象”、“大花生吃花生”等句子，它们 在语法上都正确，但在语
10、义上都不正确。,所谓文法是在形式上对句子结构的定义与描述，而未涉及语义问题。,2023/11/13,文法GS=（VN，VT，P，S）VN：非终结符号集 VT：终结符号集 P：产生式或规则的集合 S：开始符号（识别符号）S VN，S至少要在 一条规则中作为左部出现,VVN VT称为文法的字母表,补:规则的定义:或V+且至少有一个非终结符，而(VN VT)*,文法的形式定义,2023/11/13,G=(VT,VN,S,P)，其中:VN=表达式VT=+,*,(,),iS=表达式P=表达式表达式+表达式 表达式表达式*表达式 表达式(表达式)表达式i,【例2.1】程序语言中只含+、*运算的算术表达式，
11、用i表示变量或常数，其文法可以表示为：,描述了表达式的语法规则,2023/11/13,几点说明：,产生式左边符号构成集合VN，且 S VN,VN：代表程序的语法成份，如“表达式”，它不会 出现在程序中VT：会出现在程序中，如i+i,2023/11/13,有些产生式具有相同的左部，可以和在一起,GE：EE+E|E*E|(E)|i,2023/11/13,GS：SL|SL|SDLa|b|zD0|1|9,【例2.2】某种语言的标识符是以字母开头的字母数字串，如果用L表示，D表示，用S表示字母数字串,描述了标识符的词法规则,2023/11/13,例：无符号整数的文法：G|0|1|2|3|9,描述了无符号
12、整数的词法规则,2023/11/13,说明：,终结符集是输入字符集，它是构成单词的最基本元素,终结符集是经词法分析识别后的单词集，如变量i,运算符+、*和分界符(、)，它们被视为语法分析中最基本元素,描述词法规则的文法,GS：SL|SL|SDLa|b|zD0|1|9,2023/11/13,文法的表示方法,3.语法图,2.EBNF：扩充的BNF的元符号：,:=,|,(,),1.BNF的元符号：,:=,|,2023/11/13,推导的形式定义,如果是文法G=(VT，VN，S，P)的一个产生式，V*，有符号串x，y满足x=，y=,则称y是x的直接推导，也可以说，y直接归约到x，记作x y。,直接推导
13、：用产生式的右部替换产生式的左部直接归约：用产生式的左部替换产生式的右部的过程,2023/11/13,S=SD,使用规则SSD，其中=；SD=LD,使用规则SL，其中=,=D；LD=aD,使用规则La，其中=,=D；aD=a1,使用规则D1，其中=a,=。,GS：SL|SL|SDLa|b|zD0|1|9,根据文法和推导的定义，可推出终结符号串,2023/11/13,当符号串已没有非终结符号时，推导就必须终止。因为终结符不可能出现在规则左部，所以将在规则左部出现的符号称为非终结符号。,例如：G(1)(2)(3)(4)0|1|2|3|9,2023/11/13,如果存在直接推导序列：x y0 y1
14、y2yn=y则称这个序列是一个从x至y的长度为n（n0）的推导，或称y归约到x，记作x y。若有x y，或x=y，则记作x y。,=,=,*=,2023/11/13,文法GS（1）句型：x是句型 S,且 V*；（2）句子：x是句子 S,且,VT*；（3）语言：L（GS）=|VT*,S；,+,+,文法GS所产生的所有句子的集合,*,句子是所有终结符号组成的句型,语言的形式定义,GE：EE+E|E*E|(E)|i,句型：E+EE+E*EE+E*iE+i*i,句子：i+ii*ii+i*i(i+i)*i,2023/11/13,形式语言理论可以证明以下两点：（1）G L（G）；（2）L(G)G1，G2，
15、Gn；已知文法，求语言，通过推导；已知语言，构造文法，无形式化方法，更多是凭经验,2023/11/13,例：GS S:=aSb|ab求其所产生的语言。,若S:=aSb|，如何？,已知文法，求语言，通过推导,课堂练习1：GS S:=bA A:=aA|a,课堂练习2：GS S:=AB A:=aA|a B:=bB|b,2023/11/13,例：abna|n1,构造其文法,定义.G和G是两个不同的文法，若 L(G)=L(G),则G和G为等价文法。,若n0，如何？,课堂练习3：anbnci|n1,i 0,构造其文法,GS：S AB A aAb|ab BcB|,G1S：SaBa,Bb|bBG2S：SaBa
16、,Bb|Bb,G1S：SaBa,B|bBG2S：SaBa,B|Bb,2023/11/13,例：构造一个文法，使其描述的语言是无符号整数。,GS：SSD|DD0|1|2|3|4|5|6|7|8|9,G|0|1|2|3|9,2023/11/13,编译感兴趣的问题是:,给定x,G,求x L(G)?,x,算法1,算法2,x L(G)?,G,y,n,出错处理,停机,=,2023/11/13,1.递归规则：规则右部有与左部相同的符号 左递归规则：AA 右递归规则：AA 自嵌入递归规则：AA,递归文法,2.递归文法：含有递归规则的文法，为直接递归文法,ABaBAb,2023/11/13,递归文法的优点：可用
17、有穷条规则，定义无穷语言,例：对于前面给出的无符号整数的文法是有递归文法，用12条规则就可以定义出所有的无符号整数。若不用递归文法，那将要用多少条规则呢？,!,GS：SSD|DD0|1|2|3|4|5|6|7|8|9,2023/11/13,左递归文法的缺点：不能用自顶向下的方法来进行语法分析,会造成死循环（后面将详细论述）,GE：Ei+i|i*i|(i+i)*i,该文法所描述的语言为L(G)=i+i,i*i,(i+i)*i，无法表示无穷的表达式语言,2023/11/13,2.3句型的分析,句型的分析：是指识别输入的符号串是否为某一文法的 句型(或句子)的过程,对于同一个句型或句子，可以通过不同
18、的推导序列推导出来，这是因为在推导过程中所选择的非终结符的次序不同,GE：EE+E|E*E|(E)|ii+i*i的推导序列有哪些？,2023/11/13,最左(右)推导指对于一个推导序列中的每一直接推导，被替换的总是当前符号串中的最左(右)非终结符号。最右推导也称为规范推导。,规范推导的逆过程，称为最左归约，也称为规范归约。,用最左推导所推导出的句型称为最左句型用最右推导所推导出的句型称为最右句型，通常称为规范句型,规范推导与规范归约,2023/11/13,语法分析的结果-语法树,语法树与文法的二义性,2023/11/13,1.语法树：描述一个句子的语法结构,语法成分（非终结符）,单词符号（终
19、结符号),2023/11/13,语法树：句子结构的图示表示法，它是一种有向图，由结点和有向边组成。,结点：符号 根结点：识别符号 中间结点：非终结符 叶结点：终结符或非终结符,有向边：表示结点间的派生关系,2023/11/13,句型推导过程句型语法树的生长过程,2023/11/13,例：G句型10,规范推导,2023/11/13,2023/11/13,10,规范规约与规范推导互为逆过程,2023/11/13,课堂练习：对于句子ii*i，给出两种不同的规范推导，并画出语法树,定义:若一个文法的某句子存在两个不同的最右(最左)推导，则该文法是二义性的，否则是无二义性的。,2.文法的二义性,GE：E
20、E+E|E*E|(E)|i,2023/11/13,这两种不同的推导对应了两种不同的语法树,2023/11/13,若文法是二义性的，则在编译时就会产生不确定性文法的二义性是不可判定的，即不可能构造出一个算法，通过有限步骤来判定任一文法是否有二义性。,可以采用两种途径来解决文法的二义性问题,2023/11/13,例:算术表达式的文法,GE：EE+E|E*E|(E)|i,2023/11/13,2.4文法和语言的分类,形式语言(乔姆斯基)：通过抽象，对语言进行形式化描述用一组数学符号和规则来描述的语言称为形式语言*的任何子集称作上的形式语言,文法和语言分类：0型、1型、2型、3型 这几类文法的差别在于
21、对产生式施加不同的限制。,2023/11/13,0型语言：L0,0型文法称为无约束短语结构文法。规则的左部和右部都可以是符号串，一个短语可以产生另一个短语。,0型：P：:=其中V*且至少含有一个非终结符，V*,2023/11/13,0型文法GS:SABS|ABABBAA0B1,L(GS)=x|x是由n个01或10组成的二进制数字串，n1,2023/11/13,SACaBCaaaCCBDBaBBaCBE aDDaADACaEEaAE,例：0型文法GS：,2023/11/13,1型文法：P：A:=其中 AVN，V*，V,1型语言：L1,称为上下文敏感或上下文有关。也即只有在、这样的上下文中才能把A
22、改写为,2023/11/13,SaSBESaBEBEbEaBab bBbb bEbeeEee,例：1型（上下文有关）文法GS：,2023/11/13,2型：P：A:=其中 A VN，V*,2型语言：L2,称为上下文无关文法。也即把A改写为时，不必考虑上下文。,2023/11/13,例：2型（上下文无关）文法 文法GS：SABABS|0BSA|1 S,2023/11/13,（右线性）P：A:=a 或 A:=aB 其中 A、B VN a VT,3型语言：L3 又称正则语言.,3型文法称为正则文法。它是对2型文法进行进一步限制。左线性 和右线性文法是相互等价的,（左线性）P：A:=a 或 A:=Ba
23、 其中 A、B VN a VT,3型文法：,2023/11/13,GS：S0A|1B|0 A0A|1B|0S B1B|1|0,GI：I lTI lT lTT dTT lT d,例：3型文法,2023/11/13,有关文法的实用限制,1、若文法中有如U:=U的规则，则这就是有害规则，它会引起二义性，而无任何用处。,文法中不能含有有害规则和多余规则,2023/11/13,2、多余规则：（1）某条规则U:=u的左部非终结符U（U不是识别符号），不在任何其他规则右部出现，即所有的推导始终不会用到此规则。（2）在推导句子的过程中，一旦使用了该规则，将推不出任何终结符号串。即该规则中含有推不出任何终结符号
24、串的非终结符。,例如给定GS，若其中关于U的规则只有如下一条：U:=xUy 该规则是多余规则。,若还有U:=a，则此规则并非多余,若某文法中无有害规则或多余规则，则称该文法是压缩过的。,2023/11/13,四种文法之间的逐级“包含”关系,2023/11/13,形式语言与自动机,2023/11/13,图灵机,2023/11/13,2.5PL/0编译程序概述,PL/0编译程序,pcode解释程序,PL/0源程序,PASCAL语言的子集，功能简单，结构清晰，可读性强，具备了一般高级语言的必备部分,2023/11/13,PL/0语言的功能,（1）赋值语句；（2）语句串，即beginend语句；（3）
25、条件语句，即if语句；（4）循环语句，即while语句；（5）过程调用语句，即call语句；（6）输入语句，即read语句；（7）输出语句，即write语句。,语句类型,2023/11/13,数据类型,整型,2023/11/13,标识符（字母开始的字母数字串）的有效长度是10数字最多为14位过程无参，可嵌套（最多三层）定义，可递归调用变量的作用域同PASCAL13个保留字：if,then,while,do,read,write,call,begin,end,const,var,procedure,odd,2023/11/13,PL/0程序示例,const a=10;var b,c;proced
26、ure p;begin c:=b+a end;begin read(b);while b#0 do begin call p;write(2*c);read(b)endend.,不区分大小写,2023/11/13,EBNF在此基础上又增加了三种元符号，约定如下：表示其内语法成分可以重复例如：AA|，可改写为：A。表示方括号内的成分为任选项；例如：A|，可改写为：A。()例如：A1|2|n，可改写为：A(1|2|n),PL/0语言的文法,2023/11/13,=+|-=0|1|2|3|4|5|6|7|8|9,EBNF示例,2023/11/13,PL/0语言文法的EBNF表示,程序=分程序.分程序
27、=常量说明部分变量说明部分过程说明部分语句常量说明部分=CONST常量定义部分，常量定义；无符号整数=数字数字变量说明部分=VAR标识符，标识符；标识符=字母字母|数字,2023/11/13,语法图,2023/11/13,PL/0程序示例改错,var a,b,c;begin read(a,b);c=100 if(a0)thenb=b+1;write(b);else write(c);write(a,b,c);end.,2023/11/13,PL/0编译程序的总体设计,读单词,生成目标代码,核心,一遍扫描方式,2023/11/13,编译程序总体流程图,2023/11/13,内容：符号串和符号串集合的运算、文法和语言的定义几个重要概念：规范推导、规范归约、递归文法、文法的二义性文法的BNF、EBNF、语法图表示文法和语言的分类重点：在理解基本概念的基础上根据给定的语言写出文法、根据给定的文法确定语言判断文法的二义性难点：关于文法和语言的概念是形式语言的理论基础，形式语言抽象地定义为一个数学系统“形式”是指：语言的所有规则以符号串的方式来描述。文法就是这样一个工具推导，文法与语言的相互转换,小结,2023/11/13,习题2、3、4,写在16开数学作业纸上,作业题,思考题,习题1、5-8,
