编译原理

编译原理提纲

你的阳光学习频道 https://yoursunny.com/study/ 倾情奉献
阳光男孩著作权所有，转载请保留以上信息；本文只供在线阅读，请勿打印

声明：
本文只作为参考资料，“this article is provided as-is”；
本文作者阳光男孩不对本文内容的正确性及与考试的关联程度作出任何明示或默示的担保，只希望它对你有用。
@后是阳光男孩添加的注释，不是课程内容

第一章 引言

• 编译程序是一种特定的翻译程序：编译程序将源程序(高级语言，如C++、VB、Pascal)等价(功能上等价)翻译成目标程序(汇编或机器语言，与具体机器有关)
  • 翻译方式：编译方式（编译阶段→汇编阶段→运行阶段 或 编译阶段→运行阶段）、解释方式（源程序和初始数据同时输入解释程序，逐句解释，易查错、但效率低），根本区别在于是否生成目标代码 @可能考填空题
• 编译程序的结构
  • 编译程序的前端
    • 词法分析：识别“符号串”(“int a=1;++a;”)为“单词流”(“int”“a”“=”“1”“;”“++”“a”“;”)
    • 语法分析：分析“单词流”为“语法单位”(“int a=1;”“++a;”)
    • 语义分析和中间代码生成：根据语义规则检查“语法单位”生成“中间代码”(“a←1”“a←a+1”)
    • 代码优化：根据等价变换规则，尽量压缩目标程序的运行时间和占用空间(“a←2”)
  • 编译程序的后端
    • 目标代码生成：将“中间代码”根据机器特点变换成“目标代码”(“MOV AX,2”)
  • 编译程序的其他部分
    • 表格处理：管理“符号表”，符号表登记了源程序中出现的数据对象的信息和程序的信息
    • 出错处理：向用户报告发现的语法错误和静态语义错误；动态语义错误只有运行时才能发现、编译时无法报告
  • @了解：为什么要把编译程序分成前端和后端？可能考简答题
  • 编译程序的逻辑结构：遍

第二章 文法和语言

• 形式语言：对程序语言的形式化描述；产生语言的规则成为文法，识别语言的装置称为自动机
  • 字母表Σ：符号的非空有穷集合；每个元素称为一个符号；闭包（0个或多个符号连接成的字符串集合），正闭包（1个或多个符号连接成的字符串集合）
  • 字符串/符号串：字符组成的有穷序列；空串ε，字符串的长度，字符串的连接，字符串的方幂（Xⁿ=n个X依次连接），前缀和后缀，子串，真子串
  • 语言L：Σ上任意字符集合；每个元素称为一个句子；有穷语言，无穷语言
• 文法G=(终结符号非空有限集V_T,非终结符号非空有限集V_N,文法开始符S[S∈V_N],产生式非空有限集P)
  • 直接推导、直接归约：若A→δ∈P，则αAβ→αδβ，称αAβ可以直接推导出αδβ，αδβ可以直接归约到αAβ
  • 句型、句子：S经0步或多步可推导出α，则α是G的一个句型；只含终结符的句型称为句子
  • 文法产生的语言：G的句子的集合
  • 文法的等价：产生语言相等的两个文法等价
• 归约与句柄
  • 规范推导：每一步推导都是将句型中的最右非终结符替换成相应产生式右部，称为规范推导/最右推导；相反方向成为规范归约
  • 短语、直接短语：αβδ和αAδ都是句型，A经1步或多步可推导出β，则β是αβδ关于A的短语；若A可以直接推导出β，则β是αβδ关于A的直接短语/简单短语
  • 句柄：句型的最左直接短语
  • 素短语：含终结符的短语，且它不存在也有这种性质的真子串
• 分析树：根节点是S，每个父节点可以直接推导出它的子节点序列
  • 分析树的内部节点A及其所有后裔，称为A子树
  • 用分析树判断短语、直接短语、句柄、素短语 @比用定义判断方便，推荐
    
    • 短语：A子树对应的符号串就是关于A的短语
    • 直接短语：短语是2代子树
    • 句柄：最左的2代子树
    • 素短语：子树对应的字符串含终结符，且该子树不再包含有终结符的子树
• 二义性：一个句子能找到两种不同的规范推导/两颗不同的分析树，这个句子是二义性的；包含二义性句子的文法是二义性的
  • 文法是二义性的，但是该文法描述的语言有可能找到一个非二义的文法来描述
  • 二义性不可判定 @对于问文法是否二义的题目，注意题目中出现的句子，设法想出它的两颗分析树
• 文法的分类

文法类别、产生的语言类别	产生式要求	语言识别装置
0型 短语文法/语言	产生式右部至少有一个非终结符	图灵机
1型 上下文有关文法/语言	产生式右部不比左部短，或右部是ε	不确定的线性界限自动机
2型 上下文无关文法/语言	产生式左部是一个非终结符	非确定的下推自动机
3型 正规文法 左/右线性语言	产生式全部为A→α或A→Bα(左线性语言)， 或产生式全部为A→α或A→αB(右线性语言)	有穷自动机

你的阳光学习频道 https://yoursunny.com/study/ 倾情奉献
阳光男孩著作权所有，转载请保留以上信息；本文只供在线阅读，请勿打印

第三章 词法分析

• 词法分析器：从输入串识别单词。词法分析器设计过程：
  • 自然语言直接构造NFA 或 正规文法根据转换规则转换成NFA 或 正规表达式根据转换规则转换成NFA
  • 用子集法将NFA确定化为成DFA
  • 用分离法将DFA简化为归约的DFA
  • 写出程序流程，编写词法分析器
  • 也可以用Lex工具自动设计词法分析器
• 词法分析所用的“语言”，字母表是源程序的字母表、如{a,b,c,……,0,1,……,=,+,-,*,/,……}，句子是单词、如var
• 词法的表达方式
  
  • 状态转换图：有限的有向图，节点表示状态，有向边表示输入这条边上标注的字符后状态的变化，到达某个终态就识别出一个单词
  • 正规式/正规表达式：精确定义单词符号集的一种表示法，每个正规式都对应表示一个正规集 @具体定义略
  • 正规文法
  • 有限自动机FA：更一般化的状态转换图
    • 非确定有限自动机NFA M_n=(字母表Σ,状态集S,初态集s₀,终态集F,δ)；δ(S_i,a)={s₁,s₂,……}表示状态S_i时遇到输入符号a可以转换到{s₁,s₂,……}这些状态之一、但不确定到底转换到那个状态；NFA识别慢、占用空间小
    • 确定有限自动机DFA M_d=(字母表Σ,状态集S,一个初态s₀,终态集F,δ)；δ(S_i,a)={s_j}表示状态S_i时遇到输入符号a应该转换到状态s_j(只有惟一的这个状态)；DFA识别快、易于实现
    • FA可以用状态转换图、状态转换矩阵表示
    • FA M识别的语言：初态到终态的一条通路上各有向边标注的字符依次连接得到的句子是FA M所接受的句子，这种句子的集合是FA M识别的语言，记作L(M)；若某个初态是终态，则句子ε能被FA M接受
  • 正规式、正规文法、NFA、DFA是等价的——他们具有相同的描述能力
• NFA的确定化：子集法
  • 空闭包ε-closure(I)：状态子集I的所有状态、从ε-closure(I)的任意状态出发经过ε通路可到达的所有状态，都属于ε-closure(I)
  • a弧转换move(I,a)：从I的每个状态经过1条标注有符号a的有向边能到达的状态集合
  • I_a子集I_a=ε-closure(move(I,a))：从I的每个状态出发，经过0或多条ε有向边、1条a有向边、0或多条ε有向边，可以到达的状态的集合
  • 确定化算法
    • 从ε-closure(s₀)开始，求出此状态子集对所有符号的I_a子集
    • 对求出状态子集重复这个过程，直到不再出现新的状态子集
    • 每个处理过的空闭包都成为所求DFA的一个状态
    • 初态是包含原初态的状态子集，终态是包含原终态的状态子集
• DFA的简化：分离法
  • 等价状态：触发条件和下一条件都相同的状态
  • 无关状态：从初态起，任何输入序列都无法到达的状态
  • 简化算法
    • 删除所有无关状态
    • 将所有状态放在一个集合里
    • 每次将一个状态集划分成互不相交的两个子集，使它们可区分；如对{1,2,3}，1_a≠2_a=3_a，则{1}与{2,3}可区分
• 由正规式构造等价的NFA
  • 最初的NFA
    
  • 将正规式按下列三条规则进行分解，直到各有向边上只有ε和Σ的字母为止
    
• @本章肯定会考一道大题

第四章 语法分析

• 语法分析器：从终结符号串识别程序语句。
  • 基本分析方法：自顶向下分析（递归下降，预测分析表），自底向上分析（算符优先，LR）
• 语法分析所用的“语言”，字母表是终结符集合、如{int,char,double,变量名,=,+,-,*,/,常数,字符常量,……}，句子是程序语句
• 递归下降分析器
  • 对文法要求1：无公共左因子
    • 提取左因子的方法：
      A→αβ₁|αβ₂|……|αβ_n|δ₁|δ₂|……|δ_m (其中δ_i不以α为前缀)
      改为 A→αA'|δ₁|δ₂|……|δ_m A'→β₁|β₂|……|β_n
  • 对文法要求2：无左递归
    • 消除左递归的方法：
      A→Aα₁|Aα₂|……|Aα_n|β₁|β₂|……|β_m
      改为 A→β₁A'|β₂A'|……|β_nA' A'→α₁A'|α₂A'|……|α_nA'|ε
  • 对文法要求3：无间接左递归；消除算法为对非终结符排序，只允许小号依赖大号、否则代入，就可全部转换成直接左递归、予以消除
  • 分析器实现：根据产生式，为每个非终结符写一个递归过程
• 非递归的表驱动预测分析器
  • 对文法要求：LL(1)文法
    • LL(n)文法：上下文无关文法G，面对某个非终结符，需要预取后续的n个输入符号，可以惟一决定使用那个产生式进行匹配
  • 分析器的组成部分：分析表、分析栈、控制程序
  • 分析栈：开始时，栈底有结束标志$、文法开始符；输入串的最后也添加一个结束标志$
  • 预测分析表：二维数组M[A,a]，遇到非终结符A、预取符号a，应该使用M[A,a]表示的产生式进行推导。
    • FIRST集：若α是终结符，FIRST(α)={α}。若α是非终结符，FIRST(α)是α能够推导出的所有句子的第一个符号组成的集合；句子是由终结符组成的，这些符号必是终结符；若α能够推导出ε，则ε∈FIRST(α)
    • FOLLOW集：FOLLOW(A)是从语言的所有句型中，直接跟在非终结符A后面的所有终结符组成的集合；还有，$∈FOLLOW(A)
    • 预测分析表的构造：
      对每个a∈FIRST(α)，令M[A,a]=A→α
      若ε∈FIRST(α)，则对每个b∈FOLLOW(A)，令M[A,b]=A→α
      其他未定义的M[A,a]全部记错误标志
  • 控制程序 @略
  • 错误处理 可能发生的错误：栈顶终结符与输入字符不同，M[栈顶非终结符,输入字符]记有错误标志
• 算符优先分析法
  • 对文法要求：算符优先文法；这个要求对文法限制较多，导致算符优先分析法应用不广泛
    • 算符文法：上下文无关文法G，产生式右部不是ε、不含相连的非终结符
    • 优先关系：算符文法G的任意两个终结符a和b，定义它们之间的优先关系——
      • a·=b，若P→…ab…或P→…aQb…
      • a<·b，若P→…aQ…、Q可推导出b…或Rb…
      • a·>b，若P→…Qb…、Q可推导出…a或…aR
      • $<·任何符号，任何符号·>$，$·=$
      • 以下推断不成立：a·=a，a<·b则b·>a，a与b间优先关系存在/惟一
    • 算符优先文法：任意两个终结符之间优先关系至多只有一种的算符文法
  • 分析器的组成部分：分析表，分析栈，控制程序
  • 分析表：优先关系表，记录了所有终结符间的优先关系
    • FIRSTVT集：FIRSTVT(P)是P可以推出的符号串的第一个终结符组成的集合
    • LASTVT集：LASTVT(P)是P可以推出的符号串的最后一个终结符组成的集合
    • 优先关系表的构造：
      Q→…aP…，则对每个b∈FIRSTVT(P)，有a<·b
      Q→…Pb…，则对每个a∈LASTVT(P)，有a·>b
      Q→…ab…或Q→…aPb…，则a·=b
  • 分析栈：已经移进的符号串
  • 控制程序：当a·>b时归约、a·=b或a<·b时移进；归约时，向栈底查找，直到栈内终结符<·栈顶终结符，依此选择产生式
  • 错误处理 可能发生的错误：栈顶终结符与输入符之间无优先关系，应归约时无产生式匹配
• LR分析方法：自底向上，对文法限制最少、效率同样很高
  • 分析器的组成部分
    • 分析表——action表：action[s_i,a]表示在状态s_i下、输入终结符a时应采取的动作
      s_j：移进，将状态s_j与符号a推入栈顶
      r_j：归约，将栈顶按第j个产生式归约
      acc：分析成功，输入串被接受
      (空白)：出错
    • 分析表——goto表：goto[s_i,A]表示在状态s_i下，对非终结符A的下一个状态
    • 分析栈：已识别的符号串
    • 控制程序 @略
  • @LR分析方法的关键在于分析表的构造，下面介绍的都是分析表构造的方法——
    @这些步骤是循序渐进的，请读者不要试图跳过任何一个步骤，否则将无法理解后面的步骤
  • 活前缀：规范句型的一个前缀，它不含句柄之后的任何符号（即：规范句型的[句柄之前部分和句柄]的前缀）
    S可规范推导出δAω，可继续规范推导出δαβω，则αβ是δαβω的句柄，δαβ的任何前缀都是δαβω的活前缀
    • @ 为什么要识别活前缀？——句柄是活前缀的后缀，识别活前缀就可以找到句柄；找到了句柄，就可以对句柄归约。
    • 项目：用圆点.表示识别位置，E→E+T有以下项目
      E→.E+T E→E+.T ——待约项目，圆点后是非终结符，等待这个非终结符的归约
      E→E.+T ——移进项目，圆点后是终结符，应该移进
      E→E+T. ——归约项目，产生式右部全部在分析栈顶，应该归约
    • 拓广的文法：文法中，增加一条产生式S'→S，其中S是原来的文法开始符；这个拓广的文法与原文法等价
    • 构造识别活前缀的DFA方法：使用LR(0)项目集规范族构造
  • LR(0)项目集规范族C
    • 项目对活前缀有效：S可规范推导出δAω，可继续规范推导出δαβω，则项目A→α.β对活前缀δα有效
    • 活前缀的有效项目集：对这个活前缀有效的项目组成的集合
    • 文法G的LR(0)项目集规范族C：有效项目集的集合
    • closure(I)项目集：包含I的所有项目；还包含closure(I)中的每个待约项目中圆点后面那个非终结符对应的每个产生式的一个形如B→.η的项目（即A→α.Bβ B→η则包含B→.η）
    • go(I,X)=closure(J)，其中J是I的各待约项目、移进项目圆点右移一位形成的项目（即把A→α.Xβ变成A→αX.β）组成的集合。go(I,X)的含义：若I是δα的有效项目集，则go(I,X)是δαX的有效项目集
    • 文法G的LR(0)项目集规范族C的构造：
      刚开始时，C={ closure({[S'→.S]}) }。
      对C的每个项目I，对每个终结符和非终结符X，若go(I,X)不为空，则将它加入C。
      重复上个步骤，直到C不再增大。
    • 用LR(0)项目集规范族C可以构造识别活前缀的DFA，每个有效项目集是一个状态，closure({[S'→.S]})是初态，所有状态都是终态，X是状态间转换的条件
    • LR(0)项目集规范族C可能带来的冲突情况
      • 移进-归约冲突：E→E+T. T→T.*F
      • 归约-归约冲突：A→α. B→α.
      • 不存在“移进-移进冲突”
  • SLR分析表
    • 项目集I={X→α.bβ,A→α.,B→α.}，若{b}与FOLLOW(A)与FOLLOW(B)两两不交，移进或归约动作便可唯一确定
    • SLR分析表的构造算法
      • 构造文法的LR(0)项目集规范族C={I₀,I₁,I₂,……,I_n}，I_i对应状态i,I₀是closure({[S'→.S]})
      • 对每个I_i——
        若A→α.aβ∈I_i、go(I_i,a)=I_j，则action[i,a]=S_j
        若A→α.∈I_i、A→α是第j个产生式，则action[i,a]=r_j
        若[S'→S.]∈I_i，则action[i,a]=acc
      • 若go(I_i,a)=I_j、A∈V_N、，则goto[i,A]=j
      • 剩下的项，计入出错标志
        
    • 上述算法构造的分析表，如果不含多重定义，就是文法G的SLR分析表，G是SLR(1)文法；SLR(1)文法是一个较高的要求；而多重定义就是冲突情况的表现
  • LR(k)分析表
    • 项目表示为{A→α.,a₁……a_k}；只当后续的k个输入恰为a₁……a_k时才能将α归约为A；归约项目才需要a₁……a_k，待约、移进项目不需要
    • @只考上述搜索符含义，构造方法等不考，略
  • LALR(k)分析表：合并LR(k)分析表的状态，减少状态数 @不考
• 二义文法的应用：二义文法不可能是LR文法，SLR和LR(k)不能解决移进-归约冲突；分析二义文法时，一般不是把它改写成等价的非二义文法，而是采取结合性、优先级等附加规则来避免多重定义项
• 用YACC工具可以自动设计LALR分析器

第五章 语法制导翻译和中间代码生成

• 翻译：对语法分析树进行语义分析、检查，生成中间代码
  • 静态语义检查：类型检查，控制流检查，名字匹配检查，一致性检查
  • 语法制导翻译：为每条产生式写相应的翻译子程序，LR分析中按句柄归约时调用这个子程序
• 中间语言
  • 设计原则：在逻辑运算层次上，与机器特性无关
  • 特定：只包含基本运算结构，只包含基本控制结构
  • 表示方式
    • 后缀式/逆波兰式
    • 语法树
    • dag无环有向图
    • 三地址码（三地址码的存储：四元式 三元式 间接三元式）
• 说明语句的翻译：不生成中间代码，只登记名字、类型、地址到符号表
• 赋值语句的翻译：查出左值的地址p；求出右值到临时变量t；生成中间代码p:=t
• 控制流语句的翻译
  • 布尔表达式的翻译方法
    • 数据表示法 0=false,1=true
    • 解释法
      A or B    if A then true else B
      A and B   if A then B else false
      not A     if A then false else true
  • 控制流语句中的布尔表达式E的翻译：翻译成一系列条件转移/无条件转移，转向真出口E.true或假出口E.false
  • 回填技术：翻译时遇到未确定出口地址的转移语句，在地址处填上0，并用一个链表跟踪所有转到同一出口地址的转移语句；待地址确定，沿链表回填这些转移语句的出口地址

你的阳光学习频道 https://yoursunny.com/study/ 倾情奉献
阳光男孩著作权所有，转载请保留以上信息；本文只供在线阅读，请勿打印

第六章 运行时存储空间管理

• 存储空间
  • 用途：代码空间，数据空间
  • 两级地址：物理地址，逻辑地址
• 变量的存储分配：静态变量（全局变量），半静态变量（局部变量），半动态变量（调用函数时可确定的变量），动态变量（malloc）
• 活动记录：活动记录中存储了程序单元(函数)每次激活的信息，包括返回指针、参数、局部变量等
  • 静态分配：每个函数在编译时创建一个活动记录；要求无递归调用、无动态数组、无动态类型
  • 栈式分配：函数激活时创建活动记录，局部变量相对活动记录开头有一个常数偏移；要求后进先出、静态嵌套、静态作用域
  • 堆分配：随机malloc和free；
    运行时要管理堆区，malloc(n字节)（首次拟合法 最优满足法 最差满足法）、free（合并连续的空闲快）
• 参数传递：数据参数（引用调用 值调用(传值 结果调用 传值的结果)），过程参数，类型参数
• (编译过程中的)符号表：记录用户定义的identifier、类型、地址，常用线性表或散列表实现
• (程序模块的)符号表：记录了[模块中引用的、但未定义的符号]，[模块中定义的、对外公开的符号]
  • 连接程序link检查各程序模块的符号表，确保不存在未定义的符号
• 内存管理的安全分配：缓冲区溢出原理和防范

第七章 代码优化

• 优化：一种等价、有效的程序变换
• 局部优化：对“基本块”(顺序执行、单一入口、单一出口的最长语句序列)进行优化
  • 优化技术：合并已知量，删除公共子表达式，删除死代码
  • 构造dag进行局部优化，构造方法：
    对于语句(x := y op z)
    • 在已有dag中寻找或创建y、z当前值结点
      （例如对y，若存在一个结点表示y的当前值，在此结点上增加标注y，否则创建一个结点值为y的当前值、标注y）
    • 若y、z都是常数，计算y op z，寻找或创建(y op z)结点，若y、z是当前语句建立的、则删除；
      若y、z不都是常数，寻找或创建这个结点：标注op、左子结点是y、右子结点是z
    • 在上一步求得的(y op z)或op结点上标注x；
      若另一个结点上标注有x，则移除那个标注
    • 处理下一个语句直到结束
  • 注意：数组、指针等会导致变量内容间接改变
• 循环优化
  • 程序流图：每个结点代表一个基本块，有向边代表基本块间的转移
  • 代码外提：将循环不变运算提到循环入口结点前计算
    • 循环不变运算：各操作数都是——常量/循环外定值的变量/另一个循环不变运算结果
    • 等价性保证：该运算一定会执行(不处于分支中)、执行前未引用、只有一个定值点、循环体至少执行一次，才可外提该运算
  • 强度削弱：for(i=0;i<L;++i){j=K*i+B;……}改成for(i=0,j=B;i<L;++i,j+=K){……}，乘法变成较快的加法
  • 删除归纳变量：for(i=0;i<L;++i){j=K*i+B;……}在循环体内无其他对i的引用，就改成for(j=B;j<K*L+B;j+=K){……}，删除了i
• 窥孔优化：在目标代码生成阶段进行

第八章 代码生成

• 代码生成器：从中间代码生成等价有效的目标代码
  • 输入：中间代码+符号表
  • 输出：绝对机器语言代码(直接执行) 或 可重定位的机器语言(需要link) 或 汇编代码
  • 代码生成器知道：CPU运行模式，指令系统，寻址方式，寄存器数量和类型……
• 寄存器分配
  • 要引用的变量尽可能保存在寄存器；不再引用的变量所占寄存器尽早释放；到达基本块出口时释放所有寄存器；寄存器不够时释放引用点最远的变量所占寄存器
  • 循环结构的寄存器分配：循环中最频繁使用的变量可以固定分配寄存器
• 窥孔优化：删除多余存取指令，删除死代码，控制流优化，强度削弱，利用机器特点
• 由dag生成代码
  • 计算次序：使运算紧跟它的左操作数的运算，dag为树时的计算次序是“前序左深度优先遍历的反序”
  • label(n)=在不让中间结果进入主存的条件下，计算结点n所需的最少寄存器数；可以自下而上计算label(n)
  • 自顶向下递归[处理子树，生成当前节点代码]；用(编译程序的)栈保存可用的寄存器；子树生成完毕后，根结果在栈顶寄存器；寄存器不够时用临时变量补充

@2008-01-22 19:45，写完了！阳光男孩希望这篇文章对你有用