《编译原理》期末复习完全手册（直接使用版）

《编译原理》期末复习完全手册（直接使用版）第一部分：考试题型与分值分布（通用）题型题量分值主要考查范围策略选择题20-25题20-30分编译阶段划分、正则表达式与自动机、文法分类、LL(1)/LR冲突、中间代码形式、优化种类等辨析概念，牢记各种分析方法特点填空题10-15题10-15分FIRST/FOLLOW定义、规范推导概念、寄存器分配原则、常见优化名称熟记关键术语和算法步骤判断题10题10分概念正误辨析注意绝对化表述简答题4-5题20-25分编译阶段功能、NFA→DFA、递归下降/预测分析比较、LR分析过程、中间代码形式与生成、代码优化技术分点作答，条理清晰综合/计算题2-3题15-25分正则表达式→NFA/DFA、消除左递归与提取左公因子、求FIRST/FOLLOW集、构造LL(1)分析表或LR(0)/SLR(1)项目集规范族、语法制导翻译、DAG优化与目标代码生成按步骤规范作答，书写清晰第二部分：编译系统结构速查2.1编译程序工作阶段阶段输入输出主要任务词法分析源程序字符串单词（Token）序列识别标识符、常量、关键字等，去除注释空白语法分析单词序列语法分析树（推导）根据文法规则检查语法结构语义分析语法树带有语义信息的语法树类型检查、表达式的类型转换等中间代码生成语义分析结果中间表示（三地址码、四元式）生成与目标机无关的中间代码代码优化中间代码优化后的中间代码提高效率，如公共子表达式删除、循环优化目标代码生成优化后中间代码目标机器代码寄存器分配、指令选择符号表管理各阶段贯穿始终记录标识符信息（名字、类型、作用域等）错误处理各阶段错误信息定位并报告错误第三部分：词法分析速查3.1正则表达式（正规式）运算含义例子闭包（*）零次或多次重复a*表示ε,a,aa,aaa...正闭包（+）一次或多次重复a+表示a,aa,aaa...可选（?）零次或一次a?表示ε或a选择（）两者之一3.2有限自动机类型特点NFA允许空边ε、同一状态对同一输入可有多个转移DFA任何状态对每个输入符号恰有一个转移，无ε边NFA→DFA转换：子集构造法（求ε-闭包→移动→构造状态子集对应DFA状态）。DFA化简：等价状态划分法。第四部分：语法分析速查4.1上下文无关文法（CFG）四元组：G=(VN,VT,P,S)推导：最左推导、最右推导（规范推导）句型、句子、语言二义性：一个句子对应两棵不同语法树，则文法二义4.2自上而下分析：LL(1)文法要求：无左递归，无回溯（同一非终结符的各候选式FIRST集两两不相交，且若某候选式可推出ε，则其FIRST与FOLLOW不相交）。FIRST(α)：可从α推导出的首终结符号集。FOLLOW(A)：非终结符A后紧跟的终结符号集。LL(1)分析表构造：对每个产生式A→α，若a∈FIRST(α)，则M[A,a]=该产生式；若ε∈FIRST(α)，则对任何b∈FOLLOW(A)填入该产生式。消除直接左递归：A→Aα|β改写为A→βA'，A'→αA'|ε提取左公因子：A→αβ|αγ改写为A→αA'，A'→β|γ4.3自下而上分析：LR分析法移进-归约分析，使用分析栈。规范归约（最左归约=最右推导的逆过程）。句柄：句型中可归约的子串。LR分析器：驱动程序+分析表（ACTION表+GOTO表）。LR(0)项目集规范族构造：闭包运算+转移函数。

SLR(1)：利用FOLLOW集解决冲突。

LR(1)：增加展望符，提高分析能力。

LALR(1)：合并LR(1)同心集，兼具能力和效率。冲突类型：移进-归约冲突、归约-归约冲突。第五部分：语法制导翻译与中间代码生成5.1语法制导定义（SDD）综合属性：由子结点属性计算父结点属性（自底向上）。继承属性：由父结点或兄弟结点属性计算（自顶向下）。S-属性定义：只使用综合属性，适合自底向上分析。L-属性定义：综合属性+限制的继承属性，适合LL或深度优先遍历。5.2中间代码形式形式表示示例三地址码（TAC）x=yopzt1=b+c四元式(op,arg1,arg2,result)(+,b,c,t1)三元式(op,arg1,arg2)无result，用编号引用间接三元式在三元式基础上增加间接表布尔表达式翻译：回填技术，记录真出口和假出口链。控制流语句翻译：if-else、while循环生成带有标号的三地址码。第六部分：运行时存储空间组织速查6.1存储分配策略策略特点适用静态分配编译时确定数据空间，运行时不改变Fortran等栈式分配活动记录压栈，支持递归C/C++等过程式语言堆式分配动态申请释放malloc/free，new/delete6.2活动记录（AR）内容（高地址→低地址）：参数、返回地址、控制链（动态链/静态链）、局部数据、临时变量。

访问非局部变量：使用静态链（访问链）。第七部分：代码优化与目标代码生成速查7.1优化分类类型说明局部优化基本块内：公共子表达式删除、复写传播、死代码删除循环优化代码外提、强度削弱、归纳变量消除全局优化跨基本块，基于数据流分析7.2基本块与流图基本块：顺序执行，唯一入口唯一出口的语句序列。流图：以基本块为结点，控制流为边的图。7.3DAG优化用有向无环图（DAG）表示基本块内计算，自动删除公共子表达式和进行复写传播。7.4目标代码生成指令选择、寄存器分配（图着色法）、指令调度。依赖活跃变量分析和可用表达式分析。第八部分：高频选择题题库（50题）模块一：编译概论与词法题号题目ABCD答案1编译程序各阶段中，与目标机无关的阶段不包括词法分析语法分析中间代码生成目标代码生成D2词法分析器的输入是单词源程序字符串语法树中间代码B3正规式(ab)*a描述的语言是所有以a结尾的a,b串所有以b结尾的串所有a,b串以a开头4NFA与DFA的主要区别是NFA可有多余1个终态DFA可有空边NFA对一个输入可有多个下一状态DFA可有多个初态C5词法分析中，识别标识符最适合用正则表达式+DFA文法分析算符优先LR分析A模块二：语法分析基础题号题目ABCD答案6上下文无关文法的四个组成部分不包括非终结符集终结符集产生式集状态集D7最右推导也称为规范推导最左推导直接推导句型推导A8一个文法如果有两个不同的最左推导对应同一句子，则文法无二义有二义性是LL(1)是LRB9自上而下分析需要消除左递归和提取左公因子是为了避免回溯减少状态加快速度消除二义A10左递归文法使递归下降分析器陷入死循环栈溢出回溯冲突A模块三：LL(1)与FIRST/FOLLOW题号题目ABCD答案11FIRST(α)的含义是α推导出的首终结符号集α推导出的句子集合α的句型集合α的终结符集合A12在求FOLLOW(A)时，若有产生式B→αAβ且β可推出ε，则FOLLOW(A)仅含FIRST(β)FOLLOW(A)=FOLLOW(B)将FOLLOW(B)加入FOLLOW(A)FOLLOW(A)不变C13LL(1)分析表M[A,a]中若有两个产生式，则文法一定是二义的不是LL(1)是LL(1)可重写为LL(1)B14预测分析时，遇到栈顶为非终结符，则移进按输入符号查分析表展开归约接受B模块四：自下而上分析（LR）题号题目ABCD答案15移进-归约分析中，可归约的符号串称为短语直接短语句柄素短语C16LR(0)项目A→α•表示已分析完α，可归约刚分析完α前一个符号将分析α出错A17SLR(1)与LR(0)的区别在于SLR(1)考虑展望符SLR(1)用FOLLOW集解决冲突SLR(1)状态多SLR(1)不需要ACTION表B18一个文法若是LR(1)的，则必定是LALR(1)SLR(1)LL(1)以上都不一定D19LR分析器核心的分析表包括ACTION表和GOTO表FIRST表FOLLOW表项目集A模块五：语法制导与中间代码题号题目ABCD答案20由子结点的属性计算父结点属性的方式是继承属性综合属性传递属性外部属性B21三地址码x=yopz对应的四元式为(op,x,y,z)(op,y,z,x)(x,y,op,z)(op,y,x,z)B22布尔表达式翻译时，常用什么技术记录跳转目标回填条件转移标号循环A23用于翻译while语句的中间代码中，通常包括标号和条件/无条件跳转只计算表达式只跳转函数调用A24语法制导定义中，S-属性定义允许继承属性只能综合属性综合和继承都行无属性B模块六：运行时存储题号题目ABCD答案25支持递归调用的存储分配策略通常是静态分配栈式分配堆分配寄存器分配B26活动记录中存放调用者返回地址的字段是控制链访问链返回地址参数C27访问非局部变量时，若允许嵌套过程，通常使用动态链静态链（访问链）基址寄存器变址寄存器B模块七：优化与目标代码题号题目ABCD答案28基本块内的公共子表达式删除属于局部优化循环优化全局优化机器相关优化A29循环不变量外移属于局部优化循环优化全局优化不可优化B30代码外提、强度削弱主要是针对基本块循环整个程序函数B31把x=x+0优化为不变属于复写传播死代码删除无用代码删除代数化简D32DAG在基本块优化中主要用于删除公共子表达式代码外提强度削弱寄存器分配A33目标代码生成时，寄存器分配采用先进先出图着色栈队列B模块八：综合题号题目ABCD答案34编译程序中，错误处理只在词法阶段只在语法阶段贯穿所有阶段只由语义阶段完成C35已知文法G[S]:S→aAbB,A→cAd,B→cBd，则该文法是LL(1)不是LL(1)36在LR分析过程中，ACTION[s,a]=“移进s1”表示将状态s1压栈，输入指针前进归约接受出错A37递归下降分析法属于自下而上自上而下LR算符优先B38规范归约是指最左归约最右归约直接归约任意归约A39下列关于L属性定义的说法正确的是只能使用综合属性可以使用继承属性但有约束必须使用LR分析不能用于自底向上B40在优化中，将循环中的乘法变为加法是代码外提强度削弱删除归纳变量复写传播B41生成中间代码时，为临时变量命名通常使用原变量名使用符号表中序号编译器产生新临时名保留字C42对于if(E)S1elseS2，若E为假跳转到S2的开头，则E的真出口跳转到S1开头跳转到S2之后顺序执行S1无定义C43表达式a+b*c的三地址码序列通常为t1=b*c;t2=a+t1t1=a+b;t2=t1*ct1=a*c;t2=t1+bt1=b+c;t2=a+t1A44符号表中存放的信息不包括名字类型作用域优化级别D45下列优化技术中，哪些可以删除无用赋值死代码删除复写传播后可能造成死代码两者均可均不可C46活动记录中，动态链指向调用者的活动记录直接外层过程的活动记录堆区代码区A47在SLR(1)分析中，若项目集I含有A→α•和B→β•，则冲突时使用前瞻符FOLLOW(A)和FOLLOW(B)交集为空则无冲突优先规则最长匹配B48文法G:E→E+TT,T→T*FF,F→(E)id，该文法是二义无二义，非SLR49将NFA确定化为DFA时，DFA的状态对应于NFA的状态集一个状态ε闭包终态A50下列关于编译阶段的说法正确的是词法分析输出语法树语义分析生成中间代码代码优化等价变换中间代码目标代码生成可忽略寄存器分配C第九部分：填空题高频考点（直接背诵）序号题目答案1编译程序的工作阶段：词法分析、语法分析、语义分析与中间代码生成、____、目标代码生成。代码优化2词法分析器的输出是____序列。单词（Token）3若正规式R=a(ab)*，则其描述的语言是以____开头的串。4NFA与DFA的主要区别在于NFA允许____和同一输入到达多个状态。ε边5自上而下分析中，要实现不带回溯的分析，必须消除左递归和____。提取左公因子6FIRST(α)是从α出发推导出的所有____的集合。首终结符号7FOLLOW(A)是在句型中紧跟在非终结符A后面的____符号集合。终结8规范归约即是最____归约。左9LR分析法中，句柄总是出现在____的顶部。栈10一个LR(0)项目A→α•aβ称为____项目。移进11SLR(1)利用____集来解决LR(0)的移进-归约冲突。FOLLOW12语法制导定义中，由父节点属性计算子节点属性的是____属性。继承13三地址码中，x=yopz对应的四元式表示为(op,y,z,____)。x14递归过程调用通常采用____式存储分配。栈15活动记录中，指向调用者活动记录的指针叫____链。动态（控制）16基本块优化常用____图来删除公共子表达式。DAG（有向无环图）17循环不变量外移属于____优化。循环18强度削弱是指用执行速度更____的操作代替原操作。快19寄存器分配常用的方法是____着色。图20符号表贯穿编译全过程，管理标识符的____、类型、作用域等信息。名字第十部分：判断题速记（15题）序号题目答案1词法分析器的输入是单词符号序列。错（输出是单词序列）2任意正规式都存在与之等价的DFA。对3上下文无关文法可以描述任何语言。错4规范推导就是最左推导。错（规范推导是最右推导）5一个文法是二义的，则一定存在某个句型有两个不同的最左推导。对6消除直接左递归后，文法的语言会改变。错7LL(1)文法一定没有左递归和回溯。对8LR分析法是自上而下分析法。错（自下而上）9算符优先分析法是一种LR分析法。错10任何LR(0)文法都是SLR(1)文法。错11S-属性定义适合在自底向上分析时计算。对12三地址码是中间代码的一种形式。对13所有优化都在目标代码生成之后进行。错14基本块内优化属于局部优化。对15递归调用必须使用静态存储分配。错（栈式）第十一部分：名词解释高频考点名词定义编译程序将高级语言源程序翻译成目标机器语言程序的系统软件。词法分析扫描源程序字符串，识别为有意义的单词（Token）序列的过程。FIRST(α)可从符号串α推导出的所有可能的开头终结符的集合。句柄句型的一个直接短语，并且该直接短语可以在该位置被归约为某个非终结符。LL(1)文法自顶向下不带回溯的预测分析文法，要求分析表每个入口至多一个产生式。LR(k)分析自底向上的移进-归约分析，从左到右扫描，最右推导的逆过程，最多向前看k个符号。语法制导翻译为文法符号附加属性，并在产生式上附加语义规则，在语法分析的同时计算属性值并生成中间代码。三地址码一种中间代码形式，每条指令最多包含三个地址，形式为x=yopz。基本块一个顺序执行的语句序列，只有一个入口和一个出口。代码优化对中间代码进行等价变换，以提高程序运行效率和减少空间占用的过程。第十二部分：简答题高频考点速记1.简述编译程序各工作阶段的主要任务。词法分析：扫描字符串产生单词。语法分析：根据文法构建语法树。语义分析：类型检查等。中间代码生成：产生平台无关的三地址码。代码优化：等价变换提高效率。目标代码生成：产生机器指令。贯穿全程的还有符号表管理和错误处理。2.什么是LL(1)文法？如何判断？自上而下不带回溯的预测分析文法。判断条件：文法无左递归；对于任意非终结符A的任意两个候选式α和β，FIRST(α)∩FIRST(β)=∅；若α能推出ε，则FIRST(α)∩FOLLOW(A)=∅。3.简述SLR(1)分析的基本思想。在LR(0)项目集规范族基础上，当出现移进-归约冲突时，利用FOLLOW集判断：若当前输入符号属于某个归约项目左部的FOLLOW集，则用该产生式归约；否则不能归约，可移进。若冲突均能这样解决，则文法是SLR(1)。4.比较综合属性与继承属性。综合属性由子结点属性计算，用于自底向上传递信息；继承属性由父结点或兄弟结点属性计算，用于自顶向下传递信息。S-属性定义只使用综合属性，L-属性定义允许有限制的继承属性。5.列举至少三种代码优化技术。公共子表达式删除、复写传播、死代码删除、循环不变量外提、强度削弱、归纳变量消除等。第十三部分：计算与设计题示例例1：FIRST/FOLLOW集文法：E→TE'

E'→+TE'|ε

T→FT'

T'→*FT'|ε

F→(E)|idFIRST(E)=FIRST(T)=FIRST(F)={(,id}FIRST(E')={+,ε}FIRST(T')={*,ε}FOLLOW(E)={),$}FOLLOW(E')={),$}FOLLOW(T)={+,),$}FOLLOW(T')={+,),$}FOLLOW(F)={*,+,),$}例2：三地址码生成x=a*(b+c)

→t1=b+c

→t2=a*t1

→x=t2例3：DAG优化基本块：

t1=a+b

t2=t1+c

t