《编译原理课件第2章(1)》由会员分享，可在线阅读，更多相关《编译原理课件第2章(1)（67页珍藏版）》请在金锄头文库上搜索。
1、2018年9月8日,第2章 形式语言的基本知识,本章是编译原理课程的理论基础，要求掌握形式语言的基本术语和概念。 掌握文法和语言的定义，文法的二义性与递归性的判断方法及句型的分析方法。 熟练使用文法定义程序设计语言的单词和语法成分。 对形式语言的理论有一个初步认识。,教学目标,2018年9月8日,2.1 字母表和符号串的基本概念 2.2 文法和语言的形式定义 2.3 句型的分析 2.4 文法和语言的分类 2.5 PL/0编译程序概述,教学内容,2018年9月8日,字母表：符号的非空有限集 例：=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,符号就是字符，对吗？,2018年9月8日,符号串的前缀和后缀: 从符号串s的尾部删去若干个(包括0个)符号之后所余下的部分称为s的前缀,，0，01及011都是符号串011的前缀 ，1，11及011都是符号串011的后缀,符号串集合：若集合A中的一切元素都是某字母表上的符号串，则称A为该字母表上的符号串集合。 例：=a，b，c A= a,aa,ac,2018年9月8日
3、,符号串的运算,符号串x和y的连接:是把y的符号写在x的符号之后得到的符号串xy,例如x=00，y=11，则xy=0011 对于任意一个符号串s，有s= s=s,符号串的连接运算,2018年9月8日,符号串自身连接n次得到的符号串sn 定义为 ssss ，包括n个s，称为符号串的幂运算,s0=，s1=s，s2=ss， 设s=01，则 s0= s1=01 s2=0101 ,符号串的幂运算,2018年9月8日,设A、B为符号串集合，则A和B的乘积定义为：AB xy |xA,yB,例如，Aa,b，B=c,d则AB=,符号串集合的乘积,ac,ad,bc,bd,2018年9月8日,有符号串集合A，定义A
4、0 =, A1=A, A2=AA, A3=AAA, AnAn-1A=AAn-1 ，n0,例如，A0,1，则 A0= A1= A2= A3=,符号串集合的幂运算, 0,1 00,01,10,11 000,001,010,011,100,101,110,111,2018年9月8日,设A是符号串集合，定义 A A1 A2 A3 An 称为集合A的正闭包。A* A0 A称为集合A的闭包。,例：A=x,yA？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
5、,符号串集合的闭包运算,2018年9月8日,的闭包* 表示上的一切符号串（包括）组成的集合 的正闭包+ 表示上的除外的所有符号串组成的集合,例：=a,b*=,a,b,aa,ab,ba,bb,aaa,aab,+=a,b,aa,ab,ba,bb,aaa,aab,2018年9月8日,若A为某语言的字母表Aa,b,0,1,9, +,_/, ( , ), = if, else,for. B为单词集B =if, else,for,则B A* 。 语言的句子是定义在B上的符号串。 若令C为句子集合，则C B * , 程序 C,为什么对符号、符号串、符号串集合以及它们的运算感兴趣？,2018年9月8日,语言是
6、由句子组成的集合，是由一组符号所构成的集合 字母表上的一个语言是上的一些符号串的集合 字母表上的每个语言是*的一个子集,集合a,aa,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为字母表上的一个语言,2018年9月8日,2.2 文法的形式定义,文法 是对语言结构的定义与描述又称为“语法” 。,这是一个在汉语语法、语义上都正确定句子，该句子的结构是由它的语法即汉语语法决定的 。我们熟知它为“主谓宾结构”。,“男孩开汽
7、车”,2018年9月8日,计算机程序设计语言也如此 = + | * | | | ,文法是描述语言结构的工具。,文法是产生语言的工具。,1,2,文法的作用,2018年9月8日,文法的作用,如何定义句子的合法性 ？,字符串 “ y = x + r * 6 ”,2018年9月8日,赋值语句,标识符,表达式,表达式,表达式,表达式,标识符,整数,标识符,表达式,y,=,x,+,r,*,6,语法分析的结果-正确, = + | * | | | ,字符串 “ y = x + r * 6 ” 的语法结构,2018年9月8日,1.语法规则：又叫产生式，我们通过它来描述句子的语法结构。 规定用“”表示“由组成”。
8、, 驾驶 这个男孩|汽车,一组规则用来描述这个语法成分。可以生成所有句子。,文法的有关概念,识别符号（开始符号）,尖括号部分表示语法成分,2018年9月8日, = ,= ,= 这个,=这个男孩,=这个男孩,=这个男孩驾驶,=这个男孩驾驶汽车, 驾驶这个男孩 | 汽车,2.由推导生成句子：从一个要识别符 号开始推导，即用相应规则的右部 来替代规则的左部，每次仅用一条规 则去进行推导。,=这个男孩驾驶,所有带的符号都由终结符号替代,采用最左推导 , 这个, 男孩, , 驾驶, , 汽车,2018年9月8日,和语言有关的几个概念,1.直接推导,如果 是文法G的一条产生式，而 ，是(VTVN)*中任意
9、一个符号串，则将 作用于符号串 上得到符号串 ，称符号串 是符号串 的直接推导，记为: ,直接推导的逆过程称为直接归约，即由符号串 可直接归约到 。,2018年9月8日,直接推导举例,例2 见P14,2018年9月8日,2. 推导,设0、1、n均为(VTVN)*中的符号串，且有012n-1n 则称以上序列是长度为n的推导，即0可经过n步推导得到n。,显然，这里n1, 当n=1,就是直接推导。当n=0时， 0=n .当n0，我们称为广义推导。推导的逆过程称为归约，即n可归约到0 。,2.3.3 和语言有关的几个概念,2018年9月8日,2.3.3 和语言有关的几个概念,如果在某个推导过程中的任何
10、一步直接推导中，都是对符号串的最左(右）非终结符号进行替换，则称其为最左(右）推导。最右推导又叫做规范推导。规范推导的逆过程（最左规约）称为规范规约。,3. 最左推导和最右推导,2018年9月8日,【例1】设有文法GN1：N1NNNDDD012,=N2,=ND,=N,N1,=D2,=12 最右推导,=DD,=ND,=N,N1,=1D,=12 最左推导,=DD,=ND,=N,N1,=D2,=12 不是最左推导也不是最右推导,2018年9月8日,=T*F-i,=(E+i)*i-i,=F*i-i,=(E+T)*i-i,=(E)*i-i,=(E+F)*i-i,=(T+i)*i-F =(F+i)*i-F
11、 =(i+i)*i-i,=T-i,=E-i,=E-F,=E-T,E,【例2】设有文法GE：EE+TE-TTTT*FT/FFF（E）i请写出字符串 (i+i)*i-i 最右推导,=T*i-i,2018年9月8日,文法GS=（VN，VT，P，S）VN ：非终结符号集（大写字母表示，或表示）VT ：终结符号集（小写字母表示）P ： 产生式的集合S ： 开始符号（识别符号） SVN ，S至少要在一条规则中作为左部出现,VVN VT 称为文法的字母表,补: 规则的定义 V+且至少有一个非终结符，而(VN VT)*,文法的形式定义,2018年9月8日,G=(VT , VN , S , P )，其中: VN
12、= VT= + , * , ( , ) , i S =表达式 P = 表达式表达式+表达式表达式表达式*表达式表达式 (表达式)表达式 i ,【例2.1】程序语言中只含+、*运算的算术表达式，用i表示变量或常数，其文法可以表示为：,文法的BNF表示法,2018年9月8日,几点说明：,G=(VT , VN , S , P ),2018年9月8日,GS： SL|SL|SD La|b|z D0|1|9,【例2.2】某种语言的标识符是以字母开头的字母数字串，如果用L表示，D表示，用S表示字母数字串,描述了标识符的词法规则,2018年9月8日,例：无符号整数的文法：G | 0 | 1 | 2 | 3 |
13、 | 9,描述了无符号整数的词法规则,2018年9月8日,终结符集是输入字符集，它是构成单词的最基本元素,终结符集是经词法分析识别后的单词集，如变量i,运算符+、*和分界符(、)，它们被视为语法分析中最基本元素,描述词法规则的文法,GS SL|SL|SD La|b|z D0|1|9,（3） VT 在不同文法中的含义,2018年9月8日,文法GS， 是字符串 （1）句型： 是句型 S ,且 V*；（2）句子： 是句子 S , 且, VT*；（3）语言：L（GS）= | S VT*,+,+,文法GS所产生的所有句子的集合,*,句子是所有终结 符号组成的句型,语言的形式定义,VVN VT,* 表示0
14、步或多步推导 + 表示1步或多步推导,文法作为一种有效工具来描述语言的结构， 就必须通过推导生成语言的所有合法的句子。,2018年9月8日,2018年9月8日,1.递归规则：规则右部有与左部相同的符号左递归规则：AA右递归规则：AA自嵌入递归规则：AA,递归文法,2.递归文法：含有递归规则的文法，为直接递归文法,GA: ABaBAb,S表示标识符；L表示；D表示,2018年9月8日,S表示标识符；L表示；D表示 GS： S L | SL | SD L a | b | z GS：S a | ab | abc D 0 | 1 | 9,递归文法的优点：可用有穷条规则，定义无穷语言。,例：前面给出的标识符的文法是递归文法，用12条规则(如下）就可以定义出所有的标识符。若不用递归文法，那将要用多少条规则呢？,!,2018年9月8日,
