本节主要介绍了字母表、符号串等概念及其运算，还有文法、语言、文法的分类、CFG的分析树、二义性文法等内容
参考自中国大学Mooc网上的哈尔滨工业大学的编译原理课程，用到的图也是从Mooc网中下载的原课程课件
字母表
一个字母表是一个有穷符号集合，符号包括字母、数字、标点符号等，ASCII字符集和Unicode字符集都是字母表。
字母表上的运算
既然是集合，那么就有运算。
字母表上的乘运算：
字母表上的幂运算：
字母表的n次幂等于n个字母表相乘
字母表的正闭包：
字母表的正闭包是该字母表各个正次幂的并集
字母表的克林闭包：
在正闭包的基础上添加一个空串
符号串
串是字母表中符号的一个有穷序列
长度为0的串称为空串。
串上的运算
串的连接运算：
x和y的连接，是把y附加到x后面而形成的串，记作xy
串的幂运算
串s的n次幂，等于将n个s进行连接
文法
文法的定义
当我们要描述一种语言时，需要给出这种语言的所有句子，当句子的数目是有限时，则可以穷举；而当一门语言的句子是不可穷举时，就要给出可以表示它们的结构的描述方法，即 该语言的句子的组成规则。这种规则就是文法。
以自然语言为例子，例如英语的一个文法：
文法的形式化定义：
G=(VT, VN, P, S)，G代表文法，由终结符集合、非终结符集合、产生式集合和开始符组成。
VT 终结符集合
终结符是文法所定义的语言的基本符号，有时也称为token
VN 非终结符集合
非终结符是用来表示语法成分的符号，有时也称为“语法变量”
P 产生式集合
产生式( production)描述了将终结符和非终结符组合成串的方法
S 开始符号
第一条产生式的左部（该语法钟最大的语法成分）
在不引起歧义的情况下，可以只写产生式。
语言
有了文法（语言规则），如何判定一个词串是否是满足文法的句子？
推导和规约
- 直接推导：用产生式的右部替换产生式的左部
- 推导：经过n次直接推导表示n步推导（n=1即直接推导）
- 规约：推导的逆过程即为规约（用产生式的左部替换产生式的右部）
回答前面的问题，可以有两种途径去判断某一词串是否是满足该文法的句子
- 句子的推导(派生)-从生成语言的角度：如果从文法的开始符号可以推导出这个词串，则它是该语言的一个句子。
- 句子的规约-从识别语言的角度：如果从这个词串可以规约出文法的开始符号，则它是该语言的一个句子。
句型和句子
如果从开始符S可以推导出a，则a是G的一个句型，如果句型中不包含非终结符，则它是一个句子
语言的形式化定义
由文法G的开始符号S推导出的所有句子构成的集合称为文法G生成的语言，记为L(G)
既然语言是一个集合，那么也有集合的运算：
文法的分类
0型文法
也称无限制文法/短语结构文法
对于产生式几乎没有限制，只要产生式左部至少包含1个非终结符就可以了
生成的语言成为0型语言
1型文法
也称上下文有关文法（CSG）
在0型文法的基础上，进一步要求，产生式左部的长度<=产生式右部的长度，并且形如下图，注意a1和a2，用产生式的右部替换产生式的左部需要考虑上下文(a1、a2)，这也是1型文法称为上下文有关文法的原因
上下文有关文法中不包含空产生式，产生的语言成为上下文有关语言
2型文法
也称上下文无关文法（CFG）
要求产生式的左部必须是一个非终结符，形如下图，用产生式的右部替换产生式的左部，不需要考虑上下文的情况
生成的语言成为上下文无关语言
3型文法
又成为正则语言（RG）
右线性文法，在2型文法的基础上，进一步对产生式的右部进行约束，每一个产生式的右部，要么是一个终结符号串w，要么是终结符号串w右边添加一个非终结符B
左线性文法，在2型文法的基础上，进一步对产生式的右部进行约束，每一个产生式的右部，要么是一个终结符号串w，要么是终结符号串w左边添加一个非终结符B
生成的语言成为正则语言，正则文法能描述程序设计语言的多数单词，例如下面的文法，描述字母打头的字母数字串（标识符）
四种文法之间的关系：
CFG的分析树
正则文法虽然可以描述程序设计语言的大多数单词，但是它生成能力有限，它几乎描述不了程序设计语言中的句子构造，而上下文无关文法可以描述大部分程序设计语言的语法构造。
分析树是用来描述句子结构的。分析树的组成成分：根节点、内部节点、叶节点
分析树是推导的图形化表示，给定一个推导过程，对于推导过程中得到的每一个句型a，都可以构造出一个边缘为a的分析树。
（句型的）短语
给定一个句型，其分析树中的每一棵子树的边缘称为该句型的一个短语
如果子树只有父子两代节点，那么这棵子树的边缘称为该句型的一个直接短语
直接短语一定是某产生式的右部，但产生式的右部不一定是给定句型的直接短语
例子：
上图中，高人、民生、活水都是产生式的右部，但并不是该句型的直接短语，该句型的直接短语：提高、人民、生活、水平
二义性文法
如果一个文法可以为某个句子生成多棵分析树，则称这个文法是二义性的。
例如，一个条件语句的文法：
对于句型if E1 then if E2 then S1 else S2，可以构造出两棵分析树：
上面这个句型出现两棵分析树的原因是，句中有两个if，只有一个else，所以这个else既可以和第一个if匹配（分析树2），也可以和第二个if匹配（分析树1）。
因此可以增加一个消岐规则（正如大多数编译器所做的那样）：每个else和最近的尚未匹配的if匹配，这样的话，就可以保留分析树1，删除分析树2，消除了二义性。
二义性文法的判定
对于任意一个上下文无关文法，不存在一个算法，判定它是无二义性的；但是可以给出一组充分条件，满足这组充分条件的文法是无二义性的（满足的话肯定无二义性，不满足的话也未必就是有二义性的）