【编译原理】复习JMU

单选题10道（每题2分）

第一章：

• 编译前端与编译后端各包含哪些阶段？（优化可算前端，也可算后端）

第二章：

• 字母表上子集U与V的连接、V的n次自身积（V^0是空串，不是空集，即{e}）、闭包（V^*，*表示{0,1,…,n}任意一个都行）（V^+，去除了V0的V*）（V+= V*·V）、正则闭包的形式化定义。
• 能写出文法某句型的最左推导、最右推导、能画出推导过程对应的语法分析树。
  最左推导：

  E -> E+T|T
  T -> T*F|F
  F->(E)|i
  最左推导：E => i+i
  

  E => E+T => T+T => F+T => i+T => i+F => i+i
  语法分析树：
  
• 能判断某个正规式是否是指定文法的语言。
  如：文法G：S->aSb|ab，则正规式L(G) = {a^nb^n|n>=1}
  如：文法G1(A)：A->c|Ab，则L(G1)={c, cb, cbb, …}
  例：文法G2(S)：S ->AB, A ->aA|a, B ->bB|b，则L(G2)={a^m, b^n|m，n>0}

第三章：

• 会写正规式，能判断正规式是否满足指定要求，比如{0,1}上含101的字符串。
• 正规文法、左线性文法、右线性文法的关系及各自定义。
  • 如，A->aB|a是右线型（记：大写字母在哪边就是哪线型）
• DFA、NFA、正规文法、正规式、左线性文法、右线性文法之间的转换关系。
  • NFA -》 DFA/左线性文法/右线性文法/正规文法
  • 文法 可以表示成 正规式
  • 正规文法一定可以找到对应的NFA
• 状态转换图
  

第四章：

• 推导、归约的含义及关系
  • 互为逆过程
• 给出预测分析表，可以判断哪些输入串可以被LL(1)文法接收

第五章：

• 给定文法和句型，能找出短语、直接短语、句柄
  推荐看这个链接：
• 最左推导、最右归约、最右推导、最左归约、规范推导、规范归约之间的关系。
• 给出DFA，能看出是否是LL(0)文法，能看出哪些是活前缀，能找到某个活前缀对应的有效项目。

第六~十一章：

• 属性文法分为哪两类？哪类是用于自上而下传递信息，哪类用于自下而上传递信息？

  • 属性文法：属性文法（也称属性翻译文法）是在上下文无关文法的基础上，为每个文法符号（终结符或非终结符）配备若干相关的"值"（称为属性）。这些属性代表与文法符号相关信息，例如它的类型、值、代码序列、符号表内容等等。
  • 综合属性：在语法树中，一个结点的综合属性的值由其子节点的属性值确定。因此，通常使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值。仅仅使用综合属性的属性文法称S-属性文法。
  • 继承属性：在语法树中，一个结点的继承属性由此结点的父结点和/或兄弟结点的某些属性确定。用继承属性来表示程序设计语言结构中的上下文依赖关系很方便。

• 代码优化的原则有哪些？
  优化的目的是为了产生更高效的代码。
  原则：
  (1)等价原则。经过优化后不应改变程序运行的结果。

  (2)有效原则。使优化后所产生的目标代码运行时间较短，占用的存储空间较小。

  (3)合算原则。应尽可能以较低的代价取得较好的优化效果。

• 代码生成器输出代码的形式有哪些？
  代码生成器的输入包括中间代码和符号表中的信息。

  代码生成是把语义分析后或优化后的中间代码变换成目标代码。一般有以下三种形式：

  (2)带装配的机器语言模块。带需要执行时，由连接装入程序把它们和某些运行程序连接起来，转换成能执行的机器语言代码。

  (3)汇编语言代码，尚需经过汇编程序汇编，转换成可执行的机器语言代码。

简答题2道共15分

• 编译过程划分为哪几个阶段？各阶段任务是什么？

  1. 第一阶段，词法分析，任务是，输入源程序，对构成源程序的字符串进行扫描和分解，识别出一一个个单词。
  2. 第二阶段，语法分析，任务是，在词法基础上，根据语言的语法规则，把单词符号串分解成各类语法单位(语法范畴)。
  3. 第三阶段，语义分析与中间代码生成，任务是，对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译
  4. 第四阶段，优化，任务是，在对于前段产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效的目标代码
  5. 第五阶段，目标代码生成，任务是，把中间代码变换成特定机器上低级语言代码。

• 会画编译程序总体框架图。
  

• 形式化定义上下文无关文法。

• 能简述乔姆斯基四型文法之间的区别。

  • 0型文法：若P中任一产生式都有一般形式alpha -> beta ,alpha不为空
  • 1型文法：上下文有关文法，左边∈V+，右侧长度>左侧（特例a->ε）
  • 2型文法：上下文无关文法，左边是非终结符，如A,AB（不能是a,Aa）
  • 3是正规（线型）文法：左边只能有一个字符&&是非终结符，右边的每个候选满足非终结符都在终结符的一侧。
  • P36-6，7，8，9，10，11

• 能用形式语言定义文法的句型、句子、语言、等价。
  

• 能简述DFA与NFA的相同点与不同点。
  DFA（确定）

  一个确定有限自动机(DFA)M是一个五元式 M=(S,Σ,δ,s0,F),其中：
  S是一个有限集，它的每个元素称为一个状态。
  Σ是一个有穷字母集，它的每个元素称为一个输入字符。
  δ是一个从S×Σ至S的单值部分映射。δ(s,a)=s\'意味着:当现行状态为s、输入字符为a时，将转换带下一状态s\'。我们称s\'为s的一个后继状态。
  s0∈S，是唯一的初态。
  F⊆S，是一个终态集(可空)。
  

  NFA（非确定）

  一个非确定有限自动机(NFA)M是一个五元式 M=(S,Σ,δ,s0,F),其中：
  (1)S是一个有限集，它的每个元素称为一个状态。
  (2)Σ是一个有穷字母集，它的每个元素称为一个输入字符。
  (3)δ是一个从S×Σ到S的子集的映照，即δ:S×Σ\*→2S。
  (4)s0⊆S，是一个非空初态集。
  (5)F⊆S，是一个终态集(可空)。
  

  区别：

  1. DFA的s0是状态集合中的单个元素，NFA是状态集合中的子集并且非空
  2. 映射函数不一样。

• 能简述什么是LL(1)文法。
  1.文法不含左递归
  2.对于文法中每一个非终结符A的各个产生式的候选首符集两辆不相交。即，若A->a1|a2|a3|…|an，则
  FIRST(αi)∩ FIRST(αj) = 空集 (i!=j)
  3.对文法中每一个非终结符A，若它存在某个候选首符集包含ε，则：
  FIRST(A) ∩ FOLLOW(A）=空集
  如果一个文法满足上面条件，则称该文法G为LL(1)文法。
  LL(1)中的第一个L表示从左到右扫描输入串，第二个L表示最左推导，1表示分析时每一步只需向前查看一个符合。

• 理解中间代码生成对于编译器构造的好处。
  (1) 便于进行与机器无关的代码优化工作；
  (2) 使编译程序改变目标机更容易；
  (3)使编译程序的结构在逻辑上更为简单明确。以中间语言为界面，编译前端和后端的接口更清晰。

分析计算题2道大题，共50分

第三章（P49-图3.6、P65-15、P-12(b)）：

• NFA与左线性文法、右线性文法转换
  给定右线性文法G：
  S→OS|1S|1A|0B
  A→1C|1
  B→0C|0
  C→0C|1C|0|1
  求出一个与G等价的左线性文法。
  
• NFA确定化为DFA，将DFA化简
  将图(a)和(b)分别确定化和最小化
  
  
  
• 写出DFA可接收的语言

第四章（P75-例4.5、P81-1、P81-4）：

• 消除左递归
  假定关于非终极符P的规则为：P->Pα|β
  那么我们可以将P的规则改写为如下的非直接递归形式：P->βP’，P’->αP’|ε
• 证明改写后是否是LL(1)文法
  • 文法不能有左递归（左递归产生死循环）
    • 直接左递归：A→Aβ，其中A∈VN，β∈V*。
    • 间接左递归：A→Bβ，B→Aα，其中A，B ∈ VN，α，β∈V*
    • 一般左递归：A →* Aa，其中A∈ VN，a∈V*
  • 一个非终结符有多个候选，要求所有候选的所有first集的交集是空集（即Α→α|β，则FIRST(α)∩FIRST(β)=Φ）
  • 一个非终结符的候选中有ε，那么这个非终结符的follow集和他的候选的first集的交集是空集（即假若Α→α|β,β=>*ε，那么First(α)∩Follow(A)＝Φ）
• 为LL(1)文法构造预测分析表,依据预测分析表写出某输入串的预测分析过程。
  考虑下面文法G1:
  S→a|∧|(T)
  T→T,S|S
  (1) 消去G1的左递归，然后对每个非终结符写出不带回溯的递归子程序。
  (2) 经过改写的文法是否是LL（1）的？给出它的预测分析表。

（1）消去G1的左递归：S→a|∧|(T)，T→ST’，T’→,ST’|ε
（2）递归子程序：
procedures;
if sym=’a’thenadvance
elseifsym=’∧’thenadvance
elseifsym=’(’then
begin
advance
t;
ifsym=’)’thenadvance
elseerror
end
elseerror;
proceduret;
begin
s;t’
end;
procedures;
ifsym=’,’then
begin
advance
s;t’
end;

（3）

对下面的文法G

Expr→-Expr
Expr→(Expr)|VarExprTail
ExprTail→-Expr|ε
Var→idVarTail
VarTail→(Expr)|ε

（1）构造LL(1)分析表。（12分）
（2）给出对句子id—id((id))的分析过程。（8分）

（1）FIRST(Expr) = {_,(,id}
FIRST(ExprTail) = {_,ε}
FIRST(Var)={id}
FIRST(VarTail)={(,ε}
FOLLOW(Expr)={#,)}
FOLLOW(ExprTail)={#,)}
FOLLOW(Var)={_,#,)}
FOLLOW(VarTail)={_,#,)}
（2） 给出对句子id—id((id))的分析过程。（步骤符号栈输入串所用产生式)
0＃Exprid__id((id))＃
1  #  ExprTailVarid__id((id))＃Expr→VarExprTail2  #  ExprTailVarTailidid__id((id))＃Var→idVarTail
3  #  ExprTailVarTail__id((id))＃
4  #  ExprTail__id((id))＃VarTail→ε
5  #  Expr___id((id))＃ExprTail→_Expr
6  #  Expr_id((id))＃
7  #  Expr__id((id))＃Expr→_Expr
8  #  Exprid((id))＃
9  #  ExprTailVarid((id))＃Expr→VarExprTail
10  #  ExprTailVarTailidid((id))＃Var→idVarTail
11  #  ExprTailVarTail((id))＃
12  #  ExprTail)Expr(((id))＃VarTail→(Expr)
13  #  ExprTail)Expr(id))＃
14  #  ExprTail))Expr((id))＃Expr→(Expr)
15  #  ExprTail))Exprid))＃
16  #  ExprTail))ExprTailVarid))＃Exp→VarExprTai
17  #  ExprTail))ExprTailVarTailidid))＃Var→idVarTail
18  #  ExprTail))ExprTailVarTail))＃
19  #  ExprTail))ExprTail))＃VarTail→ε
20  #  ExprTail))))＃ExprTail→ε
21  #  ExprTail))＃
22  #  ExprTail  #  ExprTail→ε
23  #    #  分析成功

2.对下面的文法(G)：

E->TE’
E’->+E|ε
T->FT’
T’->T|ε
F->PF’
F’->*F’|ε
P->(E)|A|B|^

（1）计算这个文法的每个非终结符的FIRST集和FOLLOW集
（2）证明这个文法是LL（1）的
（3）构造它的预测分析表。
解：

第五章（P105-例5.8、P111-例5.11、P134-5）：

• 列出所有LR(0)项目
• 构造该文法识别活前缀的DFA
• 证明该文法是LR(0)文法或SLR(1)文法
• 构造LR(0)文法或SLR(1)文法的分析表
• 基于分析表，可写出某输入串的分析过程
  考虑文法:
  S→AS︱b
  A→SA︱a
  (1) 列出这个文法的所有LR(0)项目。
  (2) 构造这个文法的LR(0)项目集规范族及识别活前缀的DFA。
  (3) 这个文法是SLR的吗?若是,构造出它的SLR分析表。
  (4) 这个文法是LALR或LR(1)的吗?

设计应用题2道，共15分

考核：给出自然语言描述的规则要求，可用正规式、NFA描述该规则。
(1) C语言的标识符；
(2) 以01结尾的二进制数串；
(3) 含有子串010的所有二进制数串；
(4) 包含奇数个1或奇数个0的二进制串；
(5) 不包含字串abb的由a和b组成的符号串的全体。

参考博客

• 候选首符集是什么_zhixuChen200的博客-CSDN博客(https:///qq_45701514/article/details/118102285)
• JMU21级软件编译原理复习_Yef1y的博客-CSDN博客(https:///Piyriq0108/article/details/130985703)