第2章-形式语言的基本知识课件.ppt

1、编编 译译 原原 理理2023年2月15日第第2 2章形式语言的基本知识章形式语言的基本知识1.1.本章是本章是编译原理课程的理论基础编译原理课程的理论基础，要求掌握形，要求掌握形式语言的基本术语和概念。式语言的基本术语和概念。2.2.掌握文法和语言的定义，文法的二义性与递归掌握文法和语言的定义，文法的二义性与递归性的判断方法及句型的分析方法。性的判断方法及句型的分析方法。3.3.熟练使用文法定义程序设计语言的单词和语法熟练使用文法定义程序设计语言的单词和语法成分。成分。4.4.对形式语言的理论有一个初步认识。对形式语言的理论有一个初步认识。教学目标教学目标编编 译译 原原 理理2023年2月

2、15日 2.1 字母表和符号串的基本概念字母表和符号串的基本概念 2.2 文法和语言的形式定义文法和语言的形式定义 2.3 句型的分析句型的分析 2.4 文法和语言的分类文法和语言的分类 2.5 PL/0 PL/0编译程序概述编译程序概述教学内容教学内容编编 译译 原原 理理2023年2月15日字母表字母表：符号的非空有限集：符号的非空有限集 例：例：=00，11 2.12.1字母表和符号串字母表和符号串符号符号：字母表中的元素：字母表中的元素 例：例：0 0，1 1符号串符号串：由字母表中的符号组成的任何有穷序列：由字母表中的符号组成的任何有穷序列 例：例：0 0,1,1,01,1001,1

3、0,011,011，.空符号串空符号串：无任何符号的符号串，用：无任何符号的符号串，用表示表示 C语言的字母表 Aa,b,0,1,9,+,_/,(,),=if,else,for.不对不对如如=if,else,for,while符号就是字符，对吗？符号就是字符，对吗？编编 译译 原原 理理2023年2月15日符号串的前缀和后缀符号串的前缀和后缀:从符号串从符号串s s的尾部删去若干个的尾部删去若干个(包括包括0 0个个)符号之后所余下的符号之后所余下的部分称为部分称为s s的前缀的前缀，0 0，0101及及011011都是符号串都是符号串011011的前缀的前缀，1 1，1111及及011011

4、都是符号串都是符号串011011的后缀的后缀符号串集合符号串集合：若集合：若集合A A中的一切元素都是某字母表上的符号中的一切元素都是某字母表上的符号串，则称串，则称A A为该字母表上的符号串集合。为该字母表上的符号串集合。例：例：=a a，b b，c A=a,aac A=a,aa,ac,ac编编 译译 原原 理理2023年2月15日符号串的运算符号串的运算符号串符号串x x和和y y的的连接连接:是把是把y y的符号写在的符号写在x x的符号之后的符号之后得到的符号串得到的符号串xyxy 例如例如x=00 x=00，y=11y=11，则，则xyxy=0011=0011对于任意一个符号串对于任

5、意一个符号串s s，有，有s=s=s s=s=s 符号串的符号串的连接运算连接运算编编 译译 原原 理理2023年2月15日符号串自身连接符号串自身连接n n次得到的符号串次得到的符号串s sn n 定义为定义为 ssssssss ，包括，包括n n个个s s，称为符号串的，称为符号串的幂运算幂运算 s s0 0=，s s1 1=s=s，s s2 2=ss=ss，设设s=01s=01，则，则s s0 0=s s1 1=01=01s s2 2=0101=0101 符号串的符号串的幂运算幂运算编编 译译 原原 理理2023年2月15日设设A A、B B为符号串集合，则为符号串集合，则A A和和B

6、B的的乘积乘积定义为：定义为：ABAB xy xy|xA,yB|xA,yB例如，例如，A Aa,ba,b，B=c,dB=c,d则则AB=AB=符号串集合的乘积符号串集合的乘积ac,ad,bc,bdac,ad,bc,bd 编编 译译 原原 理理2023年2月15日有符号串集合有符号串集合A，定义，定义A0=,A1=A,A2=AA,A3=AAA,AnAn-1A=AAn-1 ，n0例如，例如，A A0,10,1，则，则A A0 0=A A1 1=A A2 2=A A3 3=符号串集合的幂运算符号串集合的幂运算0,10,100,01,10,1100,01,10,11000,001,010,011,10

7、0,101,110,111000,001,010,011,100,101,110,111编编 译译 原原 理理2023年2月15日设设A A是符号串集合，定义是符号串集合，定义 A A1 A2 A3 An 称为集合称为集合A A的的正闭包正闭包。A*A0 A称为集合称为集合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年2月15日的闭包的闭包*表示表示 上的一

8、切符号串（包括上的一切符号串（包括）组成的集合）组成的集合的正闭包的正闭包+表示表示 上的上的除除外的所有符号串组成的集合外的所有符号串组成的集合例：例：=a,b=a,b *=,a,b,aa,ab,ba,bb,aaa,aab=,a,b,aa,ab,ba,bb,aaa,aab,+=a,b,aa,ab,ba,bb,aaa,aab=a,b,aa,ab,ba,bb,aaa,aab,.2*.32*编编 译译 原原 理理2023年2月15日若A为某语言的字母表 Aa,b,0,1,9,+,_/,(,),=if,else,for.B为单词集 B=if,else,for,则B A*。语言的句子是定义在B上的符号

9、串。若令C为句子集合，则C B*,程序 C为什么对符号、符号串、符号串集合以及它们的运算感兴趣？为什么对符号、符号串、符号串集合以及它们的运算感兴趣？编编 译译 原原 理理2023年2月15日语言语言是由句子组成的集合，是由一组符号所构成的集合是由句子组成的集合，是由一组符号所构成的集合字母表字母表 上上的一个语言是的一个语言是 上的一些符号串的集合上的一些符号串的集合字母表字母表 上上的每个语言是的每个语言是*的一个子集的一个子集集合a,aa,aaa,或表示为w|w*且w=an,n1 为字母表上的一个语言 例如：字母表=a,b,*=,a,b,aa,ab,ba,bb,aaa,aab,集合ab,

10、aabb,aaabbb,anbn,或表示为w|w*且w=anbn,n1为字母表上的一个语言编编 译译 原原 理理2023年2月15日2.22.2文法和语言的形式定义文法和语言的形式定义 文法文法是对语言结构的定义与描述。（或称为是对语言结构的定义与描述。（或称为“语法语法”）。）。:=“=”:=“+”|“*”:=“(”“)”|编编 译译 原原 理理2023年2月15日赋值语句赋值语句标识符标识符表达式表达式表达式表达式表达式表达式表达式表达式标识符标识符整数整数标识符标识符表达式表达式y=x+r*6y =x+r*6编编 译译 原原 理理2023年2月15日 例：有一句子：“我是大学生”。这是一

11、个在语法、语义上都正确定句子，该句子的结构（称为语法结构）是由它的语法决定的。在本例中它为“主谓结构”。如何定义句子的合法性？有穷语言：只需逐一列举句子无穷语言：使用文法定义句子的结构，用适当条数的规 则把语言的全部句子描述出来。文法是以有穷的集 合刻划无穷的集合的工具。文法的非形式定义文法的非形式定义编编 译译 原原 理理2023年2月15日 1.1.语法规则语法规则：我们通过建立一组规则，来描述句子的语法：我们通过建立一组规则，来描述句子的语法结构结构。规定用规定用“:=”:=”表示表示“由由组成组成”。:=:=:=:=|:=:=你你|我我|他他:=:=王民王民|大学生大学生|工人工人|英

12、语英语:=:=:=:=是是|学习学习:=:=|文法的文法的BNF表示表示编编 译译 原原 理理2023年2月15日2.2.由规则推导句子由规则推导句子：有了一组规则之后，可以按照一定的方式：有了一组规则之后，可以按照一定的方式用它们去推导或产生句子。用它们去推导或产生句子。推导方法：从一个要识别的符号开始推导，即用相应规则的推导方法：从一个要识别的符号开始推导，即用相应规则的右部右部来替代规则的来替代规则的左部左部，每次仅用一条规则去进行推导。，每次仅用一条规则去进行推导。=这种推导一直进行下去，直到所有带这种推导一直进行下去，直到所有带的符号都由终结符号的符号都由终结符号替代为止。替代为止。

13、编编 译译 原原 理理2023年2月15日 =我我=我我 =我我是是 =我是我是=我是我是大学生大学生:=:=:=:=|:=:=你你|我我|他他:=:=王民王民|大学生大学生|工人工人|英语英语:=:=:=:=是是|学习学习:=:=|推导方法：推导方法：从一个要识别的符号从一个要识别的符号开始推导，即用相应规则的开始推导，即用相应规则的右部右部来替代规则的来替代规则的左部左部，每次仅用一条规则去进行推导。每次仅用一条规则去进行推导。编编 译译 原原 理理2023年2月15日例：有一英语句子：例：有一英语句子：The big elephant ate the peanut.:=:=:=:=:=:

14、=the:=:=big:=:=elephant:=:=:=:=ate:=:=:=:=peanut编编 译译 原原 理理2023年2月15日 =the =the big =the big elephant =the 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年2月15日上

15、述推导可写成=the big elephant ate the peanut+说明：(1)有若干语法成分同时存在时，我们总是从最左的语法成 分进行推导，这称之为最左推导，类似的有最右推导（一般推 导）。(2)从一组规则可推出不同的句子，如以上规则还可推出“大象吃象”、“大花生吃象”、“大花生吃花生”等句子，它们 在语法上都正确，但在语义上都不正确。所谓文法文法是在形式上对句子结构的定义与描述，而未涉及语义问题。编编 译译 原原 理理2023年2月15日文法文法GS=（VN，VT，P，S）VN：非终结符号集：非终结符号集 VT：终结符号集：终结符号集 P：产生式或规则的集合产生式或规则的集合 S

16、：开始符号（识别符号）开始符号（识别符号）S VN，S至少要在至少要在 一条规则中作为左部出现一条规则中作为左部出现VVN VT称为文法的字母表称为文法的字母表补补:规则的定义规则的定义:或或V+且至少有一个非终结符，而且至少有一个非终结符，而(VN VT)*文法的形式定义文法的形式定义编编 译译 原原 理理2023年2月15日G=(VT,VN,S,P)，其中，其中:VN=表达式表达式VT=+,*,(,),iS=表达式表达式P=表达式表达式表达式表达式+表达式表达式 表达式表达式表达式表达式*表达式表达式 表达式表达式(表达式表达式)表达式表达式i 【例【例2.1】程序语言中只含】程序语言中只

17、含+、*运算的算术表达式，用运算的算术表达式，用i表示变量或常数，其文法可以表示为：表示变量或常数，其文法可以表示为：描述了表达式的描述了表达式的语法规则语法规则 编编 译译 原原 理理2023年2月15日几点说明几点说明：产生式左边符号构成集合产生式左边符号构成集合VN，且，且 S VN给定一个给定一个 文法，实际只需给出产生式集合，并指定识别符号文法，实际只需给出产生式集合，并指定识别符号G表达式表达式:表达式表达式表达式表达式+表达式表达式表达式表达式表达式表达式*表达式表达式表达式表达式(表达式表达式)表达式表达式iVN：代表程序的语法成份，如：代表程序的语法成份，如“表达式表达式”，

18、它不会，它不会 出现在程序中出现在程序中VT：会出现在程序中，如：会出现在程序中，如i+i编编 译译 原原 理理2023年2月15日有些产生式具有相同的左部，可以和在一起有些产生式具有相同的左部，可以和在一起GE：EE+E|E*E|(E)|i 编编 译译 原原 理理2023年2月15日GS：SL|SL|SDLa|b|zD0|1|9【例【例2.2】某种语言的标识符是以字母开头的字母数字】某种语言的标识符是以字母开头的字母数字串，如果用串，如果用L表示表示，D表示表示，用，用S表示字表示字母数字串母数字串 描述了标识符的描述了标识符的词法规则词法规则 编编 译译 原原 理理2023年2月15日例：

19、无符号整数的文法：例：无符号整数的文法：G|00|1|2|3|9描述了无符号整描述了无符号整数的词法规则数的词法规则 编编 译译 原原 理理2023年2月15日说明说明：终结符集是输入字符集，它是构成单词的最基本元素终结符集是输入字符集，它是构成单词的最基本元素终结符集是经词法分析识别后的单词集，如变量终结符集是经词法分析识别后的单词集，如变量i,i,运运算符算符+、*和分界符和分界符(、)，它们被视为语法分析中最基，它们被视为语法分析中最基本元素本元素 描述语法规则的文法描述语法规则的文法GE：EE+E|E*E|(E)|i 描述词法规则的文法描述词法规则的文法GS：SL|SL|SDLa|b|

20、zD0|1|9编编 译译 原原 理理2023年2月15日文法的表示方法文法的表示方法3.语法图语法图2.EBNF：扩充的扩充的BNF的元符号：的元符号：,:=,|,(,)字母字母 字母字母 数字数字 数字数字 标识符标识符无符号整数无符号整数1.BNF的元符号：的元符号：,:=,|编编 译译 原原 理理2023年2月15日推导的形式定义推导的形式定义如果如果是文法是文法G=(VT，VN，S，P)的的一个产生式，一个产生式，V*，有符号串，有符号串x，y满足满足x=，y=,则称则称y是是x的的直接推导直接推导，也可以说，也可以说，y直接归约直接归约到到x，记作，记作x y。直接推导：用产生式的右

21、部替换产生式的左部直接推导：用产生式的右部替换产生式的左部直接归约：用产生式的左部替换产生式的右部的过程直接归约：用产生式的左部替换产生式的右部的过程 编编 译译 原原 理理2023年2月15日S=SD,使用规则使用规则SSD，其中，其中=；SD=LD,使用规则使用规则SL，其中，其中=,=D；LD=aD,使用规则使用规则La，其中，其中=,=D；aD=a1,使用规则使用规则D1，其中，其中=a,=。GS：SL|SL|SDLa|b|zD0|1|9根据文法和推导的定义，可推出终结符号串根据文法和推导的定义，可推出终结符号串编编 译译 原原 理理2023年2月15日 1 1 0(6)=(1)=(3

22、)(5)=(2)当符号串已没有非终结符号时，推导就必须终止。因为终结符不可能出现在规则左部，所以将在规则左部出现的符号称为非终结符号。例如：例如：G (1)(2)(3)(4)0|1|2|3|9编编 译译 原原 理理2023年2月15日如果存在直接推导序列：如果存在直接推导序列：x y0 y1 y2yn=y则称这个序列是一个从则称这个序列是一个从x至至y的长度为的长度为n（n0）的）的推推导导，或称，或称y归约归约到到x，记作，记作x y。若有若有x y，或，或x=y，则记作，则记作x y。=*=例：例：x S SD LD aD a1=yGS：SL|SL|SDLa|b|zD0|1|9=记作记作x

23、 y或记作或记作x y *=编编 译译 原原 理理2023年2月15日文法文法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年2月15日 形式语言理论可以证明以下两点：形式语言理论可以证明以下两点：（1）G L（G）；）；（2）L(G)G1

24、，G2，Gn；已知文法，求语言，通过推导；已知文法，求语言，通过推导；已知语言，构造文法，无形式化方法，更多是凭经验已知语言，构造文法，无形式化方法，更多是凭经验编编 译译 原原 理理2023年2月15日例：例：GS S:=:=aSb|ab求其所产生的语言。求其所产生的语言。若S:=:=aSb|，如何？L(GS)=anbn|n1L(GS)=anbn|n0已知文法，求语言，通过推导课堂练习课堂练习1：GS S:=:=bA A:=:=aA|aL(GS)=ban|n1课堂练习课堂练习2：GS S:=:=AB A:=:=aA|a B:=:=bB|bL(GS)=ambn|m,n1编编 译译 原原 理理2

25、023年2月15日例：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,Bb|BbG1S：SaBa,B|bBG2S：SaBa,B|Bb编编 译译 原原 理理2023年2月15日例：构造一个文法，使其描述的语言是无符号整数。例：构造一个文法，使其描述的语言是无符号整数。GS：SSD|DD0|1|2|3|4|5|6|7|8|9G|00|1|2|3|9编编 译译 原原 理理2023年2月15日编译

26、感兴趣的问题是编译感兴趣的问题是:给定x,G,求x L(G)?x算法1算法2x L(G)?Gyn出错处理停机 =编编 译译 原原 理理2023年2月15日1.递归规则递归规则：规则右部有与左部相同的符号：规则右部有与左部相同的符号 左递归规则：左递归规则：AA 右递归规则：右递归规则：AA 自嵌入递归规则：自嵌入递归规则：AA递归文法递归文法2.递归文法递归文法：含有递归规则的含有递归规则的文文法，为法，为直接递归直接递归文文法法ABaBAb GS：SL|SL|SDLa|b|zD0|1|9间接递归间接递归文文法法编编 译译 原原 理理2023年2月15日递归文法的递归文法的优点优点：可用有穷条

27、规则，定义无穷语言：可用有穷条规则，定义无穷语言 例：对于前面给出的无符号整数的文法是有递归文法，用例：对于前面给出的无符号整数的文法是有递归文法，用12条规则就可以定义出所有的无符号整数。若不用递归文法，那条规则就可以定义出所有的无符号整数。若不用递归文法，那将要用多少条规则呢？将要用多少条规则呢？!GS：SSD|DD0|1|2|3|4|5|6|7|8|9编编 译译 原原 理理2023年2月15日左左递归文法的递归文法的缺点缺点：不能用自顶向下的方法来进行语法分析：不能用自顶向下的方法来进行语法分析会造成死循环（后面将详细论述）会造成死循环（后面将详细论述）GE：Ei+i|i*i|(i+i)

28、*i该文法所描述的语言为该文法所描述的语言为L(G)=i+i,iL(G)=i+i,i*i,(i+i)i,(i+i)*ii，无法表示无穷的表达式语言无法表示无穷的表达式语言 编编 译译 原原 理理2023年2月15日2.32.3句型的分析句型的分析句型的分析：句型的分析：是指识别输入的符号串是否为某一文法的是指识别输入的符号串是否为某一文法的 句型句型(或句子或句子)的过程的过程 对于同一个句型或句子，可以通过不同的推导序列推导出来，对于同一个句型或句子，可以通过不同的推导序列推导出来，这是因为在推导过程中所选择的非终结符的次序不同这是因为在推导过程中所选择的非终结符的次序不同 GEGE：EE+

29、E|EEE+E|E*E|(E)|iE|(E)|ii+ii+i*i i的推导序列有哪些？的推导序列有哪些？编编 译译 原原 理理2023年2月15日最左最左(右右)推导指对于一个推导序列中的每一直接推导，被替推导指对于一个推导序列中的每一直接推导，被替换的总是当前符号串中的最左换的总是当前符号串中的最左(右右)非终结符号。最右推导也非终结符号。最右推导也称为称为规范推导规范推导。规范推导的逆过程，称为最左归约，也称为规范推导的逆过程，称为最左归约，也称为规范归约规范归约。用最左推导所推导出的句型称为用最左推导所推导出的句型称为最左句型最左句型用最右推导所推导出的句型称为用最右推导所推导出的句型称

30、为最右句型最右句型，通常称为，通常称为规范句型规范句型规范推导与规范归约规范推导与规范归约编编 译译 原原 理理2023年2月15日赋值语句赋值语句标识符标识符表达式表达式表达式表达式表达式表达式表达式表达式标识符标识符整数整数标识符标识符表达式表达式y=x+r*6语法分析的结果语法分析的结果-语法语法树树语法树与文法的二义性语法树与文法的二义性编编 译译 原原 理理2023年2月15日1.1.语法树语法树：描述一个句子的语法结构：描述一个句子的语法结构Thebigelephantatethepeanut语法成分（非终语法成分（非终结符）结符）单词符号（单词符号（终结符号终结符号)编编 译译

31、原原 理理2023年2月15日语法树：句子结构的图示表示法，它是一种有向图，由语法树：句子结构的图示表示法，它是一种有向图，由结点和有向边组成。结点和有向边组成。结点结点：符号：符号 根结点：根结点：识别符号识别符号 中间结点：中间结点：非终结符非终结符 叶结点：叶结点：终结符或非终结符终结符或非终结符 有向边有向边：表示结点间的派生关系：表示结点间的派生关系 SUVabcd编编 译译 原原 理理2023年2月15日句型推导过程句型推导过程句型语法树的生长过程句型语法树的生长过程 由推导构造语法树由推导构造语法树1从从识别符号识别符号开始，开始，逐步逐步建立建立推导推导序列。序列。由由根结点根

32、结点开始，开始，自上而下自上而下建立建立语法树语法树。编编 译译 原原 理理2023年2月15日例：例：G句型句型10=0 0=0=110=规范推导规范推导编编 译译 原原 理理2023年2月15日 由语法树构造推导由语法树构造推导2自下而上自下而上地修剪子树的末端结点，直至把整棵树剪掉地修剪子树的末端结点，直至把整棵树剪掉（留根），每剪一次对应一次规约。（留根），每剪一次对应一次规约。从句型开始，从句型开始，自右向左自右向左地逐步进行地逐步进行规约规约，建立推导序列。，建立推导序列。编编 译译 原原 理理2023年2月15日01=0=10 0=规范规约与规范推导互为逆过程规范规约与规范推导互

33、为逆过程编编 译译 原原 理理2023年2月15日课堂练习：课堂练习：对于句子对于句子ii *i ，给出两，给出两种不同的规范推导，并画出种不同的规范推导，并画出语法树语法树定义定义:若一个文法的某句子存在两个不同的若一个文法的某句子存在两个不同的最右最右(最左最左)推导推导，则该文法是则该文法是二义性二义性的，否则是无二义性的。的，否则是无二义性的。2.2.文法的二义性文法的二义性GE：EE+E|E*E|(E)|i 编编 译译 原原 理理2023年2月15日EEE+EE*iiiEEE*EE+iii这两种不同的推导对应了两种不同的语法树(1)E=E+E=E+E*E=E+E*i=E+i*i=ii

34、 *i(2)E=E*E=E*i=E+E*i=E+i*i=ii*i编编 译译 原原 理理2023年2月15日若文法是二义性的，则在编译时就会产生若文法是二义性的，则在编译时就会产生不确定性不确定性文法的二义性是不可判定的文法的二义性是不可判定的，即不可能构造出一个算法，即不可能构造出一个算法，通过有限步骤来判定任一文法是否有二义性。通过有限步骤来判定任一文法是否有二义性。可以采用两种途径来解决文法的二义性问题可以采用两种途径来解决文法的二义性问题 1不改变文法中原有的规则，仅加进一些语法的非形式规定。不改变文法中原有的规则，仅加进一些语法的非形式规定。规定规定“*”运算优先级高于运算优先级高于“

35、+”+”运算，且服从左结合运算，且服从左结合 改写文法，把排除二义性的规则合并到原有文法中改写文法，把排除二义性的规则合并到原有文法中2编编 译译 原原 理理2023年2月15日EiET+TF*iFTFi例例:算术表达式的文法算术表达式的文法 E:=E+T|T T:=T*F|F F:=(E)|iGE：EE+E|E*E|(E)|i 编编 译译 原原 理理2023年2月15日2.42.4文法和语言的分类文法和语言的分类 形式语言形式语言(乔姆斯基乔姆斯基)：通过抽象，对语言进行形式化描述：通过抽象，对语言进行形式化描述用一组数学符号和规则来描述的语言称为形式语言用一组数学符号和规则来描述的语言称为

36、形式语言 *的任何子集称作的任何子集称作 上的形式语言上的形式语言L（GS）=|VT*,S +由文法定义语言由文法定义语言 文法和语言分类：文法和语言分类：0型、型、1型、型、2型、型、3型型 这几类文法的差别在于对产生式施加不同的限制。这几类文法的差别在于对产生式施加不同的限制。编编 译译 原原 理理2023年2月15日 0型语言：型语言：L0 0型文法称为型文法称为无约束短语结构文法无约束短语结构文法。规则的左部和右部都可。规则的左部和右部都可以是符号串，一个短语可以产生另一个短语。以是符号串，一个短语可以产生另一个短语。0型：型：P：:=其中其中V*且至少含有一个非终结符，且至少含有一个

37、非终结符，V*编编 译译 原原 理理2023年2月15日0型文法型文法GS:SABS|ABABBAA0B1L(GS)=x|x是由是由n个个01或或10组成的二进制数字串，组成的二进制数字串，n1该文法产生的语言为该文法产生的语言为编编 译译 原原 理理2023年2月15日SACaBSACaBCaaaCCaaaCCBDBCBDBaBBaaBBaCBECBE aDDaaDDaADACADACaEaEEaEaAEAE例：例：0 0型型文法文法GSGS：编编 译译 原原 理理2023年2月15日 1型文法型文法：P：A:=其中其中 AVN，V*，V 1型语言：型语言：L1称为称为上下文敏感上下文敏感或

38、或上下文有关上下文有关。也即只有在。也即只有在、这样的这样的上下文中才能把上下文中才能把A改写为改写为编编 译译 原原 理理2023年2月15日SaSBESaSBESaBESaBEBEbEBEbEaBabaBab bBbBbbbb bEbEbebeeEeeeEee例：例：1 1型（上下文有关）型（上下文有关）文法文法GSGS：编编 译译 原原 理理2023年2月15日 2型：型：P：A:=其中其中 A VN，V*2型语言：型语言：L2 称为称为上下文无关文法上下文无关文法。也即把。也即把A改写为改写为时，不必考虑上下文。时，不必考虑上下文。编编 译译 原原 理理2023年2月15日例：例：2

39、2型（上下文无关）文法型（上下文无关）文法 文法文法GS：SABABABS|0BS|0BSA|1SA|1 S编编 译译 原原 理理2023年2月15日2 2型（上下文无关）文法型（上下文无关）文法 文法文法GS：S0A|1BA1S|1B0S|0该文法产生的语言为：该文法产生的语言为：L(GS)=anbn|n1编编 译译 原原 理理2023年2月15日（右线性）P：A:=a 或 A:=aB 其中 A、B VN a VT3型语言：L3 又称正则语言.3型文法称为正则文法。它是对2型文法进行进一步限制。左线性 和右线性文法是相互等价的（左线性）P：A:=a 或 A:=Ba 其中 A、B VN a V

40、T 3型文法：编编 译译 原原 理理2023年2月15日GS：S0A|1B|00A|1B|0 A0A|1B|0S0A|1B|0S B1B|1|01B|1|0GI：I lT lTI l lT lT lTT dT dTT l lT d d例：例：3 3型文法型文法编编 译译 原原 理理2023年2月15日有关文法的实用限制有关文法的实用限制1、若文法中有如若文法中有如U:=U的规则，则这就是的规则，则这就是有害规则有害规则，它会引，它会引起二义性，而无任何用处。起二义性，而无任何用处。例如存在例如存在U:=U，U:=a|b,则有两棵语法树：则有两棵语法树：UaUUa文法中不能含有文法中不能含有有害

41、规则有害规则和和多余规则多余规则编编 译译 原原 理理2023年2月15日 2、多余规则多余规则：（1）某条规则）某条规则U:=u的左部非终结符的左部非终结符U（U不是识别符号），不是识别符号），不在任何其他规则右部出现，即所有的推导始终不会用到此不在任何其他规则右部出现，即所有的推导始终不会用到此规则。规则。（2）在推导句子的过程中，一旦使用了该规则，将推不出任）在推导句子的过程中，一旦使用了该规则，将推不出任何终结符号串。即该规则中含有推不出任何终结符号串的非何终结符号串。即该规则中含有推不出任何终结符号串的非终结符。终结符。例如给定例如给定GS，若其中关于，若其中关于U的规则的规则只只有

42、如下一条：有如下一条：U:=xUy 该规则是多余规则。该规则是多余规则。若还有若还有U:=a，则此规则，则此规则并非多余并非多余若某文法中无有害规则或多余规则，则称该文法是若某文法中无有害规则或多余规则，则称该文法是压缩过的压缩过的。编编 译译 原原 理理2023年2月15日根据上述讨论，根据上述讨论，L0 L1 L2 L30型文法可以产生型文法可以产生L0、L1、L2、L3，但，但2型文法只能产型文法只能产生生L2，不能产生，不能产生L1。2型文法型文法1型文法型文法0型文法型文法3型文法型文法四种文法之间的逐级四种文法之间的逐级“包含包含”关系关系编编 译译 原原 理理2023年2月15日

43、2 2型文法型文法（不确定（不确定的下推自动机）的下推自动机）1 1型文法型文法（不确定（不确定的界限自动机）的界限自动机）0 0型文法型文法（图灵机）（图灵机）3 3型文法型文法（有限（有限自动机）自动机）形式语言与自动机形式语言与自动机编编 译译 原原 理理2023年2月15日图灵机图灵机编编 译译 原原 理理2023年2月15日2.52.5PL/0PL/0编译程序概述编译程序概述PL/0PL/0编译程序编译程序pcodepcode解释程序解释程序PL/0PL/0源程序源程序pcodepcode代码代码PASCALPASCAL语言的语言的子集，功能简单，子集，功能简单，结构清晰，可读结构清

44、晰，可读性强，具备了一性强，具备了一般高级语言的必般高级语言的必备部分备部分编编 译译 原原 理理2023年2月15日PL/0PL/0语言的功能语言的功能（1）赋值语句；）赋值语句；（2）语句串，即）语句串，即beginend语句；语句；（3）条件语句，即）条件语句，即if语句；语句；（4）循环语句，即）循环语句，即while语句；语句；（5）过程调用语句，即）过程调用语句，即call语句；语句；（6）输入语句，即）输入语句，即read语句；语句；（7）输出语句，即）输出语句，即write语句。语句。语句类型语句类型编编 译译 原原 理理2023年2月15日（1）常量说明（全局）常量说明（全局

45、）（2）变量说明；）变量说明；（3）过程说明。）过程说明。说明类型说明类型数据类型数据类型整型整型编编 译译 原原 理理2023年2月15日 标识符（字母开始的字母数字串）的有效长标识符（字母开始的字母数字串）的有效长度是度是1010 数字最多为数字最多为1414位位 过程无参，可嵌套（最多三层）定义，可递过程无参，可嵌套（最多三层）定义，可递归调用归调用 变量的作用域同变量的作用域同PASCALPASCAL 1313个保留字：个保留字：if,then,while,do,read,if,then,while,do,read,write,call,begin,end,const,varwrite

46、,call,begin,end,const,var,procedure,procedure,oddodd编编 译译 原原 理理2023年2月15日PL/0PL/0程序示例程序示例const a=10;var b,c;procedure p;begin c:=b+a end;begin read(b);while b#0 do begin call p;write(2*c);read(b)endend.不区分大小写不区分大小写 编编 译译 原原 理理2023年2月15日EBNF在此基础上又增加了三种元符号，约定如下：在此基础上又增加了三种元符号，约定如下：表示其内语法成分可以重复表示其内语法成分

47、可以重复例如：例如：AA|，可改写为：，可改写为：A。表示方括号内的成分为任选项；表示方括号内的成分为任选项；例如：例如：A|，可改写为：，可改写为：A。()例如：例如：A1|2|n，可改写为：可改写为：A(1|2|n)PL/0PL/0语言的文法语言的文法编编 译译 原原 理理2023年2月15日=+|-=+|-=0|1|2|3|4|5|6|7|8|9=0|1|2|3|4|5|6|7|8|9=+|-=+|-|0|0=1|2|3|4|5|6|7|8|9=1|2|3|4|5|6|7|8|9 =0|1|2|3|4|5|6|7|8|9=0|1|2|3|4|5|6|7|8|9EBNF示例示例编编 译译

48、原原 理理2023年2月15日PL/0PL/0语言文法的语言文法的EBNFEBNF表示表示程序程序=分程序分程序.分程序分程序=常量说明部分常量说明部分变量说明部分变量说明部分过程过程说明部分说明部分 语句语句常量说明部分常量说明部分=CONST=CONST常量定义部分常量定义部分，常量定义，常量定义；无符号整数无符号整数=数字数字 数字数字 变量说明部分变量说明部分=VAR=VAR标识符标识符，标识符，标识符；标识符标识符=字母字母 字母字母|数字数字 编编 译译 原原 理理2023年2月15日语句语句constidentnumber=,;varident，procedureident分程序

49、分程序分程序分程序;分程序分程序.程序程序语法图语法图编编 译译 原原 理理2023年2月15日PL/0PL/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年2月15日语法语义分析程序语法语义分析程序词法分析程词法分析程序序表格管理程序表格管理程序出错处理程序出错处理程序代码生成程序代码生成程序PL/0PL/0源程序源程序目标程序目标程序PL/0PL/0编译程序的总体设计编译程序的总体设计读单词读单词生成目标代

50、码生成目标代码核核心心一遍扫描方式一遍扫描方式编编 译译 原原 理理2023年2月15日编译程序总体流程图编译程序总体流程图启动启动置初值置初值调用G E TSYM取 单 词调用G E TSYM取 单 词调用B L OCK过 程调用B L OCK过 程当前单词当前单词是否为源程序结束符是否为源程序结束符.？.？出错出错源程序中源程序中是否有错误？是否有错误？调用解释过程I N T E R P RET调用解释过程I N T E R P RET解释执行目标程序解释执行目标程序打印错误打印错误结束结束N NY YY YN N编编 译译 原原 理理2023年2月15日内容：内容：符号串和符号串集合的运