编译原理第2章+形式语言基础

1第二章语言的基本知识§2.1语言概述§2.2符号和符号串§2.3文法与语言§2.4语法分析初步§2.5文法和语言分类§2.6文法其他表示法2§2.1语言概述一、语言的定义二、形式语言提出三、语言描述方法四、与语言有关的几个概念3一、语言的定义任何一种语言都是在某个特定字母表上定义的、按照一定的规则构成的字符串的集合。4二、形式语言提出形式语言是研究符号的语言，它仅考虑符号间的关系，不考虑含义，即用数学方法（主要是代数方法）对语言进行形式化描述。1956年N.Chomsky(乔姆斯基）在研究自然语言过程中提出一种文法数学模型，为形式语言理论打下了基础，成为计算机科学理论一个重要分支，即形式语言与自动机。5三、语言描述方法1.枚举法2.文法生成法：就是用有限个规则来产生出语言中无限个句子，这种规则集合称文法。3.自动机识别法：用自动机对语言中的句子进行识别6四、与语言有关的几个概念1.元语言：可用来描述其它语言的一种语言2.语法：是在字母表上构造句子的一组规则3.语义：是按照语法规则所构成结构的含义4.语用：是表示语言符号与使用者关系7§2.2符号和符号串一、字母表二、符号串三、符号串集合8一、字母表有限个元素的非空集合称字母表，也称符号集。它是组成一个语言最基本的成分。字母表中元素称符号。习惯上用V、Σ或其它大写字母表示。例如V={a,b,c}，V={α,β…ω}|V|表示字母表中符号的个数。对于不同程序设计语言有不同字母表。例如，机器语言字母表={0,1}，PASCAL语言的字母表由字母、数字以及一些特殊符号，如+，-，*，/，·，(，)，=，…等组成。注意：在一个语言中不能出现字母表以外的符号。9二、符号串1、定义符号串是字母表中的符号所组成的任何有穷序列(有时也称为符号行或字)例如：设V={a,b,c},则符号串有a,b,c,aa,ab,ac,ba,abc…又如：设V={0,1},则符号串有0，1，00，01，10，11，000…由上例可以看出，符号串与符号组成顺序有关，如符号串ab不同于ba，符号串01不同于10，今后我们常用t,u,v,…x,y,z等小写字母表示符号串。102、空符号串不包含任何符号的符号串称为空符号串，记为ε。3、符号串长度符号串中所含符号个数称为该符号串的长度，设符号串为x，则用|x|来表示x的长度。例如：x=abc，则|x|=3,显然,|ε|=0。114、关于符号串的几种运算（1）符号串的联结设有符号串x和y，则它们的联结xy是将符号串y直接拼接在符号串x之后，即x=x1x2x3…xm,y=y1y2y3…yn则xy=x1x2x3…xmy1y2y3…yn显然εx=x，xε=x12（2）符号串的方幂若x是符号串则x0=ε，x1=x，x2=xx，x3=xxx，…xn=xx…x(n个）如x=abc则x0=ε,x1=abc,x2=abcabcX3=abcabcabc∩13三、符号串集合举例：字母表V={a,b}，问用V中的符号，可以组成哪些符号串？解：ε,a,b,aa,ab,ba,bb,aaa,…bbb,…1、定义：若集合A中的一切元素都是字母表V上的符号串，则称A为字母表V上的符号串集合14V*定义：字母表V上各种长度符号串构成串集合，记为V*，不包括空行的集合记为V+即V*={x|x是V上符号串且包括空符号串}V+={x|x是V上符号串且不包括空符号串}V+=V*-{ε}如：V={a,b}，则V*={ε,a,b,aa,ab,ba,bb,aaa,…bbb,…}V+={a,b,aa,ab,ba,bb,aaa,…bbb,…}152、关于串集合的运算（1）串集合乘积设A和B为两个符号串集合，并包含于V*，则A和B的乘积定义为：AB={xy|x∈A且y∈B}由此定义，乘积AB是满足x∈A且y∈B的所有符号串xy所组成的集合。如：V={0，1}V*={ε,0,1,00,01,10,11,000,001，010，011，100,101…}如果A={0，101}B={10，11，110}则AB={010，011，0110，10110，10111，101110}符号ø表示空集16（2）符号串集合的方幂设符号串集合A则A的方幂运算定义为：A0={ε},A1=A,A2=AA,A3=AAA,…An=AAA…A(n个）如：设A={a,b}，则A0={ε},A1={a,b}A2={a,b}{a,b}={aa,ab,ba,bb}A3={aaa,aab,aba,abb,baa,bab,bba,bbb}17(3)符号串集合的闭包和正闭包设A为符号串集合，则A的正闭包定义为A+=A1∪A2∪…∪An∪…符号串集合A的闭包定义为A*=A0∪A+={ε}∪A+如A={a,b}则A+={a,b}∪{aa,ab,ba,bb}∪…={a,b,aa,ab,ba,bb,aaa,…,bbb,…}A*={ε,a,b,aa,ab,ba,bb,aaa,…bbb,…}我们可以证明：A+=AA*=A*AAA*=A（A0∪A1∪A2∪…An∪…）=A1∪A2∪…An∪…=A+18作业：P.38：习题2、319§2.3文法与语言一、巴科斯范式BNF(BackusNormalForm)二、语法树三、产生式（规则）四、文法五、推导和归约六、句型和句子七、语言八、递归文法九、短语和简单短语十、最左推导和最右推导十一、文法二义性20一、巴科斯范式BNF例子：1.Themanhasadog.(这人有一条狗）我们以“∷=”符号(或“→”符号)表示”定义为”，以“|”符号表示“或”，以“”符号表示语法实体(语法单位)，这些符号是元语言符号，21①句子∷=主语谓语②主语∷=冠词名词③冠词∷=the|a④名词∷=man|book|dog⑤谓语∷=动词宾语⑥动词∷=has⑦宾语∷=冠词名词我们把这种描述语法规则方法称巴科斯范式，也称为巴科斯--瑙尔范式(BackusNormalForm)，简称BNF。那么上面叙述句子的语法规则可写为：22例如,在高级语言中大家所熟知的标识符这种语法成分,它用巴科斯范式描述为:标识符∷=字母|标识符字母|标识符数字字母∷=A|B|C|D|…|Z|a|b|…|z数字∷=0|1|2|…|9这样便刻画出了标识符是以字母开始的一串字母和数字任意组合这种特点。23如果定义句子的巴科斯范式改为：①〈句子〉∷=主语谓语②〈主语〉∷=We|He|I③〈谓语〉∷=ran|ate|sat则下面9个句子都是正确的：①Weran②Heran③Iran④Weate⑤Heate⑥Iate⑦Wesat⑧Hesat⑨Isat可见，如果一个语言有无穷多个句子，那么用上述规则来描述更有实际意义.它用一组规则来代替枚举法，用有穷来描述无限。24二、语法树除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称语法树。25句子（句子themanhasabook的推导过程及对应的语法树）26（句子themanhasabook的推导过程及对应的语法树）句子主语谓语①句子∷=主语谓语27（句子themanhasabook的推导过程及对应的语法树）句子谓语主语名词冠词①句子∷=主语谓语②主语∷=冠词名词28（句子themanhasabook的推导过程及对应的语法树）句子主语谓语the名词冠词①句子∷=主语谓语②主语∷=冠词名词③冠词∷=the|a29（句子themanhasabook的推导过程及对应的语法树）句子主语谓语名词manthe冠词①句子∷=主语谓语②主语∷=冠词名词③冠词∷=the④名词∷=man30（句子themanhasabook的推导过程及对应的语法树）句子主语谓语名词动词宾语manthe冠词①句子∷=主语谓语②主语∷=冠词名词③冠词∷=the④名词∷=man⑤谓语∷=动词宾语31（句子themanhasabook的推导过程及对应的语法树）句子主语谓语名词动词宾语manhasthe冠词①句子∷=主语谓语②主语∷=冠词名词③冠词∷=the④⑤谓语∷=动词宾语⑥动词∷=has32（句子themanhasabook的推导过程及对应的语法树）句子主语谓语名词动词宾语manhas名词冠词the冠词①句子∷=主语谓语②主语∷=冠词名词③冠词∷=the④⑤谓语∷=动词宾语⑥⑦33（句子themanhasabook的推导过程及对应的语法树）句子主语谓语名词动词宾语manhas名词冠词athe冠词①句子∷=主语谓语②主语∷=冠词名词③冠词∷=the④⑤谓语∷=动词宾语⑥⑦③34（句子themanhasabook的推导过程及对应的语法树）句子主语谓语名词动词宾语manhas名词冠词abookthe冠词①句子∷=主语谓语②主语∷=冠词名词③冠词∷=the④⑤谓语∷=动词宾语⑥⑦③④35（句子themanhasabook的推导过程及对应的语法树）句子主语谓语名词动词宾语manhas名词冠词abookthe冠词36其中：句子称为语法树根带和不带的都称为语法树的结点一个结点以及向下射出部分称为子树没有向下射出部分的结点称为末端结点37三、产生式（规则）1.定义产生式(规则)就是一个符号与另一个符号串的有序偶(U,x),通常记为U→x或U∷=x其中：U是符号,x是有限非空符号串。U称为规则的左部,x称为规则的右部如果U→x1，U→x2，U→x3，…，U→xn可以写成U→x1|x2|…|xn,并称xi是U的一个候选式。382.字汇表(符号表)（1）定义用于规则左部和右部中所有符号形成集合为字汇表，记为V。39（2）分类1）非终结符号出现在规则左部,且能派生出符号或符号串的那些符号称为非终结符,也称语法实体或语法单位,它们的全体构成一个非终结符的集合,记为VN2）终结符规则中不属于VN的那些符号,称为终结符,它们的全体组成终结符的集合,记为VT。终结符一般出现在规则的右部。显然,V=VN∪VT,VN∩VT=ø40如：在PASCAL中，对标识符的定义规则为：标识符∷=字母|标识符字母|标识符数字字母∷=a|b|…|z|A|B|…|Z数字∷=0|1|…|9由此得：VN={字母,数字,标识符}VT={a,b,…,z,A,B,…Z,0,1,…9}41例如：有产生式:S∷=0S1S∷=01则VN={S}VT={0,1}V={S,0,1}42四、文法为研究方便，下面给出文法的形式定义定义：文法是规则的有穷集合,形式定义为四元组形式为G=(VN,VT,P,Z)其中：VN是非终结符集合,VT是终结符集合,P代表产生式集,Z∈VN是文法G开始符号,也称识别符号,它至少要在一条产生式左部出现。文法G通常记为G［Z］。43对于前面英语句子的例子中用7条文法规则来描述英语句子,其文法可表示为G=(VN,VT,P,Z)其中:VN={句子，主语，谓语，宾语，冠词，动词，名词}VT={the,a,man,book,dog}P是前述7条规则Z=句子44又例如：标识符文法可定义如下:G［Z］=(VN,VT,P,Z)VN={字母,数字,标识符}VT={a,b,…,z,A,B,…,Z,0,1,…9}Z=