编译原理资料

1、变量及其属性变量是对一个(或若干个)存储单元的抽象，赋值语句则是修改存储单元内容的抽象。变量除名字外,具有四个属性:作用域、生存期、值和类型1.变量的作用域：变量的作用域是指可以访问该变量的程序范围。①静态作用域绑定：按照程序的语法结构定义变量的作用域。②动态作用域绑定：按照程序的执行动态地定义变量的作用域。2.变量的生存期：一个存储区绑定于一个变量的时间区间,称为变量的生存期。数据对象：存储区和它保存的值分配：变量获得存储区的活动长度：变量所分配的存储单元的个数3.变量的值——存储区单元的内容匿名变量的访问通过指针实现变量与它的值的绑定是动态的符号常数的值不能修改变量的初始化不初始化则出错；随机；缺省值0。4.变量的类型①类型：变量的类型可以看成与变量相关联的值的类,以及对这些值进行的操作的说明。类型可用来解释变量绑定的存储区的内容(二进制位串)的意义；语言定义时,类型名通常绑定于某一个值类和某一组操作；语言实现时,值和操作绑定于某种机器二进制表示。②静态绑定：通过说明语句完成如：Pascal、Fortran③动态绑定：执行时隐式说明，且动态变化如：APLA¬5整型®A标号、转到AA¬12510一维数组 (A¬0)A[2:3]¬0二维数组 A¬B+C2、虚拟机的概念：虚拟机是由软件实现的机器3、程序单元及单元实例 1.程序单元:程序执行过程中的独立调用单元。如子程序,分程序,过程等。 2.单元表示 编译时，一个单元的源程序。 运行时，单元表示由一个代码段和一个活动记录组成，称为单元实例。 3.活动记录:执行单元所需要的信息,以及该单元的局部变量所绑定的数据对象的存储区。 4.非局部变量:一个程序单元可以引用未被本单元说明而被其它单元说明的变量。 5.引用环境:局部变量+非局部变量。 6.别名:同一单元的引用环境中有两个变量绑定于同一数据对象，称这些变量具有别名。 7.副作用的产生:对绑定于一个非局部变量的对象进行修改。 8.程序单元可以递归激活,从而一个单元可以有很多个实例,但代码段相同。不同的仅仅是活动记录。 9.静态分配和动态分配FortranPascal或C4、数据类型的作用实现了数据抽象使程序员从机器的具体特征中解脱出来提高了编程效率5、数据聚合的几种方式（6种）1.笛卡尔积N个集合A1,A2,…,An的笛卡尔积表示为A1´A2´…´An，它是一个集合,其元素为(a1,a2,…,an),aiÎ任意正多边形可表示为integer´real2.有限映像①定义：从定义域类型DT的值的有限集合，到值域类型RT的值的有限集合的函数称为有限映像。vara:array[1..50]ofchar;表示：整数1至50到字符集的有限映像②值域对象通过下标选取。③下标越界会出错，动态检查④下标可用来选取值域的多个元素⑤SNOBOL4的ARRAY构造符并不要求值域集的所有元素是同一类型的⑥DT到相应值的特定子集的绑定策略：编译时绑定(静态数组)对象建立时绑定(执行到分程序时,动态数组)对象处理时绑定(对APL，子集范围可变)3.序列①序列由任意多个数据项组成,这些数据项称为该序列的成分,且类型相同②串是序列③顺序文件的思想也是来自序列的概念,只能顺序读写4.递归若数据类型T包含属于同一类型T的成分，那么类型T称为递归类型。①允许在类型定义中使用被定义类型的名字②指针是建立递归数据对象的重要手段5.判定或判定或是一个选择对象结构的构造机制,规定在两个不同选择对象之间作出适当的选择。每一选择对象结构称为变体。例如：PASCAL的变体记录;C的联合。6.幂集类型T的元素所有子集的集合，称为幂集,记为Powerset(T),T称为基类型。应用：每次的操作对象仅仅是某个集合的子集。6、类型检查及其分类 1.类型检查：对数据对象的类型和使用的操作是否匹配的一致性检查称为类型检查 2.静态检查和动态检查 ①静态检查使程序更正确更有效②动态检查使编程方便,但影响了可读性,且降低了执行效率 3.强类型语言若一个语言允许所有的类型静态检查4.Pascal是非强类型语言 ①编译时,不能确定一个过程中的过程参数和子程序参数类型 ②Pascal的子界不能静态检查 如:a:=b+c;且a、b、c均属于子界类型1..10 ③变体记录的标识符可以在运行时改变 ④Pascal没有严格规定类型的一致性规则7、何谓类型等价：T1和T2是相容的：T1可赋给T2，T1可对应T2的形参；反之亦然。 1.名字等价：两个变量的类型名相同。 2.结构等价：两个变量的类型具有相同的结构。验证法：用用户定义类型的定义来代替用户定义名，重复这一过程，直到没有用户定义类型名为止。 3.两种相容性实现时的比较①名字等价的实现比较简单②结构等价的实现需要的模式匹配过程可能十分复杂8、语句级控制结构控制结构:程序员用来规定程序各个成分的执行流程的控制部分。语句级控制结构:语言用来构造各种语句执行顺序的机制。传统语言的三种语句级控制结构:顺序、选择、重复。9、单元级控制结构单元级控制结构:规定程序单元之间控制流程的机制四种单元级控制结构:显式调用,异常处理,协同程序,并发单元10、副作用副作用¾对非局部环境的修改①副作用降低了程序的可读性②副作用限制了数学运算律的使用。如:w:=x+f(x,y)+z③副作用影响目标代码的优化。如:u:=x+z+f(x,y)+f(x,y)+x+z11、别名别名¾在单元激活期间,两个变量表示(共享)同一数据对象①FORTRAN的EQUIVALENCE语句②Pascal的变参使得形参和实参共享同一数据对象③变参和全局变量表示同一数据对象时，也会引起别名④别名也影响编译器生成优化的代码a:=(x-y*z)+w/*若a与x、y或z中任一个b:=(x-y*z)+u是别名*/⑤别名的消除.废除可能引起别名的结构.限制使用指针、变参、全局变量、数组等12、语言的定义语言＝语法＋语义语法:用以构造程序及其成分的一组规则的集合语义:用以规定语法正确的程序或其成分的含义的一组规则的集合13、文法的定义文法是描述语言的语法结构的形式规则,必须准确,易于理解,且描述能力强文法的形式定义G=(VT,VN,S,P)例G0=(VT,VN,S,P):E→E+T|TT→T*F|FF→(E)|i显然VT={+,*,(,),i}VN={E,T,F}S=EP为上述产生式的集合14、文法的分类①0型文法:产生式形如a→b②1型文法:│α│<=│β│（S→e例外）或产生式形如αAβ→αwβ，wÎV+(上下文有关文法)③2型文法:产生式形如A→α(上下文无关文法)④3型文法:产生式形如A→α或A→αB(正则文法,右线性文法)ÎaVT15、抽象机的结构16、推导、句型、句子、语言 1.推导与归约①直接推导:αβnÞαnd即由产生式右边替换产生式左边②推导:α1Þαn、α1Þαn ③归约:推导的逆过程 举例:已知G(E)E→E+E│E*E│(E)│ii+i*i的推导过程EÞE+EÞE+E*EÞE+E*iÞE+i*iÞi+i*iEÞE+EÞi+EÞi+E*EÞi+i*EÞi+i*iEÞE*EÞE*iÞE+E*iÞE+i*iÞi+i*i设文法G=(VT,VN,S,P),若SÞα,αÎV*,则称α为文法G的一个句型。 若上述αÎVT*，则称α是一个句子，即只含终结符的句型是一个句子 文法G=(VT,VN,S,P)的句子的全体,称为由文法G产生的语言,记为L(G),即L(G)={α│SÞαÙαÎVT}17、语法树语法树（推导树）——以图的方式表示推导过程①推导树是一棵有序的标记树每个结点的标记是文法G的非终结符或终结符；标记为A的内部结点从左到右有子结点X1，X2，…,Xn,则A→X1…Xn是一个产生式;如果有结点标记为e，则它必是叶结点，且它是该父结点的唯一子结点。 G(E)E→E+E│E*E│(E)│i ②推导树的构造：例（i+i*i）EE（E）EE*EE+iiiEE（E）EE+EEiii*③推导树的边缘：一棵推导树所有叶结点的从左到右的连接。④文法的二义性：一个句子有两棵不同的推导树。④由推导树确定短语18、编译等概念翻译程序：它能够把某一种语言程序（称为源语言程序）转换成另一种语言程序（称为目标语言程序），而后者与前者在逻辑上是等价的。如果源语言是诸如Pascal、C或Java这样的“高级语言”，而目标语言是诸如汇编语言或机器语言之类的“低级语言”，这样的一个翻译程序就称为编译程序解释程序：它以该语言写的源程序作为输入，但不产生目标程序，而是边解释边执行源程序本身。19、词法分析器的功能扫描源程序的字符串,按照词法规则,识别出单词符号作为输出;对识别过程中发现的词法错误,则输出有关的错误信息。20、状态转换图状态转换图的定义有限的有向图有向边上标记字符唯一初态若干终态（至少一个）21、左递归的消除(1)直接左递归的消除P→Pα│β改写为:P→bP＇P＇→αP＇│ε一般地A→Aa1|Aa2|…|Aam|b1|b2|…|bn（ai¹ε，bj不以A开头）改写为:A→b1P’│b2P’│...│bnP’P’→a1P’│a2P’│...│amP’│ε(2)间接左递归的消除PÞPα(a)将文法G的所有非终结符按任一给定的顺序排列,设为A1,A2,…An;(b)消除可能的左递归;fori:=1tondobeginforj:=1toi-1do把一个形如Ai®Aja的产生式改写为Aid®1a|d2a|…|dka其中Ajd®1|d2|…|dk是Aj的所有产生式;消除Ai产生式的直接左递归end(c)化简以S→Qc│cQ→Rb│bR→Sa│a为例,按S,Q,R排列,或R,Q,S排列按S、Q、R排列,代入后S→Qc│cQ→Rb│bR→Rbca│bca│ca│a消除R中的直接左递归R→bcaR’│caR’│aR’R’→bcaR’│e文法产生的语言:(bca|ca|a)(bca)*bc|bc|c按R、Q、S排列,代入后R→Sa│aQ→Sab│ab│bS→Sabc│abc│bc│c消除S中的直接左递归S→abcS’│bcS’│cS’S’→abcS’│e文法产生的语言:(abc|bc|c)(abc)*22、FIRST集、FOLLOW集，预测分析表的构造1．FIRST集定义:对αÎ(VTÈVN)*,有FIRST（α）＝{a|αÞa...,aÎVT}若αÞε,则εÎFIRST(α)α=X…XÎVT,则FIRST(X)={X};XÎVN,分三种情形:X®a…X®Y…X®Y1Y2…Yk练习：X®Y1Y2AY1®y1│eY2®y2│eA®aFIRST(Y1)={y1,e}FIRST(Y2)={y2,e}FIRST(A)={a}FIRST(X)={y1,y2,a}2.FOLLOW集(1)定义:对AÎVN,有FOLLOW(A)={a│SÞ...Aa...,aÎVT}若SÞ...A,则#ÎFOLLOW(A),其中S为开始符号(2)求法#ÎFOLLOW(S)A→αBβ:将FIRST(b)-{e}加入FOLLOW(B)A→αB或者A→αBβ且βÞε:将FOLLOW(A)加入FOLLOW(B)注意:求FOLLOW(B)实际上是考察B在产生式右端的每一次出现FIRSTFOLLOWE(i)#E’+e)#T(i+)#T’*e+)#F(i*+)#例:G(E)E→TE’E’→+TE’│εT→FT’T’→*FT’│εF→(E)│i23、短语、直接短语、句柄短语:设αβd是上下文无关文法G的一个句型,如果有SÞαAd,并且AÞβ,则称β是句型αβd关于非终结符A的一个短语,或称β是句型αβd的一个短语 直接短语（简单短语）：AÞβ 句柄：一个句型的最左直接短语 例:G(E)E→E+T|T T→T*F|F F→(E)|i 求E+T*F的短语、直接短语、句柄 EÞE+TÞE+T*F 因为EÞE+T且TÞT*F，所以T*F是关于T的短语 因为E=E且EÞT+T*F,所以T+T*F是关于E的短语直接短语:T*F句柄:T*F 例:G(E)E→E+T|T T→T*F|F F→(E)|i 求T*F+i的短语、直接短语、句柄 EÞE+TÞT+TÞT*F+TÞT*F+FÞT*F+i 因为E=E且EÞT*F+i，所以T*F+i是关于E的短语 因为EÞT＋T且TÞT*F，所以T*F是关于T的短语、直接短语、句柄 为EÞE＋T且EÞT*F，所以T*F是关于E的短语 因为EÞT*F+T且TÞi，所以i是关于T的短语 为EÞT*F+F且FÞi，所以i是关于F的短语、直接短语 短语:有终结符的短语，并且它的真子传不具有这个特性 最右推导（规范推导） 最左推导24、FIRSTVT集、LASTVT集，优先关系表的构造(1)FIRSTVT集FIRSTVT(P)={a|PÞa…,或PÞQa…,aÎVT,QÎVN}若P®a…或P®Qa…,则aÎFIRSTVT(P);若P®Q…,则FIRSTVT(Q)ÍFIRSTVT(P);直至FIRSTVT(P)不再增大。(2)LASTVT集LASTVT(P)={a|PÞ...a,或PÞ…aQ,aÎVT,QÎVN}若P®...a或P®…aQ,则aÎLASTVT(P);若P®...Q,则LASTVT(Q)ÍLASTVT(P);FIRSTVTLASTVTE(i+*)i+*T(i*)i*F(i)i直至LASTVT(P)不再增大例G(E)E→E+T│TT→T*F│FF→(E)│i（3）求FIRSTVT集的矩阵规则若P®a…或P®Qa…,则M[P,a]:=1;若P®Q…,则对所有的M[Q,a]=1置M[P,a]:=1;重复上述两步，直到M矩阵不再变化。（4）求LASTVT集的矩阵规则若P®…a或P®…aQ,则M[P,a]:=1;若P®…Q,则对所有的M[Q,a]=1置M[P,a]:=1;重复上述两步，直到M矩阵不再变化FIRSTVT+*i()E1111T111F11LASTVT+*I()E1111T111F11例G(E)E→E+T│TT→T*F│FF→(E)│i(5)构造优先关系表的算法FOR每条产生式P®X1X2…XnDOFORi:=1TOn-1DOBEGINIFXi和Xi+1均为终结符THENXi=Xi+1;IFi<=n-2且Xi和Xi+2均为终结符但Xi+1ÎVNTHENXi=Xi+2;IFXiÎVT,Xi+1THEN"aÎFIRSTVT(Xi+1)Xi<a;IFXiÎVN,Xi+1ÎVTTHEN"aÎLASTVT(Xi)a>Xi+1END;FIRSTVTLASTVTE(i+*)i+*T(i*)i*F(i)i例G(E)E→E+T│TT→T*F│FF→(E)│i+*i()#+><<<>>*>><<>>i>>>>(<<<<=)>>>>#<<<<=考察E→E+T中的E和+、+和T考察T→T*F中的T和*、*和F考察F→(E)中的(和E、(和)、E和)算符优先关系表25、何谓语法制导翻译为每个产生式配上一个语义子程序,在语法分析过程中,当用一个产生式进行匹配或归约时,就调用相应的语义程序。上述语义子程序既可能包含了语义检查,也可能包含了语义处理,其核心是为了生成相应的中间代码。26、某些语句翻译后的中间代码序列27、数据参数传递的几种方法 1.引用调用（传地址） 将实参的地址传递给相应的形参 在单元中对形参的引用