文章目录
1 引论-一些名词解释1.1 解释器
总结就是Basic年代解释器是编译和解释一体，而Java由于JVM的存在先编译（javac xx.java）生成.class，后执行(java xx)。
1.2 翻译器和编译器
1.3 编译型的程序设计语言和解释型的程序设计语言各有哪些优缺点？
编译型的运行速度快，效率高，保密性较好，但是代码需要经过编译才能运行，兼容性差，只能在兼容的操作系统上运行。
解释型的兼容性好，但是运行需要解释环境，运行慢，占用资源多，效率较低，只要有解释环境，可在不同的操作系统上运行。
1.4 编译过程六个阶段的任务
前端：生成中间代码，与目标机器无关。
后端：与源程序无关，与中间代码有关，依赖于目标机器。
好处：提高编译器开发效率。
1.5 遍的概念
2.1 词法分析器
2.2 词法记号与属性
词法分析的过程就像分析英文句子的每一个单次，语法分析就是分析单词组成的每一个短语，语义分析则是更进一步。
var，count等是一个词法单元。
2.3 串和语言以及串的运算
正规集《=》语言s和t可以理解为串。
2.4 正规式、正规定义
正规式（正则表达式）
克林闭包与正闭包的关系
∑的正闭包：
∑+=∑∪∑2∪∑3∪∑4∪……
∑的克林闭包（kleene Closure）：
∑*=∑0∪∑+（与正闭包区别哦，这算是新概念）
例如：{0,1}+ = {0，1，00，01，11，000，001，010，011，100，……}
{0,1}* = {ε，0，1，00，01，11，000，001，010，011，100，…}
2.5 小结
2.6 有限自动机
会转换状态转换图即可。
2.7 不确定的有限自动机
2.8 确定的有限自动机
2.9 正规式转NFA
单个字母a的NFA，a|b的NFA，ab的NFA，a*的NFA。
可以指定为三个状态1，2，3，简化图解。
N（s）表示s的NFA.
2.10 NFA转DFA子集构造法
举个例子解释
2.11 DFA化简
首先根据分为非接受状态组和接受状态组{A,B,C,D}和{E}。
通过输入a来分组，发现第一组无法区分，看输入b的情况，A,B,C都是转到第一组，只有D是转到第二组E，所以这里就可以分出来一组D，现在有3组，{A,B,C},{D},{E}。
接着输入a,无法区分，输入b，发现B是转到现在的第二组D，A和C都是转到原来的第一组，所以分出来一组B，**得到{A,C},{B},{D},{E}，得到四组，接下来无法继续分组了。用A，B,D,E,来表示表示上述四组。**列出转换表
这样就完成了DFA的化简
2.12 有限自动机NFA-ε到NFA的转换
任何输入字母表，则A不进行任何操作。简单的图示如下：
该图下面一连串的过程可以等价为 状态q0 吸收 x 后变成状态q2
现在来看一个 NFA-ε 转为 NFA 的实例，把下图转变为NFA
**首先从状态X开始，**它能一直空跳到状态I， 由于状态I 吸收 1 后变成状态 J， 故状态 X 能接受 1直接变成状态 J，而状态G、H、I都可省去。此外，状态X也可以一直空跳到状态 A和状态 C；针对状态 A， 其接收 1 后变成状态 B ，故 X 能直接接收 1 变成状态 B， 同样由于状态 C 接受 0 后变成状态 D， 故 X 也能直接接收 0 后变成状态 D。到这里状态 X 全部讨论完毕。
接下来讨论状态 G，由于状态 G 可由状态 X 跳转得到，并且 X 已经讨论过，故状态 G 可以忽略。同理，状态 H、I、A、C也可以忽略。
接下来讨论状态 B，状态 B 可以连续跳转到 状态 A 和状态 C，由于 A 可接受 1 变成状态 B， 故 B 可直接接收 1 保持自身状态不变，又由于 C 可以接收 0 变成状态 D，故B 也可以接收 0 变成状态 D。此外，状态B也可以跳转到状态 F， 由于 F 接收 1 变成状态 J，故状态 B 也可以直接接收 1 变成状态 J。至此状态 B 讨论结束。
接下来讨论状态 C，由于状态 C 可以连续跳转到状态 A 和状态 C，由于 A 可以接收 1 变成状态 B，故C 能直接接收1变成状态B；由于C可接收0变成状态D，故D 可直接接收0保持自身状态不变。此外，状态 C也可以跳转到状态F，由于状态F接收1变成状态J，故状态 D也可以直接接收 1 变成状态 J。至此，状态 C 讨论结束。
接下来讨论状态 F，F可以由B、D经过空跳得到，由于B、D已讨论过，故F可以忽略。
接下来讨论状态 J，由于状态 J 可以通过空跳得到状态 Y，而 Y又是结束状态，故 J 是一个结束状态。
接下来讨论状态Y，由于状态 J 通过空跳得到状态 Y，故 Y 可以忽略。
至此，全部状态分析完毕，其变化后的图如下
3.1 关于文法形式化定义的探索
1 文法的概念
每一种自然语言或者是编程语言都需要文法来描述，文法相当于语言学的语义分析，即分析每一句话所表示的含义，编译器需要利用文法来完成其语法分析和语义分析。
在目前编程语言领域，上下文无关文法作为程序语言的描述工具，比如a = b + c是一个合法的赋值语句。
2 符号和符号串的定义
每个程序都可以看成是一个“基本符号”串，如果有一个基本符号集，那么C语言等编程语言可以看成是在这个基本符号集上定义的、按照一定规则构成的一切基本符号串组成的集合。
字母表是元素的非空有穷集合，字母表中的元素称之为符号，因此字母表也称之为符号集。例如C语言中的字母表由字母、数字、关键字等组成。
符号串就是由符号集中的元素组成的序列。例如给定符号集{a,b,c}，那么abc、abb、ac就是由该符号集组成的符号串。
3 文法的形式化定义
G可以是正则文法
3.1 终结符
何为终结符？在编程语言中，终结符可以理解为不能再进行拆分的基本符号，例如C语言中的if、else、while关键字，也可以是一个变量名、数字。
3.2 非终结符
和终结符相反，非终结符就是可以再进行拆分的符号，它可以推出其它的语法成分。如果要对一个非终结符进行语法分析，就需要对它需要进行递归分析。在C语言的if-else文法中，if或者else后面跟着的代码块可以看成是非终结符。
3.3 P&&S
3.2 正规文法的探索-正规文法转换为正规式
1 前言
正规文法与正规式都是描述正规集的工具。对任意一个正规文法，存在定义统一语言的正规式；反之，对每个正规式存在一个生成同一语言的正规文法。
对任何正规文法G，存在定义同一语言的正规式 r,还有正则语言
正规语言又称,正则语言,可以被确定有限状态自动机识别,可以被非确定有限状态自动机识别,
2 求解过程
① 将文法中的规则写成关于每个非终结符的正规式方程，得到一个方程组；
② 依照求解规则：
阿发在前是阿发*贝塔 在后是贝塔阿发*
3 示例
设有正规文法G：
A→ aB | bB
B→ aC | a | b
C→ aB
试给出该文法生成语言的正规式
解：首先给出相应的正规式方程组（方程组中用“+”代替正规式中的“|”）如下：
① A = aB + bB
② B = aC + a + b
③ C = aB
把 ③ 式代入 ② 式得
④ B = aaB + a + b
对 ④ 式使用求解规则得
⑤ B = (aa)*(a + b)
把 ⑤ 式代入 ① 式得
⑥ A = a(aa)* (a + b) + b(aa)* (a + b)
3.3 产生式的简写
对一组有相同左部的α产生式 α→β1 , α→β2 , … , α→βn 可以简记为： α→β1 | β2 | … | βn 读作：α定义为β1，或者β2，…，或者βn 。 β1，β2，…，βn称为α的候选式(Candidate)
➢例 产生式的简写 E → E + E E → E * E E → ( E ) E → id E → E + E | E * E | ( E ) | id
3.4 推导 (Derivations)和归约(Reductions)
给定文法G=(VT , VN , P , S )，如果 α→β ∈ P，那么 可以将符号串γαδ中的α替换为β，也就是说，将γαδ 重写(rewrite)为γβδ，记作 γαδ γβδ。此时，称文法 中的符号串 γαδ 直接推导(directly derive)出 γβδ ➢简而言之，就是用产生式的右部替换产生式的左部
3.5 句型和句子
一个句型中既可以包含终结符，又可以包含非终 结符，也可能是空串
句子是不包含非终结符的句型
3.6 语言的形式化定义
语言：在某一确定字母表上的特定符号串的集合。 空集ε，集合{ ε }也是符合此定义的语言。
句型、句子和语言要区分开。
文法：
T → L | D | TL | TD
语言：
3.7 文法的分类
CSG中不包含ε-产生式
2型文法也叫上下文无关文法。
上下文无关文法 (Context-Free Grammar, CFG )
➢ ∀α → β∈P，α ∈ VN （非终结符）
➢产生式的一般形式：A→β
➢ 上下文无关语言（2型语言）
➢由上下文无关文法 (2型文法) G生成的语言L(G )
正则文法(Regular Grammar, RG )
➢ 右线性(Right Linear)文法： A→wB 或 A→w
➢ 左线性(Left Linear) 文法： A→Bw 或 A→w
我们一般讨论CFG。
3.8 CFG 的分析树
分析树是推导的图形化表示
-（id+id）是文法产生的语言中的一个句型，没有非终结符也可以叫句子。（个人理解）
3.9 二义性文法 (Ambiguous Grammar)
如果一个文法可以为某个句子生成多棵分析树， 则称这个文法是二义性的
消歧规则：每个else和最近 的尚未匹配的if匹配.
3.10 自顶向下分析
3.11 最左推导
3.12 最右推导
3.13 自顶向下的语法分析采用最左推导方式
3.14 预测分析
找不到合理的分析树，就要回溯。
3.15 消除直接左递归
A'->aA'|空串<=>A'->a*空串。
3.16 消除间接左递归
3.17 FIRST集和FOLLOW集的计算
首先考虑直接能一眼看出的终结符，然后考虑右部串首是终结符的，比如T，因为E’可能推出空串，所以E的串首终结符就是T的。同理，考虑F，T’可以为空，所以T和F一样，E依赖于T，和T一样，完成。
E本身是一个句型，所以是最右符号，所以$要加入follow（E）。
E‘可以推出+，所以加入follow（T）。
因为E‘可以为空串，所以跟在E后面的终结符也可能跟在T的后面，所以follow（E）加入follow（T）。
E’在第一个产生式的最右侧，所以能跟在E后面的终结符也可能跟在E‘后，所以follow（E）加入follow（E’）。
第二个产生式和第一个一样。
3，4产生式和1，2同理。
E后紧跟），所以加入follow（E）。
还没有完，follow（E）更新了，依赖于他的都需要更新。
因为E‘可以为空串，所以跟在E后面的终结符也可能跟在T的后面，所以follow（E）加入follow（T）。
E’在第一个产生式的最右侧，所以能跟在E后面的终结符也可能跟在E‘后，所以follow（E）加入follow（E’）。加入了两个括号。
同理follow（T’）和follow（F）也要分别加入），完成。
（1）FIRST
（2）+
（3）FOLLOW
以此类推
第2第3个产生式有相同的左部，他们的select集互不相交，完成。
表达式时LL（1）文法。