自顶向下：递归下降法、LL(1)分析法
自顶向下分析过程的基本特点： ①如果文法是左递归的，则自顶向下分析会陷入无限循环；（消除左递归） ②每步推到的试探会形成大量的回溯；（消除回溯LL1文法） ③分析失败难于指出错误的具体情况（错误位置和错误类型）；（LL1文法）
方法：将A→Aα|β形式的产生式改写为A→βA’和A’→αA’|ε的形式
例题：E->EAT|T 消除左递归：E->TE’,E’->ATE’|ε
对于一个已化简且不含左递归的文法G，当进行自顶向下的语法分析时，不会出现回溯的充要条件是，对G中形如A→γ1|γ2|…|γm的产生式，若其候选式γi 和γj 满足：(其中1≤i,j≤m；i≠j) (1) FIRST(γi)∩FIRST(γj)=Φ (2) 若ε∈FIRST(γj)，则 FIRST(γi)∩FOLLOW(A)=Φ 则称G为LL(1)文法。
FIRST(γ)：γ可以退出的开头的终结符号（或ε）（1）若x∈VT，则FIRST(x)={x}； （2）若X∈VN，且G中有形如 X->aα (a∈VT)或（和）X->ε 的产生式， 则把 a 或（和）ε 添加到FIRST(X)中； （3）设G中有形如 X->Y1Y2…Yi…Yk 的产生式， 若Y1∈VN，则将FIRST(Y1)中一切非 ε 符号加入到FIRST(X)中； 若Y1、Y2、… 、Yi (1≤i≤k-1)均为非终结符，且其FIRST集中均有ε , 则将FIRST(Y1)、FIRST(Y2) 、… 、FIRST(Yi+1)中一切非 ε 终结 符加入FIRST(X)中； 若Y1、Y2、… 、Yk的FIRST集中均有ε，则将ε加入FIRST(X)中。
FOLLOW(A)：在所有句型中可能直接跟在A之后的终结符号（1）对文法的开始符S，#∈FOLLOW(S)； （2）若G中有形如B->αAβ的产生式， 则将FIRST(β)中一切非ε符号加入FOLLOW(A)； （3）若G中有形如B->αAβ的产生式，并且ε∈FIRST(β)， 或者有形如B->αA的产生式， 则将FOLLOW(B)中一切符号加入FOLLOW(A)。 图一
思路：为文法的每一非终结符号，依相应的候选式结构，编写一子程序识别其表示的语法范畴。
例：
若一文法为LL（1）文法，进行最左推导时，当一非终结符A有多个候选式时，只需检查当前正扫视的输入符号α属于那个候选式的首符集;或若某候选式yi的首字符集含e，且当前输入符号α属于FOLLOW (A)，便可准确的选取候选式。这种分析方法称为预测分析法。 若一文法为LL（1）文法，可以为之构造一无回溯的语法分析程序，称为LL（1）分析程序或LL（1)分析器。
例如：使用预测分析法推导图一文法：
①构造First和Follow表 ②构造此文法对应的预测分析表 ③分析过程
分析开始，将栈底符号#和文法开始符S入栈，各指示器置初值： 分析中，设某一时刻的分析格局为： 根据栈顶Xm的不同情况，分别作如下处理： a）Xm->VT（Xm是终结符号） ，若Xm=ai，则Xm出栈，输入串指针移到下一位置；若Xm ≠ ai，则进行语法错误处理。 b） Xm->VN （Xm是非终结符号），以(Xm，ai)查分析表： 若表元素为ERROR转出错处理；若表元素为Xm->Y1Y2…Yk，则Xm退栈，Y1Y2…Yk反向入栈。 c）Xm=ai=#，分析成功。
假若输入的字符串为“i+i*i”
参考分析表（后面简述表），判断余留输入串的第一个，首先是i，那么通过表知道分析栈中的E通过E->TE’才能得到i，所以E出栈，E’T入栈，继续分析通过表发现T通过T->FT’才能得到i，那么T出栈，T’F入栈，通过表知F通过F->i可以直接得到i，所以F出栈，到此余留输入串第一个字符识别完毕，开始下一个字符的识别
定义4.2：若文法中不含有两个非终结符相邻的产生式，则称为算符文法。（广义运算符: 文法的终结符号 广义运算对象: 非终结符） 定义4.6：对一算符文法G，若任何一对终结符号间至多只有一种优先关系， 则称G为算符优先文法。
步骤： ①构造算符优先矩阵 算符优先矩阵的构造方法 根据以下三种优先关系的定义，找全优先关系，构造优先关系矩阵。 定义4.3 a=b ：存在产生式 U→…ab… 或 U→…aAb… 时。 定义4.4 a<b ：存在产生式 U→…aA… 且 A 能推导出以 b 为第一个终结符号的符号串。 定义4.5 a>b ：存在产生式 U →…Ab… 且 A 能推导出以 a 为最后一个终结符号的符号串。 注意是第一个/最后一个 终结符号
例如：
（1）首先看“=”有哪些，因为相等的两个终结符号满足形式“U→…aAb…”，所以找“aAb”形式的发现只有"(E)"，所以“(” = “)” （2）其次找“<”的有哪些，因为若终结符号a<b满足形式“U→…aA…且A-+->b”，所以先找“aA”形式的，再找A的FirstVT（A）集合（第一个终结符号,不是LL1中的first集）,则a<FirstVT（A） FirstVT（T） = {“(”,“i”,“”}，FirstVT（F）= {“(”，“i”},FirstVT（E）= {“+”,“(”,“i”,“”} （3）找“>” （4）#<firstVT(E) #>lastVT(E)
②规约过程
1)寻找最左素短语：w = #N1a1N2a2…NnanNn+1#（ai VT , Ni VN∪{}）从左到右扫描 w，找到第一个ai > ai+1，再回扫找到第一个aj-1 < aj此时 Nj aj Nj+1 aj+1 … Ni ai Ni+1 就是应被归约的最左素短语。 2)归约策略：在文法中找形如 A Uj aj Uj+1 aj+1 …Ui ai Ui+1 的产生式，其中 Ui 与 Ni 不一定相同，但每个 ai 必须相同， 若存在这样的产生式，则按此产生式归约；否则报错。
LR（K）文法的特性： 每一LR(K)文法都是无二义性文法 某一由LR(K)文法产生的语言也可由某一LR(1)文法产生
LR分析器的逻辑结构及工作原理：
①分析栈：其中状态和符号顺序一致（换言之数量也一致） ②分析表：分析表由不同的LR（k）文法特制 action表： 其中行名S1,S2…Sn为分析器的各个状态，列名a1,a2…al是全部终结符号和句子界符（句子界符即#） goto表: 其中行名S1,S2…Sn为分析器的各个状态，列名X1,X2…Xp是全部文法符号（终结符号、非终结符号等，所以p>l） 两个表合并: 其中行名S1,S2…Sn为分析器的各个状态，列名a1,a2…al是全部终结符号和句子界符（句子界符即#）列名Xl,Xl+1…Xp是非终结符号
③输入符号串 ④主程序
以上算法主要是（1）（2），其中（1）是不能规约的情况，直接将分析的输入符号ai推入栈，并且将新状态同时入栈 （2）其实就是已经入栈的有一部分已经可以规约了，按照指定的产生式进行规约并出栈，同时选择下一状态
①规范句型的活前缀：指规范句型中不含句柄之右的符号的前缀。（如A→xBz的活前缀是ε和x） ② LR(0)项目：指右部某位置上标有圆点的产生式。 LR(0)项目可分为四类： 归约项目(A→ a.) 因为A的产生式全部在“.”前面（即都分析完毕了），所以可以规约 接受项目(S→ a.)因为从开始符已经将终结符号推出完了，所以归约成功 移进项目(A→ a.xβ 其中x为终结符)因为后面还有终结符，所以不能规约，要继续移进 待约项目(A→ a.Xβ其中X为非终结符)
产生式A→xyz对应有四个项目：
A→·xyz 活前缀不含句柄符号（意味着还没有识别出来A产生式右部的任何的一个符号） A→x·yz 活前缀含部分句柄符号（已经识别出来一个符号x） A→xy·z A→xyz· 活前缀含句柄所有符号 特别的：A→ε产生式的项目为A→.
冲突种类：移进规约项目、归约归约冲突 I8同时出现了移进项目和规约项目（移进规约冲突），进而其LR（0）分析表出现以下冲突
SLR（1）的DFA构造与LR（0）一模一样，接下来重点讨论其分析表的构造
消除冲突： 如果集合{a1, a2 ……, am},FOLLOW(B1), ………… FOLLOW(Bn)两两不相交，则隐含在I中的动作冲突可通过检查现行输入符号a属于上述n+1个集合中的哪一个而得到解决： 若a是某个ai ，i=1,2,………,m，则移进； 若a ∈ FOLLOW（Bi），i=1,2,……………,n，则用产生式Bi ->α归约； 此外报错
SLR(1)分析表构造步骤（标黄字段是与LR（0）构表过程的不同之处） (1)将文法拓广 (2)构造识别文法全部规范句型活前缀的DFA (3)求非终结符号Follow( )集合 (4)对每个项目集按以下四条规则填表： ① 若项目集Ii中有S’->S ·置[i,#]=acc ② 若项目集Ii中有A-> α· 的项目， A-> α 为第j个产生式，则将Follow(A)元素所在列置归约动作为rj ③ 若项目集Ii中形如A-> α·xβ的项目，若Go(Ii,x)=Ij,x为终结符，置[i,x]为Sj，x为非终结符，置[i,x]为j ④ 分析表中无定义的元素均表示”出错”
方法：将Follow集合按属性拆分为最小单位 ①重新定义项目：使每个项目后面附带一个终结符a [A->α·β,a ]。这样的项目称为LR（1）项目，a称为向前搜索符号。a的求法如下
【注意：向前搜索符号仅对归约项目有意义，对移进/待约项目无作用】 向前搜索符号解法： 对S’－>.S，向前搜索符号为＃； 对**[A->α·Bβ,a ]** ∈Closure（I）， [B-> ·η,first(βa)] ∈ Closure（I） 【注意“，”只是分隔符，用来分开搜索符号，搜索符号为βa的first集】
②识别LR（1）文法全部活前缀的DFA构造方法
对LR（1）项目集的Closure（I）定义如下： •I中任何LR（1）项目都属于Closure（I）； •若项目[A->α·Bβ,a ]属于Closure（I），B->η是一产生式，则 对FIRST（βα）中每个终结符b，若[B->· η,b ]不在Closure（I）中则加入之； •重复2直到Closure（I）不再增大为止。
③LR(1)分析表的构造（标黄为不同之处） 若项目[S’->S·,#] ∈Ii，则置ACTION[i,#]=acc 若归约项目[A->α ·,a ] ∈Ii,A->α为文法第j个产生式，则置ACTION[i,a] =rj 对每个项目集Ii中形如[A->α ·xβ,a ]的项目，若GO（Ii,x） =Ij，且x为一终结符b时，置ACTION[i,b]=Sj，若x为一非终结符，则置GOTO[I,x]=j 其余error 对给定文法用上述方法构造的LR（1）分析表，不含多重定义元素，称G为LR（1）文法。 【注意：向前搜索符号仅对归约项目有意义，对移进/待约项目无作 用】
