【编译原理】知识点总结
未经许可，禁止转载。
文章目录
-
- 绪论
- 编译前端-后端
- 语义检查
- 语法制导翻译
- 文法描述
- 上下文无关文法
- 推导
- 文法和语言
- 语法分析树
- 二义性
- 最左推导与最右推导
- 语法制导翻译
- 语法制导翻译方案
- 注释分析树
- 语法分析
- 消除左递归
- 消除间接左递归
- 回溯
- 词法分析
- 状态转换图
- 前缀后缀
- 正则表达式
- 冲突解决
- 有穷自动机
- DFA
- NFA
- 构造NFA
- NFA转DFA
- 最小化DFA
- 递归下降的语法分析
- 预测分析
- FIRST集
- FOLLOW集
- LL(1)文法
- 表驱动的预测分析法
- 构造预测分析表
- 利用预测分析表进行分析
- 自下而上分析
- 移入-规约
- 短语-直接短语-句柄
- 活前缀-可归前缀
- LR分析法
- LR(0)自动机
- 项目集闭包
- LR(0)自动机
- LR(0)分析表
- SLR(1)分析表
- LR(1)
- LR(1)文法
- LALR
- 语法制导定义
- SDD属性的计算
- 依赖图
- S-属性
- S-属性定义的SDT
- L-属性
- L-属性定义的SDT
- 抽象语法树
- 自顶向下翻译
- 翻译模式
- SDD转SDT
- 中间表示
- 三地址码
- 四元式
- 三元式
- 间接三元式
- 类型表达式
- 类型检查与转换
- 目标代码生成
绪论
编译原理主要介绍编译器构造的基本原理 和基本实现技术 。
计算思维是运用计算机科学的基础概念（递归、抽象、自动化等）进行问题求解、系统设计、以及人类行为理解等涵盖计算机科学之广度的一系列思维活动。
抽象的定义：从众多的事物中抽取出共同的、本质性的特征，舍弃其非本质的特征，它是一种从个体把握一般、从现象把握本质的认知过程和思维方法。在编译原理中表现为有限自动机、文法等。
自动化的定义：将抽象思维的结果在计算机上实现，是一个将计算思维成果物化的过程，也是将理论成果应用于技术的实践。在编译原理中表现为有限自动机、预测分析程序、算符优先分析、LR分析等。
分解的定义：将大规模的复杂问题分解成若干个较小规模的、更简单的问题加以解决。在编译原理中表现为引入中间语言、编译过程分多个阶段、分析过程分多遍等。
递归的定义：问题的解决依赖于类似问题的解决，不过后者的复杂程度或规模较原来的问题更小。当问题的复杂程度和规模化足够小时，问题的求解非常简单。在编译原理中表现为语法分析的递归下降分析、语义分析的基于树遍历的属性计算、语法制导翻译。
权衡的定义：要在理论可实现和实际可实现做出权衡，理论研究重在探寻问题求解的方法，对于理论成果的研究运用又需要在能力和运用中作出权衡。在编译原理中表现为用上下文无关文法来描述和处理高级程序设计语言、优化措施的选择（任务需求和实现约束的权衡）。
程序执行的过程为高级语言（接近人类表达习惯、不依赖于特定机器、编写效率高）->汇编语言（提高了编程的速度和准确度、依赖于特定机器、可移植性差）->机器语言（费时而且枯燥，效率较低）。
编译程序的定义：把某一种高级语言程序等价地转换成另一种低级语言程序(如汇编语言或机器语言程序)的程序。
翻译程序的定义：把某一种语言程序(源语言程序)翻译成等价的、用另一种语言编写的程序(目标语言程序)的程序，同时报告源程序中的错误。
解释程序的定义：把源语言写的源程序作为输入，但不产生目标程序，而是边解释边执行源程序本身。
反编译器的定义：进行编译器的反向操作，把一个程序由较低的抽象形式（低级语言、机器可读）转成较高的抽象形式（高级语言、人工可读）。
源到源的翻译器：把一种高级语言翻译成为另一种高级语言。
程序执行的顺序为：预处理器->编译器->汇编器
编译器由两个部分组成：
1.分析部分（前端）：用于将源程序分解成中间表示。若分析过程检查出源程序没有按照正确的语法构成，或语义上不一致，它必须提供有用的信息，使用户可以进行改正。分析部分还会收集有关信息，信息存放在符号表中。前端与源语言相关，与目标机器无关。
2.综合部分（后端）：根据中间表示和符号表信息来构建目标程序。后端与源语言无关，与目标语言相关。目标代码生成器及机器相关代码优化器属于后端。
编译程序工作的五个阶段：词法分析、语法分析、语义分析、中间代码产生、优化、目标代码产生。
词法分析的定义：从左到右扫描源程序的字符流，识别出词素，并将其抽象成词法单元。使用有穷自动机实现，遵循构词规则。
语法分析的定义：根据语言的语法规则，从词法分析器输出的Token序列中识别出各类短语（语法单位），并构造语法分析树（语法分析树是基于语言的文法来构建的），使用上下文无关文法实现。
语义分析的定义：进行语义检查，使用语法树和符号表中的信息来检查源程序是否和语言定义的语义一致；收集类型信息（种属、类型、长度等），将信息存放在语法树或符号表中；类型检查和自动类型转换，检查每个运算符是否具有匹配的运算分量，如数组下标必须是整数；发现语义错误，并支持代码生成；对分析树进行语义动作的标记，得到注释树。
中间代码生成的定义：对各类语法单位按语言的语义进行初步翻译。中间代码应易于生成，且容易被翻译成目标机器的语言，使用属性文法实现，遵循语义规则。得到的中间代码是三地址码（三元式、四元式、树等）。
三地址指令中，每个指令最多有三个操作数。
代码优化的定义：对于前阶段产生的中间代码进行加工变换，以期在最后阶段产生更高效的目标代码。遵循程序的等价变换规则，包括公共子表达式的提取、循环优化、删除无用代码等等。
目标代码生成的定义：把中间代码变换成特定机器上的目标代码。该过程依赖于硬件系统结构和机器指令的含义。
目标代码的三种形式：绝对指令代码（可直接）、可重新定位指令代码（需要连接装配）、汇编指令代码（需要进行汇编）。在以上过程中，使用符号表对信息进行管理，符号表是用于存放标识符的属性信息的数据结构。
对源程序或源程序的中间结果从头到尾扫描一次，进行加工，产生新的中间结果或目标程序，这个步骤称为遍。一遍可以由若干阶段组成，一个阶段也可以分若干遍来完成。单遍费内存，多遍耗时间但优化效果好。
为什么需要编译程序？
1.编译程序消除了人类与机器之间的语言鸿沟，硬件只能直接理解和执行机器语言（即二进制指令）
2.编译程序可以优化程序性能
3.静态错误检测可以避免出现低级错误
4.编译程序方便了跨平台开发
编译前端-后端
编译前端：词法分析、语法分析、语义分析、中间代码生成
编译后端：目标代码生成、目标代码优化
语义检查
1.变量或过程未经声明就使用变量或过程名重复声明
2.运算分量类型不匹配
3.操作符与操作数之间的类型不匹配
4.数组下标不是整数
5.对非数组变量使用数组访问操作符
6.对非过程名使用过程调用操作符
7.过程调用的参数类型或数目不匹配
8.函数返回类型有误
语法制导翻译
语义分析+中间代码生成=语义翻译
语法分析+语义分析+中间代码生成=语法制导翻译
语法制导翻译使用上下文无关文法CFG来引导对语言的翻译，是一种面向文法的翻译技术。
文法描述
文法是语言的生成规则，而语言是文法生成的字符串集合。
非终结符号也称文法符号，产生式的左侧必须要有一个非终结符。
0型文法：
文法名称为无限制文法，生成递归可枚举语言，对应自动机是图灵机。
1型文法：
文法名称是上下文相关文法，生成上下文有关语言，对应自动机为线性有界自动机。
2型文法：
文法名称为上下文无关文法，生成上下文无关语言，对应自动机是下推自动机。
3型文法：
文法名称是正则文法，生成正则语言，对应自动机为有限状态自动机。
上下文无关文法
上下文无关文法的缩写为CFG
推导
推导的定义：根据文法的产生式规则，把串中出现的产生式的左部符号替换成右部。
归约的定义：根据文法的产生式规则，把串中出现的产生式的右部替换成左部符号
文法和语言
语言的定义：从开始符号出发，利用推导能得到的所有终结符号串的集合。
给定一个文法，可以从结构上唯一地确定其语言。
给定一种语言，可以确定其文法，但确定出的文法不唯一。
句子中必须只有终结符，句型中可以有终结符，也可以没有。
语法分析树
从一个句型到一个句型的推导往往不唯一，可以以图形方式描述一个句子的推导过程，称为语法分析树（简称语法树）。根节点是开始符号，叶节点是终结符（ token）和 ε，内部节点（非叶结点）是非终结符。
对于规则A->x1x2…xn，A是内部结点，且x1…xn是其从左到右的子结点（内部节点或叶节点）。
语法分析树的叶子必须是终结符。
从编译器角度看，二义性文法存在问题：同一个程序会有不同的含义；程序的结果是不唯一的。解决方案：重写文法，引入非终结符表示不同优先级。
二义性
造成二义性的原因：文法中没有体现出结合律和优先级（如else与if的配对问题）
1.可以通过说明对于某一个串存在两个不同的最左推导来证明文法二义
2.可以通过说明对于某一个串存在两个不同的最右推导来证明文法二义
3.可以通过构造两棵不相同的语法分析树来证明文法二义
可以基于优先级和结合性构建无二义的文法，具体表现在将非终结符划分等级，再将最抽象的非终结符放在左边。
二义文法的特点：
1.二义文法不是LR类文法，也非LL文法。
2.某些二义文法很容易理解，可以在构建LR分析器时进行特殊处理：
- 例如可以通过人为规定优先级和结合性（解决冲突），来构建LR分析器；
- 保守地使用二义性文法，并且必须在严格控制之下使用。
最左推导与最右推导
最左推导：首先替换最左边的非终结符
最右推导：首先替换最右边的非终结符（规范推导）
对于某一个串，若存在两个不同的最左推导，则文法二义
对于某一个串，若存在两个不同的最右推导，则文法二义
语法制导翻译
语法制导的定义：让每个文法符号与一个属性集合相关联；让每个产生式与一组语义规则相关联。
语法制导翻译是指采用文法来指导对程序的翻译过程，具体表现为通过向一个文法的产生式附加一些规则或程序片段来实现。
语法制导定义和翻译方案分别描述了两种不同的附加规则或程序片段的方法。
语法制导翻译使用上下文无关文法CFG来引导对语言的翻译，是一种面向文法的翻译技术，语法制导翻译是目前最常用的语义分析技术。语法制导翻译横跨了语法分析、语义分析、中间代码生成三个阶段。
语法制导翻译的基本思想：当归约（或推导）到某个产生式时，除了按照产生式进行相应的代换之外(语法分析)，还要按照产生式所对应的语义规则执行相应的语义动作，如计算表达式的值、产生中间代码(语义分析)。
如何表示语义信息？为CFG中的文法符号设置语义属性，用来表示语法成分对应的语义信息。
如何计算语义属性？对于给定的输入串x ，构建x的语法分析树，并利用与产生式（语法规则）相关联的语义规则来计算分析树中各结点对应的文法符号的语义属性值。
语义规则也叫语义子程序或语义动作，将语义规则同语法规则（产生式）联系起来有两种方式：语法制导定义(Syntax-Directed Definitions, SDD)；语法制导翻译方案 (Syntax-Directed Translation Scheme , SDT)。
对输入串的翻译就是根据语义规则进行属性计算
1.语法分析—建立语法分析树。
2.语义分析—遍历语法分析树。
3.语法制导翻译—建立与遍历同时完成。
语义规则也叫语义子程序或语义动作，只给出属性计算的定义，没有属性计算的次序等实现细节。语法制导翻译方案(SDT)是SDD的补充，它给出使用语义规则进行计算的次序，把实现细节表示出来。
语法制导翻译方案
SDT的设计原则：保证语义动作不会引用还没有计算的属性值。
1.L-属性定义：本身就能确保每个动作不会引用尚未计算出来的属性。
2.S-属性定义：为每一个语义规则建立一个包含赋值的动作，并把这个动作放在相应的产生式右边的末尾。
语法制导翻译方案的定义：将语义动作直接嵌入到产生式规则中。
画出一个翻译方案的语法分析树时，要同时描述语义信息：为每个语义动作分别构造一个额外的子结点，并用虚线将它和该产生式头部对应的结点相连，如下图所示：
注释分析树
注释分析树的定义：在结点上标记相应的属性值的语法分析树。
综合属性：如果某属性在语法分析树结点N上的值是由N的子结点以及N本身的属性值确定的，这个属性称为综合属性。如果只存在综合属性，则只需要自底向上对分析树进行一次后序遍历，就可以算出各个结点的属性值。
语法分析
语法分析的定义：确定如何使用文法推导一个终结符号串（句子）的过程。
给定文法G，从G的开始符号S开始，用产生式的右部替换左侧的非终结符，此过程不断重复，直到不出现非终结符为止，最终的串称为句子。每一步推导中，都需要做两个选择：1.选择当前句型的哪个非终结符进行替换；2.选择该非终结符的哪个候选式进行替换。
语法分析器基于文法检查记号流的构成，识别正确的输入，生成分析树，发现、报告语法错误。
语法分析的基础是上下文无关文法。
语法分析方法分类：
1.自顶向下：从根结点开始，逐步向叶子结点方向进行构造；从文法的开始符号出发，反复使用各种产生式，寻找匹配的推导（手工法，最左推导，不能处理左递归）。
2.自底向上：从叶子结点开始，逐步构造出根结点；从输入串开始，逐步进行归约，直到文法的开始符号（算符优先分析法、LR分析法，短语，句柄，前缀，最左归约）。
最左归约，也称为规范规约，即反向构造最右推导，是最右推导的逆过程。
最右推导：也称为规范推导。
自顶向下分析法：1.从标号为开始符号的根结点开始，反复执行以下两个步骤；2.扩展结点：在标号为非终结符号A的结点N上，选择A的一个产生式，并为该产生式体中的各个符号构造出N的子结点；3.确定待扩展结点：寻找下一个结点来构造子树，通常选择当前语法分析树中最左边的尚未扩展的非终结符。
在递归下降分析法（属于自顶向下分析法）中，使用一组递归过程来处理输入，文法的每一个非终结符都关联一个过程。
在预测分析法（属于递归下降分析法）中，每个非终结符对应的过程中的控制流都可以通过向前看一个符号来确定，即选择哪个产生式可以通过输入中当前被扫描的终结符来确定。分析输入串时出现的过程调用序列对应着先根遍历该输入串的一棵语法分析树。但当产生式出现左递归（产生式体的最左边的符号和产生式头部相同）时，递归下降语法分析/预测分析器会进入无限循环。
消除左递归
对于形如A → Aα | β的左递归产生式（其中α和β是任意符号串），可以通过引入新的非终结符R转换为：
A → βR
R → αR | ε
实际上，左递归的消除过程是把左递归转换为右递归。
消除间接左递归
间接左递归是由多步推导带来的左递归，核心步骤是代入：
如果文法不存在环或ε产生式，一定可以消除左递归。
回溯
在预测分析法中，非终结符选择产生式是一个“尝试并犯错”的过程。即首先选择一个产生式，不合适时进行回溯，再尝试另一个产生式。当出现形如 A->αβ1|αβ2的产生式，此时无法确认应该选择A的哪个产生式，可以通过改写产生式(提取左公因子)来推后这个决定，例如A-> αA’、A’-> β1|β2，等获得足够信息后再做出正确的选择。
词法分析
词法分析用于从输入中读取字符，并将它们组织成词法单元（记号）。涉及的工作：预读（通常为一个字符）、常量识别、识别关键字和标识符、剔除空白和注释。为了区分关键字（for、if）和标识符，在初始化符号表时即加入所有关键字。
词法分析的任务：从左向右逐行扫描源程序的字符，识别出各个单词，确定单词的类型，并将识别出的单词转换成统一的机内表示——词法单元(token)形式。
编译程序是在单词的级别上来分析和翻译源程序，因此词法分析是编译的基础。
记号（词法单元、单词、Token）：具有独立含义的最小语法单位，每个记号代表一类符号串。
模式（Pattern）：描述某个记号的词素集合的构造规则。
词素Lexeme：源程序的符号序列，可匹配某个记号的模式，如标识符count等。
词法分析器的作用：
1.读入源程序，去除注释、空格、制表符、换行符等
2.建立符号表
3.识别词素，抽象成记号
4.将记号插入符号表
5.发现词法错误，建立错误消息与源程序的位置联系
6.将记号提交给语法分析器
词法分析器的输出：<单词种别，单词自身的值>，单词种别通常用整数编码表示。
单词的属性值：
1.对于关键字、分界符、运算符，单词种别就可以表示其完整的信息，其单词自身的值通常为空
2.对于标识符，词类编码所反映的信息不够充分，标识符的具体特性还要通过单词自身的值进行互相区分。标识符的单词自身的属性常用其在符号表中的入口指针来表示。
3.对于常数，单词自身的值常用其在常数表中的入口指针来表示。
词法错误
当前输入的前缀无法匹配任何记号时，将导致词法错误，如：出现当前语言中不会出现的字符@；整数越界；标识符名太长；字符串跨行。
双缓冲双指针策略
采用双缓冲，一个缓冲I/O，另一缓冲词法分析
采用大块存储空间作为缓存，一次性将大批数据读入缓存，提高源程序读入速度的策略
词法分析的设计形式
1.设计成一个独立程序，完成词法分析的任务，结果以文件的形式组织，做为语法分析的输入
2.作为语法分析的子程序
单独划分词法分析阶段的原因：
1.结构简洁、清晰和条理化，有利于简化编译器的设计
2.提高编译器的效率
3.增强编译器的可移植性
词法分析器的设计
1.给出程序设计语言的单词规范——单词表
2.对照单词表设计识别该语言所有单词的状态转换图
3.根据状态转换图编写词法分析程序
词法分析器的三种构造策略
1.使用传统的程序设计语言手工编写
2.使用汇编语言手工编写
3.使用词法分析器生成器，从基于正规式的说明自动产生
状态转换图
状态转换图是一张有向图，用来描述和识别记号，是模式的图形化表示。一张状态转换图包含有限个状态，其中有一个为初始状态，有若干个终止状态。结点代表状态，用圆圈表示；有向边代表动作Actions，边上的字符表示射出状态下可能出现的输入字符；初态表示模式的开始，无源箭头的目标；终态表示模式的结束，用双圈表示。
状态转换图可用于识别（或接受）一定的字符串，若存在一条从初始状态到某一终止状态的道路，则称该道路被该状态转换图所识别（接受）。
在状态转换图中，对不含回路的分叉结点，用一个switch或if-else语句实现；对含回路的结点，用一段while和if语句构成的程序实现。
前缀后缀
正则表达式
程序设计语言的单词符号都是一些特殊的字符串，可以用正规集和正规表达式来描述。
正则表达式(RE)：又名正则式、正规表达式、正规式，是一种用来描述词素模式的更紧凑的表示方法，是基于字母表构造串的一组规则。正则表达式可以由较小的正则表达式按照特定规则递归地构建。
正规集：如果r是正则式，则L®是r描述的语言，也称为正规集、正则集。所有词法结构一般都可以用正则集描述。
正则表达式与正规集的联系：
1.正规集可以用正规式表示
2.正规式是表示正规集一种方法
3.一个字集合是正规集当且仅当它能用正规式表示
冲突解决
词素的选择
1.匹配最长串的规则优先
2.长度相同时，在前的规则优先
有穷自动机
有穷自动机(FA)是对一类处理系统建立的数学模型，这类系统具有一系列离散的输入输出信息和有穷数目的内部状态。系统只需要根据当前所处的状态和当前的输入信息就可以决定系统的后继行为（下一状态）。每当系统处理了当前的输入后，系统的内部状态也将发生改变。有穷自动机是识别器，它只能对每个可能的输入串，简单地回答是或否。
可以使用状态转换图中的结点来表示有穷状态机的状态。
状态转换矩阵（表）：描述各个状态下，对应于各个输入的状态迁移。
FA分为DFA（确定的有穷自动机）和NFA（不确定的有穷自动机），DFA是NFA的一个特例。
在FA中，当输入串的多个前缀与一个或多个模式匹配时，总是选择最长的前缀进行匹配。
DFA
DFA：确定有穷状态自动机
DFA可以使用状态转换图和状态转换矩阵表示。
正规式转换为确定有限状态自动机（DFA）时，不同构造方式可能生成不同结构的DFA，但经过最小化后会得到唯一的最简DFA。
NFA
NFA：非确定有穷状态自动机
NFA可以有多个初态，弧上的标记可以是一个字（如aab），而不一定是单个字符。同一个字可能出现在同状态射出的多条弧上（如状态1输入a可能得到状态0或状态1）。
DFA可以使用状态转换图和状态转换矩阵表示，且不忽略ε边。
DFA与NFA描述能力相同：
1.对任何非确定的有穷自动机NFA，存在定义同一语言的确定的有穷自动机DFA
2.对任何确定的有穷自动机DFA，存在定义同一语言的非确定的有穷自动机NFA
DFA的状态集是NFA状态集合的一个子集
构造NFA
NFA转DFA
步骤：
1.画出表格 DFA | NFA | 终结符1 | 终结符2
2.完善表格
3.画出DFA
最小化DFA
最小化DFA的基本思想：将M的状态集划分为一些不相交的子集，使得任何两个不同子集的状态是可区分的，而同一子集的任何两个状态是等价的。最后，选择每个子集一个状态作代表，消去其他状态。所有状态的初始划分为：终态和非终态两个集合。
递归下降的语法分析
一个递归下降分析程序由一组过程组成，每个非终结符号有一个对应的过程，识别对应的语法单位，当需要从某个非终结符出发进行展开(推导)时，就调用这个非终结符对应的子程序。
程序的执行从开始符号对应的过程开始，如果这个过程的过程体扫描了整个输入串，它就停止执行并宣布语法分析成功。
预测分析
预测分析法是一种表驱动的方法，它由下推栈，预测分析表和控制程序组成，是一种确定性的下推自动机。
在预测分析的每步推导过程中，通过在输入中向前看固定个数（通常是一个）符号来选择正确的产生式。为保证分析的确定性，选出的候选式必须是唯一的。预测分析不需要回溯，是一种确定的自顶向下分析方法。可以对某些文法构造出向前看k个输入符号的预测分析器，该类文法有时也称为LL(k)文法类。
综上所述，预测分析可以：消除左递归、消除二义性、消除回溯。
FIRST集
FOLLOW集
非终结符A的后继符号集FOLLOW(A)：可能在某些句型中紧跟在A右边的终结符号的集合。
LL(1)文法
L: 从左到右扫描输入串；L: 最左推导；1:每一步只需向前查看一个符号即可确定语法分析动作
对于LL(1)文法，可以构造不需要回溯的递归下降分析器，左递归和二义性文法都不是LL(1)文法，如果G是左递归或二义的，那么M至少含有一个多重定义入口，LL(1)文法的预测分析表M不含多重定义入口；
成立条件：文法G是LL(1)，当且仅当G的任意两个不同的产生式A→α｜β，满足FIRST(α)∩FIRST(β)＝空集；若ε∈FIRST(β)，则FIRST(α)∩FOLLOW(A)=空集；α也有类似结论。
流程：
1.消除文法左递归，消除回溯
2.计算FIRST集、FOLLOW集
3.构造预测分析表
4.分析表无多重定义，分析句子
表驱动的预测分析法
特征：不需要为每个非终结符编写递归下降过程，而是根据预测分析表构造一个不需要回溯的非递归下降语法分析器。
要求：文法是LL(1)的。
对于LL(1)文法，可以对输入串进行有效的无回溯的自上而下分析。若表中存在多重定义项目，则本文法不是LL(1)。
构造预测分析表
步骤：1.计算FIRST集、FOLLOW集；2.计算每条产生式的FIRST集；3.填写表格，行为非终结符，列为终结符。
两种情况下可以检测到错误：
1.栈顶的终结符和当前输入符号不匹配；
2.栈顶非终结符与当前输入符号在预测分析表对应项中的信息为空。
利用预测分析表进行分析
自下而上分析
移入-规约
自底向上语法分析的通用框架：移入-归约分析
归约的定义：先将一个子串与某规则的右部匹配，然后将该子串替换为该规则的左部。
移入-归约分析器可采取的4种动作：
1.移入：将下一个输入符号移到栈的顶端
2.归约：被归约的符号串的右端必然处于栈顶。语法分析器在栈中确定这个串的左端，并决定用哪个非终结符来替换这个串
3.接受：宣布语法分析过程成功完成
4.报错：发现一个语法错误，并调用错误恢复子例程
移入-归约分析中存在的问题：错误地识别了句柄。
短语-直接短语-句柄
任一子树的叶节点从左到右排列所组成的符号串都是该句型的短语。
任一最小子树（树高为1）的叶节点所组成的符号串都是该句型的直接短语。
句柄是句型中最左边的直接短语。
活前缀-可归前缀
活前缀，也称为可行前缀
可归前缀是以句柄结尾的前缀，即最长的活前缀
LR分析法
LR 文法定义：
L：从左到右扫描输入串。
R：反向构造最右推导序列（规范归约）。
性质：最大可构造移入 - 归约分析器的文法类，属于上下文无关文法。
LR (k) 分析核心概念：
分析方式：规范归约，以句柄为可归约串。
句柄：最右推导的直接短语，识别进展由状态表示。
向前看 k 个符号：LR (k) 分析需查看 k 个输入符号确定动作。
LR 分析法基本原理：
自底向上分析：关键是识别句柄，通过状态抽象历史信息与展望信息。
动作确定：由栈顶状态和当前输入符号唯一确定移入或归约。
活前缀：保证栈中始终为规范句型的活前缀（不含句柄之后的符号）。
LR 分析表组成：
ACTION：状态与输入符号对应的动作（移入 / 归约 / 接受）。
GOTO：状态与非终结符对应的转移状态。
LR(0)自动机
规范归约过程中，栈内的符号串和扫描剩下的输入符号串构成了一个规范句型。栈内如果出现句柄，句柄一定在栈的顶部，一旦栈顶出现可归约串（句柄），则进行归约。
LR(0) 自动机是一个确定性有穷状态自动机（DFA）。指导LR分析的目标是保证栈中总是活前缀，可构造一个DFA来识别G的所有活前缀。
如果基于某文法构建的所有 LR(0) 项集，要么只有移入项目，要么只有一个归约项目，则可以构建 LR(0) 分析表。同时有：
• 该文法称为 LR(0) 文法；
• 在分析时，不需要看后续输入即可确定动作；
• 分析表中，归约项目无需考虑后继。
“归约项目”和“归约项目或移进项目”共存于一个项目集中会引起冲突。
同属于一个产生式的项目，但圆点的位置只相差一个符号，则称后者是前者的后继项目。如A→α· Xβ的后继项目是A→αX·β
可以把等价的项目组成一个项目集(I)，称为项目集闭包，每个项目集闭包对应着自动机的一个状态。
项目集闭包
LR(0)自动机
LR(0)分析表
如果基于某文法构建的所有LR(0)项集，要么只有移入项目，要么只有一个归约项目，则可以构建LR(0)分析表，并且该文法称为LR(0)文法；在分析时，不需要看输入即可确定动作；分析表中，归约项目无需考虑后继。
SLR(1)分析表
1.LR(0)文法能分析的文法有限，没有太大的实用价值；
2.LR(0)分析表可能包含冲突。
解决LR(0)冲突的方法是向前看一个输入符号，得到SLR分析法。
LR(1)
SLR(1)的优点是：相比LR(0)，可能减少需要归约的情况；可能消除移入-归约冲突。但SLR只是简单地考察下一个输入符号b是否属于与归约项目A->α相关联的FOLLOW(A)，b∈FOLLOW(A)只是归约α的一个必要条件，而非充分条件。
解决方法：通过分裂状态，使LR分析器的每个状态A->a·能确切知道句柄a后紧跟哪些终结符时才能把a归约成A。对于产生式 A→α的归约，在不同的使用位置，A会要求不同的后继符号。
LR(1)文法
如果LR(1)分析表中没有语法分析动作冲突，那么给定的文法就称为LR(1)文法。
第二步：构造带向前搜索符的项目集规范族
1.文法开始符后面直接写$
2.对于I0的S->·BB，满足其上一行中·后为S，且·后第二位为空，因此直接将上一行的向前搜索符抄下来。
此外，对于I0的B->·aB，满足其上一行中·后为B，且·的后第二位为不为空，则将第二位的FIRST集写下来，即B->·aB,a；B->·aB,b。
由上图的项目集规范族可知，对于状态I8，在a列及b列填写r2即可，故得到LR(1)分析表如下：
LALR
LR(0)->SLR(1)->LALR(1)->LR(1)，功能越来越强大。
LALR分析：寻找同心集，并将它们合并成一个项集。（同心集：具有相同核心的项集，即除展望符外，两个LR(1)项目集是相同的。）
可以压缩LR(1)分析表中的状态数，从而可能得到LALR分析表，压缩不会导致移入/归约冲突，但可能导致归约/归约冲突(此时文法不是LALR)。
特点：
1.LALR分析能力介于SLR(1)和LR(1)之间。
2.具有SLR(1)的状态数少的优点和LR(1)的适用范围广的优点。
3.状态数和LR(0)自动机的状态数相同。
4.归约项目的后继符号既不采用SLR(1)的Follow集方法，也不采用LR(1)的完全精确法。
5.把类似的项目集进行合并，修改ACTION表和GOTO表，反映合并的效果。
语法制导定义
为每个文法符号（终结符或非终结符）配备若干相关的“值”（称为属性），代表与文法符号相关信息，如类型、值、代码序列、符号表内容等。为每个文法的每个产生式配备一组属性的语义规则，对属性进行计算和传递。如果X是一个文法符号，a是X的一个属性，则用X.a表示属性a在某个标号为X的分析树结点上的值。
文法符号的属性：
1.综合属性：在分析树结点N上的非终结符A的综合属性只能通过N的子结点或N本身的属性值来定义。终结符可以具有综合属性。
2.继承属性：在分析树结点N上的非终结符A的继承属性只能通过N的父结点、N的兄弟结点来定义。
3.终结符没有继承属性。终结符从词法分析器处获得的属性值被归为综合属性值。
SDD属性的计算
计算属性值
1.创建分析树(自顶向下或自底向上)
2.构建依赖图(基于分析树和语义规则)
3.对依赖图进行拓扑排序
4.计算属性值
B.c为综合属性，只能由自身或子结点确定。
依赖图
语法树中各结点的综合属性和继承属性之间的相互依赖关系可以用依赖图（有向图）来描述。依赖图指出语法树中各结点属性值的计算顺序。特点：先有文法，后确定语义计算顺序。
如果一个SDD中不存在属性之间的循环依赖关系（即依赖图中不存在环），则该文法是良定义的，依赖图存在拓扑排序。一个依赖图的任何拓扑排序都给出一棵语法树中结点的语义规则计算的有效顺序。
S-属性
仅仅使用综合属性的SDD称为S属性的SDD，或S-属性定义、S-SDD。如果一个SDD是S属性的，可以按照语法分析树节点的任何自底向上顺序来计算它的各个属性值；S-属性定义可以在自底向上的语法分析过程中实现。
S-属性定义的SDT
L-属性
L-属性定义(也称为L属性的SDD或L-SDD)的直观含义：在一个产生式所关联的各属性之间，依赖图的边可以从左到右，但不能从右到左(因此称为L属性，L是Left的首字母)。
每个S-属性定义都是L-属性定义。
L-属性定义的SDT
抽象语法树
在语法分析树中去掉那些对翻译不必要的信息，从而获得更有效的源程序中间表示。这种经变换后的语法树称为抽象语法树。
自顶向下翻译
翻译模式
SDD转SDT
中间表示
1.后缀式：逆波兰式（后缀式是语法树的线性表示（后序遍历树的结点））
2.图表示：抽象语法树AST、有向无环图DAG
3.三地址码：三元式、四元式、间接三元式
三地址码
三地址码（TAC，三地址代码）用来描述指令序列，指令的右侧最多有一个运算符。三地址码可以看成是抽象语法树或DAG的一种线性表示。三地址码的名字对应图中的内部结点。
四元式
if x relop y goto n 的四元式表示：(relop,x,y,n)
If x<y goto n 的四元式表示：(j<,x,y,n) 其中j表示jump
三元式
间接三元式
在优化编译器中，指令实际存储位置常常会发生变化，因此需要使用间接三元式。
间接三元式包含：三元式表+间接码表
类型表达式
类型检查与转换
拓宽转换：较低层的类型转换为较高层
窄化转换：较高层到较低层
隐式转换：由编译器自动完成
显式（强制类型转换）转换：程序员写出代码
目标代码生成
目标代码生成以源程序的中间表示形式作为输入，并把它映射到目标语言。
目标代码生成的一个重要任务是为程序中使用的变量合理分配寄存器。