编译原理第2讲(第三章).ppt

1,第三章 文法和语言,为语言的语法描述寻求工具 工具要对程序设计语言给出精确无二义的语法描述。（严谨、简洁、易读） 形式工具-“形式”是指这样的事实：语言的所有规则只以什麽符号串能出现的方式来陈述,2,本章内容,符号和符号串 文法和语言的形式定义 文法的类型 上下文无关文法及其语法树 上下文无关文法的句型分析 有关文法实用中的一些说明,3,语言漫谈,自然语言：英语，汉语，法语。 形式语言：C,Pascal,Fortran等(简单说，文法严格的语言) 自然语言比形式语言复杂。为什么？想想翻译软件的质量。 俄文的“心灵乐意，但肉身衰弱”(对应中文：心有余而力不足；对应英文：The spirit is willing，but the flesh is weak)，以机器翻译为英文时就变为“伏特加酒很不错，但肉已腐败”(The vodka is good，but the meat is rotten)。,4,语言漫谈,程序设计语言（形式语言）：是一个记号系统，完整的定义应包括的语法和语义2个方面。 语法：是指一组规则，用它可以形成和产生一个合适的程序。（定义什么样的符号序列是合法的） 语义：自然语言中词语的意义，逻辑形式系统中符号的解释。（定义什么样的符号序列是有含义的） 文法：是阐明语法的一个工具。这是形式语言理论的基本概念之一。 ？：是阐明语义的工具。这是很困难的。,5,符号和符号串,先了解一些基本概念,6,基本概念,符号：可以相互区别的记号（元素）。 字母表：符号（元素）的非空有穷集合。 符号串：由字母表中的符号组成的任何有穷序列称为该字母表上的符号串。 例： （1）符号“a”组成的字母表记作a （2）符号“a”和“b”组成的字母表记作a,b a, b, aa, bb, ab, abb, aab,都是字母表a,b上的符号串。,7,基本概念,符号串的长度：符号串中符号的个数。 如果符号串x中有m个符号，则长度表示 |x| = m 空串 ：长度为0的符号串，它不同于 (表示空集)。 连接：连接符号串x、y，是把y的符号串写在x的符号串之后得到的符号串；即x、y的连接为xy。 方幂：符号串自身连接n次得到的符号串； 如：x的n次连接为x x x (n个x)，也记作xn,8,基本概念,头、尾、固有头、固有尾； 例：符号串x=abc的 头： , a, b, abc； 尾： , c, bc, abc； 固有头： , a, b； 固有尾： , c, bc； 符号串集合：若集合中所有元素都是某字母表上的符号串，则称之为该字母表上的符号串集合。 符号串集合乘积 例：符号串集合A=ab, aa，B= ba, bb 乘积AB=abba, abbb, aaba, aabb AB=xy|xA, yB,9,基本概念,语言（language） 某字母表上的串的集合，是*的一个子集。 例如： =a, b a, aa, aaa, 或记作：w|w*且w=an, n1 ab, aabb, aaabbb, , anbn, 或记作：w|w*且w=anbn, n1 都可称为一种语言,10,基本概念,闭包： *称为的闭包，若* 表示为上的所有有穷长的串的集合，可表示为： * 123 正闭包： +称为的闭包，可表示为： + * * 123 （其中用代表逻辑“或”运算） 例： a, b * , a, b, aa, ab, ba, bb, aaa, aab, + a, b, aa, ab, ba, bb, aaa, aab, ,11,基本概念,字母，数字，空格，标点符号 , . 等 * 就是所有可能的符号串的集合。 比如： r5*e3!dfd this is a dog. 英语：所谓英语就是那些符合词法（字典，构词法）和语法，语义规则的在字母表上的符号串集合。,12,文法和语言的形式定义,如何来描述一种语言？ 如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示 如果语言是无穷的，找出语言的有穷表示。语言的有穷表示有两个途经： 生成方式 （文法）：语言中的每个句子可以用严格 定义的规则来构造。 识别方式（自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要么能停止并回答“不是”，要么永远继续下去。,13,文法与语言的关系,文法即是生成方式描述语言的 语言中的每个句子可以用严格定义的规则来构造,14,文法的定义,文法G定义为四元组(VN，VT，P，S ),其中 VN:非终结符号(或语法实体，或变量)集； VT:终结符号集； P: 规则的集合； VN，VT和P是 非空有穷集。 S:称作识别符号或开始符号的一个非终结符，它至少要在一条产生式中作为左部出现。 VN和VT不含公共的元素，即VN VT = 用V表示VN VT ，称为文法G的字母表或字汇表。 规则，也称重写规则、产生式或生成式，是形如或 =的( ，)有序对，其中是字母表V的正闭包V+中的一个符号，是V*中的一个符号。 称为规则的左部， 称作规则的右部。,N:Nonterminal ;T:terminal,用大写字母表示A,用小写字母表示a,15,文法的例子(1),例3.1 文法G=（VN，VT，P，S） VN = S , VT = 0, 1 P= S0S1, S01 S为开始符号,16,文法的例子(2),例3.2 文法G=（VN，VT，P，S） VN =标识符，字母，数字 VT =a,b,c,x,y,z,0,1,9 P= a z 0 9 S=,17,文法的写法,元符号: = | 习惯 大写字母表示非终结符 小写字母表示终结符,G： SaAb Aab AaAb A,(2) GS： Aab AaAb A SaSb (3) GS: Aab |aAb | SaSb,18,推导的定义(1),直接推导“” 是文法G的产生式，若有v,w满足：v=,w= , 其中V*,V* 则称v直接推导到w,记作 v w. 也称w直接归约到v 例：G： S0S1， S01 0S1 00S11 00S11 000S111 000S111 00001111 S 0S1,19,推导例子,. ( . ) . . ( ) VAR;BEGIN READ()END. VAR A;BEGIN READ( ) END. ( A) VAR A;BEGIN READ( ) END. VAR A;BEGIN READ( A) END. ( A),20,推导的定义(2),若存在v =w0 w1 . wn=w,(n0) 则记为v =+ w，称作v推导出w，或w归约到v 若有v =+ w 或 v=w， 则记为v =* w,21,推导例子,例：G： S0S1， S01 0S1 00S11 00S11 000S111 000S111 00001111 S 0S1 00S11 000S111 00001111 S =+ 00001111 S =* S 00S11 =* 00S11,22,句型、句子的定义,句型：有文法G，若S =* x，则称x是文法G的句型。 句子：有文法G，若S =* x，且xVT*，则称x是文法G的句子。 例：G： S0S1， S01 S 0S1 00S11 000S111 00001111 G的句型S,0S1 ,00S11 ,000S111,00001111 G的句子00001111, 01,23,句型和句子例子,例：GE： EE+T|T TT*F|F F(E)|a EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a 句子：用符号a，+，*，(和)构成的算术表达式,24,(文法生成的)语言的定义,由文法G生成的语言记为L(G),它是文法G的一切句子的集合: L(G)=x|S =* x，其中S为文法的开始符号，且x VT* 例：G： S0S1， S01 L(G)=0n1n|n1,25,语言的例子,例 文法GS： （1）SaSBE （2）SaBE （3）EBBE （4）aBab （5）bBbb （6）bEbe （7）eEee L（G）= anbnen | n1 G生成的每个串都在L(G)中 L(G)中的每个串确实能被G生成,26,文法的等价,若L（G1）=L（G2），则称文法G1和G2是等价的。 如文法G1A：ADB 与G2S：S0S1 等价 ADE S01 EAB D0 B1,27,文法的其它表示法(除产生式外),1、BNF表示 标识符的BNF: :=| 表示可以取里面的元素0到多次,2、语法图,28,BNF表示的说明,BNF范式概念 BNF:= := := | | := | | | := （ 但愿能有人看得懂:-) ) BNF就是巴科特瑙尔式的缩写，在计算机的史前时代(1950s)，曾有一位大师，他奠定了现代计算机的基础。在他老人家的诸多成就之中，包括了对形式语言的研究，和发明了高级语言：FORTRAN。为了纪念他老人家，我们把他提出的一套描述语言的方法叫做BNF,29,BNF表示的说明,其实BNF很简单 :=表示定义 |表示或 尖括号()括起来的是非终结符 所谓非终结符就是语言中某些抽象的概念， 终结符就是可以直接出现在语言中的符号 比如：C语言的声明语句可以用BNF这样描述： := ; | ; 这一句中这个非终结符被定义成了两种形式（上面用|隔开的两部分） 在这里引入了三个终结符: 分号; 左右方括号 ,30,BNF表示的说明, := | | := * | * := int|char|double|float|long|short|void := enum|struct|union| 到这里就基本上把定义清楚了,31,BNF表示的说明, := 0X | 0 | := | := | := | := | A | B | C | D | E | F := | 8 | 9 := 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 到这里就把定义清楚了,32,BNF表示的说明, := | := | := _ | | := a|b|c|d|e|f|g|h|i|j （偷个懒） := A|B|C|D|E|F|G|H|I|J ,33,BNF表示的说明,到此为止整个声明语句就定义完了（就是说已经没有非终结符了），虽然看起来很繁，但前面定义的各种非终结符都可以很容易的在别的地方重用比如，函数声明可以定义成下面的样子： := (); := | , 只用两句就描述完了，所以BNF实际上比用自然语言要简练得多（整个C语言只用一二百句就可以描述清楚）而且相当的精确，不会有自然语言中那种模棱两可的表达 如果你对BNF比较敏感的话，会发现C里面的标识符不能由数字开头而且在C里面下划线是被当做字母看待的（也就是说能用字母的地方都可以用下划线）,34,BNF表示的说明,比如：（最好用老一点的编译器比如PDP11上的cc） #define _ main #define _ for typedef char* _; int (*_)(char *, .) = printf; /如果这一句不灵，就用下面这句 /#define _ printf /如果你用的是C+可以试一下下面这个 /int (*_)(const char *, .) = printf; _(_,char* _) /要是你编译器不吃，可以改成int _(int _,char*_) _( ; _ ; _ -) _(“%sn“