计算机执行用高级语言编写的程序主要有两种途径：解释和编译编译：专指由高级语言转换为低级语言编译和解释的区别：是否产生目标程序编译程序的五个阶段：词法分析、语法分析、语义分析和中间代码生成、优化、目标代码生成此外还包括:表格处理和出错处理词法分析器（扫描器）的任务：从源程序中识别出一个个具有独立含义的最小语法单位。扫描器的输出格式：二元式序列（单词种别，单词符号的属性值）状态转换图：结点代表状态，用圆圈○表示。状态之间用箭弧→连结，弧上的标记指明在射出弧的结点状态下可能出现的输入字符初始状态接受状态正规式和有限自动机正规式和正规集的转换给出正规式，要求写出相应的NFA、DFA给出正规集，要求写出相应的NFA、DFA1、正规式和正规集三种运算：“”读为“或”，“”读为“连接”“*”读为“闭包”转换正规式等价：两个正规式所表示的正规集相同，则称两个正规式等价令Σ是一个有限字母表，则Σ上的正规式及其表示的集合递归定义如下:1.ε和都是Σ上正规式，它们表示的正规集为{ε}和2.若a是Σ上的字符，则a是正规式，它表示的正规集为{a}3.若r和s都是Σ上的正规式，他们表示的正规集记为L(r)和L(s)，则（a）r|s是正规式，表示集合L(r)∪L(s)，（b）rs是正规式，表示集合L(r)L(s)，（c）r*是正规式，表示集合(L(r))*，（d）(r)是正规式，表示的集合仍然是L(r)。（加括弧改变优先级、结合性）有限自动机1、确定的有限自动机M=(S,Σ，δ,S0,F)其中:1.S—有穷状态集2.Σ—输入字母表3.δ—映射函数(也称状态转换函数)S×Σ→Sδ(s,a)=S’,S,S’∈S,a∈Σ4.s0—唯一的初始状态s0∈S5.F—终止状态集ZS2、不确定的有限自动机M=(S,Σ,δ,S0,F)其中:1.S—有限状态集（非终极符集合）；2.Σ—输入字母表（终极符集合）；3.δ—转换函数S({})P(S)，即S*到S的幂集(2S)的一种映射；4.S0—唯一的初始状态集合（非空）S0∈S5.F—终止状态集合FS语法分析器的任务：按照语言的语法构成规则，识别输入的符号串能否构成一个句子语法分析的理论基础上下文无关文法和下推自动机文法：描述语言语法结构的形式规则。乔姆斯基（Chomsky）对文法的分类：0型文法1型文法2型文法3型文法文法G=(VT,VN,S,P)0型文法：，,(VNVT)*,||11型文法：||||，但S可以例外2型文法：A，AVN,(VN∪VT)*3型文法：AaB或Aa，A,BVN,aVT短语文法、上下文有关文法、上下文无关文法、正规文法分析树：表示语言的句子结构，推导的图形表示（1）子树：除叶子结点之外的任意结点连同它的所有子孙结点构成子树。（2）句型：在一棵语法树生长过程中的任何时刻，所有那些叶子结点排列起来就是一个句型。（3）短语：子树的末端符号自左到右连成串，相对于子树树根而言称为短语。简单短语（直接短语）：若短语事某子树根经过1步推导得到的，则称之为该子树根的简单短语。（4）句柄：句型中的最左简单短语。自上而下：消除左递归：消除直接左递归：PPa|消除后：PP’P’P’|消除间接左递归：自上而下语法分析包括：递归下降分析程序和预测分析程序预测分析程序：预测分析表是一矩阵M[A,a]，其中行标A是非终结符，列标a是终结符或串结束符；矩阵元素M[A,a]是存放A的一个侯选式，指出当前栈顶符号为A且面临读入符号为a时应选的候选式；或者存放“出错标志”，指出A不该面临读入符号a。求首符集（First集）假定是文法G的一个符号串，V*，则First()＝{a|a……,aVT}注：1)若,那么First()。2)First()集合是的所有可能推导出的开头终结符或所组成的集合。求随符集（Follow集）假定S是文法G的开始符号，对于G的任何非终结符A，Follow(A)＝{a|S…Aa…,aVT}注：1)若S…A,则规定：#Follow(A)。2)Follow(A)集合是指在所有句型中紧跟A之后的终结符或#所组成的集合。LL(1)文法：若文法G的预测分析表M中不含有多重定义项，则称G为LL(1)文法。自上而下语法分析过程思想：是一个最左归约的过程，从输入串开始，朝着文法的开始符号进行归约，直到达到文法的开始符号为止的过程。LR：自左至右扫描，最右推导的逆过程。LR分析法