# 编译原理填空题
编译程序是将 高级语言程序 翻译成 汇编语言或机器语言程序。
编译程序的工作过程一般可以划分为 词法分析，语法分析，语义分析，中间代码生成，中间代码优化，目标代码生成几个基本阶段，同时还会伴有 表格处理，出错处理 。
对编译程序而言，输入数据是 源程序，输出结果是 目标程序 。
程序设计语言的单词符号一般可分成下列 5 种 保留字，标识符，常数，算符，界符。
一个程序设计语言是一个记号系统，如同自然语言一样，它的完整的定义应包括 语法和 语义两个方面。
文法中的终结符和非终结符的交集是 空集 。
最左推导是指每都对句型中的 最左 非终结符进行扩展。
在语法分析中，最常见的两种方法，一是 自底向上 分析法，另一是 自顶向下 分析法。
一个句型中的最左简单短语称为该句型的 句柄 。
若 A={a , b} , B={c , d} , 则集合 AB = {ac , ad , bc , bd}。
设 x=AB , 则 x0= ε , x1= AB , x2 = ABAB。
文法描述的语言是该文法一切 句子的集合。
设文法 G 有两条产生式（1）S→0S1 （2）S→01 , 则该文法的语言 L(G)={0n1n│n≥1} 。
一种描述字符串集合的工具叫文法，它是由一个四元式组组成的，分别是 VT（终极符集） , VN（非终极符集合） , P（产生式集合） , S（开始符） 。
乔姆斯基把文法分成四种类型，即 0 型，1 型，2 型和 3 型。其中 2 型文法又称为上下文无关文法，3 型文法又称为正规文法。
上下文无关文法 有足够的能力描述现今程序设计语言的语法结构，比如描述算术表达式，描述各种语句等。
最右推导 称为规范推导。
最右推导亦称为 规范推导，由此得到的句型称为 规范 句型。
令 ={a,b} , 上的正规式（a|b）* 对应的正规集为: {ε , a , b , aa , ab… , 所有 a , b 组成的串} 。
令 ={d,.,e,+,-}, 则上的正规式 d*(.dd*|ε)(e (+|-|ε) dd*|ε) 表示的是 无符号数 。
设 Σ={a , b} , 则 Σ 上的正规式（a∣b）(a∣b) 相应的正规集为 {aa,ab,ba,bb}。
一种描述字符串集合的工具叫自动机，它是由一个五元组组成的，分别是 字母表，状态集，开始状态，末态集，映射集 。
确定有限自动机 DFA 是 NFA 的一个特例。
编译技术中的词法分析阶段，常用的描述单词词法的工具主要包括正规文法和 正规式 。
词法分析阶段，常用的识别单词的有效工具是 有穷自动机 。
所谓一个语言的 语法 是指一组规则，用它可以形成和产生一个合适的程序。
自顶向下的语法分析方法的基本思想是：从文法的 开始符号 开始，根据给定的输入串并按照文法的产生式一步一步的向下进行 直接推导，试图推导出文法的 句子，使之与给定的输入串 匹配 。
预测分析法属于 自顶向下 的语法分析方法。
编译技术中，常用的确定的自顶向下语法分析技术有预测分析法和 递归下降法 。
预测分析程序是使用一张 分析表 和一个 符号栈 进行联合控制的。
自底向上的语法分析方法的基本思想是：从输入串入手，利用文法的产生式一步一步地向上进行 直接归约，力求归约到文法的 开始符 。
自底向上分析法采用 移进，归约，错误处理，接受 等四种操作。
分析句型时，应用算符优先分析技术时，每步被直接归约的是 最左素短语，而应用 LR 分析技术时，每步被直接归约的是 句柄 。
已知算符文法 G: S→b|∧|(T) T→T,S|S 则 F IRSTVT ((T)=
b, ∧, ( , ,。自下而上 语法分析的关键问题是精确定义可归约串的概念。
LR 分析法属于 自底向上 的语法分析方法。
LR 分析器由 总控程序，分析表，分析栈 3 个部分组成。
活前缀是指 规范句型 的一个前缀，这种前缀不含 句柄 之后的任何符号。
LR 语法分析技术的 LR (0) 项目中，根据分隔符所在位置及分隔符后符号的类别，我们称 A→α.[n] 称为归约 项目 ；对文法开始符号 S΄ , 称 S΄→α.[n] 为 接受 项目；称 A→α.aβ[n]（a 为终结符）为 移进 项目。
假定一个 LR (0) 规范族中含有的项目集 (状态) I , I={X→α.bβ[n] , A→γ.[m] , B→δ.[k]} , 则该项目集中含有 移进 - 归约 冲突和 归约 - 归约 冲突。
属性文法中，文法符号的属性有两种，一种称为 继承属性，另一种称为 综合属性。
在编译技术中，常用的中间代码表示有 抽象语法树（AST） , 四元式（TAC） , P-code,Bytecode 及 SSA。
编译技术中，常用的两种语义计算模型有 属性文法 和 翻译模式 。
根据属性文法中包含属性的类别，属性文法可分为 S - 属性 文法和 L - 属性文法。
翻译模式在形式上类似于属性文法，但允许用 { } 括起来的语义动作出现在产生式右端的 任意 位置，和属性文法相对应，翻译模式分为 S - 翻译模式 和 L - 翻译模式 。
优化就是对程序进行各种 等价 变换，使之能生成更有效的 目标代码 。
依据优化所涉及的程序范围，编译过程中可以进行的优化可以分为 局部优化， 循环优化， 全局优化。
局部优化是在 基本块 范围内进行的一种优化。
在程序流图中，对任意两个结点 m 和 n 而言，如果从流图的首结点出发，到达 n 的任一通路都要经过 m , 则称 m 是 n 的 支配结点（必经结点） 。
