编译原理
1.字母表上的运算
字母表的乘积
字母表的n次幂
字母表的正闭包：字母表正数次幂的并集
- 字母表的克林闭包：正闭包的基础上再加上空
2.串
串是字母表中符号的一个有穷序列
串s的长度，通常记作｜s｜，是指s中符号的个数，例如：｜aab｜=3
空串是长度为0的串，用epsilon表示
3.串上的运算
乘法可看作连接
4.文法
形式化定义：G=（VT，VN，P，S）
终结符和非终结符不相交。
5.语言的定义
6.文法分类体系
- 0型文法
- 0型文法形成的语言称为0型语言
- 1型文法
- 上下文有关文法
- 2型文法
- 上下文无关文法
- 3型文法
- 正则文法
- 右线性文法
- 左线性文法
- 正则文法
7.上下文无关文法的分析树/CFG的分析树
上下文无关文法可以描述大部分语法构造，被研究的做多。
分析树：
- 根节点的标号为文法开始符号
- 内部节点表示对一个产生式A->𝛃的应用，该节点的标号是此产生式左部A，该结点的子结点的标号从左到右构成了产生式的右部𝛃
- 叶结点的标号既可以是非终结符，也可以是终结符，从左到右排列叶结点得到的符号串称为是这棵树的产出或边缘。
短语：
分析树中每一棵子树的边缘称为该句型的一个短语
直接短语：
如果子树只有父子两代，其边缘则为直接短语
【直接短语一定是某产生式的右部】
【但产生式的右部不一定是给定句型的直接短语】
二义性文法：一个句子可能对应多于一个语法树
【有歧义的文法】
【解决方法】每个else和最近的尚未匹配的if匹配
总结：
分析树能反映句型的推导过程，也能反映句型的结构。然而实际上，我们往往不关心推导的过程，而只关心推导的结果。因此，我们要对分析树进行改造，得到语法树。语法树中全是终结符，没有非终结符。而且语法树中没有括号。
