「编译原理」期末复习
本文最后更新于:2023年4月15日 晚上
0 | 考点
from 张南老师
编译期末试卷题型
一、填空题 20分,每空1分
二、简答题 20分,共4~5题
三、计算题 60分,共4题
考试重点但不局限于以下内容:词法分析、Thompson算法、子集法构造DFA、DFA最小化;自上而下语法分析、LL(1)文法、预测分析表;自下而上语法分析、短语、直接短语、句柄、识别活前缀的DFA、LR(0)分析表或SLR(1)分析表;语法制导翻译、布尔表达式短路计算、拉链回填。
1 | 填空题总结
19年填空
- 识别3型文法描述语言的自动机是有限自动机
- 描述含010的01串的正规式是
(0|1)*010(0|1)*
- 词法分析器的输入是源程序, 输出是记号流
- 自下而上的语法分析中, 需要对输入序列进行规范归约, 反复用产生式的左部替换句型中的句柄, 最终得到开始符号
- 在自上而下的语法分析中, 需要消除左递归以避免死循环, 需要提取左因子以避免虚假匹配(陷入回溯)
- 设有表达式
a * b - c
, 将其中的a * b
识别为表达式的编译阶段是语法分析 - 语义规则的两种表示方式是语法制导定义和翻译方案
- 综合属性在语法树上的计算次序和自下而上语法分析形成语法树的过程一致
- CFG无法描述语法中的变量声明与引用, 可以在语义规则中通过对符号表的插入, 查找等操作实现
- 参数传递的方法有值调用, 引用调用, 复写-恢复, 换名调用, 其中引用调用和复写-恢复要求实参一定是左值
- LL(1)分析中, 第一个L表示自左向右扫描输入串, 第二个L表示最左推导, 1表示向前看1个终结符
- 常见的中间代码形式有三地址码, 后缀式, 树
- 程序变量的重复定义会在语义分析阶段被发现
14年填空
- 符号表管理和出错处理是编译程序各阶段都涉及到的工作
- 在编译器工作过程中, 实现语言关键字大小写不敏感的阶段是词法分析, 分析语言结构的阶段是语法分析
- 不确定有限自动机中的有限是指状态的数量是有限的
- 程序的语义错误可分为静态语义错误和动态语义错误
- 推导的过程可以用一棵树来表示, 被称为分析树
a*-(b+c)
的后缀式是abc+-*
- 当文法的FIRST集两两不相交时, 该文法对应的句子分析不含有回溯性
- 在自上而下的语法分析中, 应先消除文法的间接递归, 再消除文法的直接递归
15年填空
- Lex和Yacc是用于生成词法分析器和语法分析器的工具
- 描述含010和01串的正规式是
(0|1)*010(0|1)*
- 识别3型文法描述语言的自动机是有限自动机
- CFG的定义包含有非终结符集合, 终结符集合, 开始符号, 产生式
- 自下而上的分析中, 需要对输入序列进行规范归约, 反复用产生式的左部替换句型的句柄, 最终得到开始符号
- 文法产生二义性的原因是缺少对文法符号优先级和结合性的规定
- 语义规则的两种表示方式是语法制导定义和翻译方案
- 综合属性在分析树上的计算次序与自下而上语法分析形成分析树的过程一致
- LR分析的语法制导翻译将语义规则放在产生式右部的最右边, LR分析器在执行归约动作时执行语义动作
- 赋值语句
x = a + (b * c)
的后缀式是xabc*+=
- CFG无法描述在语法中的变量声明与引用, 可在语义规则中通过对符号表的插入, 查找等操作实现
- 参数传递的方法有值调用, 引用调用, 复写-恢复, 换名调用
作业-引言
- 一个编译程序中包含的部分除了词法分析, 语法分析, 语义分析, 中间代码生成, 代码优化, 目标代码生成五个部分, 还应包括出错处理和符号表管理
- 编译器的各阶段工作中, 中间代码生成和代码优化部分不是每个编译程序都必须的
- 词法分析器用于识别单词
- 解释器处理程序语言时, 大多数采用的是先将程序转化为中间代码, 再解释执行
- 高级语言的语言处理程序分为解释程序和编译程序两种, 编译程序有五个阶段, 而解释程序通常缺少目标代码生成和代码优化
- 受到具体机器主存容量的限制, 编译程序几个不同阶段的工作往往被组合成遍, 诸阶段的工作往往是穿插进行的
- 编译方式和解释方式的根本区别在于是否生成目标代码
- 从功能上说, 程序语言的语句大体可分为执行性语句和声明性语句两大类
作业-词法分析
- 词法分析器用于识别单词
- 三型文法是正规文法
- 表示源程序中信息单元的字符序列叫做记号
- 有限字母表上有限长度的字符串的集合叫做语言
- LEX源程序的三个组成部分: 定义部分, 识别规则部分, 辅助函数部分
作业-语法分析
- 一个句型中的最左直接短语称为该句型的句柄
- 有限自动机能识别正规文法
- 由文法的开始符号S经零步或多步推导产生的文法符号序列是句型
- 规范规约是指最右推导的逆过程
- 在LR分析法中, 分析栈中存放的状态是识别规范句型活前缀的DFA状态
- 设G是一个给定的文法,S是文法的开始符号,如果
S*=>x
(其中x∈(N∪T)*
),则称x是文法的一个句型 - 设G是一个给定的文法,S是文法的开始符号,如果
S*=>x
(其中x∈T*
),则称x是文法的一个句子 - 在自上而下的语法分析中, 应先消除文法的间接递归, 再消除文法的直接递归
- 规范归约是指在移进过程中, 当发现栈顶呈现句柄时, 就用相应产生式的左部符号进行替换
- 在LR(0)分析法的名称中, L的含义是从左向右扫描输入串, R的含义是最右推导, 0的含义是向前看0个终结符
作业-语法制导翻译
- 中间代码生成时所根据的是语义规则
- 编译程序中语法分析器接收以单词为单位的输入
- 终结符只具有综合属性, 它由词法分析器提供
- 所谓属性文法指的是在上下文无关文法的基础上为每个文法符号(终结符或非终结符)配备若干相关的“值”
- 语义规则的描述方法有语法制导定义和翻译方案
- 综合属性是用于自下而上传递信息, 继承属性是用于自上而下传递信息
- 语法制导翻译既可以用来产生中间代码, 也可用来产生目标指令, 甚至可以用来对输入串进行解释执行
- 在语法树中, 一个结点的综合属性的值由其子结点的属性和自身的其他属性值确定, 而继承属性则由该结点的父结点和兄弟结点的某些属性确定
2 | 简答题总结
19年简答
- 简述三元式和四元式的区别
- 正规式
(a | b)*
,(a* | b*)*
,((ε|a)b*)*
等价吗, 为什么? - 证明某文法为二义文法
- 给出逆波兰式的中缀式表示
- 画出表达式的注释语法树
14年简答
解释什么是LR(0)项目中的移进/归约冲突, 简单说明SLR(1)方法如何解决移进-归约冲突
为什么在一般情况下用正规式而不用CFG来描述语言的词法
- 词法规则简单, 用正规式描述已经足够
- 正规式的表达比CFG更加直观, 简介, 易于理解
- 有限自动机的构造比下推自动机简单, 且分析效率高
- 区分词法和语法, 为编译器前端模块的划分提供方便
符号表的作用是什么? 符号表的操作有哪些?
符号表的作用:
连接声明与引用的桥梁。一个名字在声明时,相关信息被填写进符号表;而在引用时,根据符号表中的信息生成相应的可执行语句。有效记录各类符号的信息,以便于在编译的各个阶段对符号表进行快速、有效的查找、插入、修改、删除等操作。
符号表的操作:
插入, 修改, 删除, 查找
控制栈中的活动记录保存的信息有什么? 具体内容有什么?
句子按找某文法归约值是多少, 判定文法是否是二义文法
15年简答
- 解释什么是编译器的扫描遍数
- 简述DFA和NFA的区别
- 解释什么是LR(0)项目中的移进/归约冲突, 简单说明SLR(1)方法如何解决移进-归约冲突
- 生成中间代码的目的是什么? 中间代码的特性是什么?
作业-引言
编译程序在逻辑上由哪几部分组成?
词法分析, 语法分析, 语义分析, 中间代码生成, 代码优化, 目标代码生成
编译的前端和后端分别是什么
前端: 词法分析, 语法分析, 语义分析, 中间代码生成
后端: 代码优化, 目标代码生成
什么是编译程序
编译程序是一种能够把高级语言程序翻译为低级语言程序的程序
什么是语义
一种语言的单词符号和语法单位的意义
什么是程序的遍
遍就是对源程序或程序的中间结构从头到尾扫描一次, 并做有关的加工处理, 生成新的中间结果或目标程序
作业-词法分析
简要说明词法分析器的功能
扫描字符串形式的源程序中的各个字符, 逐个识别出其中的单词, 并将其转换为内部编码形式的单词符号串作为输出
简要叙述从正规式构造词法分析器的一般方法和过程
- 用正规式对模式进行描述
- 为每一个正规式构造NFA
- 将构造出的NFA转化为等价的DFA(确定化)
- 把DFA化为最简形式(最小化)
- 将简化后的DFA构造词法分析器
DFA和NFA有何区别?
- NFA可以有ε转移, 而DFA没有ε转移
- DFA对于每一个状态s和每一个字符a, 最多有一个下一状态, 而NFA可能有多个
NFA的表示
NFA是一个五元组M =
(S, Σ, move, s0, F)
S是有限状态集合, Σ是输入符号集合, move是状态转换函数, S0是唯一的初态, F是终态集合
作业-语法分析
最左/右推导和左/右句型的定义
最左/右推导: 在推导过程中, 每次直接推导均替换句型中最左/右边的非终结符, 称为最左/右推导
左/右句型: 最左/右推导产生的句型
自上而下分析的宗旨
对于给定输入串w, 试图用一切可能的方法, 从文法开始符号S出发, 自上而下, 从左到右地为输入串建立一棵以S为根结点的语法树
叙述递归下降法
递归下降法是指对消除左递归和回溯以后的文法的每一个非终结符号, 都根据响应产生式各候选式的结构, 为其编写一个子程序(或函数), 用来识别该非终结符表示的语法范畴, 由于文法的定义是递归的, 因此这些过程也是递归的
根据程序错误性质可以分为哪几种错误?
- 词法错误
- 语法错误
- 静态语义错误 (如算符作用于不相容的运算对象)
- 动态语义错误 (逻辑错误, 如无穷的递归调用)
自下而上分析的思想
从输入串开始, 逐步进行「归约」, 直到归约到文法的开始符号; 或者说从语法树的末端开始, 步步向上归约到根结点
上下文无关文法的表示
四元组(N, T, P, S)
N是非终结符集合, T是终结符集合, P是产生式集合, S是开始符号
句柄是什么
一个句型的最左直接短语
活前缀是什么
右句型的前缀并且不包含句柄之后的符号
作业-语法制导翻译
语法制导翻译的基本思想是什么?
基本思想是根据翻译的需要设置文法符号的属性,以描述语法结构的语义
常用的中间语言种类有哪几种, 使用中间语言的好1处有哪些? 中间语言的特性?
常用的中间语言种类有逆波兰表示、三元式、四元式和树形表示。
中间代码上起一个编译器前端与后端分水岭的作用,目的是便于编译器的开发移植和代码的优化。
特性:
- 便于语法制导翻译
- 既与机器指令的结构相近, 又与具体机器无关
三元式和四元式的表示
三元式: (i) (op, arg1, arg2)
四元式: (op, arg1, arg2, result)
语义规则
对于文法的每个产生式都配备了一组属性的计算规则, 称为语义规则
翻译方案
用具体属性和运算表示的语义规则称为翻译方案
3 | 大题总结
本部分按章进行总结
大题共四题, 按照往年经验, 就是
- 正规式->最小化DFA
- LL(1)预测分析表
- SLR(1)分析表
- 语法制导翻译
词法分析
题型1 | 正规式->最小化DFA
方法步骤:
- 正规式->NFA (thompson算法)
- 由NFA->DFA (子集法)
- 最小化DFA
- 几条基本的Thompson转换:
- 子集法确定化的方式:
- 首先求出
ε-闭包({0}) = {状态集合}
并标上序号A
作为A
状态 - 对于每一个状态
X
和每一个标记a
求ε-闭包(smove(X, a)) = {状态集合}
并标上序号, 如果状态集合包含终态, 则化俩圈圈, 不包含终态就画一个圈圈
- 首先求出
- 最小化DFA的方式
- 首先将所有状态分为包含终态的G1和不包含终态的G2
- 对于G1和G2的每一个转移
move(s, a)
, 假设s和t都在G1中, 如果出现了move(s, a)在G2中, 而move(t, a)在G1中, 则将s和t分裂到两个集合G11和G12中 - 直到不能再分, 最后将每一个集合作为一个状态, 构造最后的DFA就是最小化DFA
e.g.
当题目没有明确给出必须使用Thompson算法时, 可以简化NFA, 即合并一些空边的状态(from 张南老师)
简化的NFA如下:
NFA->DFA(子集法) 确定化
1 |
|
得到确定化的DFA
最小化:
初始分为G1 = {A, B, C, D} 和 G2 = {E, F, G, H}
最后分裂为{A}{B}{C}{D}{E}{F}{G}{H}
故原来的DFA已经为最简形式
语法分析
题型1 | LL(1)文法构造预测分析表
方法步骤:
- 首先消除左递归和左因子, 构造原来文法G的等价的LL(1)文法G’
- 求每一个非终结符的FIRST集合和FOLLOW集合
- 画出预测分析表M, 第一列是所有非终结符, 第一行是所有终结符(不包括ε) +
#
- 对于每一个产生式
A->α
, 对于每一个FIRST(α) = a, 在M[A, a]上填上这个产生式, 如果FIRST(α) = ε, 则找到FOLLOW(A) = b, 在所有M[A, b]上填上产生式A->ε
消除左递归和左因子的方式
消除左递归先消除间接左递归(展开), 再消除直接左递归
方法见下面例子
消除左因子就是提出所有的左因子, 再增加一个产生式
求FIRST集合的方式
对于产生式
A->a...
加入a到FIRST(A)对于产生式
A->BCDE..
首先加入FIRST(B)到FIRST(A), 然后若FIRST(B)包含ε, 就加入FIRST(C)….
求FOLLOW集合的方式
- 首先加入
#
到FOLLOW(S) (S为文法开始符号) - 对于产生式
A->..Ba..
将a加入FOLLOW(B) - 对于产生式
A->..BC..
将FIRST(C)除了ε外的全体加入FOLLOW(B) - 对于产生式
A->..B
将FOLLOW(A)全体加入FOLLOW(B) - 对于产生式
A->..BC 且ε∈FIRST(C)
FOLLOW(A)全体加入FOLLOW(B)
- 首先加入
注意FIRST集合中包含ε, FOLLOW集合中不包含ε, FOLLOW集中首先要加上
#
, 构造M[A, a]时是对于每一个A->α
中的FIRST(α)
e.g.
(1) 发现A中有左递归, 消除得LL(1)文法
(2) 先求FIRST集合
1 |
|
再求FOLLOW集合
1 |
|
(3) 预测分析表构造
1 |
|
得到如下预测分析表:
a | b | c | d | e | # | |
---|---|---|---|---|---|---|
S | aABe | |||||
A | bA’ | |||||
A’ | bcA’ | ε | ||||
B | d |
(4) 分析过程
格局:三元组(栈内容^top,剩余输入^ip,改变格局的动作)
改变格局的动作
- 匹配终结符:若^top = ^ip(但≠‘#’),则pop且next(ip);
- 展开非终结符:若^top = X且^ip=a且M[X, a] = α(X→α),则pop且push(α)(α逆序入栈);
- 报告分析成功:若^top = ^ip = #,则分析成功并结束;
- 报告出错:其它情况,调用错误恢复例程。
初始状态
| 栈内容 | 剩余输入 | 动作 |
| ——— | ———— | —— |
| #S | xxxxx# | |
题型2 | LR(0)分析表和SLR(1)分析表
方法步骤:
- 写出拓广文法即在原文法中加入
S'->S
- 写出识别活前缀的DFA(I0开始标号)
- 判断DFA中是否有移进-归约冲突/归约-归约冲突
- 如果没有, 文法为LR(0)文法, 直接构造LR(0)分析表
- 如果有, 判断移进项{a1, a2…}, 每一个归约项的FOLLOW集是否相交, 如果不相交就是SLR(1)文法, 构造SLR(1)分析表
- SLR(1)分析表的样子: 第一列为所有的DFA状态序号0-n, 第一行分为Action和Goto, Action中包括所有终结符和
#
, Goto包含所有非终结符- SLR(1)分析表的四种情况:
A->α.aβ
: 将Action[k, a] = sj (j为下一状态序号)A->α.
: 将Action[k, a] = rj (a为属于FOLLOW(A)的终结符, j为归约的产生式标号) (注意这里是和LR(0)分析表的唯一区别, LR(0)分析表这里是对Action的所有终结符均记Action[k, a] = rj)S'->S
: 将Action[k, #] = accA->α.Bβ
: 将Goto[k, B] = j (j为下一状态序号)
注意:
- 当某个状态的下一状态推出来就是已存在的状态的子集时, 应将边指回到已存在的那个状态
- Z’不出现在GOTO表中
e.g.
(1)
拓广文法并给每一个产生式标号:
1 |
|
识别活前缀的DFA
注意到I8状态就存在移进-归约冲突, 故需要构造SLR(1)分析表
(2)构造SLR(1)分析表
首先需要求所有非终结符的FOLLOW集, 又有求FOLLOW集需要先求FIRST集(Z’不用求, Z’也不出现在SLR(1)分析表中)
1 |
|
if | then | = | V | i | # | Z | C | S | A | E | ||
---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | s3 | 1 | 2 | |||||||||
1 | acc | |||||||||||
2 | s11 | 4 | 5 | |||||||||
3 | s11 | 6 | 12 | |||||||||
4 | r1 | |||||||||||
5 | s7 | |||||||||||
6 | r5 | r5 | r5 | |||||||||
7 | s11 | 6 | 8 | |||||||||
8 | s9 | r3 | ||||||||||
9 | s11 | 10 | ||||||||||
10 | r4 | r4 | r4 | |||||||||
11 | r6 | r6 | r6 | r6 | ||||||||
12 | s13 | s9 | ||||||||||
13 | r2 |
语法制导翻译
题型1 | 将语句翻译成三地址码, 布尔表达式采用短路计算
两年都有这道题
感觉没啥好说的…就注意一个整型和实型的运算, 加入a是整型(int), b是实型(real), a+b流程如下:
1 |
|
即先把int->real, 计算后再把结果real->int
e.g.
- 将语句
if a < c or b > d then while a > 3 and b < 4 do a := a + b;
翻译成三地址码, 其中a, c
为整型,b, d
为实型, 布尔表达式采用短路计算
1 |
|
- 将语句
while a < b or not c < d do if b < a then a := b * d else c := a + b
, 其中a, b为整型, c, d为实型, 布尔表达式采用短路计算
1 |
|
4 | 其他补充知识点
4.1 | 绪论+词法分析
二义性: 一个句子对应多于一颗语法树
上下文无关文法的二义性是不可判定的, 即不存在这样一种算法, 对于任意一个上下文无关文法G, 该算法都可以计算出G是否是一个二义文法。
消除二义文法:
- 改写二义文法为非二义文法。
- 规定二义文法中符号的结合性和优先级, 使得仅产生一棵语法树。
改写二义文法的关键步骤:
- 引入一个新的非终结符,增加一个子结构并提高一级优先级;
- 递归非终结符在终结符左边,运算具有左结合性,否则具有右结合性。
4.2 | 语法分析
定义 | 解释 |
---|---|
句型 | 设G是一个给定的文法,S是文法的开始符号,如果S*=>x (其中x∈(N∪T)* ),则称x是文法的一个句型。 |
句子 | 设G是一个给定的文法,S是文法的开始符号,如果S*=>x (其中x∈T* ),则称x是文法的一个句子。 |
短语 | 设αβδ是文法G的一个句型,若存在S *=> αAδ ,A=+>β ,则称β是句型αβδ (相对于A)的短语。 |
直接短语 | 设αβδ是文法G的一个句型,若存在S *=> αAδ , A=+>β ,则称β是句型αβδ (相对于A)的短语, 特别地, 若有A→β ,则称 β 是句型 αβδ 相对于产生式 A→β 的 直接短语。 |
句柄 | 一个句型的最左直接短语。 |
活前缀 | 给定文法 G ,如果在符号序列 α 的右边增添零个或多个终结符之后,能够形成一个右句型并且 α 不含该句型句柄之后的任何符号,则称 α 为文法 G 的活前缀。(即: 右句型的前缀并且不包含句柄之后的符号。) |
右句型 | 最后推导产生的句型。 |
文法, 语言和自动机
文法 | 语言 | 自动机 |
---|---|---|
0型文法(短语文法) | 短语结构语言 | 图灵机 |
1型文法(CSG) | CSL | 线性界限自动机 |
2型文法(CFG) | CFL | 下推自动机 |
3型文法(正规文法) | 正规集 | 有限自动机 |
判断LL(1)文法的方法:
- 构造分析表
- 推论判断:$G$是$LL(1)$的,当且仅当$G$的任何两个产生式$A \rightarrow \alpha | \beta$条件
- $FIRST(\alpha) \cap FIRST(\beta) = \emptyset$
- 若$\beta \overset{*}{=>} \epsilon$,则$FIRST(\alpha) \cap FOLLOW(A)=\emptyset$
移进-归约分析器和预测分析器对比:
分析器 | 改变格局的动作 |
---|---|
预测分析器 | ①匹配:若匹配终结符:若 ^top = ^ip 但 ≠# ,则 pop 且 next(ip);②推导:若 ^top = X 且 ^ip=a 且 M[X, a] = α( X→α )),则 pop 且push(α) (α 逆序入栈) ③接受:若 ^top = ^ip = #,则分析成功并结束。 ④报错:其它情况,调用错误恢复例程。 |
移进-归约分析器 | ①移进 ( shift):输入序列中的终结符进栈。(当栈顶没有形成句柄时) ②归约 ( reduce):将栈顶句柄替换为对应非终结符。(当栈顶形成句柄时) ③接受 ( accept):宣告分析成功。 ④报错 ( error):发现语法错误,调用错误恢复例程。 |
4.3 | 语法制导翻译
中间代码:
中间代码起到编译器前端和后端分水岭的作用。
中间代码需要便于编译器的开发移植和代码优化,需要满足如下特性:
- 便于语法制导翻译。
- 既与机器指令的结构相近,又与具体的机器无关。
graph LR
A[中间代码主要形式]-->后缀式
A-->B[三地址码]
B-->三元式
B-->四元式
A-->树
符号表:
符号表的作用: 连接声明与引用的桥梁
左值与右值:
左值是容器, 具有存储空间
右值可以仅仅是一个值(内容), 没有存储空间
拉链-回填技术的基本思想
- 当三地址码中的转向不确定时,将所有转向同一地址的三地址码拉成一个链;
- 一旦所转向的地址被确定,则沿此链将所有的三地址码中回填入此地址。