编译原理复习

什么是有穷自动机？NFA和DFA有什么区别(2023/12/18)

一个确定的有穷自动机（DFA）M是一个五元组M=（S，Σ，δ，$s_0$，F），其中

• S是一个有穷集，它的每一个元素称为一个状态
• Σ是一个有穷字母表，它的每个元素称为一个输入符号，所以也称Σ为输入符号表
• δ是转换函数，是在S×Σ→S上的单值部分映射，即，如果 δ（s，a）=s’，（s∈S，s’∈S）就意味着，当前状态为s，输入符为a时，将转换为下一个状态s’，s’称作s的一个后继状态
• $s_0$ ∈S是唯一的一个初态
• F ⊂ S是一个终态集（可空），终态也称可接受状态或结束状态

一个非确定的有穷自动机（NFA）M是一个五元组：$M=（S，Σ， δ，S_0，F）$,其中:

• S是一个有穷集，它的每个元素称为一个状态；
• Σ是一个有穷字母表，它的每个元素称为一个输入符号，所以也称Σ为输入符号表；
• δ是状态转换函数，是在S×Σ*→S的子集的映射，即， $δ : S×Σ^*→2^S $；表明在某状态下对于某输入符号可能有多个后继状态；
• $S_0 ⊂ S$是一个非空初态集；
• $F ⊂ K$是一个终态集（可空）。

简述推导和规约的概念(2023/12/18)(2022-2023第二学期)

• 推导：将非终结符替换为它的某个产生式的体。
• 归约：将一个与某个产生式的体相匹配的特定子串替换为该产生式的头。

什么是文法的二义性？为什么要消除二义性？如何消除二义性？(2022-2023第二学期)

• 给定文法，若存在某个句子，有多个最左/右推导，即可以生成多棵解析树，则这个文法就是二义的。
• 通常要求程序设计语言的文法的无二义性的，否则会导致一个程序有多个“正确”的解释。即使文法允许二义性，但仍需要在文法之外加以说明，来剔除不要的语法分析树。总之，必须保证文法消除了二义性使得最后的语法解析树只有一棵。
• ①改写原文法 ②引入消除二义性的规则。

简述递归下降语法分析技术的基本思想。

• 对于LL(1)文法，不必实际构建解析树，而且可以借助系统栈来实现预测分析，这就是递归下降算法。

简述划分基本块的算法。

• ①确定首指令：第一个三地址指令；任意一个转移指令的目标指令；转移指令后的一个指令。
• ②确定基本块：从一个首指令开始到下一个首指令之间的部分为一个基本块。

什么是语法制导定义（SDD）? L-SDD和S-SDD的区别

• SDD
  • SDD 将每个文法符号和一个语义属性集合相关联，将每个产生式和一组语义规则相关联，用来计算该产生式中各文法符号的属性值。
• L-SDD
  
• S-SDD
  • 仅仅使用综合属性的SDD称为S属性的SDD

简述语法制导翻译的思想

• 对字符串进行语法分析，构建语法分析树，然后根据需要遍历语法树并在语法书的各结点处按语义规则进行计算。这种有源程序的语法结构驱动的处理方法就是语法制导翻译。

列举至少四种代码优化的方法，并简述他们的基本思想/写出至少四个优化方法，并简述其算法。

• ①删除公共子表达式：如果表达式 x op y 先前已被计算过，并且从先前的计算到现在，x op y 中变量的值没有改变。那么可以删除公共子表达式。
• ②删除无用代码：在复制语句x = y的后面尽可能地用y代替x
• ③常量合并：如果在编译时刻推导出一个表达式的值是常量，就可以 使用该常量来替代这个表达式
• ④代码移动：对于那些不管循环执行多少次都得到相同结果的表达式，在进入循环之前就对它们求值。
• ⑤强度削弱：用较快的操作代替较慢的操作。

解释综合属性和继承属性，终结符的综合属性和继承属性是什么

• 属性文法：
  • 基础文法
  • 每个文法符号都有一个属性
  • 每个文法产生式$A → α$有一组形式为$b :=f(c_1, c_2, …, c_k )$的语义规则，其中$f$是函数，$b,c_1, c_2, …, c_k$ 是该产生式文法符号的属性
• 综合属性
  • b是A的属性，$c_1, c_2, …, c_k$是产生式右部文法符号的属性或A的其他属性
• 继承属性
  • b是产生式右部某个文法符号X的属性

什么是依赖图

• 依赖图是用来描述相应语法树中属性的信息流；
• 在语法树的基础上，对每个文法符号的属性都有一个结点
• 针对每一个语义规则，从产生式右边的属性向产生式左边的属性引一条有向边

说明局部优化和全局优化的不同

• 局部优化是指单个基本块范围内的优化；全局优化是指面向多个基本块的优化。

什么是上下文无关文法CFG

• 这个文法中所有的产生式左边只有一个非终结符

什么是LL1文法

• 第一种
  
• 第二种
• 一个上下文无关文法是LL(1)文法的充分必要条件是每个非终结符A的两个不同产生式，$A→α ,A→β$；满足$SELECT(A →α ) ∩ SELECT(A →β)= Ф$。其中α、β不能同时 $\overset{*} {\Rightarrow} \varepsilon$。

3型文法

• 产生式右边要么没有非终结符，要么只有一个