版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
华南理工大学《编译原理》期末全套复习资料(考点+真题+完整答案)适配华工计算机本科期末大纲,课程核心章节:绪论、文法、词法分析、LL(1)自顶向下、LR自底向上、语法制导翻译、中间代码、运行时环境、代码优化,试卷题型:填空、选择、判断、简答、计算大题(满分100分,闭卷120min)。一、华工官方考纲核心考点(必考)第1章编译概述(填空/选择)编译器5大阶段:词法分析→语法分析→语义分析→中间代码生成→目标代码生成,优化穿插在中间/目标代码阶段编译vs解释:编译生成完整目标程序再执行;解释逐行执行无目标文件遍、趟、前端、后端、符号表、错误处理基础概念文法四类(乔姆斯基):0型(短语文法)、1型(上下文有关)、2型(CFG上下文无关,语法分析核心)、3型(正规文法,词法分析)第2章文法与语言(大题必考)术语:字母表、串、句型、句子、短语、直接短语、句柄、素短语最左/最右推导(规范推导)、语法树、文法二义性判断(两棵不同语法树)必考计算:消除直接/间接左递归、提取公共左因子根据语言构造CFG、3型正规文法第3章词法分析(计算大题)正规式、正规集、NFA、DFA标准三步解题:正规式→NFA→子集法确定化DFA→分割法最小DFA词法分析器功能:识别token(标识符、关键字、常数、运算符、界符)第4章自顶向下语法分析LL(1)(高频计算题)FIRST集、FOLLOW集、SELECT集计算公式LL(1)判定:同一非终结符所有候选SELECT集互不相交构造预测分析表、递归下降分析程序设计第5章自底向上LR分析法(华工重中之重,分值最高)活前缀、项目、归约-移进冲突LR(0)项目集规范族、LR(0)分析表构造SLR(1)(解决LR0冲突)、LALR(1)、LR(1)基础原理算符优先文法、优先关系表构造、素短语归约第6章语法制导翻译&中间代码(大题)属性文法:综合属性、继承属性中间代码形式:逆波兰(后缀式)、三元式、四元式(三地址码)翻译:算术表达式、if-else、while循环翻译成四元式(每年必考)第7章运行时存储环境(简答)静态分配、栈式分配(活动记录AR结构)、堆式分配;作用域、变量存储布局第8章代码优化(计算简答)基本块划分算法局部优化:删除公共子表达式、复写传播、删除无用赋值循环优化三大核心:不变量外提、强度削弱、删除归纳变量二、客观题题库(填空+选择+判断,附标准答案)(一)填空题(20分)编译过程中,识别单词符号的阶段是\\\\\\。
答案:词法分析乔姆斯基2型文法又称\\\\__文法,用于语法分析。
答案:上下文无关(CFG)LL(1)中第一个L代表\\\\\\,第二个L代表最左推导,1代表向前看1个符号。
答案:从左至右扫描输入串LR分析器由总控程序和\\\\__两部分构成。
答案:LR分析表自底向上分析的核心是寻找\\\\__进行归约。
答案:句柄循环优化中,将循环内不变表达式移到循环外称为\\\\\\。
答案:循环不变量外提三地址代码的标准表示形式是\\\\\\。
答案:x=yopz(四元式:(op,y,z,x))消除左递归后,非终结符新增\\\\__型非终结符。
答案:'(撇)有限自动机分为NFA和DFA,区别在于\\\\__是否唯一。
答案:状态转换函数划分基本块的首要识别对象是\\\\__语句。
答案:入口(二)单项选择题(每题2分)下面属于3型正规文法的是()
AS→aSbBS→aA|aCS→ABDS→aSb|ab
答案:B文法二义性问题()
A存在判定算法B不可判定C所有CFG都无二义DLR文法一定二义
答案:B下列哪种分析法不会产生回溯()
A简单递归下降BLL(1)C带回溯自顶向下D算符优先
答案:B循环优化优先级最高,原因是()
A循环执行次数多,优化收益最大B代码最短C实现最简单D无冲突
答案:A后缀式ab*c+对应中缀表达式()
Aa+bcBab+cC(a+b)cDa(b+c)
答案:B(三)判断题(√/×,附解析)解释程序不生成目标代码(√)所有上下文无关文法都能使用LR(0)分析(×,存在移进归约冲突)一个文法若存在两棵不同语法树,该文法是二义文法(√)三元式比四元式更适合代码优化(×,三元式依赖索引,优化困难)LL(1)文法一定不含左递归和公共左因子(√)DFA允许同一个字符映射多个状态(×,NFA特性)句柄一定是素短语,但素短语不一定是句柄(√)静态分配支持递归函数(×,递归需要栈式动态分配)三、计算大题(华工期末高频原题+完整解题步骤)题型1:消除左递归+提取左因子,判断LL(1)题目:文法G[S]
S→Sa|aT|a
T→Tb|b步骤1:消除直接左递归S左递归:S→Sa|aT|a
改写:S→aTS'|aS',S'→aS'|ε
T左递归:T→Tb|b
改写:T→bT',T'→bT'|ε步骤2:提取S公共左因子S→a(TS'|S')
最终文法:
S→aS''
S''→TS'|S'
S'→aS'|ε
T→bT'
T'→bT'|ε步骤3:求FIRST/FOLLOW/SELECT,判断LL(1)FIRST(S)={a}
FIRST(S'')={b,a},FIRST(S')={a,ε}
FIRST(T)={b},FIRST(T')={b,ε}FOLLOW(S)={#},FOLLOW(S')={#},FOLLOW(S'')={#},FOLLOW(T)={a,#},FOLLOW(T')={a,#}SELECT(S''→TS')={b},SELECT(S''→S')={a,#},无交集;其余候选SELECT均不相交
结论:改造后文法是LL(1)文法题型2:正规式转最小DFA(词法必考)题目:正规式(a|b)*abb构造NFA;2.子集法确定DFA;3.分割最小化;4.画出最简DFA
核心结论:最简DFA共4个状态,终态接收串以abb结尾。题型3:LR(0)项目集+分析表(华工分值最大12分)文法:E→E+T|T,T→T*F|F,F→(E)|id列出全部LR(0)项目求项目集规范族,识别冲突(该文法无LR(0)冲突)构造LR(0)移进-归约分析表题型4:表达式/控制语句翻译四元式题目:翻译ifa+b>cthenwhilex<ydox=x+1elsed=5
四元式核心格式(行号,op,arg1,arg2,result)
100(+,a,b,t1)
101(>,t1,c,t2)
102(jtrue,t2,*,104)
103(j,,,110)
104(<,x,y,t3)
105(jtrue,t3,*,107)
106(j,,,110)
107(+,x,1,t4)
108(=,t4,*,x)
109(j,,,104)
110(=,5,*,d)题型5:基本块划分+循环优化代码序列:
i=1
sum=0
while(i<100){
sum=sum+i*2
i=i+1
}划分3个基本块;循环优化:强度削弱i2→t=2i,每次t+=2;删除归纳变量i(可选)四、简答题背诵(期末8道必背)词法分析与语法分析的区别
词法分析处理字符流,识别单词;语法分析处理单词流,判定语法结构,基于CFG。LL与LR分析法核心区别
LL:自顶向下、推导、无回溯、适合手工递归下降;
LR:自底向上、归约、表达能力更强、适合机器自动生成分析器。什么是句柄?句柄在自底向上分析作用
句柄:规范归约中最左直接短语;每次归约句柄,逐步规约到开始符号。SLR(1)相比LR(0)如何解决冲突?
LR(0)归约无限制;SLR利用FOLLOW集,仅当下一输入属于FOLLOW时才归约,消除冲突。活动记录AR包含哪些内容?
返回地址、动态链、静态链、局部变量、形参、临时变量。三地址代码三种形式优缺点逆波兰:适合表达式计算,不适合控制流;三元式:节省空间,优化修改困难;四元式:独立地址,易于优化,编译器最常用。代码优化三大原则
等价(不改变语义)、有效(减少时间/空间)、代价可控。NFA与DFA的三点区别
①DFA唯一初态,NFA可多初态;②DFA转换唯一,NFA多分支;③NFA含ε空转移。五、华南理工往年期末A卷完整真题(含答案)《编译原理》期末A卷(满分100)一、填空(20分,略,见上面客观题库)二、选择(10分,5道)三、判断(10分,5道)四、简答(24分,4道,背诵题)五、计算题(36分,4道)文法消除左递归+LL(1)判断(9分)正规式构造最小DFA(9分)while语句翻译成四元式(9分)LR(0)项目集与分析表(9分)试卷参考答案说明所有计
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 五年级主题班会《识别隐形杀手 筑牢安全防线》预防一氧化碳中毒教学设计
- 初中信息技术八年级《游戏制作》教学设计
- 初中七年级地理教学设计:西亚-石油宝地与水资源困境的区域认知构建
- 人教版八年级物理下册 12.3 滑轮 教学设计
- 小学三年级书法教学设计:横画笔法核心要素与“乐”字书写实践
- 初中语文说明文阅读专题复习教学设计:中考真题破解与考点深度剖析
- 高中二年级英语选择性必修二Unit 4 Welcome to the unit板块教学设计
- 高三英语选择性必修一Unit4 Body Language大一轮复习课教案
- 四年级美术教学设计:剪纸故事情境创编与群像构图
- 小学二年级英语Unit 6 In the Sea Talking Time教学设计
- 混凝土工程冬季施工专项方案
- (2026版)《建筑公司经营部年终工作总结》
- 2026地球小博士知识竞赛试题附答案
- 2026银行信用卡业务盈利模式转变规划分析研究报告
- 2026新教材语文 2《啊我们踯躅于黑暗的丛林里!》教学课件
- 钉子板上的多边形教学设计
- 2026年认证基础CCAA考试练习题及答案
- 气体灭火系统培训课件
- (2026年)ICU人工气道气囊微误吸防控证据总结课件
- 2026年株洲市天元区社区工作者招聘笔试参考题库及答案解析
- 《机械制图》电子教材
评论
0/150
提交评论