【编译原理】往年题汇总（山东大学软件学院用）

🌈 个人主页：十二月的猫-CSDN博客
🔥 系列专栏： 🏀编译原理_十二月的猫的博客-CSDN博客

💪🏻 十二月的寒冬阻挡不了春天的脚步，十二点的黑夜遮蔽不住黎明的曙光 

目录

1. 前言

2. 22-23年 编译原理

2.1.编译原理的程序框图

2.2.有穷自动机？DFA和NFA的区别？

2.3.推导和归约的概念

2.4.SDD，简述S-SDD和L-SDD

2.5. 划分基本块的算法

2.6. 正规式→DFA LL(1) LR(0) SLR(1) LR(1) LALR(1)

2.7. 简述语法制导翻译的思想

2.8. 简述四个优化代码的算法

3. 21-22年 编译原理

3.1 判断一个文法是不是二义文法

3.2 给一个句型，找它的句柄

3.3 消除左递归（看一下后面的例子）

3.4 正规式转化为DFA

4. 20-21年 编译原理

4.1 综合属性继承属性概念

4.2 用语法制导翻译思想，把语句翻译成三地址码序列。while a < b do if c > d then x = y * z

5. 19-20年 编译原理

5.1 编译的前端，后端，什么是一遍扫描

5.2 在语法制导翻译中，空返产生式的作用（M->ε）

6. 总结

---

1. 前言

为什么打算开始这一系列的文章——编译原理🎄🎄

其实本学期开始就一直想持续更新，陆陆续续主要更新了实验部分。

正好趁着快要考试，便和大家一起花费几天的时间回顾编译原理的知识点。

目前，十二月猫的回顾计划如下🔞🔞：

祝大家都能取得好成绩呀~~🥰🥰 

---

参考书籍：

英文名：Compilers: Principles,Techniques,and Tools （龙书）🦖

作者：Alfred V.Aho,Ravi Sethi,Jeffrey D.Ullman 

        1．本课程介绍编译器构造的一般原理和基本实现方法，主要介绍编译器的各个阶段：词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成。

        2．本课程在介绍命令式程序设计语言实现技术的同时，强调一些相关的理论知识，如形式语言和自动机理论、语法制导的定义和属性文法、类型论等。

        3．本课程强调形式化描述技术，并以语法制导定义作为翻译的主要描述工具。

        4．本课程强调对编译原理和技术在宏观上的理解，而不把读者的注意力分散到一些枝节的算法上，如计算开始符号集合和后继符号集合的算法，回填技术等。作为原理性的教材，本书介绍基本的理论和方法，而不偏向于某种源语言或目标机器。

2. 22-23年 编译原理

2.1.编译原理的程序框图

• 词法分析器：输入源程序，进行词法分析，输出单词符号；（扫描字符流，滤掉空白符、换行符、制表符、注释等，分离出词素，输出词法单元序列

• 语法分析器：根据文法构建分析表，对单词符号进行语法分析，检查程序是否符合语法规则；

• 语义分析与中间代码生成器：按照文法翻译规则对语法分析器归约出的语法单位进行语义分析，并把它们翻译成一定形式的中间代码；

• 优化器：对中间代码进行优化处理；

• 目标代码生成器：把中间代码翻译成目标代码。

2.2.有穷自动机？DFA和NFA的区别？

        用于语法分析中转载在扫描仪中的程序算法，是语法分析的一种方式，与手工编写的语法分析不同。有穷自动机的语法分析更加通用，是自动生成语法分析器的一种方式。分为两类，非确定有限自动机和确定有限自动机。对于每个可以用正则表达式描述的语言，均可用某个NFA或DFA来识别。

• NFA：对边上的标号没有限制，一个符号可以作为标号出现在离开同一个状态的多条边上，ϵ可以做标号
• DFA：对于每个状态以及每个标号，有且只有一条边

2.3.推导和归约的概念

推导：将非终结符替换为它的某个产生式的体。分为直接推导、间接推导、最左推导、最右推导

• 最左推导：任何一步α => β都是对α中的最左非终结符进行替换
• 左右推导：任何一步α => β都是对α中的最右非终结符进行替换

归约：归约是推导的逆过程。分为直接、间接、最左、最右归约。

2.4.SDD，简述S-SDD和L-SDD

• SDD：即语法制导定义，将每个产生式和一组语义规则相关联，这些规则用于计算该产生式中各文法符号的属性值。
• S-SDD：每个属性都是综合属性，都是根据子构造的属性计算出父构造的属性。
• L-SDD：每个属性是综合属性，或是继承属性，且A→X1 X2 … Xn 中计算Xi.a的规则只用到A的继承属性，或Xi左边的文法符号Xj的继承属性或综合属性，或Xi自身的继承或综合属性。

这个地方的记忆可以使用 树的深度优先遍历

2.5. 划分基本块的算法

1. 找基本块的入口：一共有三类入口：①代码段的第一个指令；②条件跳转和无条件跳转的目标语句；③条件跳转语句的下一条语句；
2. 根据划分的入口画流图，一个基本块的区间：从入口开始，至到遇到下一个入口结束；

2.6. 正规式→DFA LL(1) LR(0) SLR(1) LR(1) LALR(1)

见另外三篇文章：

【编译原理】编译原理知识点汇总·词法分析器（正则式到NFA、NFA到DFA、DFA最小化）-CSDN博客

【编译原理】一篇搞定LR分析法（LR(1)、LR(0)、SLR、LALR）-CSDN博客

【编译原理】编译原理知识点汇总·语法分析器（消除左递归、消除二义性、自顶向下语法分析、自下向上语法分析）-CSDN博客

2.7. 简述语法制导翻译的思想

        从概念上讲，基于属性文法的处理过程如下：对单词符号串进行语法分析，构造语法分析树，然后根据需要遍历语法树并在语法树的各节点处按照语义规则进行计算。这种有源程序的语法结构驱动的处理办法就是语法制导翻译法。

2.8. 简述四个优化代码的算法

（1）删除公共子表达式

如果表达式 x op y 先前已被计算过，并且从先前的计算到现在，x op y 中变量的值没有改变，称为公共子表达式。可以将其删除。

（2）删除无用代码

无用代码，其计算结果永远不会被使用的语句。例如重复对多个变量赋相同的值。

（3）常量合并

如果在编译时刻推导出一个表达式的值是常量，就可以使用该常量来替代这个表达式。替换后，节省一次内存访问。

（4）代码移动

对于那些不管循环执行多少次都得到相同结果的表达式，在进入循环之前就对它们求值。

（5）强度削弱

用较快的操作代替较慢的操作。

3. 21-22年 编译原理

3.1 判断一个文法是不是二义文法

给定一个文法G，如果这个文法G的一些句子中存在不止一棵分析树，或者这些句子存在不止一种最左(最右推导)， 我们就称该文法为二义性的，G也叫二义性文法。

注意：文法二义并不代表语言一定是二义的，只有当产生一个语言的所有文法都是二义时，这个语言才成为二义的。

3.2 给一个句型，找它的句柄

句柄，也是归约项，是指在进行归约操作时，被替换的右侧产生式的符号串。

【编译原理】一篇搞定短语、直接短语、句柄-CSDN博客

3.3 消除左递归（看一下后面的例子）

具体方法有：消除直接左递归、消除间接左递归

【编译原理】一篇搞定语法分析器对文法的要求（上下文无法文法、消除二义性文法、消除左递归）-CSDN博客

3.4 正规式转化为DFA

【编译原理】一篇搞定正规式到NFA、NFA到DFA、DFA最小化_正规式转化为nfa-CSDN博客

4. 20-21年 编译原理

4.1 综合属性继承属性概念

• 综合属性：假设分析树结点N对应非终结符A，只能通过N的子结点或N本身的属性值来定义的属性称为A的综合属性。终结符综合属性由语法分析器提供。
• 继承属性：假设解析树结点N对应非终结符A，只能通过N的父结点的继承属性、N的兄弟结点或N本身的继承属性和综合属性来定义的属性称为A的继承属性。终结符没有继承属性。

4.2 用语法制导翻译思想，把语句翻译成三地址码序列。while a < b do if c > d then x = y * z

5. 19-20年 编译原理

5.1 编译的前端，后端，什么是一遍扫描

前端：前端对源语言进行分析，并产生中间表示，处理与源语言相关的细节，与目标机器无关。

后端：后端对中间表示进行分析、优化，并产生新的中间表示；处理与目标机器相关的细节，生成目标机器代码。

记忆：输入输出+处理内容（和什么无关和什么有关）

一遍扫描：对源程序扫描一次被称为一遍扫描

5.2 在语法制导翻译中，空返产生式的作用（M->ε）

        在语法制导翻译中，空返产生式(Epsilon production)的作用是允许语法分析树在不生成任何输出的情况下，从一个非终结符移动到另一个非终结符。这对于模拟语法的省略部分(如可选的子句)很有用。因此，空返产生式允许更灵活的语法分析，并且可以使语法分析过程更加简化。

6. 17-18年 编译原理

6.1 描述LR语法分析算法

        LR语法分析法是编译原理中的一种语法分析方法，其全称为“自左至右扫描和自底向上规约”，是一种自底向上的分析方法。这种方法对文法的限制最少，适用于大部分的上下文无关文法。LR分析法的基本思想是在归约的过程中，一方面记住移入和归约的整个符号串，另一方面通过产生式推测未来可能的输入符号。

6.2 举例说明文法二义性

记住常见的例子：

S - >S and S | S or S | not S | p | q | (S)

句子：not p and q

 关键点：

1. 存在and和or还有not
2. 这几个的优先级和结合性都没有确定

6.3 符号表作用

• 收集符号属性
• 上下文语义的合法性检查的依据
• 作为目标代码生成阶段地址分配的依据

记录符号本身特性

辅助分配空间

语义检查

6.4 解释LL(1)文法

一个文法满足下面条件：

（1）文法不含左递归

（2）对于文法中每一个非终结符A的各个产生式的候选首符集不相交

（3）对于于文法中每一个非终结符A，若它存在的某个候选首符集包含ε，那么first(A)∩follow(A)=空

6.5 写出语言L的上下文无关文法

6.6 正规式的概念

正则表达式是一种用来描述正则语言的更紧凑的表示方法。

6.7 语言和文法的概念

语言：语言 (language) 是某个给定字母表上的串的可数集合

文法：文法（Grammar）是一种形式化的表达式，用于描述一种语言的语法规则。文法由一组产生式组成，每个产生式定义了一种语法结构及其对应的生成方式。

一般包括四个部分：终结符、非终结符、产生式、开始符

6.8 现有一个词法分析方法GetToken()，和ACTION和GOTO的LR(0)预测分析表，请用伪代码完成自底向上的语法分析

6.9 代码优化目的是什么

提高程序的性能；减小程序的体积；提高程序的可维护性和可读性；降低程序的错误率.

6.10 DAG做目标代码生成 

设DAG有N个内部节点，线性表T[N] 记录计算顺序，初始为空值。

• 最后T[1],T[2], …,T[N] 即为节点计算顺序

6.10 简述算符优先文法原理

7. 总结

 本文到这里就结束啦~~

本系列专栏将专注于【编译原理】知识。

内容包括：知识点讲解、习题练习、重点知识带练等~~目前已完成：

【编译原理】编译原理知识点汇总·概论与文法-CSDN博客

【编译原理】编译原理知识点汇总·词法分析器（正则式到NFA、NFA到DFA、DFA最小化）-CSDN博客

【编译原理】编译原理知识点汇总·语法分析器（消除左递归、消除二义性、自顶向下语法分析、自下向上语法分析）-CSDN博客

【编译原理】编译原理知识点汇总·属性文法和语法制导翻译-CSDN博客

【编译原理】编译原理知识点汇总·中间代码（中间代码+翻译）-CSDN博客

【编译原理】编译原理知识点汇总·代码优化-CSDN博客

【编译原理】词法分析器设计（山东大学实验一）_山东大学编译原理实验-CSDN博客

【编译原理】语法、语义分析器设计（山东大学实验二）_语法分析实验-实现一个简单语法分析器(自上而下方法)实验小结-CSDN博客

【编译原理】代码生成器的构建与测试（山东大学实验三）_编译原理实验语义分析代码-CSDN博客 【编译原理】一篇搞定正规式到NFA、NFA到DFA、DFA最小化-CSDN博客

【编译原理】一篇搞定语法分析器对文法的要求（上下文无法文法、消除二义性文法、消除左递归）-CSDN博客

【编译原理】一篇搞定LR分析法（LR(1)、LR(0)、SLR、LALR）-CSDN博客

【编译原理】一篇搞定注释分析树-CSDN博客

【编译原理】一篇搞定短语、直接短语、句柄-CSDN博客

期待您的关注~~🥰🥰 

猫猫陪你永远在路上💪💪

如果觉得对你有帮助，友友们可以点个赞，收个藏呀~