编译程序是将高级语言书写的源程序翻译成低级语言程序.ppt

编译程序是将高级语言书写的源程序翻译成低级语言程序。一般包括词法分析，语法分析，中间代码生成，代码优化，目标代码生成五个部分，还应该包括表格管理和出错处理。 其中中间代码生成和代码优化并不是每个程序都需要的。 词法分析器用于识别单词，语法分析器用于发现源程序中的语法错误。 代码优化一般都是在中间代码级上完成的，对中间代码的优化可以使目标程序的运行时间更短或所占的空间更少。,第2讲,第一章课程复习,词法分析，语法分析，中间代码生成，代码优化，目标代码生成均要与符号表格管理打交道，他们各自把工作产生的一些信息存放在符号表里，都涉及到制造，查询，更新符号表格的工作，所以符号表的存取方法直接影响着编译程序的效率。 许多编译程序采用了一种与“3地址指令”非常相似的“四元式”作为中间代码，格式是：,第2章 文法和语言,QU： 1、AB 2、ABC 在C语言中的，以上两个符号串是否是合法的、正确的？,QU：那么，Compiler如何对语法进行定义？是基于什么形式进行判断识别的？ AN：形式语言中的文法是阐明语法的一个重要工具。,2.1 引言,形式化方法：指用一整套带有严格规定的符号体系来描述问题的方法。, ,2.2 符号串,一、字母表和符号串 二、符号串的运算,一、字母表和符号串,1、字母表（） Def：是元素的非空有穷集合。 Note1： 中至少有一个元素； 2： 中可以是字母、数字或其它符号。 Ex1：C语言的字母表 C保留字，字母，数字，专用符号， C语言 C 一组规则 Ex2：汉语的字母表 汉汉字，数字，标点符号，,2、符号与符号串 符号（字符）：一个符号是字母表中的元素。 符号串：是符号的有穷序列。 EX1： a, b, c，则a, b, c, ab, ba都是上的符号串。 Note1：符号串的顺序很重要，如：abba; 2：不含任何符号的符号串称为空串，用 表示。 符号串长度：a1，ab2， 0,二、符号串的运算,1、连接 设X和Y是符号串，则串XY称为它们的连接。 EX：XABC，YCDF XY=ABCCDF YX=CDFABC Note： 与X的连接或X与的连接X,2、集合的乘积 设A、B是符号串的集合，则定义A与B的乘积为： ABxy | xA, y B EX: A=a, b, B=c, d，则AB =ac,bc,ad,bd A=A=A , = ,3、符号串的幂运算 设X是符号串，则 X0 注： X0 1 X1X X2XX Xn XXX,例、设Xabc，则 X0 X1abc X2abcabc Xn abcabc,n个X,n个abc,4、集合的幂运算 设A是符号串的集合，则定义： A0 A1A A2AA AnAAAAn-1A,EX: A=a, b ,则有 A0=ac,bc,ad,bd A1Aa,b A2AAaa, ab, ba, bb A3A2Aaaa,aab,aba,abb,baa,bab,bba,bbb,5、集合的闭包（A+和A） 设A是任意一个集合，则定义： A+A1 A2 A3 A*A0 A+ A0 A1 A2,A的正闭包，其中无空串,A的 * 闭包，其中有空串,EX: A=a, b ,则有 A+a, b, aa, ab, ba, bb, aaa, aab, A*A0 A ,a ,b, aa, ,2.3 文法与语言的形式意义,形式语言 形式语言的描述 文法的形式定义 语言的形式定义 最左、最右推导 归约 递归,一、形式语言, He me a gave book,QU:句子He gave me a book 语法上是否是正确的？,“定义为”或“由组成”, ,推导出,同样还可推导出： He gave He a book, Me gave me a book Me gave He a book,句子,主语,谓语,间接宾语,直接宾语,代词,He,动词,gave,代词,me,冠词,a,名词,book,Note: 1、形式语言是一种上下文无关的语言，是有别于自然 语言的一种语言。 2、定义语言的一组规则及其有关符号，称为文法。 因此，我们把定义形式语言的规则和有关符号的集合，称为上 下文无关的文法。,二、形式语言的描述,方式一：当语言为有穷集合时，用枚举法表示。 EX：设字母表Aa, b, c L1a, b, c L2aa, ab ,a ,ac L3c, cc,ccc,EX：设字母表0, 1，则有 0,1,00,10,001,000,这是一个无穷集合。其中，任何一个元素就相当于一个程序！本身则相当于某一语言的所有程序的集合。,方式二：当语言为无穷集合时，用文法表示。 EX(续上例）： 设用A表示，用式子A0表示0A（读作：“A产生0”）。 符号：“”定义为“产生”、“生成”、“导出”等。 反复用 A0 A1 AA0 AA1 以上四条规则式，则可以生成无穷的集合。,设字母表0, 1，则有0,1,00,10,001,000,三、文法的形式定义,1、规则（产生）式 一个规则式是一个符号与一个符号串的有序偶（对），形如:（A，）、A 或 A : ，用以描述语言中的句子是怎样产生的。 一组规则可以描述一个语言的语法结构。 非终结符，一般在左边，它能派生出符号、符号串。用大写字母表示,如上述中的A。与之对应地，终结符用小写表示，由它不能派生出任何符号，是一个不可再分的基本单位，即字母表（）中的一个元素。,2、文法的形式定义 一个文法是规则的非空有穷集合。常用一个四元组表示，定义为 G（VT，VN，S，P） 其中： VT：所有终结符的集合 VN：所有非终结符的集合 S：开始符 P：规则式的集合,EX: 一个文法G（VT，VN，S，P）,其中： VT0, 1 所有终结符的集合 VNA 所有非终结符的集合 SA 开始符 PA01A0A1 规则式的集合,Qu: 给定一个语言L，如何求文法G？,Ex1：设a, b，试设计一个文法G，定义语言La2n,b2n | n1,解：由串结构的特征L=aa,bb,aaaa,bbbb,可以令P： Aaa AaaB Baa | aaB 以此得序列aa,aaaa,，同理 Abb AbbD Dbb|bbD 可以得到序列bb,bbbb, 文法G（VT，VN，S，P）,其中： VTa, b，VNA，B，D，SA PAaa|bb|aaB|bbD, Baa|aaB, Dbb|bbD,另解：P：ABD BaaaBa Dbb|bDb 文法G（VT，VN，S，P）,其中： VTa, b，VNA，B，D，SA PAB|D, Baa|aBa, Dbb|bDb,以上简记为： GA：ABD BaaaBa Dbb|bDb,Note1：给定一个语言时，文法不是唯一的。 2：用文法描述语言时，要准确，既不能扩大也不能缩小。,Ex2：用文法定义一个含，运算符的算术表达式。,解1：非形式化描述， 1、变量是一个表达式； 2、若E1和E2是一个表达式，则E1E2、E1E2、（E1）也是一个表达式。,解2：形式化描述： GE：E i EE + EE E | ( E ),以上所描述的句子的集合为： i , ( i ), i+i, ii, i+ii, . ,Ex3：设计一个表示所有标识符 I 的文法。,分析：标识符字母或字母开头的字母数字串。,解1：形式化描述： GI：ILILID La | b | c z | A | B | C | Z | D1 | 2 | 3 | 9 |,解2:GI：ILILD La | b | c z | A | B | C | Z | D1 | 2 | 3 | 9 | ,Ex4：已知L ( n ) n | n 0, 1 , 2 , , 求文法G。,解： L , ( ) ,( ), ( ), GS：S ( S ),2th class over,1、字母表、符号串、符号串的长度、空串 2、符号串运算：连接、符号串的幂 3、集合的运算：集合乘、集合的幂、集合的闭包 4、形式语言的描述： （1）枚举法描述 （2）用文法描述 5、文法的形式定义 G（VT，VN，S，P）,复习基本概念,文法的作用是什么？,第3讲,四、语言的形式定义,1、直接推导 设X，Y是符号串，如果使用一次规则式可以从X推导出Y，则Y为X的直接推导。记为：XY,Ex: 设GS：S0S101，则 S01 S 0S1 0S1 0011 0S1 00S11 ,2、+推导 (正推导） 设X，Y是符号串，若使用一次或多次规则可以从X推导出Y，则Y为X的推导。 记为：X Y,Ex: 设GS：S0S101，则 S01 S 0S1 00S11 000111 所以 S 000111,3、*推导 (广义推导） 设X，Y是符号串，若使用0次或多次规则可以从X推导出Y，则Y为X的*推导。 记为：X Y,区别: 直接推导长度1 正推导长度1 广义推导长度 0 即：直接推导正推导广义推导,4、句型、句子 设有文法GS，若从文法开始符号S x,则称符号串x为文法GS的句型；仅仅由终结符组成的句型叫句子。 若x是一个句型，则x （VNVT） 若x是一个句子，则x VT,(句型、句子） (句型） (句型、句子）,Ex: 设GE：EEEEE（E）i，试证明符号串( i * i + i )是文法GE的一个句子 证明：从E出发，只要证明符号串x = ( i * i + i ) 对于文法GE 存在一个推导。 E（E）（EE） （EEE） （i*E+E） （i*i+E） （i * i + i ）,5、语言L(GS) 对一个文法GS，其句子的全体所组成的集合即语言L(GS)。 L(GS)x | S x 且 xVT* 换言之，文法描述的语言是该文法一切句子的集合。,Note1: 若文法给定，则语言也确定了。 2: 一个语言是所有终结符VT的子集（所有满足文法规定的终结符的集合）。,VT*,L(GS),Ex1:已知文法GS：S0S101，求L？ S 0S1 00S11 000S111 0n-1S1n-1 0n1n 即S 0n1n L(GS)=0n1n | n1,Ex2:已知文法GS：S0S1S，求L？ L(GS) ，0，1，00，01，10，11， x | x 0,1* ,Why?,Ex3:已知： SaBbA Aa | aS | bAA Bb | bS | aBB ，求 L？ 分析： S=aB=ab S=aB=abS=abaB=abab S=aB=aaBB=aabB=aabb S=bA=ba S=bA=baS=babA=baba S=bA=bbAA=bbaA=bbaa L(GS) ab ,ba,abab,baba,aabb,bbaa, x | x a,b+ 且 x中a和b个数相同 ,Why?,Note 1:以上推导不严格，必须得到证明（控制论自动机理论）。 2:每个规则式在推导时必须用到。 3:这个推导过程是否唯一？,Ex: 已知GN1: N1N NND | D D0 | 1 | 2，试列出句子22的推导过程。 1、N1 N ND N2 D2 22 2、N1 N ND DD 2D 22 3、N1 N ND DD D2 22,总是先处理最右的VN 总是先处理最左的VN 右、左,五、最左、最右推导,在推导过程中，任何一步 ，都是对中的最左（最右）非终结符进行替换的过程，叫最左（最右）推导。 特别称最右推导过程叫规范推导； 由规范推导得到的句型叫规范句型。,Ex:已知: SAB AAa | bB Ba | Sb ,给出句子babaab的最左、最右推导。,最左：S=AB =bBB =baB =baSb =baABb =babBBb =babaBb =babaab,最右：S=AB =ASb =AABb =AAab =AbBab =Abaab =bBbaab =babaab,六、归约,归约是推导的逆过程。即：将句型中的某一子串用一串非终结符代替的过程。 若有A，则XAY X Y，于是X Y XAY。 称规范（最右）推导的逆过程为规范归约（先归约最左那一串（不是一个）符号）。,最右：S=AB =ASb =AABb =AAab =AbBab =Abaab =bBbaab =babaab,逆推导：S=AB =ASb =AABb =AAab =AbBab =Abaab =bBbaab =babaab,归约： babaab=bBbaab =Abaab =AbBab =AAab =AABb =Asb =AB =S,七、递归,两种递归：规则递归和文法递归 规则递归 若文法中有规则式 AA ,称该规则左递归； 若文法中有规则式 AA ,称该规则右递归； 若文法中有规则式 AA ,称该规则递归； 文法递归 若文法中有 A A ,称该文法左递归； 若文法中有 A A ,称该文法右递归； 若文法中有 A A ,称该文法递归；,用递归规则定义无穷集合： Ex: N1N ND | DD | | DDD D0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9,结论 若语言L是一无穷集合，则描述这个语言的文法一定是递归的。,NND | ,递归作用：用递归规则可以定义无穷集合的语言。,2.4 文法和语言的分类,自从乔姆斯基（Chomsky）1956年建立形式语言的描述以来，形式语言的理论对发展对计算机科学，特别是对程序语言的设计、编译方法及计算复杂性等方面的作用是巨大的。 Chomsky将文法分成四类，它们是：0型、1型、2型和3型文法,对应地，其定义的语言称为0、1、2、3型语言。,一、0型文法,0型文法是最宽松的文法，又称无限制文法。通过对其产生式施加不同的限制可以得到1、2、3型文法。 定义： 设文法G（VN，VT，P，S），如果它的每一个产生式有如下形式： （VNVT）， 不能为空且至少含有一个非终结符。 （VNVT）* 即允许 由0型文法得到的语言为0型语言。,Ex:设有文法GS，其中P为 S0AB 1B0 BSA01 A1SB1 A0S0B,二、1型文法,设文法G（VN，VT，P，S），如果它的每一个产生式满足 A ，其中 A VN , （VNVT）， 即不为空 、 （VNVT）* 即必须左右，S除外 这种文法意味着，对非终结符A进行替换时务必考虑上下文，因为只有A出现在和 的上下文中，才允许用替换A。,Ex: SaSAB|abB BABA BAAA AAAB bAbb bBbc cBcc,三、2型文法,若G中的任何产生式为 A ，其中 A VN , （VNVT）* 2型文法又称上下文无关文法，用以描述语法结构，如算术表达式、各种语句等。,四、3型文法,若文法中的每一规则式有如下形式： A B A 或 AB A 其中A、B VN , VT*,右线性文法,左线性文法,正规文法,3型文法又称正规文法或正则文法。 3型文法对应有穷自动机，用三型文法描述词法分析,Ex: Il | Il |Id,文法类型小结,Question: G0G1G2G3 Or G3G2G1G0 谁正确？,第一次作业,教材P44练习 第1，2，3，4，5题,3th class over,第4讲,复习基本概念,1、直接推导、推导、推导 2、句型和句子 3、语言的形式定义 L(GS)x | S x 且 xVT* 4、最左推导、最右推导（规范推导） 5、归约、规范归约,规范归约：先归约最左那一串（不是一个）符号。,6、递归：规则递归、文法递归 (1) A-BA,B-CA, (2) A-B,B-CA, 7、文法的等价性：G1G2,SAB，AAa | bB，Ba | Sb,8、文法和语言的分类,SaSAB|abB BABA BAAA AAAB bAbb bBbc cBcc,S0AB 1B0 BSA01 A1SB1 A0S0B,SaBbA Aa | aS | bAA Bb | bS | aBB,EEE EE （E） i,2.5 句型分析及句柄,Qu: 1、何谓句型分析？ 2、为什么要进行句型分析？ 3、如何进行句型分析？,一、句型分析,Def: 是一个识别过程。 从形式上它识别一个符号串是否是文法G的句型； 从实质上，它能确定输入符号串是否为语法上正确的程序。,S AB ab 终结符串 I II,I：推导法：其关键问题是选择哪一条规则式。 II：归约法：先扫描源程序，然后归约为一个开始符号。关键是如何确定当前的“可归约串”。,分析方法： 从上到下：S 终结符号串（推导法） 从下到上：终结符号串S（归约法）,二、基本概念,1、短语 Def: 设文法GS，（一串符号）是G的一个句型，若有S A且A ，则称是(句型相对)非终结符A的短语。,EX:N1N NND|D D0|1|2 若DD是一个句型，问句型DD的短语有哪些？ 若D2是一个句型，问句型D2的短语有哪些？ 若ND是一个句型，问句型ND的短语有哪些？ 问符号串DN的短语有哪些？,2、直接短语 Def:已知GS， 是G的一个句型，若有S A且A ，则称是（句型）相对非终结符A的直接短语。 3、句柄 最左边的直接短语称为句柄。 句柄即“可归约串”。,Ex:已知文法GS：SAB AAa | bB Ba | Sb 求字符串baSb的全部短语、直接短语句柄。,解：（分析：由定义，第一步，判符号串baSb是否是句型，如果不是句型则不作第二步；第二步，再求短语、直接短语和句柄；） 由最右推导有： SAB ASb bBSb baSb，所以baSb是文法G的句型。 1）S S，S baSb，所以baSb是相对S的一个短语； 2）S ASb，A ba，所以ba是相对A的一个短语； 3）S bBSb，B a，所以a是相对B的一个短语，也是直接短语；,（续上）由最左推导有： SAB bBB baB baSb，所以baSb是文法G的句型。 1）S S，S baSb，所以baSb是相对S的一个短语； 2）S AB，A ba，所以ba是相对A的一个短语； 3）S baB，B Sb，所以Sb是相对B的一个短语，也是直接短语； 由上可知，a, Sb均为直接短语，但a为最左边的直接短语，所以，a为其句柄（可归约串）。,SAB AAa | bB Ba | Sb,根据定义求短语、直接短语和句柄，很不直观。下面介绍 直观的方法：语法树。,2.6 语法树及二义性,语法树又称语法分析树、分析树、推导树。它是进行句型分析（判句子、句型，短语、直接短语和句柄）的重要而又直观的工具。,一、语法树,1、语法树：对句型的推导过程，给出一种树形表示，称树形为语法树。约定： （1）文法的开始符树根 （2）句型树所对应的叶子 （3）语法树构造过程从开始符出发构造一个推导过程 2、子树：由某个结点及其所有分支组成。 3、简单子树：只有单层分支的子树。 4、结论 （1）每棵子树的叶子组成一个短语； （2）每棵简单子树的叶子组成一个直接短语； （3）最左边简单子树的叶子是句柄。,Ex:已知GE: EETETT TTFT / FF F（E）i 求符号串(Ti)iF的全部短语、直接短语和句柄。,解：由符号串(Ti)iF 可得一棵推导树如右：,E1,以E1为树根： 以E2或T2为树根： 以T3或F2为树根： 以E3为树根： 以E4为根： 以T4或F3为根： 以F1为根： 以T1为根：,Note: 一个句型不一定只对应一棵唯一的语法树。,Ex: 文法GE: EEEEE（E）i 的句子 ii+i 存在两棵不同的语法树。,E,E,所以GE是一个二义性的文法。,二、文法的二义性,def: 如果一个文法存在某个句子对应二棵不同的语法树或者二个不同的最左（右）推导，则这个文法是二义性的。,要么两个最左推导，要么两个最右推导。,Ex: 文法GE: EEEEE（E）i 的句子 ii+i 存在两个不同的最左推导。 (1) E E+E E*E+E i*E+E i*i+E i*i+i (2) E E*E i*E i*E+E i*i+E i*i+i,三、消除文法的二义性,方法一： 不改变规则式，仅加进非形式化的语法规定。如上例，规定：优先于，左结合。则（1）对。,(1) E E+E E*E+E i*E+E i*i+E i*i+i,方法二： 把排除二义性的规则合并到原有的文法中，即构造等价的无二义的文法。如上例改为：,E E+TT T T*FF F （E）i,即可消除二义性。,Ex:已知文法G： Sif B then S Sif B then S else S SS 请画出句子: if B then if B then S else S 对应的语法树。,S,S,将：Sif B then S Sif B then S else S SS 改造成： SS1 | S2 S1if B then S1 else S1 | S S2if B then S | if B then S1 else S2 使得 else 总是跟前边最近的 then 配对,可消除二义性。,S2,Note:并不是所有二义文法都可以改造，有一些文法是先天 二义的，是无法改造的。如：定义语言 Lai bj ck | i=j 或 j=k, i,j,k1 的文法是先天二义的。,第二次作业 2003、9、24,教材P45练习 第8，9，10，11，13题,4th class over,第5讲,一、设计一个文法,定义一个已知的语言L 1、文法定义（搞清楚）G（VT，VN，S，P） 2、分析已知句子的特征，设计出P 3、设计的文法必须能够精确定义已知的L 4、若L是无穷的，则G一定是递归的,第2章 小结,Ex1: 已知文法G1(a,b,c,A,B,C,A, P1),其中P1： ABbC BaB| CcC| 已知文法G2(a,b,c,D,E,D, P2),其中P2： DaD | bE | EcE | 求：1）G1、G2所产生语言L1和L2的并、连结的文法。 2）G1、G2各自产生语言闭包的文法。,解：并的文法： SAD ABbC DaD | bE | ,连结的文法： SADDA ABbC DaD | bE | ,G1所产生语言L1闭包的文法： S AS A ,L1*： L10L11 L12,G2所产生语言L2闭包的文法： S DS D ,Ex2: 一种表结构如下： 1） 是一种表结构； 2）a 为原子，是一个表结构； 3）若T1,T2,Tk（k1）是一个表结构，则（ T1,T2,Tk）也是一个表结构。 求：描述这个语言的上下文无关文法。,解： P： S a( T ) TT,SS,Ex3: 已知Lai bj ck | i=j 或 j=k, i,j,k0 求：文法G。,解：SABDC AaAb | BcB | DaD | CbCc | ,Ex4: 已知Lx x -1 | xa,b+ ,若x=ab,则x-1=ba,求文法G。,解：因为x=a,b+=a,b,ab,ba,aa,bb, 则Laa,bb,abba,baab,aaaa,bbbb, 所以：Aaa | bb | aAa | bAb,Note: 1）文法的开始符一定写在文法的前面（第一条规则式中）； 2） 是表示空符号串，不是终结符