编译原理笔记

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

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

冯·诺伊曼 : 二进制, 五大功能, 存储控制
翻墙软件 : 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 届的补考题

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

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

  1. 简述 Linux 操作系统下 C 语言程序的编译过程
    答案预处理
    编译
    汇编
    链接

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


  1. 设文法 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

已知某文法 G：
bexpr→bexpr or bterm|bterm
bterm→bterm and bfactor | bfactor
bfactor→not bfactor|(bexpr)|true |false
则以下哪个是该文法中的起始符号（ ）

（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)={ # };；若有 A->αBβ，则将 First(β){ɛ}并入 Follow(B)集；若有 A->αB 的推导，或者 A->αBβ 中，β 可推导出 ɛ，则将 Follow(A)并入 Follow(B)中。其实质就是，对于文法推导过程中，所有可能包含非终结符 B 的句型，可能出现在 B 之后的文法终结符的集合（不包括 ɛ），特殊的，对于起始符号 S，其 Follow(S)集包括#。
D、 在判断文法是否为 LL(1)文法时，需要计算所有非终结符的 First 集和 Follow 集。

正确答案：D

20 届期末试题


20 届补考题

专业课
#编译原理 #专业课
编译原理笔记
https://xiamu.icu/专业课/编译原理笔记/
作者
肉豆蔻吖
发布于
2022年10月18日
许可协议