编译原理知识汇总

转自：https://www.jianshu.com/p/eb63d31ad638

编译原理

第一章 引言

1.从面向机器的语言到面向人类的语言

汇编指令： 以符号形式存在的指令被称作汇编指令
汇编语言： 汇编指令所组成的集合则被定义为汇编语言

2.语言之间的翻译

预处理是高层语言间的翻译过程（也被称为转换），例如FORTRAN到ADA的转换
编译器有两种工作模式：一种是直接将源代码翻译为目标代码生成目标二进制程序；另一种是先生成中间代码再将其转换为目标二进制程序
汇编器负责将中间代码（如机器指令）转换为目标代码生成目标二进制程序
交叉汇编技术是一种将一个目标平台上的二进制文件转换为目标平台上的相应指令集的技术
反汇编工具能够从目标二进制文件提取出可执行文件中的关键信息
逆向编译器能够解析可执行文件并恢复出原始源代码

3. 编译器与解释器

（1）语言翻译的两种基本形态

解释器与编译器的主要区别: 在执行目标程序时对代码拥有完全控制权的不再是被解释的目标代码。

（2）各自特点

• 编译器: 具有显著的效果,即运行速度快、占用内存少；灵活性较低、适应性较弱. * 解释器: 性能不佳,即运行速度慢、占用内存大；灵活性较高、适应性较强.

共同点：都实现了对源程序的翻译。差异：编译器采用了先进行翻译而后执行的方式；而解释器则采用了在进行中进行翻译和执行的方法。

4. 编译器的工作原理与基本组成

（0）通用程序设计语言的主要成份 声明＋操作＝完整定义

（1）以过程为基本结构的程序设计语言的组成

• 声明性语句：描述操作对象的属性（包括数据类型的种类、具体数值以及作用范围等）；
• 操作性语句：规定运算执行的顺序，并实现具体的运算功能；
• 过程定义 = 过程头部 + 过程体。

（2）以阶段划分编译器

注：符号表管理器和出错处理贯穿编译器工作的各个阶段.

（3）编译器各阶段工作

在词法分析过程中, 系统接收源程序作为输入, 经过处理后生成并输出记号流作为结果. 其主要目标在于辨识词汇, 并将这些词汇分类归纳为以下几个方面的内容: 关键字（保留字）、标识符、常量以及特殊符号.

2 > 语法分析过程： 输入信息 是词法分析器返回的记号流, 生成的结果 是语法树. 目标是通过生成语法树来清晰展示语言结构. 对于声明性的语句内容, 进行符号表查询填充; 对于有效的表达式运算, 进行有效性验证和处理.

**3 > 语义分析：**遵循给定的语义规则，在语法树中实施针对各个语法单元的静态分析（包括类型检查和转换操作等），其目标在于确保在任何情况下所有符合语法正确的结构都满足合法性要求。

**4 > 中间表示的生成(可选)：**创建一种既能贴近目标语言又不受具体机器影响的表示形式,有助于提高代码优化效率并简化编译流程.

(到目前为止，编译器与解释器可以一致)

**5 > 中间代码可选的优化：**从局部到循环再到全局的层次进行调优；其本质是一种功能等价的转换关系，在空间占用和运行效率方面均有显著提升

**6 > 目标代码生成：**多种类型的目标编码包括以下几种：汇编表示法；基于可重新定位的二进制格式；以及Load-and-Go内存布局。

**7 > 符号表管理：**合理组织符号,便于各阶段查找\填写等.

8 > 出错处理：

 动态错误：源程序中的逻辑错误，发生在程序运行的时候。也称为动态语义错误

    
 静态错误：静态错误分为语法错误和静态语义错误.  
    
 <1> 语法错误：有关语言结构上的错误，如单词拼写错误、表达式缺少操作数、begin和end不匹配
    
 <2> 静态语义错误：分析源程序时可以发现的语言意义上的错误，如加法的两个操作数一个是整形变量，另一个是数组名

（4）编译器的分析\综合模式

从结构上说，逻辑上编译器被划分为两个主要部分：前段（前端）与后段（后端）。前段负责对输入的语言进行语义解析工作流程设计与实现；而后段则专注于对编程语言进行语义处理工作流程设计与实现。具体来说：

• 前段工作流程包括：
  • 词法分析
  • 语法分析
  • 中间代码生成等多阶段工作流程
• 后段工作流程包括：
  • 中间代码优化
  • 目标代码生成等多阶段工作流程
• 编译器与解释器的主要区别在于如何处理中间表示这个关键阶段——主要区别在于如何处理中间表示这个关键阶段，并在此基础上完成最终的目标。

5. 编译器扫描的遍数

在各个阶段对程序进行全面解析处理的工作模式被称为一轮扫描或全面解析处理流程；其中不仅包含对原始源代码及其各种中间表示形式进行完整的解析处理过程被称为一轮扫描或全面解析流程；也可称为全面解析流程

第二章 词法分析

1. 词法分析中的若干问题

(1) 记号、模式与单词

分类如下： 保留的关键字、变量名、固定字符串、特殊字符
规则如下： 产生和识别单词的方式是什么？
记号是...: 按照某种规则识别出的一组元素
这些记号被称为...: 被识别出的一串字符组合
这些被称为...: 这些组合被称作词值

(2) 词法分析器的作用与工作方式

词法分析器的作用：

1> 检测并提交给语法分析器相应的符号（依据模式识别的结果）
2> 过滤掉源程序中的冗余部分以及注释、空格和回车等空白内容
3> 处理与具体平台相关的输入形式（确保输入数据的一致性）
4> 负责调用相关管理工具（包括符号表管理器及错误处理系统）完成相应的数据管理和错误修复工作

工作方式：
1.单独一遍扫描
2.作为语法分析器的子程序
3.并行方式

2. 模式的形式化描述

(1) 字符串与语言

语集L 被定义为受限于字符集合∑及其上所能构造出的所有有穷长度串所构成的空间。在该定义中，“受限于”的双重限制源于计算机处理信息容量的限制：一方面要求字符集合∑仅包含有穷多个字符；另一方面则要求这些字符串必须具有有穷长度。这两点共同构成了该语集的核心约束条件。

涉及字符串及其集合的相关术语及其运算包括：如前缀操作符等。具体而言，在这种数据结构中定义了一系列基本操作符以实现特定功能：例如用于表示子串的匹配操作符或用于表示字符插入位置的操作符等

(2) 正规式与正规集

 令Σ是一个有限字母表，则Σ上的 正规式 及其表示的集合递归定义如下:

    
     1. ε是正规式，它表示集合  L(ε) = {ε}
    
     2. 若a是Σ上的字符，则a是正规式，它表示集合L(a)={a}
    
     3. 若正规式r和s分别表示集合L(r)和L(s)，则
    
    （a） r|s是正规式，表示集合L(r)∪L(s)，
    
    （b） rs是正规式，表示集合L(r)L(s)，
    
    （c） r*是正规式，表示集合(L(r))*，
    
    （d）(r)是正规式，表示的集合仍然是L(r)。                                   
    
    括弧用来改变运算的先后次序！

可用正规式描述(其结构)的语言称为 正规语言 或 正规集 。

 若运算的优先级和结合性做下述约定:

    
     1. 三种运算均具有左结合性质；
    
     2. 优先级从高到低顺序排列为:闭包运算、连接运算、或运算。
    
 则正规式中不必要的括号可以被省略。

若正规式P和Q表示了同一个正规集，则称P和Q是等价 的，记为P=Q

(3) 简化正规式描述(主要是简化书写上的复杂)

 (a) 正闭包 若r是表示L(r)的正规式，则r+是表示(L(r))+的正规式，且下述等式成立:r+ = rr* = rr，r = r+|ε;

    
       +与*具有相同的运算结合性和优先级
    
 (b) 可缺省  若r是正规式，则r?是表示L(r)∪{ε}的正规式，且下述等式成立:r? = r|ε
    
        ? 与 * 具有相同的运算结合性和优先级
    
 (c) 串    若r是若干字符进行连接运算构成的正规式，则:串“r” =  r ，且: ε= “”，   a = “a”（a是Σ的任一字符）
    
 (d) 字符组 若r是若干字符进行|运算构成的正规式，则可改写为 [r’]，其中r’可以有如下两种书写形式： 枚举: 如 a|b|e|h，可写为 [abeh]： 分段: 如0|1|2|3|4|5|6|7|8|9|a|b|c|d|e , 可写为： [0-9a-e] (e) 非字符组 若[r]是一个字符组形式的正规式，则[^r]是表示∑- L([r])的正规式。

3. 记号的识别——有限自动机

(1) 不确定的有限自动机（NondeterministicFinite Automaton, NFA）

 NFA是一个五元组（5-tuple）：M =（S，∑，move，s0，F），其中

    
 （1） S是有限个状态（state）的集合；
    
 （2） ∑是有限个输入字符（包括ε）的集合；
    
 （3） move是一个状态转移函数，move(si，ch)=sj表示，当前状态si下若遇到输入字符ch，则转移到状态sj；
    
 （4） s0是唯一的初态（也称开始状态）；
    
 （5） F是终态集（也称接受状态集），它是S的子集，包含了所有的终态。

<1> 直观的表示方式

① 状态机的转换图：可直观展示为一个有向图（其中节点代表状态）
② 状态机的转换矩阵：可直观展示为一个二维表格（表格中行对应状态而列对应输入字符）

<2> NFA(识别记号)的主要特点在于其高度的不确定性和多路转移特性。具体而言，在每个状态下对于同一个输入符号，在不同的状态下可能会导向不同的后续状态。

 具体体现：

    
 定义： move函数是1对多的；
    
 状态转换图：从同一状态出发，可通过多于一条标记相同字符的边转移到不同的状态；
    
 状态转换矩阵： M[si,a]是一个状态的集合

<3> NFA识别记号存在的问题

1. 为了确定一个输入序列不被接受,我们需要遍历所有可能的路径;随着路径长度的增长,这些路径的数量将呈现指数级数量增加。
2. 在识别过程中,由于需要频繁回溯以验证每一步骤的有效性,这将导致计算效率降低且使算法变得更为复杂。

(2) 确定的有限自动机（Deterministic Finite Automaton, DFA）

 定义: DFA是NFA的一个特例，其中：

    
   （1）没有状态具有ε状态转移(ε-transition)，即状态转换图中没有标记ε的边；
    
   （2）对每个状态s和每个字符a，最多有一个下一状态。 特点：与NFA相比，DFA的特征：确定性 定义：move（si, a)函数都是 1对1 的； 转换图 从一个状态出发的任2条边上的标记均不同； 转换矩阵：M[si,a]是一个状态 且字母表不包括ε。 提示：正规式和有限自动机从两个侧面表示正规式。正规式是描述，自动机是识别。

4. 从正规式到词法分析器

 构造词法分析器的一般方法和步骤：

    
 1. 用正规式描述模式（为记号设计正规式）；
    
 2. 为每个正规式构造一个NFA，它识别正规式所表示的正规集；
    
 3. 将构造的NFA转换成等价的DFA，这一过程也被称为确定化；
    
 4. 优化DFA，使其状态数最少，这一过程也被称为最小化；
    
 5. 根据优化后的DFA构造词法分析器。

(1) 从正规式到NFA

Thompson 算法

(2) 从NFA到DFA

 - smove(S, a)：从状态集S出发，标记为a的下一状态全体。与move(s, a)的唯一区别：用状态集取代状态

    
 - ε-闭包(T)：从状态集T出发，不经任何字符达到的状态全体
    
 - “子集法”构造DFA

(3) 最小化DFA

任意选取两个状态t与s，在自状态t经过输入字符串ω后达到接受状态的同时，则自状态s经过输入字符串ω后无法达到接受状态。

或者说是起始点t与源点s分别达到不同的接受态时，则称ω对于状态t和s是可区分的。

​ 不可区分的状态位于一个组内，可以合并成一个状态.

主要步骤：

1. 初步分类：终止状态集合与非终止状态集合；
2. 通过可区分数学概念对各分组Gi持续细分直至无法细分为止；
3. 基于最终分群构建D'的关键在于选取代表元并修正状态转移关系；
4. 消除可能的死状态和不可达状态。

5. 从DFA构造词法分析器

分类： 表驱动型的词法分析器；直接编码的词法分析器
比较：

第三章 语法分析

词法分析： 符号系统的组成部分包括符号集合、字符构成以及呈现线性排列的特征；语法分析： 整个语言系统可划分为多个句子组，在每个句子中都包含多个符号，并以树状结构组织起来

语法分析的双重含义：

• 语法规则：上下文无关文法中的子类体系（如LL与LR体系）
• 语法分析：基于下推自动aton的自顶向下处理与基于状态机的自底向上处理并存的技术架构

1. 语法分析的若干问题

许多编译程序通常将语法分析模块作为核心组成部分

（1）语法分析器的作用

• 基于词法分析器提供的符号序列，以正确输入的词法分析为基础构建相应的分析树（或语法树）。
  • 验证输入中的所有语法错误（包括词法错误），并对出现的语法错误进行有效的纠正。

（2）语法错误的处理原则

源程序中可能出现的错误

语法(包括词法)错误和语义错误(静态语义错误和动态语义错误)

注：与上一章的分类思路相异，在上一章中我们则是基于语法和语义两个维度分别探讨了静态与动态两类问题...然而结果却出人意料的是

语法错误： 涉及非法字符、关键字拼写或标识符等异常情况
语法错误： 指语法结构异常
静态语义错误： 包括类型不符以及参数配对不当
动态语义错误(逻辑性问题)： 包含死循环现象以及变量在进行除法运算时为零的情况

2. 上下文无关文法(CFG)

（1）上下文无关文法(Context Free Grammar,CFG)

  CFG是一个四元组G =（N，T，P，S），其中

    
 （1） N是非终结符（Nonterminals）的有限集合；
    
 （2） T是终结符（Terminals）的有限集合，且N∩T=Φ；
    
 （3） P是产生式（Productions）的有限集合，A→α，其中A∈N(左部),α∈(N∪T)*(右部),若α=ε，则称A→ε为空产生式(也可以记为A →);
    
 （4） S是非终结符，称为文法的开始符号（Start symbol） 注： S ∈ N , N可以出现在产生式左边和右边，T绝不出现在产生式左边.

（2）CFG产生语言的基本方法－推导

上下文自由语法（Context-Free Grammar, CFG）通过推导的方式生成语言。具体来说，则是从起始符号S出发，并按照一定的规则进行替换：将产生式左部的非终结符逐步替换成右部定义的具体文法符号序列(以=>表示单步展开)，直至最终生成一组终结符。

**1 > 直接推导：**在句型生成的过程中，在文法符号序列中以单一非终结符为中心进行替换操作而产生的一个步骤被称为"一步推导"（step derivation）。具体而言，在文法符号序列中存在形如 α A β 的部分时（其中 α 和 β 是任意的文法符号序列），如果将其替换为 α γ β（其中 A → γ 是一个给定的产生式），则称该过程为一步推导，并以 α A β => α γ β 的形式记录这一变化过程。

**2 > 零步骤或多步骤推导：**对于任意的文法符号序列\alpha_1, \alpha_2,...,\alpha_n，若有\alpha_1\Rightarrow\alpha_2\Rightarrow...\Rightarrow\alpha_n成立，则此过程被称为零步骤或多步骤推导，并记作\alpha_1 \Rightarrow^* \alpha_n；特别地，当\alpha_1=\alpha_n时，则称为零步骤推导。

**3 > 至少一次使用：**当α₁ ≠ α_n时，则意味着在推导过程中至少应用了一次生成规则，并被定义为此过程的最小推演次数；记为：该过程称为至少一步推演过程，并表示为α₁ =+> αn

(推导具有自反性和传递性)

4 > 由 CFGG 生成的语言L(G)被称作：L(G) = { ω | S → ω 且 ω∈T* } ，
L(G)被称为上下文无关语言（Context Free Language, CFL），其中ω被称为句子。
若S ⇒* α（其中α∈(N∪T)*），则α被称为该文法G的一个句型。需要注意的是，所有句子都是句型，但并非所有的句型都是句子。

在演算过程中，在每次直接演算时均替代（代替）句式中最左边的非终结符，则称这种行为为最左替代（或作最左演算），由此生成的结果被称为左式子式（简称左式）。类似地可定义最右替代（规范替代）及其相关概念：其中最右替代也被称为规范替代过程或规范化演算法则。

（3）推导、分析树与语法树

1、分析树既反映语言结构的实质，也反映推导过程。

2、对CFGG的句型，分析树 被定义为具有下述性质的一棵树。

（1）该树基于起始符号生成；
（2）每个叶子以终结符、非终结符或空字符串 ε 形式表示；
（3）每个内部节点以非终结符形式表示；
（4）若 A 是某个内部节点所代表的非终结符，并且 X₁,X₂,…,Xₙ 是该节点从左至右的所有子节点所使用的记号，则 A → X₁ X₂ … Xₙ 是一条生成规则；如果 A → ε，则表示以 A 为标志的节点只有一个 ε 子节点。

注：分析树中的叶子节点按照从左到右的顺序组成G的一个句型结构。当叶子节点全部被标记为终结符时，则形成一个完整的句子。

3、对CFG G的句型，表达式的语法树被定义为具有下述性质的一棵树:

（1）根与内部节点基于表达式中的操作符进行标记；
（2）叶子基于表达式中的操作数进行标记；
（3）括号用于调整运算顺序和结合方式，并且它们在语法树结构中被隐含地包含。

• 语法树是表示表达式结构的最好形式

（4）二义性与二义性的消除

二义性： 若文法G对 同 一句子产生不止一棵分析树，则称G是二义的.

结论：
1> 一个句子有多于一棵分析树，仅与文法和句子有关，与采用的推导方法无关；
2> 造成文法二义的根本原因：文法中缺少对文法符号优先级和结合性的规定

二义性消除的方法：
① 规范化处理二义文法为非二义文法；
② 明确符号的优先级和结合性后，则能确保仅有一棵分析树生成。

3. 语法与文法简介

（1）正规式与上下文无关文法

• 符号可用正则表达式来表示。
  • 句子可用上下文无关文法来描述。适用于表示那些具有层次结构且非线性的语法规则。例如，在编程语言中使用if-then-else以及while-do等不同的句法构造。

正规式所描述的语言结构均可以用CFG描述，反之不一定.

（2）上下文有关文法CSG

此类语言结构主要包括对计数问题进行抽象以及处理变量声明与引用的过程，并在处理过程调用时需要进行形参与实参的一致性校验，并且上述提到的各种情况都属于此类语言结构。这些语法被称为上下文有关文法（Context Sensitive Grammar, CSG）。然而这些语法无法仅通过上下文无关文法CSG来进行描述

（3）形式语言与自动机简介

若文法G=(N,T,P,S)的每一个规则α→β中均有α和β都属于(N∪T)，并且至少包含一个非终结符符号，则这种文法被称为0型文法。

​ 对0型文法施加以下第i条限制，即得到i型文法。

1. G的所有产生式中α → β（除了S → ε的情况）均满足其长度不大于右侧字符串；
2. 所有的非终结符生成规则均为"A → β"的形式, 其中"A"属于非终结符集合, "β"由非终结符与终结符组成的序列构成；
3. 所有的非终结符生成规则包括"A → a", "A → aB", 或者"A → Ba"等形式, 其中"A"和"B"属于非终结符集合, "a"属于终结符集合。

4. 自上而下语法分析

分为：递归下降分析法、预测分析法

基本思想： 给定任意输入序列ω时 以S为起点进行最左展开 直到生成合法句子的同时若出现非法结构则提前终止。整个自顶向下分析机制是一种不断试错的过程 通过持续应用不同的产生式规则来逐步匹配输入序列。

提前准备——重写文法： 1.去除左向递归，并由此防止出现无限循环的情况； 2.去除左边因素，并由此防止回溯现象的发生。

（1）消除左递归

定义为：在文法G中存在非终结符A时，则当存在一个文法符号序列α使得推导关系成立（即A =+> Aα），则可称该文法G具有左递归特性。进一步而言，在这种情况下如果出现形式化的产生式"A → A α"（其中包含至少一个后续符号），则此产生式被认定为直接导致了非终止符"A"的左递归性。

<1> 消除文法的直接左递归

 A→Aα|β     替换为     A →βA'

    
                 A'→αA'|ε

首先将生成式A整理为以下形式：A \rightarrow A\alpha_1 \mid A\alpha_2 \mid \dots \mid A\alpha_m \mid \beta_1 \mid \beta_2 \mid \dots \mid \beta_n；随后采用以下生成式替代原有的生成式：A \rightarrow (\beta_1)^\vee (\beta_2)^\vee \dots (\beta_n)；其中A^\prime的定义如下所示：A^\prime = (\alpha_1)^\vee (\alpha_2)^\vee \dots (\alpha_m)^\vee /epsilon

<2> 消除文法的左递归

核心思想：将没有直接左递归的非终结符扩展至其他生成式中，并继而消除那些可能存在的其他生成式中的直接左递归

若G产生句子的过程中出现A=+A的推导，则无法消除左递归(出现回路)

（2）提取左因子

<1> 提取文法的左因子

左因子产生原因：公共前缀：A → αβ1|αβ2
方法：将 A → αβ1|αβ2|γ
​ 替换为 A→αA'|γ A'→β1|β2

（3）递归下降分析

直接以程序代码（的方式）模拟产生式产生语言的过程:

基本思想： 每个非终结符对应一个子程序（函数），过程体中：

• 产生式右部的非终结符由子程序调用完成，
• 产生式右部的终结符用于与输入符号序列进行匹配。

特点：

1. 子程序具有递归特性（由于文法本身具有递归性质）；
2. 该方法涉及文法结构的相关性；
3. 该方法规定文法不能包含公共左因子或出现左递归现象；
4. 这种方法不具备严格的规范性。

（4）预测分析器

预测分析器由一张预测分析表、一个符号栈以及一个驱动装置共同构成，并且其数学模型被设定为下推自动机的形式。
为了确保文法的有效性，在设计时必须遵循以下两个原则：一是禁止存在公共左因子；二是必须避免出现左递归结构。

预测分析器的核心概念：
1> 分析手段：模式与模式转换
2> 模型+核心组件（模拟算法）
3> 预测模型构建
4> LL（文法、语言、解析系统）

在初始状态下余下的内容即为全部输入序列，在接收方的余下内容应当为空的情况下，则其余可能出现的情况下的余下内容则应视为某个后续补充部分

☆ 改变格局的动作：

① 匹配终结符： 若top=ip(但≠#)，则pop且next(ip)；
② 展开非终结符：若top^= X且M[X,ip^]=α(X→α)，则pop且push(α)；
③ 报告分析成功： 若top ^= ip^ = #，则分析成功并结束；
④ 报告出错：其它情况，调用错误恢复例程.

☆ 驱动器算法

☆ 构造预测分析表

步骤：1. 生成文法符号X的所有FIRST元素以及非终结符的所有FOLLOW元素；2. 基于这两个关键集合构建预测分析表

在由α出发的所有导出序列中位于最前端的终结符即为α的FIRST集合，在任何含有A且从起始符号出发可导出的文法序列中紧随其后出现的所有终结符即为A的FOLLOW集合

<1> 求取X的FIRST集合 -----从下往上进行
<2> 求取所有非终结符的FOLLOW集合 —— 从上往下进行
<3> 构建预测分析表
<4> LL(1)文法

称该文法为LL(1)文法，则当且仅当其预测分析表中各条目均无多重定义时成立

☆ 第一个L按顺序扫描输入序列；第二个L执行最左推导；1用于向前查看一个终结符。

 推论3.2 G是LL(1)的，当且仅当G的任何两个产生式A→α|β满足:

    
 1. 对任何终结符a，α和β不能同时推导出以a开始的串；即First(α) ∩ First(β) = ∅
    
 2. α和β最多有一个可以推导出ε；
    
 3. 若β =*> ε,则α不能导出以FOLLOW(A)中终结符开始的任何串. 即First(α) ∩ Follow(A) = ∅

包括递归下降子程序法在内的多种方法都仅限于处理LL(1)文法

5. 自下而上语法分析

☆ 基于上下文的分析采用了推导方法；基于上下文的解析系统采用了规范归约策略，并通过剪枝优化来减少计算量。

（1）自下而上分析的基本方法

☆ 基本思想： 最左归约.

考虑任意输入序列ω：首先从最左边开始逐步向右扫描该序列；接着以该序列作为起点反复利用产生式规则中左边模式替代右边模式（即当前生成串中的主干部分），并试图实现与输入序列ω的整体匹配；最终将导出文法起始符或判定出现语法错误。

☆ 基本概念：

 a) > 设αβδ是文法G的一个句型，若存在S=*>αAδ，A=+>β， 则称β是句型αβδ相对于A的"短语".

    
    > 特别的，若 有A→β，则 称β是句型αβδ相对于产生式A→β的"直接短语".
    
    > 一个句型的最左直接短语被称为"句柄".
    
  
    
    特征：
    
     1.  短语：以非终结符为根子树中所有从左到右的叶子；
    
     2.  直接短语：只有父子关系的子树中所有从左到右排列的叶子（树高为2）；
    
     3.  句柄：最左边父子关系树中所有从左到右排列的叶子（句柄是唯一的）
    
     
    
     
    
 b)最左归约：若 α是文法G的句子且满足下述条件，则称序列αn，αn-1，...，α0是α的一个最左归约。
    
    1) αn = α
    
    2) α0 = S（S是G 的开始符号）
    
    3) 对任何i(0<i<=n)，αi-1是将αi中句柄替换为相应产生式左部非终结符得到的
    
    
    
  ☆ 最左归约的逆过程是一个最右推导，分别称最右推导和最左归约为规范推导和规范归约.
    
  
    
  c）移进-归约分析器
    
  1. 工作方式：格局与格局变换
    
  2. 分析表
    
  3. 驱动器（模拟算法）
    
  4. SLR分析表的构造
    
  5. LR（文法、语言、分析器）
    
  
    
 ☆ 改变格局的动作：
    
 1. 移进(shift)：当前剩余输入的下一终结符进栈。
    
 2.归约(reduce)：将栈顶句柄替换为对应非终结符(最左归约)
    
 3.接受(accept)：宣告分析成功
    
 4. 报错(error)：发现语法错误，调用错误恢复例程

(2) LR分析

a) LR分析与LR文法
LR分析：** 允许左递归，但不能有二义**

    定义3.15 若为文法G构造的移进-归约分析表中不含多重定义的条目，则称G为"LR(k)文法"，分析器被称为是"LR(k)分析器"，它所识别的语言被称为"LR(k)语言"。"L"表示从左到右扫描输入序列，"R"表示逆序的最右推导，"k"表示为确定下一动作向前看的终结符个数，一般情况下k<=1。当k=1时，简称"LR"。

构造SLR(1)分析器

<1> 活前缀与LR(0)项目

出现在移进-归约分析器栈中的右句型的前缀，被称为文法G的活前缀(viable prefix).
LR(0)项目(简称项目) 是这样一个产生式，在它右边的某个位置有一个点"."。对于A→ε，它仅有一个项目A→.。
项目A→α.β显示了分析过程中看到(移进)了产生式的多少。
β不为空的项目称为可移进项目 ，β为空的项目称为可归约项目.

<2> 拓广文法与识别活前缀的DFA

G′=G∪{S′→S}其中：S′→S标识初始状态而S′→·S则标识终止状态其目的在于确保所构建的确定型上下文无关自动机（DFA）的状态集合仅包含唯一的一个初始状态与终止状态①closure(I)指的是从项目集I出发无需经过任何文法规则可直接到达的所有项目的集合

② goto(I，x)：所有从I经文法符号x能直接到达的项目全体。

 项目[S’→.S]和所有“.”不在产生式右部最左边的项目称为核心项目(kernel items)，

    
 其它“.”在产生式右部最左边的项目(不包括[S’→.S])称为非核心项目(nonkernel items).
    
  
    
 核心项目：J=goto(I，X)，S'→.S（作为项目集的代表）
    
 非核心项目：closure(J)-J（特点：可由J某中某项目算得）

<3> 识别活前缀

    定义3.21 若存在最右推导S’=*> αAω => αβ1β2ω，则称项目[A→β1.β2] 对活前缀αβ1有效。

 当一个项目集中同时存在：

    
     1. A→β1.β2和B→β.：既可移进又可归约，移进/归约冲突
    
     2.A→α.和B→β.：均可指导下一步分析，归约/归约冲突
    
  
    
 解决方法：简单向前看一个终结符：
    
     1. 移进/归约冲突：若FIRST(β2)∩FOLLOW(B)=Φ，冲突可解决
    
     2. 归约/归约冲突：若FOLLOW(A)∩FOLLOW(B)=Φ，冲突可解决
    
  
    
 若冲突可以解决，则称文法为SLR(1)文法，构造的分析表为SLR(1)分析表。
    
 SLR(1)文法：简单向前看一个终结符即可解决冲突
    
 ☆ 二义文法不是SLR(1)文法

第四章 静态语义分析

采用语法制导翻译生成中间代码

1. 语法制导翻译简介

（1）语法与语义的关系

语法即为语言的形式、也指语言的"形态特征"；而语义则依附于语言形式并承载了其深层含义；也就是指语言的"内涵"。
一个从语法角度分析是正确的句子，在意义上未必准确。

☆ 语义分析的作用

• 对结构正确且意义明确的句子进行合法性验证；
• 实施指定的操作逻辑：包括表达式的计算、符号表的检索及填充、中间代码的生成等

☆ 主要采用的是基于逻辑的技术框架——语法制导翻译系统——来实现自然语言处理的核心目标。其核心理念是通过上下文ensitive的方式对语言进行建模，并在此基础上实现对自然语言的理解与生成能力。这种技术框架的主要特点在于它能够有效地处理复杂的人类语言信息，并通过上下文信息引导机器完成后续的任务处理过程。

（2）属性/语义规则的定义

 定义4.1 对于产生式A→α，其中α是由文法符号X1X2...Xn组成的序列，它的语义规则可以表示为(4.1)所示关于属性的函数f：

    
       b := f(c1, c2, ..., ck)                  (4.1)
    
 语义规则中的属性存在下述性质与关系：
    
       (1)   称(4.1)中属性b依赖于属性c1, c2, ..., ck。
    
       (2) 若b是A的属性，c1, c2, ..., ck是α中文法符号的属性，或者A的其它属性，则称b是A的综合属性。
    
       (3) 若b是α中某文法符号Xi的属性，c1, c2, ..., ck是A的属性，或者是α中其它文法符号的属性，则称b是Xi的继承属性。
    
       (4) 若语义规则的形式如下述(4.2)，则可将其想像为产生式左部文法符号A的一个虚拟属性。属性之间的依赖关系，在虚拟属性上依然存在。
    
       f(c1, c2, ..., ck)                (4.2)          ■

继承属性由前辈及兄弟的属性源自,整体性特征源自子孙及其自身的技术特性

即,继承属性"自上而下,包括兄弟",综合属性"自下而上,包括自身".

（3）语义规则的两种形式

☆ 语义规则的两种形式（忽略实现细节，二者作用等价）

<1> 语法制导定义(Syntax Directed Definition)

    用抽象的属性和运算表示的语义规则；(公式，做什么)

<2> 翻译方案(Translation Scheme)

    用具体的属性和运算表示的语义规则。(程序段，如何做)

☆ 继承属性是自上而下计算的，综合属性是自下而上计算的.

（4）LR分析翻译方案的设计

☆ LR分析中的语法制导翻译实质上是对LR语法分析的扩充：

1. 扩充LR分析器的功能

当触发归约产生式这一操作时，则会自动触发相应的语义动作。这是因为只有在进行归约操作时才会自动执行这些语义动作。

​ 因此限制语义动作仅能放在产生式右部的最右边；

2. 扩充分析栈

增设一个与分析栈配套设置的一个语义栈，并专门用于存储分析栈中各语法符号所对应的属性值

扩充后的LR分析特别适合对综合属性的计算；而对于继承属性的计算，则需要采取适当措施。

2. 中间代码简介

遵循语法制导的翻译方式

使用中间代码的好处: 一方面有助于编译器程序的构建与迁移,另一方面经过优化处理后能够提升性能.

☆ 中间代码的主要形式包括后缀式、表达式树以及三地址码等多种类型.基于树的中间代码是最基本的形式;而三地址码是最常用的中间代码形式,其实现通常采用四元式结构.

☆ 符号表是帮助声明语句实现存储空间分配的重要数据结构。

（1）后缀式

被操作的对象位于前面；后面紧跟的是运算符号；不需要通过括号来限定运算的优先顺序和结合方式；这有助于计算结果的得出。

（2）三地址码

① 三元式 形式： (i) (op, arg1, arg2)

​ 三地址码：(i):= arg1 op arg2

序号的双重含义：既代表此三元式，又代表三元式存放的结果

存放方式：数组结构，三元式在数组中的位置由下标决定

弱点：给代码的优化带来困难

② 四元式 形式： ( i ) (op，arg1，arg2，result)

​ 所表示的计算： result:= arg1 op arg2

四元式与三元式的区别主要在于：它们替代地使用变量来表示运算结果。

该方法使得多项式的计算结果与其在多项式序列中的位置无关.这一变化为代码优化提供了显著的帮助,因为这种不受位置影响的特点允许删除或移动相关的项而不影响计算结果.

③ 树形表示

1> 语法树能够准确地呈现句子的结构特征，在此基础上进行适当修改（引入语义信息），即可形成一种注释式的中间代码形式（标记化语法树）
2> 以有向无环图为形式的优化表示
3> 探讨了与现有其他中间代码体系之间的关系

☆ 树表示的中间代码与后缀式和三地址码之间有内在联系

1. 树 → 后缀式

方法：采用深度优先后续遍历对树进行操作，则生成的线性序列即为后缀式表达；或者说是这样的线性化表示方式被称为后缀式。

2. 树 → 三元式/四元式

特点：树的每个非叶子节点和它的儿子对应一个三元式或四元式；

方法：执行深度优先后序遍历过程（针对树的非叶子节点），即可得到一个三元式或四元式序列。

3. 符号表简介

• 符号表的主要功能是充当连接工具，在程序生命周期中维护声明与引用之间的桥梁关系。它通过精确地存储关于每个标识符的关键信息（如作用域和类型），为编译器各阶段提供必要的数据支持以实现高效可靠的运行。
• 符号表的核心任务是精准地存储相关信息并支持快速定位所需数据。
• 其符号表设计必须满足以下基本要求：
  • 精确存储关键数据；
  • 满足不同编译阶段的需求；
  • 支持高效的查询操作以及增删改等基本功能；
  • 空间规模能够灵活扩展。

（1）构成名字的字符串

构成名字的字符串的存储方式： 直接存储---定长数据是将所有构成名字的字符串直接放置于符号表中的条目中；而间接存储---变长数据则是通过特定分隔符将所有这些字符串分隔开来，并在符号表中的条目中仅记录每个字符串首字符的位置信息。

（2）名字的作用域

☆ 程序语言范围的划分可以有两种划分范围的方式：并列和嵌套

☆ 名字的作用域规则： 规定一个名字在什么样的范围内应该表示什么意义.

 <1> 静态作用域规则（static-scope rule）：编译时就可以确定名字的作用域,即仅从静态读程序就可确定名字的作用域

    
 <2> 最近嵌套规则（most closely nested）：名字的声明在离其最近的内层起作用

（3）线性表

符号表以栈(线性表) 的方式组织.

线性表上的操作：查找、插入、删除、修改

搜索并定位到第一个符合条件的名称；添加并放置于表顶端位置。

关键字 = 名字＋作用域；

（4）散列表

名字挂在两个链上(便于删除操作)：

散列链(hash link)：将所有具有相同hash值的元素连接到表头数组中；
作用域链(scope link)：将所有属于同一作用域的元素连接到作用域表中。

☆ 操作：查找、插入、删除

4. 声明语句的翻译

（1）变量的声明

☆ 一个变量的声明应该由两部分来完成：类型的定义和变量的声明

• 类型负责： 编译器存储空间容量的相关信息
• 变量负责： 为程序中的变量分配存储空间
• 组合数据的类型负责与变量负责： 定义与实现分开进行
• 组合数据的类型负责与变量负责： 在代码实现中将两者分开处理

基本数据类型占用内存空间预先确定（例如int变量占用4个字节、double变量占用8个字节、char变量占用1个字节等）

其存储空间取决于程序员提供的相关信息

（2） 过程

 1．过程（procedure）：过程头(做什么) ＋  过程体(怎么做)；

    
    - 函数:  有返回值的过程
    
    - 主程序:  被操作系统调用的过程/函数
    
  
    
 2．过程的三种形式：过程定义、过程声明和过程调用。
    
    过程定义：过程头+过程体；
    
    过程声明：过程头；
    
  
    
 3. 左值与右值 
    
    1> 直观上，出现在赋值号左边和右边的量分别称为左值和右值；
    
    2> 实质上，左值必须具有存储空间，右值可以仅是一个值，而没有存储空间. 3> 形象地讲，左值是容器，右值是内容. 4. 参数传递 1> 形参与实参 - 声明时的参数称为形参(parameter或formal parameter) - 引用时的参数称为实参(argument或actual parameter) 2> 常见的参数传递形式：（不同的语言提供不同的形式） - 值调用（call by value）---过程内部对参数的修改，不影响作为实参的变量原来的值. - 引用调用（call by reference）--- 过程内部对形参的修改，实质上是对实参的修改. - 复写－恢复（copy-in/copy-out）--- ① 过程内对参数的修改不直接影响实参，避免了副作用; ② 返回时将形参内容恢复给实参，实现参数值的返回. - 换名调用（call by name）--- 宏调换 3> 参数传递方法的本质区别： 实参是代表左值、右值、还是实参本身的正文. 5. 作用域信息的保存 ☆ 能够画出嵌套过程的嵌套关系树(P191 4.33),根据语法制导翻译(P193 4.35)画出分析树,写出推导步骤,构造的符号表

5. 简单算术表达式与赋值句

P197 例4.36 主要是变量类型的转换

6. 数组元素的引用

（1）数组元素的地址计算

• 注意是行主存储还是列主存储

（2）☆数组元素引用的语法制导翻译(考试热点之一)

• P201 例4.37

7. 布尔表达式

布尔表达式的运算有两种途径：基于数值表示的线性代数运算和基于逻辑表示的逻辑短路运算。

☆ 布尔表达式短路运算的处理：在处理逻辑时遵循的执行流程包括逻辑结果为真的输出端与结果为假的输出端；分别连接到结果为真的输出节点和结果为假的情况下的节点集合；一种用于优化中间代码的技术（见教材P207页中的示例4.41），而该技术在当前考试中被列为重要考点。

8. 控制语句

控制语句的分类： ①无条件转移、②条件转移、③循环语句、④分支语句

• 无条件转移(goto)\条件转移(if、while)
• 条件转移的语法制导翻译：P213 例4.42

    多看课件PPT，多做题练手

链接

转载于:https://www.cnblogs.com/jacksplwxy/p/10807180.html