编译程序总框

词法分析

1. NFA转DFA

   1. 

      合并NFA所有可以同时到达的状态集，若状态集中包含接收状态，则新状态为接收状态

   2. 最小化状态数：若两个状态同为接收状态或非接收状态，且接收相同的字符去到相同的状态，则这两个状态是等价的，可以合并为一个状态

2. 五种类型Token：标识符，保留字，数字，操作符，特殊符号

语法分析

四种文法

1. 上下文无关文法（CFG）

   • 概念：一个四元组 G=(V_T,V_N,S,P),其中：

     • V_T：终结符集合（非空）
     • V_N：非终结符集合（非空）
     • S：文法的开始符号
     • P：产生式集合

       巴克斯范式 把—>用::=表示

   • 句型、句子和语言：

     • 可由开始符号推出的即为句型
     • 不含非终结符的句型叫句子
     • 所有句子的全体叫做语言

   • 若一个句子不对应唯一的一颗语法分析树，则这个文法是二义的；若一个语言找不到无二义的文法，则这个语言是二义的

2. 抽象语法树

   • 语法分析树包含了过多的无用信息，

     

     语法分析树与抽象语法树

3. 语法分析

   1. 目标：给定一个token序列，找到一个语法分析树与之匹配

   2. 匹配方法：

      • 自顶向下：从开始符号进行推导，试图找到一个推导方式可以推导成该用户代码

        • 问题：应该采用哪个产生式进行规约

        • LL(1)文法:第一个L表示从左到右扫描输入字符串，第二个L表示最左推导，k表示需要向前看k个token

          • FIRST(β) = { a ∈ V_T | β => a……} , if β=> ε then ε ∈ FIRST(β)
          • FOLLOW(A)={a ∈ V_T | S=> …Aa…}， if S=> …A, then $ ∈ FOLLOW(A)

          • 如何判断一个文法是LL(1)的：

            • For each production A → α₁ | α₂ |…| α_n , for all i and j, 1≤i, j ≤ n, i≠j , First( α_i ) ∩ First(α_j ) = Φ

            • For each nonterminal A such that First(A) contains ε, First(A) ∩ Follow(A) = Φ.
              
              若一个文法是左递归的或者有左公因子，那么它一定不是LL(1)文法
              
              将非LL(1)文法转换为LL(1)文法

              • 消除左公因子：

                • A→αβ₁ |αβ₂ |…|αβ_n
                  
                  可以重写为
                  
                  A→αA’
                  
                  A’→ β₁ |β₂ |…|β_n

              • 消除左递归：

                • A→Aα₁ |Aα₂ |…|Aα_m |β₁ |β₂ |…|β_n
                  
                  可以重写为
                  A→β₁A’|β₂A’|…|β_nA’
                  
                  A’→α₁A’|α₂A’|…|α_mA’|ε

        • 解决：可预测的分析方法

          • 递归下降分析法：首先判断是否为LL(1)文法，然后构造递归下降分析器
          • LL(1)分析法：
            1. 首先构造LL(1)分析表，对每个M[A,a]，确定每个产生式A->α在表中的位置。对每个终结符 a ∈ FIRST(α)，把A->α加至M[A,a]中；若 ε ∈ FIRST(α)，则对任何 b ∈ FOLLOW(A) 把 A-> α 加至M[A,b]中
            2. 利用符号栈进行分析。将开始符号推入栈顶，当前输入字符为a，利用LL(1)分析表进行相应的操作
               
               
          • 错误恢复——恐慌模式：语法分析器忽略输入中的一些符号，直到输入中出现同步词法单元集合中的某个词法单元
            • 常将FOLLOW(A)放到非终结符A的同步集合中
            • 较高层次的开始符号加入到较低构造的同步集合中去
            • FIRST(A)
            • 默认使用推导出空串的产生式
            • 若栈顶的一个终结符不被匹配，则将该终结符弹出栈，并发出一个消息称已经插入了这个终结符

      • 自底向上：从用户代码开始，找到一个规约的方法使得其能回到开始符号

        • 这个从左到右自底向上的分析相当于最右推导的逆运算，每一个最右推导得到的中间句型称为右句型
        • 短语、直接短语和句柄：以某非终结符为根的所有末端结点从左到右排列就是相对于该非终结符的一个短语；如果子树只有两代，该短语就是直接短语；句柄是最左端的直接短语，即需要马上进行规约的直接短语；
        • 前缀、活前缀：字的前缀指字的任意首部，如字abc的前缀有ε,a,ab,abc；活前缀指不含句柄之后的任何符号的前缀

        • LR(K)分析法：L表示从左到右处理输入，R表示会产生一个最右推导，k表示需要向前看k个token

          LR(0) < SLR(1) < LR(1) < 无二义文法

          1. 构造LR分析表：先拓展文法，再根据所有项目构建DFA
             • 若不存在一个项目集既含规约项目又含移进项目或者含有多个规约项目，则该文法是 LR(0) 的文法，若项目集I_k属于移进项目且GO(I_k,a)=I_j，a为终结符，则置ACTION[k,a]为sj；若I_k为规约项目，则所有a，ACTION[k,a]为rj（j表示第j个产生式）；若S’->S·属于I_k，则置ACTION[k,#]为acc

            - 若有规约-移进冲突，使用 **SLR(1)** 解决冲突：假定该状态集移进项目的下一个终结符与规约项目的FOLLOW两两不相交（包括不得有两个#），则面临任何输入a都有唯一选择
          
            - 若FOLLOW集合相交，则使用 **LR(1)** 解决冲突：项目附带1个终结符，称为向前搜索字符串或展望串，利用这个展望串来进行规约，展望串通过下一个非终结符的FIRST集合或下一个终结符生成
          

          

语法制导的翻译

1. 语法制导定义（SDD）是一个上下文无关文法和属性及规则的结合

   一个没有副作用的SDD也称为属性文法

   1. 属性的区分：
      • 综合属性：根据右部候选式中的符号的属性计算左部被定义符号的综合属性，既根据子结点的属性和父节点自身的属性来计算父节点的综合属性
      • 继承属性：根据右部候选式中的符号的属性和左部被定义符号的属性计算右部候选式中的符号的继承属性，既根据父节点和兄弟结点的属性计算子节点的继承属性

   1. 属性计算的三种方法：

      • 依赖图：依赖图为每个属性设置一个结点，若属性b依赖于属性c，则从属性c的结点有一条有向边连接到属性b的结点。首先构造有向图，若该有向图不存在环，则称该文法为良定义的
      • 树遍历算法：如果还有没被计算的属性，就遍历树，将所有能计算的属性都计算出来
      • 一遍扫描：使用mknode(),mkleaf()边构建抽象语法树边计算属性
        

   2. 属性文法分类：

      • S-属性文法：所有属性都是综合属性的属性文法
      • L-属性文法：每个产生式每个属性或者是综合属性，或者这个继承属性只依赖于这个结点的左兄弟属性与父节点的继承属性

        S-属性文法一定是L-属性文法

2. 一个显示了所有属性值的语法分析树称为注释语法分析树

3. 语法制导的翻译方案（SDT，翻译模式）：原来的语义规则只给出了属性计算的定义，没给出属性计算的次序，翻译模式把语义动作用花括号{}括起来，插入到产生式右部合适的位置上。如果既有综合属性又有继承属性，在建立翻译模式时就必须保证：

   1. 产生式右边的符号的继承属性必须在这个符号以前的动作计算出来
   2. 一个动作不能引用这个动作右边的符号的综合属性
   3. 产生式左边的非终结符的综合属性只有在它所引用的所有属性都计算出来以后才能计算

4. 递归下降翻译器

   1. 按照产生式右部从左到右，对于终结符、非终结符和语义动作，分别实现
      • 对带有综合属性x的终结符X，把x的值存入为X.x设置的变量中。然后匹配X，读入下一个输入符号
      • 对每个非终结符B，产生一个右边带有函数调用的赋值语句c=B(b1,b2,…)，其中，b1…是为B的继承属性设置的变量，c是为B的综合属性设置的变量
      • 对于语义动作，把动作的代码抄进分析器中，用代表属性的变量来代替对属性的每一次引用

中间代码生成

1. DAG——一个用来表示具有公共子表达式的语法的有向无环图

2. 步骤：

   1. 中间代码生成
   2. 生成某种形式的汇编代码而不是可执行的代码
   3. （可选）代码优化

3. IR(Intermediate Representation)

   • 一种在翻译过程中用来表示源代码的数据结构，如抽象语法树

4. 中间代码(Intermediate Code)

   • 用一种顺序形式来替代中间表示的更类似于目标代码的形式

   • 其中最流行的中间代码：三地址码（TAC）：

     • 三地址码示例：

       

       三地址码示例

     • 表示方法：三元组与四元组：

       • 四元组：运算符，2个操作数地址，1个结果地址
       • 三元组：运算符，2个操作数地址，指令本身用来存储临时变量
       • 优劣：三元组节省地址空间，并且不需要额外为临时变量命名，但是三元组在优化的时候位置会变化导致指令也需要相应变化，而四元组更适合优化
       • 间接三元式——三元式表+间接码表：三元式表存储操作，间接码表存储操作次序，这样优化代码的时候只需要更改间接码表

5. SSA——一种IR方便了代码优化

6. 控制流

   • 多遍扫描

     • 建立语法树
     • 自上而下地计算继承属性
     • 自下而上计算综合属性生成代码

   • 一遍扫描

     • 约定：
       • (jnz,a,-,p) 表示if a goto p
       • (jrop,x,y,p) 表示 if x rop y goto p
       • (j,-,-,p) 表示 goto p
     • 扩展文法加上一个ε产生式，用于存储下一个非终结符代码的起始位置
     • 对于E -> id₁ relop id₂，生成truelist与falselist链表，发射一个真跳转四元组与一个假跳转四元组
     • 规约则将进行回填

7. 代码优化的主要方法：

   1. 将经常使用的值放在寄存器中
   2. 减少不必要的操作，如将公共计算的代码结果保存起来
   3. 用一些更廉价的方法实现某种耗时操作，如将递归转换为循环