概述
1.词法分析：也成线性分析或扫描
完成字符流到记号流（词法记号序列）的转换。
是一个程序。
2.词法单元：
是词法分析的最小单位。构成句子的基础
就是一个单词
3.语法分析：也称分析
把词法分析出来的记号流里所有记号的第一元提出来，根据构造（构造：函数、语句、表达式等），生成语法树
是一段程序
4.语法树：
给中间代码生成器提供输入。 另外一种解决办法是三地址指令
是一种中间表示
5.语义分析：
和类型检查有关，其他不清楚
6.中间代码生成：
把语法数转成三地址指令。还可以实现有条件控制转移，无条件控制专业和过程调用。
是什么？
7.代码优化：
改变中间代码生成，以便运行提高效率，比如把final的值在编译期就确定
是什么？是一段程序。
8.代码生成：
生成可以放到寄存器里的等等各种代码
9.符号表
记录变量名字，并且记录变量的各种属性：作用域、存储分配、类型等
是一个表，表里的每一条记录就是一个变量
词法分析
2.1 词法记号与属性
2.1.1 词法记号、模式、词法单元
10.词法记号：
用来做语法分析的输入值。
是被词法分析的输出结果。由符号流转化而来。写作：记号(记号名，属性值)
11.模式：
用来归类词法单元。（词法单元前面）
词法单元遵从相同的模式，就是一个词法记号。例：任何数值常数。
12.关键字：
保留字：
标准标识符：
2.1.2 词法记号的属性
13.词法记号的属性：
从目标代码来看，不同的关系运算符，翻译结果不一样。
记号名影响语法分析的决策，属性影响记号的翻译
2.1.3 词法错误
错误恢复策略：
14.词法分析器：
输出记号序列。
2.2 词法记号的描述与识别
2.2.1 串和语言
15.串：
16.语言：
17.字母表：
这仨前面有讲
18.正规式：
就是前面所讲的模式的一种实现方法。
是按照一组定义规则，由较简单的正规式构成的。每个正规式r表示一个语言L(r)
这些定义规则能说明L(r)是怎样从r的子正规式所表示的语言中构造出来的。
正规式表示的语言叫做正规语言或正规集。
19.正规定义：
前面讲过了，就是一个过程。
20.状态转换图：
词法分析器被语法分析器调用时，词法分析器为返回下一个记号所做的动作。
是啥以前的文章里有讲
2.3 有限自动机
把正规式翻译成识别器
是转换图的一般实现（所以就是一个转换图。）
识别器：判断输入的串x是否是语言的一个句子。输出“是”或“否”
21.不确定的有限自动机NFA
不确定：存在这样的状态，对于某个输入符号，它存在不止一种转换。
词法分析器的生成器
语法分析
22.语法分析输入是记号序列，输出是分析树的某种表示。以易理解的方式报告错误。把各种信息存到符号表中。
编程语言有一些规则来描述正确的语法结构。比如c语言程序由若干函数组成，函数由若干声明和语句组成，语句由若干表达式组成。 这些规则就是语法分析。
这些规则可以用上下文无关文法或BNF表示法来描述。
语法分析通常有 自下而上或自上而下两种。
但是最好的自下而上和自上而下分析法只能处理上下文无关文法的子类。
可以这么说，语法分析按照文法分类有：上下文无关文法和BNF表示法
按照顺序分类有：自下而上或自上而下。
23.上下文无关文法G
作用是用来描述正规式描述不了的复杂语言（比如配对或嵌套的结构、配对括号构成的串）
是个四元组（终结符集合，非终结符集合，开始符号，产生式）
24.上下文无关语言
不知道有啥用。
开始符号经过推导，就是上下文无关语言。
25.推导
用来描述文法定义的语言，即文法经过推导才能形成语言。
推导就是把产生式的箭头改成=>。 但是分三种：=>是一次推导。 =>+是一次或多次推导。 =>*是零或多次推导
从开始符号E开始，不断使用产生式，可以得到一个代换序列。这个代换序列就称为从E到id+id的推导。(p42下）
26.句型
当且仅当S=>+w，则终结符串w在L(G)中。如果串w是L（G）语言的句子。也可以说w是文法G的句子。
如果串w里包含非终结符，那么串就是句型。 句子是只包含终结符的句型。
27.分析树
CFG的分析树
分析树的作用和推导的作用一模一样
分析树就是推导的图形表示
俩文法：
正则文法描述大部分词语，但是没法描述句子结构
上下文无关文法可以描述句子结构。
上下文无关文法推导句子结构的过程的图形化显示就是分析树。
28.自上而下分析的一般方法
根据输入，不断的测试产生式，以求能够完美匹配。
但是会遇到两个问题：回溯和递归
对于递归，前面说了，一个办法是消除左递归。
对于回溯，前面说了，一个办法是提取公因子。或者使用其他办法。比如一个办法是LL(1)文法
29. LL(1)文法
30.自下而上分析的一般方法
自下而上分析，其中一种分析方法是 LR分析法。
31. 短语、直接短语
分析树其实是上下文无关文法的分析树。 分析树就是推导的图形化显示。 分析树显示了从文法到语言的推导过程。
分析树：
根节点、内部节点、叶子节点（产出、边缘）
短语：每个子树的边缘
直接短语：高度为2的子树的边缘
32. 句柄
句柄就是句型里的一个子串。
句型就是组成带有非终结符的串。串是语言的一个实例。即句型就是语言的一个实例，只不过这个实例里有非终结符。 实例里没有非终结符的叫做句子。
句柄是句型里的一个子串，只不过这个子串是最左直接短语。
直接短语：先画出分析树，分析树的高度为2的子树的边缘就是直接短语。
句柄的右边仅含终结符
如果文法二义，那么句柄可能不唯一
33. 右句型
最右推导可得到的句型。
题目
34.NFA的确定化
35.NFA的最小化
36.正规式转化成有限自动机
37.消除左递归
38. First
39. follow
40. LL(1)文法举例、预测分析表
41. 自下而上分析法
42. LR分析法
L：从左到右扫描输入串
R：构建一个最右推导的逆过程
LR方法的基本思想
43. 文法的项目
带点的。
44. 项目集规范簇（GO函数）
45. 闭包 CLOSURE(I)
46. LR(0)分析表的构造
47. SLR(1)分析表的构造
48. 全部活前缀的DFA
若有收获，就点个赞吧
0 人点赞
