第二章-形式语言与文法1

编译原理第二章形式语言与文法主要内容:1语言的形式描述.2语言与文法的形式定义.3文法的分类.4语法树及句型分析.主要问题：已知给定的文法求该文法表示的语言已知语言求描述该语言的文法求给定语句的短语、简单短语和句柄§1.符号串符号串是形式语言中最基本的名词.一,字母表与符号串1,字母表∑定义:元素的非空有穷集合例:∑={a,b,c}(a,b,c字母表)∑={0,1}(二进制数字字母表)∑={汉字,数字,标点符号,…}(汉字组成的字母表)注:元素可是字母、数字或其他符号.字母表中至少有一个元素.2.符号(字符)定义：字母表中的元素.注:符号是字母表中不可再分解的最小单位.3.符号串定义：字母表中的符号组成的有穷序列.例:∑={a,b,c}符号:a,b,c符号串:a,b,c,ab,ac,aa,ba,ca,abc,…例;设字母表A={0,1}A中的符号:0,1A中的符串:0,1,01,10,00,11,001,010,…,01000,…显然:字母表上的符号串可形成一个集合(可数无穷)注:1.符号串的组成是有序的.如:01≠10,ab≠ba2.空符号串为不包含任何符号的符号串,记为:ε3.符号串的长度:符号串所含符号的个数.设符号串为x,则x的长度为∣x∣。例:∣a∣=1∣abc∣=3特别：|ε|＝0即空符号串的长度为零．二．符号串的运算１．连接运算定义：设x和y为符号串，则xy被称为x与y的连接．设x＝abc，y＝10a则xy＝abc10a；yx＝10aabc２．符号串的方幂设有符号串x，则x的n次连接称为x的n次方幂，记为:x例：x＝ε（注:x≠１）x＝xx＝xxx＝xx＝xx＝xxx……x＝xx＝xx＝xx…xn次连接例:x＝abc则x＝ε，x＝abc，x＝abcabc即︱x︱＝０，︱x︱＝３，︱x︱＝６n0012322nn－1n－1011022３．符号串集合的乘积设AB＝｛xy︱x∈Ａ，y∈Ｂ｝即:AB是x∈Ａ,且y∈Ｂ的所有符号串xy构成的集合．例:设A＝｛a，b｝，B＝｛c，d｝则AB＝｛ac，ad，bc，bd｝注：{ε}A=A{ε}=AA=A=A(其中为空集)={}注:ε不属于，即空符号串并不属于空集4.符号串集合的方幂设A为符号串集合,则定义A={ε}A=AA=AAA=AA=AA=AAA……A=AA=AA=AA……A(n个)例:设A={a,b}A={ε}A={a,b}A={aa,ab,ba,bb}(A共有2=4个长度为2的元素)A=AA={aa,ab,ba,bb}{a,b}={aaa,aba,baa,bba,aab,abb,bab,bbb}(A共有2=8个长度为3的元素)012322nn－1n－1012322335.符号串集合的正闭包A和闭包A⑴.符号串集合的正闭包A设A为符号串集合,则A定义为:A=AUAUAU……UAU……例设A={a,b}则A={a,b}={a,b}U{aa,ab,ba,bb}U……={a,b,aa,ab,ba,bb,aaa,…,bbb,……}即:A包括了由A上的元素a,b构成的所有符号串.⑵.符号串集合A的闭包A.A=AUAUAU…UAU……(A=AUA)即A={ε}UA=AU{ε}(A=A－{ε})＋＊＋＋＋123n＋＋＊＊012n＊0＋＊＋＋＋＊+例设A={a,b}则A={a,b}={ε,a,b,aa,ab,ba,bb,aaa,…,bbb,……}显然:对于所有的A,有ε∈A注意：闭包A中包含着ε；A中不包含着ε＊＊＊＊＋§2.文法和语言的形式定义一.文法与语言的关系●语言:由定义在该语言字母表上,且按一定组成规则所构成的句子的集合.即:字母表{字符串(句子)}(语言)●语言的描述⑴.当语言为有穷个句子的集合时,可用枚举的方法表示语言.⑵.当语言为无穷个句子的集合时,则用有穷的语法规则(文法)描述无穷的句子的结构.语法规则例:汉语:人们无法列出全部的句子.但人们可以给出一些规则,用这些规则来说明(或定义)句子的组成结构.如:汉语句子结构：句子∷=主语谓语主语∷=代词︱名词代词∷=我︱你︱他名词∷=王明︱大学生︱工人︱英语谓语∷=动词直接宾语动词∷=是∣学习直接宾语∷=代词∣名词利用以上规则(文法)推导句子:我是大学生.句子主语谓词代词谓语我谓语我动词直接宾语我是直接宾语我是名词我是大学生利用上列文法:可以产生的句子:我学习英语,他学习,语,他是工人,….(很多句子)利用上列文法不可产生“我大学生是”.它不符合以上规则.文法的作用:不仅严格定义句子的结构,也是为了用有限的规则把语言的全部句子描述出来。它是用有穷的集合刻画无穷集合的工具.文法:语言的语法规则的有穷表示.(文法又称元语言)注:1.有穷的文法通过推导的方法,可以推导出给定字母表上的所有句子.2.描述文法的所有字符构成了语言的字母表.3.通过文法在推导合法句子过程中会有多个句型产生.4.合法的句型和句子是用字符串表示的.二.文法的形式定义1.规则(产生式,生成式,重写规则)是一个符号与一个符号串的有序对(A,β)常写成:A∷=β或A→β其中:A是产生式的左部.它是某个字母表∑的正闭包∑中的一个符号.即A∈∑.β是产生式的右部.它是∑中一个符号串.(包括ε)2.文法的形式定义定义:文法G是一个四元组,它是规则的非空有穷集合.G=(V,V,P,S)其中:V是文法产生式中的非终结符号集.V是文法产生式中的终结符号集.＋＋NTNT﹡V∩V=ФP是文法的产生式集。S是文法的开始符号（识别符号）。S∈V非终结符号：出现在产生式的左边，能派生出符号和符号串的符号,常用大写字母表示，即，每一个非终结符号表示一定的符号串。它至少要在产生式左边出现一次。终结符号：不能派生出符号串的符号，它是组成语言不可再分的基本符号，一般用小写字母表示。NTN例：文法G=(V,V,P,S)其中VN={S}VT={0,1}P={S→0S1,S→01}一般约定:1.只写出文法的产生式2.第一条产生式的左部是开始符号，且习惯用G[开始符号]表示。上例文法可写成：G[S]:S::=0S1S::=01NT该文法G所描述的语言的字母表：V=VN∪VT={S，0,1}例：G[标识符]:标识符::=字母|标识符字母|标识符数字字母::=a|b|c|…|z数字::=0|1|2|…|9其中：VN={标识符，字母，数字}S={标识符}VT={a,b,c,…,z,0,1,2,…,9}字母表：V=VN∪VT={标识符,字母,数字,a,b,c,…,z,0,1,2,…,9}3.推导有了文法，怎样由文法推导出与该文法相应的语言？为此引入了“推导”等概念。1)直接推导设x,y是V*中任意符号串，若用一次产生式可以从x推出y，则称y是x的直接推导，记为：xy。（或称符号串x直接产生了符号串y，或称y直接归约到x）例：设G[S]:S::=0S1|01则有如下一些直接推导：S01（利用S::=01）S0S1（利用S::=0S1）0S10011（利用S::=01）0S100S11（利用S::=0S1）2)推导（＋推导）若使用若干次规则式可以从x推出y，则称y为x的推导，记为：x＋y（或称x产生y，或称y规约到x），或记为：xy例：上例：0S100S11000S11100001111∴0S1+00001111（推导长度为3）＋3)广义推导（＊推导）若x＋y或者x＝y（表示0步推导），则写为x＊y（反之亦然，即：x＊y，当且仅当x＋y或者x＝y）例，上例中：0S1+00001111也可记为：0S1*00001111注：直接推导、推导、广义推导的区别：推导长度n不同：直接推导：n＝1推导：n≥1广义推导：n≥0(0步推导：如S＝s)＊包涵＋包涵4.句型和句子设有文法G[S],若有S＊x,则称符号串x为文法G[S]的句型。换句话说：凡是由识别符号推导出来的任意符号串称为句型。句子：仅有终结符号组成的句型称为句子。区别：符号串x∈(VN∪VT)*;x称为句型，符号串x∈VT*;x称为句子。例：G[S]:S::=01|0S1S01S0S100S11000111可见：01,0S1,00S11,000111均为文法G[S]的句型。其中：01，000111为句子（说明句型包含了句子，句子是特殊的句型）但是：符号串000S11,0000111都不是文法G[S]的句型。例：已知文法G[E]：E::=E+E|E*E|(E)|i(其中:VN={E}VT={+,*,i,(,)})试证明:符号串(i*i+i)是文法G[E]的一个句子。证明：只要证明(i*i+i)是文法G[E]的一个存在的推导）(需从开始符号出发)E=(E)=(E+E)=(E*E+E)=(i*E+E)=(i*i+E)=(i*i+i)即：E=＊(i*i+i)所以,符号串(i*i+i)是文法G[E]的一个句子。三、语言的形式定义：定义：由文法G[S]产生的所有句子的集合。即：L(G[S])={x|S=x,且x∈V*}注：①一旦文法给定，语言就确定。②语言L(G)是V*的子集。（语言是字母表中终结符号串闭包的子集）即：属于L(G)的句子一定属于V*反之,属于V*的符号串x不一定属于L(G)。TTTT+例：已知文法G[S]：S::=0S1|01求:L(G)=?解：分析：S=0S1=00S11=000S111…=0n-1S1n-1=0n1n即：S=＊0n1n∴G描述的语言：L(G[S])={0n1n|n≥1}语言句子：由0和1组成，且0在1的前面，0和1个数相等。但：VT’＝{0,1,00,01,10,11,000,…,111,0000,…,0011,…,1111,…}，可见L(G)仅是VT‘的真子集。＋＋1.已知文法求语言方法：推导法（1）利用文法产生式，从文法开始符号开始推导出每个句子；（2）观察组成句子结构的规律，用通式写出。例：已知文法：G[S]:S→0S|1S|ε,求L(G)=?解：SεS=0S=000，000，0000，…..S=1S=111，111，1111，…..S=0S=01S=01S=0S=01S=011S=011,…….以一个0开头，后面是若干个1组成的句子。S=0S=00S=001，………..以两个0开头，后面是若干个1组成的句子。以若干0开头，后面是若干个1组成的句子。以若干1开头，后面是若干个0组成的句子。以若干0或1开头，中间任意个（包括没有）0或1，最后0或1结尾的所有句子。L(G[S])={ε,0,1,01,11,00,10,011,110,101,…}={x|x∈{0,1}*}例：已知G[S]：S∷=aB|bAA∷=a|aS|bAAB∷=b|bS|aBB求：L(G[S])＝？解：S=aB=abS=aB=abS=abaB=ababS=aB=aaBB=aabB=aabb又∵S=bA=baS=bA=baS=babA=babaS=bA=bbAA=bbaA=bbaa∴L(G[S])={x|x∈{a,b},且x中a，b个数相同}反过来，给定语言L(G)后，若要写出能正确描述此语言的文法，是有一定难度的。+例：试对语言L(G)={(n)n|n=0,1,2,…}构造相应的文法G。解：（1）首先分析L是由怎样的符号串x组成的。当n=0时，x=ε当n=1时，x=()当n=2时，x=(())当n=3时，x=((()))…∴L(G)={ε,(),(()),((())),…}2.已知语言求文法(2)归纳集合L(G)的组成特点：L(G)中每个符号串呈对称形式，即(和)成对出现。L(G)为无穷集合，因此描述出的规则中必然含有递归定义。L(G)中的终结符号只有两个:(和)。(3)写出规则：S∷=(S)|ε即，定义此语言L(G)的文法：G