1.编译程序：
翻译程序，源语言翻译为目标语言
C语言 ——>汇编语言
2.逻辑过程
词法分析 语法分析 语义分析 中间代码生成优化 目标代码生成优化
词法分析： 最基本的单词分析出来
语法分析：看组成的句子是否有语法错误
语义分析： 分析所写程序具体的含义
3.字母表（符号的集合）
∑ = {a,b,c}
aa,ab,aac 都是∑上的符号串 空串ε 长度|ab|=2
对于x=abc，a，ab，abc都是子串，ε不是子串
4.符号串的头，尾，固有头，固有尾
符号串的头使得尾不为空，头为固有头，固有尾类似
5.符号串连接
x，y为符号串，则他们的连接就是xy
6.符号串的方幂
x的n次幂就是把x写n次，x的0次幂等于空串
7.符号串的集合
若集合A中的一切元素都是某字母表上的符号串，则A为该字母表上的符号串的集合
8.空集
没有任何元素的集合（连空串都没有）
9.符号串集合的乘积
AB={x|x∈A，y∈B}； A={1，2} B={5，6，7} AB={15,16,17,25,26,27}
10.字母表∑的闭包（∑*）
∑*=∑的零次∪∑的一次∪∑的二次∪∑的三次∪...
∑*表示∑上一切长度为n(n>=0)的符号串所组成的集合
∑={a,b,c} ∑*={ε，a,b,c,aa,ab,ac,ba,bb,bc,ca,cb,cc.....}
∑的正闭包就是∑*去除ε
∑+=∑∑*
11.文法和语言
文法G[<标识符>] ： <标识符> -> <字母>
（上下文无关文法 <标识符> -> <标识符><数字>
<标识符> -> <标识符><字母>
<字母> -> a/b...../z
<数字> -> 0/1/2...../9
左部 右部
非终结符 除了非终结符都是终结符
重写规则（产生式）：
元语言符号 ——>和::= 表示“定义为”
G定义为四元组（VN非终结符集合，VY终结符集合，P重写规则集合，S识别符号）
VN={<标识符>,<字母>,<数字>}
VT={只在右边出现的}
P={<标识符> -> <字母> 默认第一条是文法的开始符号
...
}
S=<标识符>
很多时候，只将四元组的产生式写出来，就可以表示四元组
v = 233<字母>666 w = 233a666
<字母> ::= a v直接推导/产生出w v => w
w直接归约为v
如果只用了一步，推到长度为1 没有用规则，推导长度为0
G[Z] 推导出的x只含有终结符，x为句子 既含有终结符也含有非终结符，x为句型
文法描述的语言是该文法一切句子的集合
L (G[S]) = {x | S = >X,且x是句子}
递归规则：右边出现了左部，在右部中标识符出现在最左边就是左递归，最右边就是右递归
12.2型文法（上下文无关文法）
对于文法G 每个规则都有如下性质：非终结符 ——> 终结符或非终结符
13.语法分析树
每个节点都是某一终结符/非终结符
树根 文法的开始符
分支 有分支的节点一定是非终结符
子树 这个节点的树根连同向下射出的部分
简单子树 只含有单层分支的子树
14.最左推导
每次的推导都替换最左边的非终结符
最右推导（规范推导）：每一步都是替换最右边的非终结符
最左归约（规范归约）：从最左边开始归约
规范句型：在最右推导中推导出来的句型
15.二义性
一个语法中存在某个句子有两个不同的语法树，就是二义性的
16.句型分析
定义：识别一个符号串是否为某文法的句型
分类：自上而下（推导），自下而上（归约）
自下而上：
子树的末端节点的符号串是相对于子树根的短语
简单子树的末端节点组成的符号串是相对于简单子树根的简单短语（直接短语）
最左简单子树的末端节点组成的符号串是句柄
