编译原理第二章08本.ppt

1、第二章 编译基础,Compiler,预备知识 - 形式语言基础,文法和语言的定义,几个重要概念,文法的表示：扩充的BNF范 式和语法图,文法的构造和语言的分类,2.1 文法的直观概念,一、高级语言程序设计语言是一个记号系统 语法 语义,二、语法 -任何语言程序都可以看成是一定字符集（字母表）上的字符串。 -语法使得这串字符形成一个形式上正确的程序 -语法=词法规则+语法规则 例如：0 .5*x1+c 0.5,x1,c,*,+是语言的单词符号 0 .5*x1+c是语言的语法单位,1.单词符号：语言中具有独立意义的最基本的结构 1.1词法规则-词法规则规定了字母表中哪些字符串是单词符号 -单词符号

2、一般包括：常数、标识符、基本字、算符、界限符 -通常用正规式和有限自动机理论来描述词法结构和进行词法分析,二、语法 1.单词符号 2.语法单位 表达式、子句、语句、函数、过程、程序 3.语法规则 规定了如何以单词符号来形成语法单位 现在多数程序语言使用上下文无关文法来描述语法规则。 语言的词法规则和语法规则定义了程序的形式结构，是判断输入字符串是否构成一个形式上正确的程序的依据。,三、语义 对于一个语言来说，不仅要给出它的词法、语法规则，而 且要定义它的单词符号和语法单位的意义。 离开语义，语言只是一堆符号的集合。 各种语言中有形式上完全相同的语法单位，含义却不尽相同。 对某种语言，可以定义一

3、个程序的意义的一组规则称为语义规则。 目前，大多数编译程序使用基于属性文法的语法制导翻译方法来分析语义。,对于高级程序设计语言及编译程序来说，语言定义是很重要的。本章主要介绍语法结构的形式描述问题，编译原理的主要内容也可以归结为应用形式语言理论，并将它贯穿于词法分析和语法分析两个阶段。 本章重点讨论正规文法、上下文无关文法及其对应的有限自动机和下推自动机，以及在构造编译程序时如何应用？,Compiler,2.1 文法的直观概念,1.什么是文法：文法是对语言结构的定义与描述。即从形式上 用于描述和规定语言结构的称为“文法”（或称为“语法”）。,例：有一句子：“我是大学生” 。这是一个在语法、语义

4、上都正确的句子，该句子的结构（称为语法结构）是由它的语法决定的 。在本例中它为“主谓结构”。,如何定义句子的合法性？ 有穷语言 无穷语言,Compiler,2.语法规则：我们通过建立一组规则，来描述句子的语法结构。 规定用“:=”表示“由组成”。,:= :=| :=你|我|他 := 王民|大学生|工人|英语 := :=是|学习 :=|,Compiler,由规则推导句子：有了一组规则之后，可以按照一定 的方式用它们去推导或产生句子。,推导方法：从一个要识别的符号开始推导，即用相应规则的 右部来替代规则的左部，每次仅用一条规则去进行推导。, = = ,:= :=| :=你|我|他 := 王民|大学

5、生|工人|英语 := :=是|学习 :=|,这种推导一直进行下去，直到所有带的符号 都由终结符号替代为止。,Compiler,推导方法：从一个要识别的符号 开始推导，即用相应规则的 右部来替代规则的左部， 每次仅用一条规则去进行推导。,:= :=| :=你|我|他 := 王民|大学生|工人|英语 := :=是|学习 :=|, = ,= ,= 我,=我,=我是,=我是,=我是大学生,用有穷集合刻画无穷集合,Compiler,例：有一英语句子：The big elephant ate the peanut. := := :=the :=big :=elephant := :=ate := :=pe

6、anut,Compiler, = ,= ,:= := :=the :=big :=elephant | peanut := :=ate :=,= the ,= the big ,= the big elephant ,= the big elephant ,= the big elephant ate ,= the big elephant ate ,= the big elephant ate the ,= the big elephant ate the peanut,1.字母表：非空有穷字符集 -用，V表示 例如：=a-Z,A-Z,0-9,+,-,*,/,(,),=. 2.符号：是语言中

7、最基本的不可再分的单位 3.符号串：字母表中符号组成的任何有穷数列单词 例如：scanf,int,3.1415,x1,100,a. 空串：不会有任何符号的串称作空串，记作e 4、句子：字母表上符合某种规则构成的串 5、语言：字母表上句子的集合 注：约定用a,b,c表示符号；用a,b,g.表示符号串；用A,B,C.表示其集合,2.2 预备知识-符号和符号串,Compiler,2.2 符号和符号串,单词符号 语句 符号串 语言 符号串集合,符号串的形式定义,有字母表，定义：,(1)是上的符号串；,(2) 若x是上的符号串，且a ，则ax或xa是上的符号串；,(3) y是上的符号串，iff（当且仅当

8、）y可由(1)和(2)产生。,符号串集合：由符号串构成的集合,Compiler,符号串和符号串集合的运算,1.符号串相等：若x、y是集合上的两个符号串，则xy iff（当且仅当）组成x的每一个符号和 组成y的每一个符号依次相等。,2.符号串的长度：x为符号串，其长度|x|等于组成该符 号串的符号个数。,例： xSTV ， |x|=3,Compiler,3.符号串的联接：若x、y是定义在上的符号串， 且 xXY，yYX，则x和y的联结 xyXYYX也是上的符号串。,注意：一般xyyx，而xx,4.符号串集合的乘积运算：令A、B为符号串集合，定义,AB ab|aA,bB,例：Aa,b,B=c,d,

9、 AB= ？,因为xxx，所以A=A=A,ac，ad，bc，bd,Compiler,5. 符号串集合的幂运算：有符号串集合A，定义,A0 =,A1=A, A2=AA,A3=AAA, AnAn-1A=AAn-1 ，n0,6.符号串集合的闭包运算：设A是符号串集合，定义,A A1 A2 A3 An ,称为集合A的正闭包。,A* A0 A,称为集合A的闭包,例：A=x,y,A？,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,Compiler

10、,为什么对符号、符号串、符号串集合以及它们的 运算感兴趣？,若A为某语言的基本字符集 ( 把字符看作符号） Aa,b,z,0,1,9, +,*, /, ( , ), = B为单词集 B =begin, end, if, then,else,for, 则B A* 。 语言中的句子是定义在B上的符号串 把单词看作符号，句子便是符号串 若令C为句子集合，则C B * , 程序 C *,Compiler,2.3 文法和语言的形式定义,一、文法的定义,定义1. 文法G=（VN，VT，P，S） VN：非终结符号集 VT：终结符号集 P：产生式或规则的集合 S：开始符号（识别符号） SVN,VVN VT 称

11、为文法的字汇表,规则：U : x UVN, xV*,规则的定义： 规则是一个有序对(U, x), 通常写为: U : x 或U x ， | U| = 1 |x| 0,2.相关概念,(1) 非终结符 出现在规则的左部、用括起来、表示一定的语法概念的词 VN -非终结符的集合 (2) 终结符 语言中不可再分割的字符串（包括单个字符组成的串）。注：终结符是组成句子的基本单位 VT-终结符的集合,(3) 开始符号 表示所定义的语法范畴非终结符 注：开始符号又称为识别符号,(4)产生式 是用来定义符号串之间关系的一组语法规则。 形式：Aa（A产生a） A:=a,Compiler,例：无符号整数的文法：,

12、G=（VN，VT，P，S） VN = , VT = 0,1,2,3,9,P = ； ； ； 0； 1； 9； S = ；,Compiler,几点说明：,产生式左边符号构成集合VN，且 S VN,有些产生式具有相同的左部，可以合在一起,例： ； | ； 0 | 1 | 2 | 3 | | 9,给定一个 文法，实际只需给出产生式集合，并指定识别符号,例： G ； | ； 0 | 1 | 2 | 3 | | 9,文法的BNF 表示,文法规则的扩充表示 扩充的BNF表示 （） 提因子 -例：把U ax|ay|az改写为U a(x|y|z) 重复次数指定 -例：把 |50 任选符号 -例： +|- ,C

13、ompiler,文法的其它表示法,扩充的BNF表示 BNF的元符号： , := ， | 扩充的BNF的元符号： , :=,|, , , (, ),G | 0 | 1 | 2 | 3 | | 9,G 0m 0 | 1 | 2 | 3 | | 9,()推导 推导是从开始符号开始，通过使用产生式的右部取代左部，最终能产生语言的一个句子的过程。 最左（右）推导：每次使用一个规则，以其右部取代符号串最左（右）非终结符。 注：最左推导和最右推导称为规范推导,(6) 归约 归约是推导的逆过程，即，从给定的源语言的句子开始，通过规则的左部取代右部，最终达到开始符号的过程。 最左（右）归约是最右（左）推导的逆过

14、程 注：最左归约和最右归约称为规范规约,(7) 句型、句子和语言 句型： -从文法的开始符号S开始，每步推导（包括0步推导）所得到的字符串a 记作： S a,其中a(VNVT)* 句子：是仅含终结符的句型,*,Compiler,例：有一英语句子：The big elephant ate the peanut. := := :=the :=big :=elephant := :=ate := :=peanut,Compiler, = ,= ,:= := :=the :=big :=elephant | peanut := :=ate :=,= the ,= the big ,= the big

15、elephant ,= the big elephant ,= the big elephant ate ,= the big elephant ate ,= the big elephant ate the ,= the big elephant ate the peanut,Compiler,:= := :=the :=big :=elephant | peanut := :=ate :=, = ,= ,= the ,= the big ,= the big peanut ,= the big peanut ,= the big peanut ate ,= the big peanut a

16、te ,= the big peanut ate the ,= the big peanut ate the elephant,Compiler,说明： (1) 有若干语法成分同时存在时，总是从最左的语法成 分进行推导，这称之为最左推导，类似的有最右推导或一 般推导。,(2) 从一组规则可推出不同的句子，如以上规则还可推出 “大象吃象”、“大花生吃象”、“大花生吃花生”等句子， 它们在语法上都正确，但在语义上都不正确。,所谓文法是在形式上对句子结构的定义与描述，而未 涉及语义问题。,（8）文法规则的递归定义 -非终结符的定义中包含了非终结符自身 -使用文法的递归定义要谨慎,Compiler,递

17、归文法,1.递归规则：规则右部有与左部相同的符号 对于 U:= xUy 若x=, 即U:= Uy， 左递归； 若y=, 即U:= xU， 右递归； 若x,y，即U:= xUy，自嵌入。,+,+,+,Compiler,例：无符号整数的文法：,G=（VN，VT，P，S） VN, VT = 0,1,2,3,9,P = ； ； ； 0； 1； 9； S = ；,例如：字母表A=0,1 语法规则1为： 01 再如：字母表A=0,1 语法规则2为： 01,Compiler,3. 左递归文法的缺点：不能用自顶向下的方法来进行语法分析,4. 递归文法的优点：可用有穷条规则，定义无穷语言,例：对于前面给出的无符

18、号整数的文法是左递归文法，用13条规则就可以定义出所有的无符号整数。若不用递归文法，那将要用多少条规则呢？,会造成死循环（后面将详细论述）,!,（9）元语言符号,用来说明文法符号之间关系的符号，如“ ”和“ ”称为元语言符号,文法等价,定义:若L(G1)=L(G2),则称文法G1和G2是等价的。 举例： 文法1: G(A):P=A0R ,A01, RA1 文法2: G(S):VN=S，VT=0,1， P=S0S1，S01,2.4 文法的类型,chomsky对文法的分类： 根据对产生式施加的限制，可分为 0型文法 1型文法 2型文法 3型文法,chomsky对文法的分类 1. 0型文法（短语文法

19、或无限制文法） P中产生式a b 其中aV+并至少含有一个非终结符， bV* 注：a)识别0型语言的自动机称为图灵机（TM） b) 0型文法是对产生式限制最少的文法。 c)任何 0型语言都是递归可枚举的。 d)对0型文法产生式的形式作某些限制，可得到其它类型文法定义。,2. 1型文法 P中产生式a b ，除可能有S e外，均有|b|=|a|,若有S e，规定S不得出现在产生式右部 或者， P中产生式a b ，除可能有S e外，均有aAb a b，其中， a，bV*，AVN ， V+ 注： a)1型文法又称为长度增加文法、上下文有关文法； b)识别1型语言的自动机称为线性界限自动机（LBA）；

20、c)1型文法意味着，对非终结符进行替换时务必考虑上下文，并且，一般不允许替换成e除非是开始符号产生e,1型文法举例 设文法G=（VN，VT，P，S） VN=S,B,E, VT =a,b,e, 其中P为（0）S aSBE （1）S aBE （2）EB BE （3）aB ab （4）Bb bb （5）bE be （6）eE ee,3. 2型文法 P中产生式具有形式A b 其中AVN ，bV* 注: a)2型文法对产生式的要求是：产生式的左部一定是非终结符，产生式的右部可以是VN，VT或e ；非终结符的替换可以不必考虑上下文。 b)识别2型语言的自动机称为下推自动机（PDA） c)2型文法也称上下文

21、无关文法。,2型文法举例 设文法G=（VN，VT，P，S） VN=S,A,B, VT =a,b, 其中P为（0）S aB （1）S bA （2）A a （3）A aS|bAA （4）B b （5）B bS|aBB,4.3型文法 P中产生式具有形式A aB, A a或者 A Ba， A a，其中A，BVN ， aVT* 注： a) 3型文法也称为正规文法RG、右线性文法或左线性文法； b) 3型文法中的产生式要么是右线性产生式，要么是左线性产生式，不能既有左线性产生式，又有右线性产生式，若所有产生式均是左线性，则称为左线性文法；若所有产生式均是右线性，则称为右线性文法。 c)识别3型语言的自动机

22、称为有限状态自动机,3型文法举例 设文法G=（VN，VT，P，S） VN=S,A,B, VT =0,1, 其中P为（0）S 0A|1B|0 （1）A 0A|1B|0S （2）B 1B|1|0,chomsky对文法的分类 根据对产生式施加的限制，可分为 0型文法 1型文法 2型文法 3型文法,文法的类型,四种文法之间的逐级“包含”关系,3型文法,0型文法,1型文法,2型文法,i型文法 由i型文法生成的语言称为i型语言。 记为：L(G); L(G)=w|wVT* ,且S + w,文法构造与文法简化,例1：设文法G1=（S，a,b, P, S) 其中P为: (0) S aS (1) S a (2)

23、S b L（G1）=ai(a|b) i=0 例2：设文法G2=（S，a,b, P, S) 其中P为: (0) S aSb (1) S ab L（G2）=anbn n=1,一、如何由文法构造语言,二、如何由语言构造文法,例1:设L1 =a2nbn|n=1 且a,bVT 试构造生成L1的文法G1 设n=1, L1=aab 设n=2, L1=aaaabb 设n=3, L1=aaaaaabbb 所以得：S aaSb S aab,例2.设L2 =aibjck|i,j,k=1 且a,b ,cVT 试构造生成L2的文法G2 解: S aS S aB B bB B bC C cC|c,例3.设L3=w|w(a

24、,b)*且w中含有相同个数的a和b, 试构造生成L3的文法G3 解: S e S bB, S aA A bS , A aAA B aS, B bBB,Compiler,例3.设L3=w|w(a,b)*且w中含有相同个数的a和b, 试构造生成L3的文法G3 S e S bB, S aA A bS , A aAA B aS, B bBB,(0)S e S aSbS S bSaS,例4.设L4=w|w(0,1)*且w中1的个数为偶数 试构造生成L4的文法G4 S e S 0S, S 1A A 0A, A 1S,Compiler,2.5 语法分析树与二义性,一、语法树 1.定义： 用来表示语言句子结构

25、的树。 2.作用： 使用语法树可以使语法分析过程直观、形象，易于判断文法二义性。,给定文法G=(VN,VT,P,S），对于G的任何句型都能构造与之关联的语法树（推导树）。 这棵树满足下列4个条件： (1)每个结点都有一个标记，此标记是V的一个符号。 (2)根的标记是S。 (3)若一结点n至少有一个它自己除外的子孙，并且有标记A，则A肯定在VN中。 (4)如果结点n的直接子孙，从左到右的次序是结点n1,n2,nk,其标记分别为A1,A2, ,Ak, 那么AA1A2Ak一定是P中的一个产生式。,语法树：也称推导树,用语法树来描述一个句子 的语法结构。,Compiler,1. 推导与语法树,（1）语

26、法树：句子结构的图解表示法，它是一种有向图，由 结点和有向边组成。,结点：符号 根结点：识别符号 中间结点：非终结符 叶结点：终结符或非终结符,有向边：表示结点间的派生关系。,Z U V a b c d,Compiler,( 2 ) 句型的推导及语法树的生成（自顶向下）,给定GS，句型w： 可建立推导序列，S=w 可建立语法树，以S为树根结点，每步推导生成语法 树的一枝，最终可生成句型w的语法树。,例：,*,G,Compiler,例：无符号整数的文法：,G=（VN，VT，P，S） VN, VT = 0,1,2,3,9,P = ； ； ； 0； 1； 9； S = ；,Compiler,一般推导

27、：10的推导过程,(1),(2),(3),0,(4),1,(5),注意一个重要事实：文法所能产生的句子，可以 用不同的推导原则（使用产生式顺序不同）将其 推导出来。语法树的生长规律不同，但最终生成 的语法树形状完全相同。某些文法有此性质，而 某些文法不具此性质。,语法规则：, Young pop men music like,例如：根据英语的语法规则看能否用最左推导得出“Young men like pop music”是个语法正确的句子；在推导过程中有哪些句型。,对上句的最左推导, Young Young men Young men Young men like Young men like

28、 Young men like pop Young men like pop music,最左推导,最右归约,Young,men,like,pop,music,用图示化方式表示,Young,men,like,pop,music,Young,men,like,pop,men,pop,men,like,young,music,.,例如，有一个2型文法 G1=（S,A,B，a,b, P, S)，其中P: (0)S aB|bA (1)A a|aS|bAA (2)B b|bS|aBB 采用最左推导产生句子aabbab: -S aB aaBB aabSB aabbAB aabbaB aabbab,S ba

29、ck a B a B B b b S b A a S aB aaBB aabSB aabbAB aabbaB aabbab,语法树中的相关概念 （1）子树：除叶子结点以外的任意结点连同它的所有子孙结点构成子树。 （2）修剪子树：剪去子树树根的所有孩子。 （3）句型：在一棵语法树生长过程中的任何时刻，所有那些叶子结点排列起来就是一个句型。,S back a B a B B b b S b A a S aB aaBB aabSB aabbAB aabbaB aabbab,语法树中的概念 （4）短语：子树的末端符号自左至右连成串，相对于子树树根而言称为短语。 简单短语（直接短语）：若短语是某子树根经

30、过1步推导得到的，则称之为该子树根的简单短语。 句型的短语：该句型中哪些符号串可以构成某子树根的短语。,Compiler,子树与短语,子树：语法树中的某个结点（子树的根）连同它向下派生的部分所组成。,某子树的末端结点按自左向右顺序为句型中的符号串，则该符号串为该句型的相对于该子树根的短语。,定理,只需画出句型的语法树，然后根据子树找短语简单短语句柄。,S back a B a B B b b S b A a S aB aaBB aabSB aabbAB aabbaB aabbab,Compiler,（5）定义:任一句型的最左简单短语称为该句型的句柄,给定句型找句柄的步骤： 短语简单短语 句柄

31、注：句柄是最左归约时要寻找的简单短语,注意：短语、简单短语是相对于句型而言的，一个句型可能有多个短语、简单短语，句柄只能有一个。,S back a B a B B b b S b A a S aB aaBB aabSB aabbAB aabbaB aabbab,Compiler,= ,= ,= 0,= 10, ,(1),(2),(4),(3),(5), , , ,0,0,0,0,0,0,0 , ,0,0,1,1,0,10 ,1,0,10,= 0,句型,短语,简单短语,句柄,Compiler,树与推导,句型推导过程句型语法树的生长过程,由推导构造语法树,1,Compiler,由语法树构造推导,2

32、,从句型开始,自右向左地逐步进行归约，建立归约序列。,二、文法的二义性,1.句子的二义性： -如果文法的一个句子存在对应的两棵或两棵以上的语法树，则该句子是二义的。 2.文法的二义性： -包含二义性句子的文法就是二义文法。,例如：文法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+E) (i*i+i) 2) E （E） （E*E） （i*E） （i*E+E） （i*i+E) (i*i+i),E ( E ) E E + E ( E ) E * E

33、 i E * E i i i E + E i i,定义: 若一个文法的某句子存在两个不同的规范 推导，则该文法是二义性的，否则是无二义性的。,从自底向上的归约过程来看，上例中规范句型E+E*i 是由ii*i通过两步规范归约得到的，但对于同一个句型E+E*i，它有两个不同的句柄（对应上述两棵不同的语法树）：i 和 EE。因此，文法的二义性意味着句型的句柄不唯一。,E,E,E,+,E,i,*,E,E,i,i,E,E,E,E,*,+,i,i,i,i+i*i 对应 的两棵语法树,Compiler,句柄：i,句柄：EE,定义 若一个文法的某规范句型的句柄不唯一， 则该文法是二义性的，否则是无二义性的。,

34、注： 1）二义性会给语法分析带来不确定性。 2）文法的二义性是不可判定的，即不存在算法，能够在有限步数内确切判定一个文法是否是二义性文法。 3）若要证明是二义性，只要举出一例。 4）若能控制文法的二义性，即加入人为的附加条件，则二义文法的存在并非坏事。,Compiler,解决办法是：提出一些限制条件，称为无二义性的充分条件，当文法满足这些条件时，就可以判定文法是无二义性的。,E,E,E,+,E,i,*,E,E,i,i,E,E,E,E,*,+,i,i,i,GE: E:= E+E|E*E|(E)|i VN=E VT= +, * , ( , ) , i ,乘法的优先级高于加减法，先推导加法，后推导乘

35、法,举例：if语句采用下面的产生式： S if C then S else S S if C then S S 其它语句 C 具体条件表达式 判断它是不是二义性文法？ 解法：只要找到一个例子，一个句子有两个语法树，就可以证明它是二义性文法。 if c1 then if c2 then s1 else s2,S if C then S else S C1 if C then S S2 C2 S1 S if C then S c1 if C then S else S C2 S1 S2,三、文法的简化,1.由于同一语言可以用不同的文法来描述，显然应该选择产生式的个数最少，最符合语言特征的来描述。 2.在文法中，有些产生式对推导不起作用，要删除掉。 如某个产生式在推导