编译原理笔记

收集了两届的期末考题, 哪怕问到刘伟跃老师手机号码照样背出来

没啥用的网课(一些名词解释)

冯·诺伊曼 : 二进制, 五大功能, 存储控制
翻墙软件 : VPN
远程桌面
开源操作系统
虚拟化: vmware
编辑器: vim

考试复习方向

1.编译原理实验环境：参见资料中的实验指导一。 2.模块化的 C 语言程序设计：参见资料中的实验指导二。 3.编译器组成/结构：前端（词法分析、语法分析、语义处理）、后端（中间代码生成、代码优化、运行时存储器组织、目标代码生成）、公共模块（符号表、错误处理），对每个功能模块的理解。
4.PL/0 语言：基本概念，具备使用 PL/0 语言编写简单应用程序的能力。 5.文法与语言中的概念：文法、语言、句子、句型、推导、规约、语法树、二义性文法、回溯、无穷语言与有穷文法（递归文法）、文法等价->文法改造->文法分类。 6.文法分类，不同语法分析对文法的要求：短语文法（0）、上下文有关文法（1）、上下文无关文法（2）、正规文法（3）；自顶向下语法分析需要 LL（1）文法，自底向上语法分析需要 2 型文法；对不同类型文法的识别；简单文法的句子推导证明。 7.词法分析：理论基础（符号的连接、或者、闭包运算、正则式），对正则式的识别能力，对 NFA、DFA 的理解与应用（顶点集的空弧闭包、顶点集的 a 弧转换）。 8.自顶向下语法分析：
概念与基本思路；First 集、Follow 集计算；
LL(1)文法的判断；
LL（1）文法的改造；
编写递归下降 LL(1)语法分析程序。 9.自底向上语法分析：概念与基本思路；
根据语法树反向构造句子在符号栈中的移进-规约过程；
利用 Action 和 Goto 表构造句子的状态栈变化过程；
文法->扩广文法->非终结符的左文->推导式的 LR(0)左文方程->NFA->DFA->生成 Action 和 Goto 表。 10.语义处理：基本概念（数据类型、强语言与弱语言、函数依赖与循环依赖、作用域）；语义分析的错误可能；语法树、抽象语法树、前缀中缀后缀、波兰式、逆波兰式、四元组、三元组、间接三元组等；符号表。 11.运行时存储组织：栈与堆的应用；参数传递。 12.代码优化：窥孔优化（修身）、局部优化（齐家）、循环优化（治国）、全局优化（平天下）；指令调度与循环展开。 13.目标代码生成：目标代码的一般形式；指令选择、寄存器选择、指令调度的关系。

LL(1)语法的判断

LL(1)文法是自上而下的分析方法。

LR(0)语法的分析

与 LL（1）相对，LR(0)文法是下而上的分析方法，从左分析，从栈顶归约。

三个练习题

例题 1

分析 1+(2+3)

例题 2

分析(a+b)

例题 3

分析 a*(b+c)

临时抱佛脚

看的1 编译原理求语法树的短语直接短语等等_哔哩哔哩_bilibili这个速成视频
学习什么的不重要, 主要是妹子声音好听

1 编译原理求语法树的短语直接短语等等

**二义性: **如果两种推导方式画出的树不同, 则说明该文法有二义性

一道练习题

答案

2 编译原理消除左递归消除回溯

3 编译原理如何求 first 集和 follow 集

4 编译原理构造 LL(1)文法完整分析过程

5 编译原理构造优先关系表

妈的不会

6 编译原理构造优先关系图

妈的不会

7 编译原理构造 LR(0)分析表(包含构建项目规范族）

12 编译原理根据五元组构建状态转换图即状态转换矩阵

逆波兰

其实就是后缀表达式

19 届的复习资料

自行下载看吧
编译原理.docx 编译原理复习资料.docx

19 届的补考题

何谓编译器? 编译器应由那几部分组成? 简述各部分作用
答案编译器就是将“一种语言（通常为高级语言）”翻译为“另一种语言（通常为低级语言）”的程序

编译器可分为前端、后端。
前端：词法分析、语法分析（自顶向下、自底向上）、语义处理等；
后端：运行时存储组织、代码优化、目标代码生成等。

简述 Linux 操作系统下 C 语言程序的编译过程
答案预处理
编译
汇编
链接
何谓文法? 举例说明文法的分类
答案文法是用来定义语言的规则的，如一般自然语言的句子的结构是：
名词短语+动词短语+句号
动词短语=动词+名词短语
文法分 4 种
0 型文法: 没有约束, 是个文法就是 0 型文法
1 型文法(上下文有关): 右边的长度大于左边
2 型文法(上下文无关): 左边必须为非终结符
3 型文法(正规文法):
设 G = (VN,VT,P, S), 若 P 中的每一个产生式的形式都是 A→aB 或 A→a, 其中 A 和 B 都是非终结符, a∈VT*

设文法 G 为: S→aS|bS|c. 请设计其 LR(0)分析表, 请给出输入串 ababc 的分析过程

20 届期中考试题

一、单选题（共 20 题，100 分）
1、在 Linux 下，将 C 语言源程序编译为可执行程序，可使用命令（）
**（5.0） **
A、 gcc
B、 touch
C、 ls
D、 ar
正确答案正确答案：A
解析：

2、在 C 语言程序设计中，用来定义功能函数原型、声明数据接口的文件是（）
**（5.0） **
A、 _.c 文件
B、 _.h 文件
C、 _.cpp 文件
D、 _.exe 文件
正确答案正确答案：B
解析：

3、从编译的阶段来看，词法分析应属于（）
**（5.0） **
A、编译的前端
B、编译的中端
C、编译的后端
D、编译的末端

正确答案正确答案：A
解析：

4、文法是具有“包含”关系的。下列文法中，处于最内层的文法是（）
**（5.0） **
A、 0 型文法
B、上下文有关文法
C、上下文无关文法
D、正规文法

正确答案正确答案：D
解析：

**（5.0） **
A、 bexpr
B、 bterm
C、 bfactor
D、 not

正确答案正确答案：A
解析：

6、刘伟跃老师的电话号码是（）
**（5.0） **
A、 13507440668
B、 13574404624
C、 18874445225
D、 18974471616

正确答案正确答案：B
解析：

7、形如 0101010的正则表达式，描述的语言是（）
**（5.0） **
A、以字符’0’、’1’构成的任意字符串。
B、以字符’0’、’1’构成，以字符’0’开始和结束，包含三个字符’1’的任意字符串。
C、以字符’0’、’1’构成，包含至少三个字符’1’的任意字符串。
D、以字符’0’、’1’构成，有且仅有三个字符’1’的任意字符串。

正确答案正确答案：D
解析：

8、若文法 G:S->0S1，S->01。
则 00S11 是符合文法的（）,000111 则是符合文法的（）。
**（5.0） **
A、句型、句型
B、句型、句子
C、句子、句型
D、句子、句子

正确答案正确答案：B
解析：一个句型中既可以包含终结符，又可以包含非终结符，也可能是空串。

9、若文法 G：S->cAd，A->ab，A->a，在证明输入串 w=cabd 是否符合文法时，有如下证明过程：
**根据 S->cAd，将 S 装换为 cAd； **
再根据 A->ab，将 cAd 装换为 cabd，从而证明 w 是符合文法的串。
则该证明过程为（）。
**（5.0） **
A、自上向下的推导语法分析
B、自下向上的规约语法分析

正确答案正确答案：A
解析：

10、在实现 LL(1)语法分析时，要求文法是正规文法。文法改造中的“消除左递归”，即要能将 P->Pa|b 的含左递归的文法进行改造，改造成形如（）的文法。
**（5.0） **
A、 P->bP’，P’->aP’|ɛ
B、 P->aP’，P’->bP’|ɛ
C、 P->bP’，P’->aP’
D、 P->aP’，P’->bP’

正确答案正确答案：A
解析：

11、在 Linux 系统下，若要对 C 语言程序进行静态编译（即编译时使用-static 参数），需要安装的组件是（）。
**（5.0） **
A、 glibc-static
B、 mysql
C、 qt-devel
D、 libgl

正确答案正确答案：A
解析：

12、在如下的 C 语言源程序中，识别的词法单元有（）个。
main()
{
int x;
x = 1+2*3;
}
**（5.0） **
A、 6
B、 16
C、 8
D、 18

正确答案正确答案：B
解析：

13、在编译器设计模型中，符号表是贯穿词法分析、语法分析、语义处理、代码优化、目标代码生成等过程的公共模块，符号表中符号的唯一标识是（）。
**（5.0） **
A、符号名
B、符号类型
C、符号存储类别
D、符号作用域

正确答案正确答案：A
解析：

14、若有文法 G：S->aA|bB，aA->ab，bB->bA，则该文法是（）。
**（5.0） **
A、 0 型文法
B、 1 型文法
C、 2 型文法
D、 3 型文法

正确答案正确答案：B
解析：

15、若文法 G：S->cAd，A->ab，A->a，在证明输入串 w=cabd 是否符合文法时：
先利用 A->ab，将 cabd 转换为 cAd；
再利用 S->cAd，将 cAd 转换为 S，从而证明输入串符合文法。
则该证明过程为（）。

**（5.0） **
A、自上而下的推导证明
B、自下而上的规约证明

正确答案正确答案：B
解析：

16、形如 a(a|b)*b 的正则表达式，表达的是（）。
**（5.0） **
A、由字符’a’、’b’字符构成的任意字符串
B、由字符’a’、’b’字符构成，以’a’开始，’b’结束的所有字符
C、由字符’a’、’b’字符构成，以’a’开始的所有字符串
D、由字符’a’、’b’字符构成，以’b’结束的所有字符串

正确答案正确答案：B
解析：

17、在如下图的 NFA 中，状态’5’的 ɛ 闭包是（）

**（5.0） **
A、集合{1,5,6,2}
B、集合{5,6,2}
C、集合{5,6}
D、集合{5,6,2,3}

正确答案正确答案：B
解析：

18、在如图的 NFA 中，状态集{1,2}的 a 弧转换结果为（）

**（5.0） **
A、 {5,3}
B、 {5,3,4}
C、 {3,4,5,6,7,8}
D、 {2,3,4,5,6,7,8}

正确答案正确答案：D
解析：

19、在进行 LL(1)语法分析时，文法中如有 A->aB，A->aCd 的规则时，需要进行提取左公因子的文法改造，即将该文法改造为（）。
**（5.0） **
A、
A->aA’，
A’->B|Cd
B、
A->bA’，
A’->aA’|ɛ

正确答案正确答案：A
解析：

20、在判断一个文法是否为 LL(1)文法时，以下描述不正确的是（）。
**（5.0） **
A、若存在 A->α|β 的文法，即文法定义中，存在某非终结符可以推导出多个不同句型，则需要计算 First(α)和 First(β)集合，即 A 推导出的不同句型，各句型的 First 集应该没有交集；若 A 推导出的句型存在 ɛ，则还需要计算 A 的 Follow 集合，A 推导出的句型的 First 集和 A 的 Follow 集没有交集。
B、 First(A)集，其实质就是，非终结符 A 所推导出的句型中，所有可能出现在句型首部的文法终结符的集合（包含 ɛ）。
C、 Follow(B)集，定义为：对于文法的起始符号 S，Follow(S)=

编译原理

#编译原理 #计算机基础课

编译原理笔记

https://xiamu.icu/编译原理/编译原理笔记/

作者

肉豆蔻吖

发布于

2022年10月18日

许可协议

Nginx 上一篇

SpringBoot 下一篇