不同层次的错误：
词法：拼写错误（then->them）语法：单词漏掉、顺序错误（花括号不配对）语义：类型错误（声明void f()和调用aa = f()）逻辑：无限循环/递归调用( ==->= )LL，LR，可最快速度发现错误，由于可行前缀特性（viable-prefix property），一旦一个输入前缀不是语言中任何符号串前缀就会发生错误。
错误恢复策略 恐慌模式的恢复短语层次的恢复错误产生式全局纠正 上下文无关文法定义：四元式（Vt，Vn，S，P）：终结符，非终结符，开始符号，产生式。
推导，文法，语言，句子和句型。
**语法树：**推导的图示，但不体现推导的顺序。一颗语法树可以对应多个推导，但是有唯一的最左推导和最右推导。
**二义性文法：**一个句子对应多个语法树，最左推导，最右推导。
证明CFG G生成语言L：（数学归纳法）
G生成的每个符号串都在L中。L中的每个符号串都可由G生成。NFA->CFG：
状态：非终结符初态：开始符号终态：推出空串状态n->α->状态m：An->αAm为什么需要正则表达式：
正则表达式更适合描述标识符，常量，关键字……的结构。CFG更适合描述单词的结构化联系，层次化结构，如括号匹配，if-then-else，……**设计CFG：**设计NFA->NFA to CFG
CFG的修改：
消除二义性：修改文法 stmt -> matched_stmt | open_stmtmatched_stmt -> if expr then matched_stmt else matched_stmt | otheropen_stmt -> if expr then stmt | if expr then matched_stmt else open_stmt 消除左递归（直接，间接）消除空产生式：利用产生式进行代入消除回路：保证每个产生式都加入终结符（开始符号的空产生式除外）提取左公因子上下文无关文法只能描述编程语言的大部分文法，例如检查标识符必须在使用前定义，检查函数的形参与实参的数目是否匹配等是CFG无法描述的语言结构。
自顶向下分析方法：递归实现、表驱动自顶向下分析：从开始符号出发推导出句子，确定输入串的一个最左推导。
递归下降分析（recursive-descent parsing） 选择一个产生式每个非终结符对应一个处理过程每个终结符判断是否与当前输入一致缺点：
不能处理左递归复杂的回溯技术回溯导致重复推导难以报告出错的确切位置效率低消除回溯：
提取左因子或消除左递归预测：向前看n个符号预测分析表的构造：
对所有的终结符a ∈ FIRST（α），将 A->α 加入M[A，a]若ε ∈ FIRST（α），对所有的终结符b ∈ FOLLOW（A），将 A->α 加入M[A，b]所有未定义的表项设置为错误 LL（1），无回溯若文法G的预测分析表M中不含有多重定义项，则称G为LL（1）文法。
L：由左至右扫描输入；L：构造最左推导；1：向前搜索一个输入符号，结合栈中符号，即可确定分析器动作；LL（1）文法一定是无二义性的，二义性文法一定不是LL（1）文法。LL（1）文法一定是没有左递归的。非递归预测分析方法：输入缓冲，栈，预测分析表，输出流。
错误恢复恐慌模式恢复策略：
同步集-FOLLOW集：略过非终结符A，此时的错误为丢失A。跳过输入符号。短语层次错误恢复：
预测分析表空位填入错误处理函数。 实现方法 构造文法；改造文法：消除二义性，消除左递归，消除回溯；求每个变量的FIRST集和FOLLOW集，构造预测分析表；检查是不是LL（1）文法；对于递归的预测分析，为每一个非终结符编写一个过程；对于非递归的预测分析，实现表驱动的预测分析算法。 自底向上分析方法自底向上语法分析，是从输入符号串出发，试图把它归约成识别符号。
从图形上看，自底向上分析过程是以输入符号串作为末端结点符号串，向着根结点方向往上构造语法树，使识别符号正是该语法树的根结点。
规约：某产生式体相匹配的特定子串被替换为该产生式头部的非终结符号。
自底向上分析是一个不断进行直接归约的过程。任何自底向上分析方法的关键是要找出这种句柄。
符号串的“句柄”（Handle）：与某个产生式右部匹配的子串，归约为产生式左部。
一个句型可有多个不同句柄，非多义性文法的最右句型有唯一句柄。
移入－归约语法分析技术：
定位句柄确定产生式一般实现方法——栈： 将输入符号“移进”栈，直至在栈顶形成一个句柄；将句柄“归约”为相应的非终结符；不断重复，直至栈中只剩开始符号，输入缓冲区为空——接受输入串；错误处理。基本操作：移进（shift），规约（reduce），接受（accept），错误（error）。
LR分析方法LR分析方法：当前最广义的无回溯的“移进- 归约”方法。
LR分析方法：“自左到右扫描和最左归约（最右推导）”的自底向上的分析方法。
从逻辑上说，一个LR分析器包括两部分：一个总控程序和一张分析表。
LR分析表：（核心）
分析动作表： sj：移进动作，下一个状态sj进栈rj：按第j个产生式进行规约acc：接受error：出错 状态转换表：.
最简单分析表LR(0)：局限性大，但它是建立其它分析表的基础。简单分析表SLR：比较容易实现，SLR分析表的功能比LR(0)稍强些 。**LR(k)**分析表：分析能力最强，但实现代价高。主要讨论LR(1)。LALR分析表：称为向前看LR分析表，功能介于SLR(1)和LR(1)之间，适用于大多数程序设计语言的结构，并且可以比较有效地实现。LR（0）分析表的构造
可行前缀规范句型（右句型）的一个前缀，如果它不含句柄后任何符号，则称它是该规范句型的一个可行前缀。也就是说在可行前缀右边增添一些终结符号之后，就可以成为规范句型。
在LR分析过程中的任何时候，栈里的文法符号X1X2…Xm应该构成可行前缀，把输入串的剩余部分配上之后即成为规范句型（如果整个输入串确实构成一个句子的话）。
LR（0）项目：移进项目，待约项目，规约项目。构造识别可行前缀的有穷自动机 将一般文法G改写成增光文法G‘，即增加一个产生式：S’->S。写出增广文法的全部项目。构造DFA： 求出DFA初态I0的状态集。由初态I0构造其他状态（实际上，可以直接画图画出DFA）。 LR（0）项目集规范族：即为构成识别一个文法的可行前缀的DFA的项目集(状态)的全体。LR（0）文法: 冲突项目：如果一个项目集中既有移进项目又含有归约项目，或一个项目集中有两个以上不同归约项目，则称这些项目是冲突项目。LR（0）文法：如果一个文法的项目规范族的每个项目集不存在任何冲突项目，则称该文法为LR(0)文法。 LR（0）分析表的构造：si，ri，acc。 SLR对于冲突项目，如果移进项目的终结符集合，规约项目的FOLLOW集不相交，则可根据当前符号进行区分，这种解决“移进-规约”冲突的方法称作SLR方法。
SLR（1）文法：对于给定的文法Ｇ，若按上述方法构造的分析表不含多重定义的元素，则称文法Ｇ是SLR(1)文法。这里SLR(1)中的S代表Simple(简单)的意思，而数字１代表查看句柄外一个输入符号，即在分析过程中至多只需要向前查看一个符号。
规范LRSLR(1)也存在不足，即如果冲突项目的非终结符FOLLOW集与有关集合相交时，就不能用SLR(1)方法解决。
在归约时，不但要向前看一个符号，而且还要看栈中符号串情况，才可以知道用某种产生式归约。
若分析表中不存在多重定义的元素，则称此分析表为规范LR（1）分析表。使用这种分析表的分析器叫做规范LR分析器。具有规范LR（1）分析表的文法称为一个LR（1）文法。
任何二义性文法都不是LR（k）文法。
LALR（Look Ahead LR）LALR分析法与SLR相类似，但功能比SLR（1）强，比LR（1）弱，LALR分析表比ＬＲ表要小得多。对于同一文法，LALR分析表与SLR分析表具有相同数目的状态(SLR是不区分向前搜索符的)。
合并同心集
如果除去搜索符以外，两个LR（1）项目集是相同的，则称为同心集。
同心集合并后不会存在“移进—归约”冲突，但存在“归约—归约”冲突，因为移进和归约不同心，所以不会出现“移进—归约”冲突。