2编译过程和编译程序的结构.PPT

资源描述

1、1.2 编译过程和编译程序的结构,编译逻辑过程词法分析语法分析语义分析中间代码生成代码优化目标代码生成,词法分析,从左至右读字符流的源程序、识别(拼)单词例： position := initial + rate * 60;,词法分析position := initial + rate * 60;,单词类型单词值标识符1(id1) position 算符(赋值) := 标识符2(id2) initial 算符(加) + 标识符3(id3) rate 算符(乘) * 整数 60 分号；,又如一个C源程序片断： int a; a = a + 2;词法分析后可能返回:单词类型单词值保留字 in

2、t标识符(变量名) a界符 ;标识符(变量名) a算符(赋值) =标识符(变量名) a 算符(加) +整数 2界符；,有关术语,词法分析(lexical analysis or scanning) -The stream of characters making up a source program is read from left to right and grouped into tokens,which are sequences of characters that have a collective meaning.单词-token保留字-reserved word标识符 -i

3、dentifier(user-defined name),语法分析,功能:层次分析.依据源程序的语法规则把源程序的单词序列组成语法短语(表示成语法树).position := initial + rate * 60 ;规则 :=“:=” :=“+” :=“*” :=“(”“)” := := :=,赋值语句,标识符,表达式,表达式,+,表达式,表达式,标识符,整数,标识符,:=,表达式,*,id1:=id2+id3*N,术语,语法分析(syntax analysis or parsing)The purpose of syntax analysis is to determine the sou

4、rce programs phrase structure.This process is also called parsing.The source program is parsed to check whether it conforms to the source languages syntax,and to construct a suitable representation of its phrase structure.语法树(推导树)(parse tree or derivation tree),语义分析,语义审查(静态语义)上下文相关性类型匹配类型转换,例:Progra

5、m p();Var rate:real;procedure initial;position := initial + rate * 60 /* error */ /* error */ /* warning */;,又如: int arr 2,abc; abc = arr * 10;Program p();Var rate:real; Var initial :real; Var position :real ; position := initial + rate * 60,语义分析,术语,语义分析(semantic analysis) The parsed program is furt

6、her analyzed to determine whether it conforms to the source languages contextual constraints:scope rules, type rulese.g. To relate each applied occurrence of an identifier in the source program to the corresponding declaration.,中间代码生成,源程序的内部(中间)表示三元式、四元式、P-Code、C-Code、U-Code、bytecode( * id3t1t2)t2 =

7、 id3 * t1t2 := id3 * t1,中间代码生成,id1:= id2 + id3 * 60(1)(inttoreal,60-t1)(2)(*,id3t1t2)(3)(+,id2t2t3)(4)(:=,t3-id1),中间代码生成(intermediate code generation),This is where the intermediate representation of the source program is created.We want this representation to be easy to generate,and easy to transla

8、te into the target program.The representation can have a variety of forms,but a common one is called three-address code or 4- tuple code.,代码优化,id1:= id2 + id3 * 60(1)(inttoreal60-t1)(2)( * id3t1t2)(3)( +id2t2t3)(4)( :=t3-id1) 变换（1） ( *id360.0t1) ( 2）（ + id2 t1id1),代码优化,t1 = b* c t1 = b* c t2 = t1+

9、0 t2 = t1 + t1t3 = b* c a = t2t4 = t2 + t3a = t4,代码优化(code optimization),Intermediate code optimizationThe optimizer accepts input in the intermediate representation and output a version still in the intermediate representation .In this phase,the compiler attempts to produce the smallest,fastest and

10、 most efficient running result by applying various techniques.Object code optimization,目标代码生成,(*,id360.0t1)(+,id2t1id1),movfid3,R2mulf#60.0,R2movfid2,R1addfR2,R1movfR1,id1,符号表管理,记录源程序中使用的名字收集每个名字的各种属性信息类型、作用域、分配存储信息,Const1常量值：35Var1变量类型：实层次：2,符号表(symbol table),Symbol table is a data structure which

11、is employed to associate identifiers with their attributes .An identifiers attribute consists of information relevant to contextual analysis,and is obtained from the identifiers declaration.,出错处理,检查错误、报告出错信息、排错、恢复编译工作,出错处理(error handling)(error reporting and error recovery),The compiler should repor

12、t the location of each error,together with some explanation. The major categories of compile-time error: syntax error, scope error, type error.After detecting and reporting an error,the compiler should attempt error recovery,means that the compiler should try to get itself into a state where analysi

13、s of the source program can continue as normally as possible.,编译程序结构(components),词法分析程序语法分析程序语义分析程序中间代码生成程序代码优化程序目标代码生成程序符号表管理程序出错处理程序,出错处理,表格管理,编译阶段的组合,分析，综合(synthesis)源程序的分析线性分析层次分析语义分析目标程序的综合编译的前端（front end）编译的后端（back end）遍（趟）从头到尾扫描源程序（各种形式）一遍(pass),高级语言解释系统(interpreter),功能让计算机执行高级语言（basic,lisp,

14、prolog)与编译程序的不同 1）不生成目标代码 2）能支持交互环境（同增量式编译系统）源程序初始数据,解释程序,计算结果,解释系统,直接对源程序中的语句进行分析，执行其隐含的操作。如： b := 2 ; a := b+2 ; 编译程序 write a ; 解释程序直接将4的值输出（显示）,Int 2St bLd badd 2St a,生成代码,编译阶段和运行阶段存储结构,编译时运行时,名字表,目标代码缓冲区,编译用源程序中间表示各种表格,目标代码区,数据区,源程序缓冲区,解释系统存储结构,文法的直观概念和语言概述,当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有有

15、穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷句子的语言来讲，存在着如何给出它的有穷表示的问题。以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明(或者定义)句子的组成结构，比如汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语，我们采用第2章所介绍的EBNF来表示这种句子的构成规则：,“我是大学生”。是汉语的一个句子,句子=主语谓语主语=代词名词代词=我你他名词=王明大学生工人英语谓语=动词直接宾语动词=是学习直接宾语=代词名词,有了一组规则以后，按照如下方式用它们导出句子：开始去找=左端的带有句子的规则并把它由=右端的符号串代替，这个动作表

16、示成：句子主语谓语，然后在得到的串主语谓语中，选取主语或谓语，再用相应规则的=右端代替之。比如，选取了主语，并采用规则主语=代词，那么得到：主语谓语代词谓语，重复做下去，句子：“我是大学生”的全部动作过程是：句子主语谓语代词谓语我谓语我动词直接宾语我是直接宾语我是名词我是大学生,“我是大学生”的构成符合上述规则，而“我大学生是”不符合上述规则，我们说它不是句子。这些规则成为我们判别句子结构合法与否的依据，换句话说，这些规则看成是一种元语言，用它描述汉语。这里仅仅涉及汉语句子的结构描述。其中一种描述元语言称为文法。,英语句子,sentence subject This

18、个句子的含义每个句子和使用者的关系,有关定义和记号回顾,符号串s的头（前缀）：移走符号串s尾部的零个或多于零个符号得到的符号串. 如： b是符号串banana的一个前缀. 符号串s的尾（后缀）：删去符号串s头部的零个或多于零个符号得到的符号串. 如:nana是符号串banana的一个后缀. 符号串s的子串：从s中删去一个前缀和一个后缀得到的符号串. 如:ana是符号串banana的一个子串.,对于每个符号串s， s和两者都是符号串s的前缀，后缀和子串。符号串s的真前缀，真后缀，真子串：任何非空符号串 x,相应地，是s的前缀，后缀或子串，并且 s x 符号串的运算符号串的长度：符号串中符号的

19、个数.符号串s的长度记为|s|。的长度为0连接：符号串x、y的连接,是把y的符号写在x的符号之后得到的符号串xy 如 x=ab,y=cd 则 xy=abcd 有a = a 方幂：符号串自身连接n次得到的符号串 an 定义为 aaaa n个a a1=a, a2=aa则a0=,符号串集合：若集合A中所有元素都是某字母表上的符号串，则称A为字母表上的符号串集合。两个符号串集合A和B的乘积定义为 AB =xy|xA且yB 若集合A=ab,cde B = 0,1 则 AB =ab1,ab0,cde0,cde1使用 * 表示上的一切符号串（包括）组成的集合。*称为的闭包。上的除外的所有符号串组成的集

20、合记为+ 。 +称为的正闭包。,例：=a,b *=,a,b,aa,ab,ba,bb,aaa,aab, +=a,b,aa,ab,ba,bb,aaa,aab,文法和语言的形式定义,如何来描述一种语言？如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示如果语言是无穷的，找出语言的有穷表示。语言的有穷表示有两个途经：生成方式（文法）：语言中的每个句子可以用严格定义的规则来构造。识别方式（自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要麽能停止并回答“不是”，（要麽永远继续下去。）,文法即是生成方式描述语言的：语言中的每个句子可

21、以用严格定义的规则来构造.下面给出文法的定义.进而在文法的定义的基础上,给出推导的概念,句型、句子和语言的定义.,定义,文法G定义为四元组(VN，VT，P，S )其中VN为非终结符号(或语法实体，或变量)集；VT为终结符号集；P为产生式(也称规则)的集合； VN，VT和P是非空有穷集。 S称作识别符号或开始符号，它是一个非终结符，至少要在一条产生式中作为左部出现。 VN和VT不含公共的元素，即VN VT = 用V表示VN VT ，称为文法G的字母表或字汇表规则，也称重写规则、产生式或生成式，是形如或=的(，)有序对，其中是字母表V的正闭包V+中的一个符号，是V*中的一个符号。称为规则的左部，

22、称作规则的右部。,文法的定义,例文法G=（VN，VT，P，S）VN = S , VT = 0, 1 P= S0S1, S01 S为开始符号,推导的定义,直接推导“”是文法G的产生式，若有v,w满足：v=,w= , 其中V*,V* 则称v直接推导到w,记作 v w 也称w直接归约到v例：G： S0S1， S01 0S1 00S11 00S11 000S111 000S111 00001111 S 0S1,. . . VAR;BEGIN READ()END. VAR A;BEGIN READ( ) END.,推导的定义,若存在v w0 w1 . wn=w,(n0) 则记为v =+ w，v推导出w

23、，或w归约到v 若有v =+ w，或v=w，则记为v =* w,例：G： S0S1， S010S1 00S1100S11 000S111000S111 00001111 S 0S1 00S11 000S111 00001111 S =+ 00001111 S =* S 00S11 =* 00S11,句型、句子的定义,句型有文法G，若S =* x，则称x是文法G的句型。句子有文法G，若S =* x，且xVT*，则称x是文法G的句子。例：G： S0S1， S01S 0S1 00S11 000S111 00001111G的句型S,0S1 ,00S11 ,000S111,00001111G的句子00

24、001111, 01,例：GE： EE+T|T TT*F|F F(E)|aEE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a句子：用符号a，+，*，(和)构成的算术表达式,文法，语言的定义,由文法G生成的语言记为L(G),它是文法G的一切句子的集合: L(G)=x|S =* x，其中S为文法的开始符号，且x VT* 例：G： S0S1， S01L(G)=0n1n|n1,例文法GS：（1）SaSBE（2）SaBE（3）EBBE（4）aBab（5）bBbb（6）bEbe（7）eEee L（G）= anbnen | n1 ,S a S BE (SaSBE) a aBE

25、BE (SaBE) aabEBE ( aBab ) aabBEE ( EBBE ) aabbEE （bBbb) aabbeE （bEbe) aabbee （eEee)G生成的每个串都在L(G)中L(G)中的每个串确实能被G生成,使用产生式(1)n-1次，得到推导序列：S =* an-1S(BE)n-1，然后使用产生式(2)一次，得到：S =* an-1S(BE)n-1 an(BE)n。然后从an(BE)n继续推导，总是对EB使用产生式(3)的右部进行替换，而最终在得到的串中，所有的B都先于所有的E。例如，若n=3, aaaBEBEBE aaaBBEEBE aaaBBEBEE aaaBBBEEE

26、。即有：S =* anBnEn接着，使用产生式(4)一次，得到S =* anbBn-1En，然后使用产生式(5)n-1次得到：S =* anbnEn，最后使用产生式(6)一次，使用产生式(7)n-1次，得到：S =* anbnen 也能证明，对于n1，串anbnen是唯一形式的终结符号串,文法的等价,若L（G1）=L（G2），则称文法G1和G2是等价的。如文法G1A：A0R 与G2S：S0S1 等价 A01 S01 RA1,文法的类型,通过对产生式施加不同的限制，Chomsky将文法分为四种类型：0型文法：对任一产生式，都有(VNVT)+， (VNVT)*1型文法：对任一产生式，都有|，仅仅

27、 S除外2型文法：对任一产生式，都有VN ， (VNVT)*3型文法：任一产生式的形式都为AaB或Aa，其中AVN ，BVN ，aVT,文法的类型,例：1型（上下文有关）文法文法GS： SCDAbbA CaCABaaB CbCBBbbBADaD CBDbD DAabD,文法的类型,例：2型（上下文无关）文法文法GS：SABABS|0BSA|1,3型文法,GS： S0A|1B|0A0A|1B|0SB1B|1|0,GI：I lTI lT lTT dTT lT d,文法的类型,0型文法,四种文法之间的逐级“包含”关系,3型文法,文法和语言,0型文法产生的语言称为0型语言1型文法或上下文有关文法（

28、 CSG ）产生的语言称为1型语言或上下文有关语言（CSL）2型文法或上下文无关文法（ CFG ）产生的语言称为2型语言或上下文无关语言（ CF L ） 3型文法或正则（正规）文法（ RG ）产生的语言称为3型语言正则（正规）语言（ RL ）,文法和语言,四种文法之间的关系是将产生式做进一步限制而定义的。语言之间的关系依次：有不是上下文有关语言的0型语言，有不是上下文无关语言的1型语言，有不是正则语言的上下文无关语言。,根据形式语言理论,文法和识别系统间有这样的关系,0型文法（短语结构文法）的能力相当于图灵机，可以表征任何递归可枚举集，而且任何0型语言都是递归可枚举的 1型文法（上下文有关

29、文法）：产生式的形式为1A212，即只有A出现在1和2的上下文中时，才允许取代A。其识别系统是线性界限自动机。,带 a0 a1 a2 a3 a4 a5 a6 a7 a8 an-1 an,有限控制器,磁头,任何能用图灵机描述的计算都能机械实现，任何能在现代计算机上实现的计算都能用图灵机描述,2型文法（上下文无关文法CFG）：产生式的形式为A，取代A时与A的上下文无关。其识别系统是不确定的下推自动机。 3型文法（正规文法RG）：产生的语言是有穷自动机（FA）所接受的集合,3型文法产生的语言是有穷自动机（FA）所接受的集合.,定理设G=（VN，VT，P，S）是3型文法，则存在一个有穷自动机 M=

30、(K, , f, A, Z)，使得L(M)=L(G)有穷自动机NFA M 这样构造： = VT K= VN N, N为一个新状态,它不在VN中 A=S Z=N 对G中的形如 DtB的产生式,t为终结符或,有f(D,t)=B；对G中形如Dt的产生式， t为终结符或,有f(D,t)=N; 对VT中的每一个a ,有f(N,a)=,G： SaA|bB AbB|aD|a BaA|bD|b DaD|bD|a|b,B,A,S,a,a,a,b,b,b,a,b,D,a,b,a,b,定理已知一有穷自动机M= (K, , f, A, Z),存在有一个3型文法G = （VN，VT，P，S）,使得L(G)=L(M)

31、G 的定义： VT = VN= K S = A 若 f(D,t)=B ，则DtB在P中若 f(D,t)=B ，且B在Z中，则Dt在P中,G： SaA|bB AbB|aD|a BaA|bD|b DaD|bD|a|b,B,A,S,a,a,a,b,b,a,b,b,正规文法和正规式对上的正规式r ,存在一个RG=(VN,VT,P,S)：L(G)=L(r),初始， VT= ,S VN ，生成正规产生式 Sr (R.1) 对形如 Ar1r2的正规产生式：Ar1B Br2 BVN (R 2)对形如Arr1的正规产生式： ArB Ar1 BrB Br1 BVN (R 3)对形如Ar1r2的正规产生式:Ar

32、1 A r2 不断应用R做变换，直到每个产生式右端至多有一个VN,例 r=a(ad),Sa(ad) SaA A(ad) A(ad)B A B(ad)B B Gs: SaA A VT=a,d AaBVN=S,A,B AdB BaB BdB B,正规文法和正规式对G=(VN,VT,P,S),存在一个 =VT上的正规式r : L(r)=L(G),AxB, By A=xy AxAy A=xy Axy A=xy,正规文法和正规式,Gs:SaA|a AaAadAd A(ad)A(ad) A(ad)(ad) S=a(ad)(ad)a=a(ad)(ad)=a(ad) R=a(ad),句型、推导,GE： EE

33、+T|T TT*F|F F(E)|aEE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a EE+T E+T*F E+T*a E+F*a E+a*a T+a*a F+a*a a+a*aEE+T T+T T+T*F F+T*F F+F*F a+F*F a+F*a a+a*a,规范推导规范句型,最左（最右）推导：在推导的任何一步，其中、是句型，都是对中的最左（右）非终结符进行替换最右推导被称为规范推导。由规范推导所得的句型称为规范句型,构造语法树,GE： EE+T|T TT*F|F F(E)|aEE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a

34、*a,E EE + T E + T T E E + T T F,EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*aEE+T E+T*F E+T*a E+F*a E+a*a T+a*a F+a*a a+a*aEE+T T+T T+T*F F+T*F F+F*F a+F*F a+F*a a+a*a,E E + T T T * F F F a a a 看不出句型中的符号被替代的顺序,二义文法,若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的判定任给的一个上下文无关文法是否二义，

35、或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不可解的，但可以为无二义性寻找一组充分条件,文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同的文法G和G，其中G是二义的，但是却有L(G)=L(G)，也就是说，这两个文法所产生的语言是相同的。二义文法改造为无二义文法GE: E i GE：E T|E+T E E+E T F|T*F E E*E F （E）|i E (E) 规定优先顺序和结合律如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的。对于一个程序设计语言来说，常常希望它的文法是无二义的，因为希望对它的每个语句的分析是唯一的。,句型的分析,句型分析

36、就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。在语言的编译实现中，把完成句型分析的程序称为分析程序或识别程序。分析算法又称识别算法。从左到右的分析算法，即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号，直到分析结束。,句型的分析算法分类,分析算法可分为：自上而下分析法：从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导。自下而上分析法：从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。,两种方法反映了两种语法树的构造过程。,自上而下方法是从文法符号开始，将它做为语法树的根，向下逐步建立语法树，使语法树的结果正好是输

37、入符号串自下而上方法则是从输入符号串开始，以它做为语法树的结果，自底向上地构造语法树,(1)S cAd (2) A ab (3)A a识别输入串w=cabd是否为该文法的句子自上而下的语法分析,若S cAd 后选择(3)扩展A，S cAd cad那将会？ w的第二个符号可以与叶子结点a得以匹配，但第三个符号却不能与下一叶子结点d匹配？宣告分析失败（其意味着，识别程序不能为串cad构造语法树，即cad不是句子）-显然是错误的结论。导致失败的原因是在分析中对A的选择不是正确的。,S c A d a,(1)S cAd (2) A ab (3)A a识别输入串w=cabd是否为该文法的句子自下而上的语法分析,对串cabd的分析中，如果不是选择ab用产生式(2),而是选择a用产生式(3)将a归约到了A，那么最终就达不到归约到S的结果，因而也无从知道cabd是一个句子,c a b d c A b d a,句型分析的有关问题,1）在自上而下的分析方法中如何选择使用哪个产生式进行推导？假定要被代换的最左非终结符号是B，且有n条规则：BA1|A2|An，那么如何确定用哪个右部去替代B？2）在自下而上的分析方法中如何识别可归约的串？在分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串”,

展开阅读全文