《编译原理实践及应用》第2章文法基础.ppt
形式语言基本知识,第二章,本章要求,主要内容：符号串，文法的概念及分类，语言的定义过程重点掌握：上下文无关文法、推导、句型、句子、语言，语法树、二义性文法、文法的语言生成过程,以C和PASCAL为例复习高级语言1 语言的基本字符集的定义(字母,数字,界符)2 单词集的定义3 数据类型的定义4 表达式的定义5 语句的定义6 程序定义PASCAL和C的主要区别,2.1 符号和符号串,1.字母表：是元素的有穷非空集合2.符号：字母表中的每个元素，因此字母表也称为符号集。不同的语言可以有不同的字母表，例如英文的字母表中26个字母、数字及标点符号等。PASCAL语言的字母表是由字母、数字、若干专用符号组成。符号是该语言能识别的符号，字母表是该语言能识别的所有符号的全体（字符集）。,基本概念(续),3.符号串:由字母表中的符号组成的任何有穷序列称为符号串，例如00 11 10 是字母表=0，1上的符号串.字母表A=a,b,c上的一些符号串有：a,b,c,ab,aaca等。在符号串中，符号的顺序是很重要的，符号串ab就不同于ba,abca和aabc也不同。符号串STR表示“由符号S、T和R，并按此顺序组成.,基本概念(续),4.符号串的运算a.字符串的连接：字符串称为字符串和的连接 符号串的长度:符号串中符号的个数，例如:某符号串中有m个符号,则称其长度为m，表示为x=m，如001110的长度是6。空符号串:即不包含任何符号的符号串，用表示，其长度为0，即=0。用*表示上所有的符号串的全体(长度为0，1，2，)。,集合的运算b.*的子集U、V的积：UV=|U&V 长度相加即:集合UV中的符号串是由U和V的符号串连接而成。U=aa,bb V=00,11 则UV=?c.集合的方幂：n个相同符号连接Vn=VVVV.V 规定V0=d.闭包、正闭包的运算,例：=a,b*=,a,b,aa,ab,ba,bb,aaa,aab,+=a,b,aa,ab,ba,bb,aaa,aab,使用*表示上的一切符号串（包括）组成的集合。称为的闭包。上的除外的所有符号串组成的集合记为+。称为的正闭包。,V=0,1 V*=?V+=?,2.2 上下文无关文法及其语言,文法是描述语言的语法结构的形式规则。是一种工具，它可用于严格定义句子的结构；用有穷的规则刻划无穷的集合文法是被用来精确而无歧义地描述语言的句子的构成方式.文法描述语言的时候不考虑语言的含义。,引 例,例1：有如下规则(表示由组成)|我大学生是|现要求根据如上规则得出句子：我是大学生=我是大学生,句子“我是大学生”也可以如下图示分析,在有规则的情况下，每一次用上述规则的右边去替换左边，得到“我是大学生”是符合上述规则的句子,上下文无关文法的形式定义,由四部分组成：终结符号：是组成该语言的最基本的符号，是不可再分的基本符号,如保留字、标识符等。非终结符号：规则中用尖括号括起来的符号，表示一些语法成分，可以推导出其他的语法成分,表示一定符号串的集合，是一个类，如表达式。开始符号：规则中的一个特殊的非终结符号，语言中的句子都从它开始推导,如程序、句子产生式：定义语法成分的规则，其中：,文法的形式定义(续),一个文法G抽象地表示为四元组G=（Vn,Vt,P,S）其中Vn表示非终结符号Vt表示终结符号，VnVt=(字母表)，VnVt=S是开始符号，P是产生式，形如：(V+且至少含有一个非终结符号，V*),上例中：G=（Vn,Vt,P,）Vn=（，）Vt=(我，是，大学生)P=,|我 大学生 是|,产生式的形式为：A,左部符号，非终结符,右部，可以含有非终结符和终结符,又称为一条规则有时一个产生式不足以描述该语法范畴，就用多个产生式，如算术表达式的描述为：(递归定义)E E+E E E*E E i相同左部的一个右部又称一个候选式,上下文无关文法所定义的语法成分独立于它可能出现的环境，即不考虑上下文。,算术表达式的文法定义,变量是表达式表达式+表达式是表达式表达式*表达式是表达式(表达式)是 表达式,E E+E E E*E E(E)E i,E E+E|E*E|(E)|i,从上下文无关文法得到某个符号串的方法:从文法的开始符号出发,反复连续使用产生式,对左边的非终结符进行替换和展开，直到全部为终结符为止。例：表达式定义规则,E E+E E E*E E(E)E i,(i+i),E=(E)=(E+E)=(i+E)=(i+i),推导:连续使用产生式右部去替换左部某个非终结符的过程,得到的连续序列称为一个推导。直接推导：又称一步推导(用 符号=表示),就是用某条规则的右部去替换该规则的左部,几个概念的形式定义,直接推导:如果是文法 G=（Vn,Vt,P,S）的产生式，和是*中的任意符号，若有符号串v,w满足：v=,w=,则说v直接产生w，(w是v的直接推导)记作：v=w,例3:G=(E,i,+,*,(,),P,E)P：E E+E|E*E|(E)|i 表达式(i)和(i+i)*i的推导：,E(E)(i)E E*E(E)*E(E+E)*E(i+E)*E(i+i)*E(i+i)*i,E E 0步推导 E(i+i)*i 6步推导 E(i+i)*i 6步推导 E(E)直接推导,句型：设(s)是一文法，如果符号串x是从开始符号推导出来的，即有s=x,则称x是文法G(s)的一个句型。即:任何由开始符推导出来的符号串都是句型。句子：若x仅由终结符号组成，则称x为G(S)的句子,*,练习 文法G：SaAcB|Bd AAaB|c BbScA|b 写出句型aAcbBdcc和句子acabcbbdcc的推导过程。,文法G所产生的语言定义为：L(G)=x|S=x,其中S为文法的开始符号，xVt*。即:一个文法G可以推导出的所有句子构成的一个集合,就确定了一个语言。,*,例：考虑文法G:它定义了什么语言。,S bAA aA|a,推导过程：S=bA=ba S=bA=baA=baa.S=bA=baA=baa,归纳得：L(G1)=ban|n1,练习：文法(A,B,S,a,b,c,P,S)S Ac|aB A ab B bc写出(G)的全部元素,L(G)=abc,例：考虑文法G2:它定义的语言是：,S ABA aA|aB bB|b,L(G2)=ambn|m,n1,思考：构造一个文法G3使得：,L(G3)=anbn|n1,S aSbS ab,a,b的个数相同,则文法G3为：,文法等价：若文法G1和文法G2所产生的语言相同，即L(G1)=L(G2)，则称文法G1和文法G2等价。,例：有如下两个文法，判断它们是否等价？G1=（S，0，S，S0S，S0）G2=（S，0，S，SS0，S0）,S0S0S00S0S 00S 0000,L(G1)=0n|n1,对于G2：,对于G1：,SS0 S00 0000,L(G2)=0n|n1,G1G2，但L(G1)=L(G2)，文法G1和G2等价,例3:G=(E,i,+,*,(,),P,E)P：E E+E|E*E|(E)|i 表达式(i+i)*i的推导过程：(1)E E*E(E)*E(E+E)*E(i+E)*E(i+i)*E(i+i)*i(2)E E*E E*i(E)*i(E+E)*i(E+i)*i(i+i)*i,对给定的文法，利用所有的产生式推导出所有可能的句子构成的一个集合，称为该文法定义的语言。但是一个句型到另一个句型(句子)的推导过程不是唯一的。,最左推导:在整个推导过程中,任何一步推导=都是对中最左边的非终结符进行替换。最右推导:,在推导之前确定推导的顺序，是对句子进行确定性分析所必须的,例3：G=(E,i,+,*,(,),P,E)P：E E+E|E*E|(E)|i(i+i)*i的最左推导过程：E E*E(E)*E(E+E)*E(i+E)*E(i+i)*E(i+i)*i最右推导过程：E E*E E*i(E+E)*i(E+i)*i(i+i)*i,2.3 语法树和文法的二义性,语法树：推导的形式化表示，有助于理解句子语法结构的层次每个结点都有一个标记，该标记属字母集中的一个符号，根由开始符号标记。当某个非终结符被它的某个候选式所替换时，就产生相应的下一层的结点，候选式中自左至右的每个符号对应一个新的结点，并标记它，画出其与父结点之间的连线。,例：对文法G=(E,i,+,*,(,),P,E)P：E E+E|E*E|(E)|i 句子(i+i)*i 的语法树：,在语法树的推导过程中的任何时刻，没有后代的端末结点自左至右排列起来就是一个句型一棵语法树表示了一个句型很多可能的不同推导过程。(包括最左推导和最右推导),例3：G=(E,i,+,*,(,),P,E)P：E E+E|E*E|(E)|i 句子(i*i+i)的语法树：(1)E(E)(E+E)(E*E+E)(i*E+E)(i*i+i),(2)E(E)(E*E)(i*E)(i*E+E)(i*i+E)(i*i+i),并不是任何情况下一个句型就唯一地对应一棵语法树。,2.3 文法的二义性,定义：如果一个文法存在某个句子对应两棵不同的语法树，则说这个文法是二义的,对二义文法中的某个句子的分析不是唯一的，因此总是希望文法是无二义的。但是二义文法有时也是有用的。,2.4 文法的分类,文法有四种:设有G=(Vn,Vt,P,S),不同类型的文法只是对产生式的要求不同：型文法(短文文法)：G的每个产生式满足：V+且中至少含有一个非终结符,V*型文法(上下文有关文法)：如果G的每个产生式 均满足|=|,仅当除外，但S不得出现在任何产生式的右部型文法(上下文无关文法)：G的每个产生式为A,A是一非终结符，V*型文法(正规文法)：G的每个产生式的形式都是：AB或A，其中A,B是非终结符，是终结符串。(右线性文法),语言的层次,这四种语言可被4种自动机识别：0型图灵机 1型线性界限自动机2型下推自动机 3型有穷自动机,从外到内，四种文法对产生式的限制越来越多，语言的描述能力越来越弱,正规文法的描述能力比上下文无关文法的描述能力弱正规文法只能用于描述单词的构成上下文无关文法有足够的能力描述现今大多数程序设计语言的语法结构,例.3:L(G3)=anbn|n1 a,b的个数相同,不能由任何正规文法产生，可以由下述上下文无关文法产生。,S aSbS ab,同样，上下文无关语言的描述能力比上下文有关语言的描述能力弱。,思考题2,写出PASCAL语言中IF语句的上下文无关文法的完整定义,
