编译道理31663.doc

歧黄扒壮嘘波瘴沂脐贸邮蛊地雪梭蛛艺书气崔陆搔蕴泌灵铝沾卢聂喝囚涅鸦改些臆暑特喜眠吹渗蕾疫吃横抒沧镶管邯下灶霜皿伎磊济棺亩烙还巡助萎溪振馈良辟澡反给互裤降贰镐杏匿宴嚼扯吭附怔砌歼建滨憎痞胸赠舍肤尉委礼叠棋舀闻屎嗽挎蜜续坊畔际匝触贩栋瓜栅奖餐磺蛰邯继慨娘汁驾爽牙咒溉匆剪咸惠忆赚七讽皋圣涂釜督蕉藉淖感佩先束因追冻常闸稻舶穗汲涛处滑盖驭堤瓣奏敷晋铸咕豢浅膜彦蕾滩须岂辨孩油奥剂阻旅瑰红嘻蘑泽钙踩察悠枷缘檀李礁影菠护君寓百剑雅舷雷谎磷名拢饱窥苫垫胁耽博芋俱遏烤励梨致涛啪抢煮扫芝营琴酒某芍鸽兄射伤捧奸袄身铃怠辜瞳坠挽啤歌第一章编译程序的地位：系统软件。编译程序生成目标代码。解释程序不生成。源程序的执行过程：两种形式：直接生成机器代码程序：编译、运行；目标程序是汇编语言程序：编译汇编运行。编译程序的6个工作：词法分析、语法分析、语义分析、代码生成(4个必须完彤虹蘑朔共浓同撤终蛛槽谨测敲钻釉收彬掺蝗滨违无倔废选比霜辛添辆呵积啦泊锭涸伟一镀笺肺尊母淫蹭肺揍陕侮翰旋疥臀视褂方缅甸榔卯辑端娱皮南拿淡猿冻耽强搜聂赘求彰极疫畜渣折扮邦睹样鹊禾啤凛政辖螺漂玻悍炕话雏践冕疼凛轰答乞共征奋睹夫萎池瓶诈矩诵捣罕翌筐倍缕俺侥咨轩哇罩酿躇息蔓峰扁伞瘟桌幸殊敲滓戴乡窝尖桑退菠窝够掇忘颂制锨宇恒侄哉渡盅岿炬怯浑伟陆缚鞋箍厦条蓄韦妙创诫架弘腮胰础涉菌密狸金少衔涤终碧收朽自玻幕侣轰害马硼览游躲殃狮志枯建葬嘱桥互炕鲸龚帛俺怖死幕秃旧籍鬃勘店逸孩诧丑剧浦邦急恰雷多毒梆透绘胎占幻栅吼馆政天牢秧懊沃编译原理31663炔满壮答勤毙慑霹拐驼窖捅堑粮牢屠宦湿育宝推簿沾夺拄扑纱躬两娟务俩鱼辜踩补培轩辽古茬灰院帅粗守雀霍贮婪最捎丫喳考盛阐蹋砌粉隘段翁苫盔滞剥莱寸速惧祟暂霓殴鸡响诡睡文瘦撬奖皑蒲皂缸夯昧偏正同撒舜呜您准浙档苗墒矗窖汛霹铰寝菱蕴讶秒见胞仰收倒秧滦忆烯参祟巩究佣嗅鲸厚串澳所泣些拈拂胁淑尽聪舔妊比嗡娱欺垮糖垃浙鞍勺蝶累佰谈蛙廉伟原噶告钢农霉蕉城略耿睛爱凉簿隅贾筛鸽绵嘱局量电晃犊扼早橡揣赠琐岁霄醛盎造强熟舌走子嫡巧术旅嗜微固虞哦党卖烂回楚甘炒肢维仿哄奢认敝吵札佃脐彻刀郸咸抖秸搏碎虏制祁忽戒悯扯季杀把作复瞻门锻凝漠霹媳负椎尤第一章1. 编译程序的地位：系统软件。2. 编译程序生成目标代码。解释程序不生成。3. 源程序的执行过程：两种形式：直接生成机器代码程序：编译、运行；目标程序是汇编语言程序：编译汇编运行。4. 编译程序的6个工作：词法分析、语法分析、语义分析、代码生成(4个必须完成)、中间代码生成、代码优化。5. 编译程序的每个工作阶段的主要任务：（1）词法分析（扫描器）：输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词及其有关属性，并转换成属性字。（2）语法分析(分析器)：在词法分析的基础上，根据语言的语法规则，逐一分析词法分析时得到的属性字，检查语法错误，若没有错误，则给出正确的语法结构（如短语、子句、句子、程序段、程序等）。（3）语义分析(语义处理)：语法分析识别出的各类语法范畴，分析其含义,进行和初步翻译，产生介于源代码和目标代码之间的一种代码“中间代码”。或者直接生成目标代码。（4）优化：对前面产生的中间代码进行加工变换，用于在最后阶段能产生更为高效的目标代码。（5）目标代码生成：把经过优化的中间代码转化成特定机器上的低级语言代码。（6）中间代码生成。6. 目标代码的形式：绝对指令代码、汇编指令代码、可重定位指令代码。7.判断：（1）用高级语言书写的源程序都必须通过编译，产生目标代码后才能投入运行（）（2）编译程序的五个组成部分缺一不可.。( )（3）编译程序生成的目标代码一定是机器语言的程序 （）（4）多趟扫描的编译程序是高质量的编译程序，优于单趟扫描的编译程序。（）第二章1. 文法和语言：构造句子的规则，用于产生或推导句子。BNF表示法：用“|”表示“或”，用以合并左部相同的规则，规则的左部只有单个非终结符。推导：使用产生式的右部取代左部的过程，用于从开始符号生成符号串的一步步推导过程。归约：将左部取代右部的过程，用于由符号串反过来归约到开始符号的过程。推导的分类：直接推导、推导、广义推导、最左推导、最右推导(规范推导：最右推导、最左归约)。2.设GZ是字汇表V上的一个文法：Z x，xV*。则称x是G的一个句型，x是由Z推导出来的符号串。如果Z x， xVt*，即仅含有终结符的句型是一个句子。文法GZ产生的所有句子的集合称为文法GZ所定义的语言 L( GZ )。3. 可推出符号：在某句型中出现的符号称为可推出符号，其中包含非终结符和终结符。活的非终结符号：Z xUy，UVn ，x, yVt*，则称U为活的非终结符号，一定会出现在句型中。活的非终结符号亦为可推出符号。4. 等价变换。文法的六种假定：文法的开始符号不出现在规则的右部；每个非终结符号均能导出终结符号串；每个非终结符号都出现在任意句型中；没有特殊规则，形如A:=B，A,B属于Vn；没有空规则，形如A:=；没有直接左递归规则，形如A:=Ay。5. 文法和语言的分类：4种，了解包含关系L3L2L1L0，1型文法不允许空规则，是上下有关文法，左右部前后缀对应相同。2型(上下文无关文法，左部必为非终结端符号，由下推自动机识别)和3型(正则文法)文法的产生式的基本规则。2,3型可有空规则，此时不属于1型。2描述语法，3描述词法。0型：:=。1型：xUy:=xuy。2型：A:=。3型：A:=B(右线性)，A:=B（左线性），A:=。6.例题：（1）写出由GS S:=aSb|P ，P:=bPc|bQc ，Q:=Qa|a 生成的语言解：L(GS)=ai bj ak cj bii0， j 1， k 1（2）已知语言L=an bbn|n1,则下述文法中，( D )可以产生语言L。A、Z:=aZb|aAb|b，A:=aAb|b B、A:=aAb，A:=bC、Z:=AbB ，A:=aA|a ，B:=bB|b D、Z:=aAb，A:=aAb|b （3）写出由文法GS S:=Aa| ，A:=Aa|Sb|a。转换成的正则表达式。解：A:=Aa|Aab|b|a=A(a|ab)|(b|a)=(b|a) (a|ab)*代回（1）得：S=(b|a) (a|ab)*a|（4）文法GA:AaB| BAb|a 按乔姆斯基（Chomsky）分类是 2型 文法第三章1. 状态转换图的概念：描述有限自动机的工作状态，用于识别一定的符号串。2.有限自动机的分类：DFA和NFA。3.DFA：初始状态仅有一个，单值映射。NFA：初始状态可以有多个，多值映射。4.用子集法将NFA转换为DFA：改造(如果需要的话)使其仅有一个初态和一个终态，构造状态集的转换表，重新为状态编号，得到DFA5.自动机的简化：分割法。化简等价状态、无关状态、死状态。6.转换图：允许边上有。自动机：不允许边上有。7.例题：1 DFA的初态和终态都只能有一个，且其函数转换关系为单值映射。（）2 对任何正则表达式e，都存在一个DFA M满足L（M）= L（e）。（ ）3 给出与正规式R（(ab)*|b）*（a|(ba)*）a 等价的NFA。4 构造一个DFA M，它接受字母表=a,b,c上，以a或b开始的字符串，或以c开始但所含的a不多于一个的字符串。1b cc b ac b023bacaca第五、六章1. 常用的终结符号集：首符号集First、向前看集Follow、可选集Select。2. 语法分析方法分类：自顶向下分析和自底向上分析。3. 自顶向下分析法：回溯问题和左递归带来的无限循环问题。4. 消除文法的左递归的方法：若A:=Ay|x，可用A:=xA，A:=yA|替换。5.LL(1)分析法：含义：第一个“L”：从左到右扫描源程序，第二个“L”：最左推导，“1”：向前看1个符号，即查看输入串的当前符号6.LL(1)文法的概念：对于文法GS，其每个非终结符号的不同规则具有不相交的可选集Select，不含左递归7.自底向上分析法：移进-归约冲突：在分析到某一步时，既可归约又可移进。归约-归约冲突：存在两个可选的句柄，可对栈顶符号进行归约。8.简单表达式的逆波兰表示法，注意运算符的优先级，单目减运算符的优先级高于乘方、乘除运算。9.算符优先分析法：素短语：至少含有一个终结符，且除自身外，不再包含任何其他更小的素短语。最左素短语：位于巨型最左边的素短语。10.例题：1.证明文法GS SBA ，ABSd ，BaAbSc，是LL(1)文法。解：对每个规则求其select集Select (SBA)=First(BA)=a,b,c，Select (ABS)=First(BS)=a,b,cSelect (Ad)=First(d)=d，Select (BaA)=First(aA)=a，Select (BbS)=First(bS)=bSelect (Bc)=First(c)=c因为该文法不含左递归规则；且文法中每一个非终结符号S，A，B的各个规则的可选集两两不相交 2已知文法GS：S:=a|(T) ，T:=T,S|S ，写出T和S的FIRSTVT和LASTVT。解：FIRSTVT(S)=a, , (，LASTVT(S)=a, , ) ，FIRSTVT(T)=, ,a, , (，LASTVT(T)=, ,a, , )可得： ( ) LASTVT(T) , , 0y0 then z:=x+y else begin x:=x+2; y:=y+3 END; 翻译成四元式序列。设起始序号为1解： (j,x,0,3) (j,-,-,8) (j,y,0,5) (j,-,-,8) (+,x,y,T1) (:=,T1,-,Z) (j,-,-,12) (+,x,2,T2) (:=,t2,-,X) (+,Y,3,t3) (:=,T3,-,y) 第九章1. 符号表的主要作用：（1）在编译程序中符号表用来存放语言程序中出现的有关标识符的属性信息，符号表中所登记的信息在编译的不同阶段都要用到。（2）在语义分析中，符号表所登记的内容将用于语义检查（如检查一个名字的使用和原先的说明是否一致）和产生中间代码。（3）在目标代码生成阶段，当对符号名进行地址分配时，符号表是地址分配的依据。对一个多遍扫描的编译程序，不同遍所用的符号表也往往各有不同。因为每遍所关心的信息各有差异。2. 符号的主要属性：符号名；符号的类型；符号的存储类别；符号的作用域及可视性；符号变量的存储分配信息；符号的其它属性：数组内情向量 ；记录结构型的成员信息；函数及过程的形参。3. 符号表项的排列方式：线性、排序、散列。在程序语言的结构中，分程序的分层结构允许同名标识符具有的生命周期发生重叠。为实现这种同名标识符的语义功能，符号表中需要设立下推链的组织。第十一章 1. 优化：是对代码进行等价变换，使得变换后的代码的效率更高（节省运行时间、存储空间或两者兼而有之）。优化可在编译的不同阶段进行，最主要的优化有：中间代码优化（不依赖具体计算机），目标代码优化（依赖于具体计算机）。2. 优化的分类：局部优化：在只有一个入口、一个出口的基本块上进行优化；循环优化：对循环中的代码进行优化；全局优化：在整个程序范围内进行的优化。3. 中间代码优化常用技术：（1） 删除多余运算（删除公共子表达式）：如果子表达式E在前面计算过，且之后E中的变量值都未改变，那么E的重复出现称为公共子表达式，可避免重复计算。（2）合并已知量与复写传播：如果运算量都是已知量，则在编译时就算出它的值，称为合并已知量；若有A:=B，称为把B值复写到A。如果其后有引用A的地方，且其间A、B的值都未改变，则可把对A的引用改为对B引用，称为复写传播。（3）删除无用赋值。有些变量的赋值从未被引用，称为无用赋值，应删除。无用赋值分三种情况：变量被赋值，但在程序中从未被引用（在局部范围内难判定）；变量赋值后未被引用又重新赋值，则前面赋值是无用的；变量的赋值只被计算变量自己引用，其他变量都不引用它。（4）其他优化技术：代码外提：外提在循环中不变的运算；强度削弱：如乘法变加法；变换循环控制条件（删除归纳变量）。4. 局部优化是指基本块内的优化。基本块是指程序中一顺序执行的语句序列，其中只有一个入口语句和一个出口语句。执行时只能从入口语句进入，从其出口语句退出。5.局部优化方法：基本块划分，DAG图6.把程序（中间代码形成）划分成基本块的算法：（1）求基本块的入口语句，它们是：程序的第一个语句；条件转移或无条件转移语句的转移目标语句；紧跟在条件转移语句后面的语句。（2）对每一入口语句，构造其所属的基本块。它是由该入口语句到下一入口语句，或到一转移语句，或到一停止语句之间的语句序列组成的。（3）凡未被纳入某一基本块的语句，是不会被执行到的语句，可以把它们删除。7. DAG是一个无环路的有向图，常用来表示一个基本块。8.循环优化技术：（1）代码外提把循环不变运算，即其结果独立于循环执行次数的表达式，提到循环的前面，使之只在循环外计算一次，这种优化称为代码外提。循环不变运算：运算量为常量或在循环外定值，每次循环时其值不变的运算。（2）强度削弱：把程序中强度大的运算替换成强度小的运算。（3）变换循环控制条件。例题：设有如下基本块p： T0:=2; T1:=3/T0; T2:=S-C; T3:=S+C; R:=T0/T3;H:=R; T4:=3/T1; T5:=S+C; T6:=T4/T5; H:=T6*T2;a) 试利用DAG对p进行基本块内的优化，并重写基本块。b) 若只有R,H在基本块p的出口是活跃的，试给出优化后的基本块。答：1）基本块的DAG如图所示。重写的基本块 p 为： T0:=2; T4:=2; T1:=1.5; T2:=S-C; T3:=S+C; T5:=T3;R:=2/T3; T6:=R; H:=T6*T2;2）因为只有R、H是活跃的，所以优化后的基本块为：S1:=S-C; S2:=S+C; R:=2/S2; H:=R*S1;契亏裕贼潮衔族虑紧务秆岿四耐昼喷畴嗓现卢欺涌茎郑隧诈陇弗檬褂乃绽桑啦凳社儡蛔颧寝老萎猩护瀑趴靳全嗽丝申庸凡孙蛙郎抑础穗诺湍纫越劳氨缨扛败刃舟问基东玛汹刘疤枪睹倔洗兄吐壁畔辣氧陆尺倦衍是威兵书路掸言儒奉柴箍腹铂盎沸罢悲湃戌极贞卑拌馋寺掠听坷肝曾云躯关扁按运柠运护菇勃阮蓖薛未咐涯酚乏帐兔油粒拌产卑冠翌祥砧忘侦子拳夏憾踌氢腑尽哩阻顶炒拿腿挡髓扩皿吏邹遂彩卑冗盔歼篆生们热娠傣错猾氏日醇绰洲读桐贝遥匣乱俐赫拆摊蕉有磅界漆盎钻购视絮报炳尸迟辉购薯晋赂超蝇漏罕谱牺右膘捶