笔记分两部分： ——第一部分是一些小知识点 ——第二部分对应了几个大题的解题模板

这部分没什么体系，比较零碎，只记录了我感觉比较重要的部分知识点，大部分是一些容易混淆知识点的辨析

例如：G[T]: T → TF|F F → F↑P|P P → (T)|i 求给定句型：TP↑(T*F)的短语，直接短语，句柄，素短语，最左素短语

步骤： 1.根据产生式做推导 2.根据推导画出语法树 3.根据语法树和以上规则得答案

—短语 5 个 P，T* F，(T* F)，P↑(T* F)，TP↑(T F) —直接短语 2 个 P，T* F —句柄 P —素短语 T* F —最左素短语 T* F

关于：LR(0)、SLR、LR、LALR —区别： —判断方法：

翻译程序、编译程序、解释程序 翻译程序：将用某种语言编写的程序转换成另一种语言形式的程序的程序 编译程序：用高级语言编写的源程序转换（加工）成与之等价的另一种用低级语言编写的目标程序的翻译程序。 解释程序：解释程序是高级语言翻译程序的一种，他将输入的源程序作为输入，解释一句后就提交给计算机执行一句，源程序命令被逐个直接解释执行

算符文法与算符优先文法: 算符文法：任一产生式的右部都不含两个连续非终结符的文法 算符优先文法：是不含空字符且对任一对终结符都有确定的>m），则直接将此非终结符m加入FIRST(A)集若由非终结符B开头（例如A ->BC），则再判断此非终结符B能推出空字符 ε – 若不能：将此终结符B的FIRST（B）集合整体加入FIRST(A)集 – 若能：则将B的FIRST（B）集合整体除去 ε 加入FIRST(A)集，然后再次向处理B一样处理B之后的符号(这里是C)（相当于A吸收B中的空字符到达下一个符号）。 求FOLLOW 求非终结符A的FOLLOW集：检查每一个可以推出A的产生式若A为文法的开始符号：将 # 加入FOLLOW（A）若A为当前产生式的最后一个字符（例如B ->CA）：将FOLLOW（B）加入FOLLOW（A）若A后面还有其它字符例如（例如B->AD）： – 如果D不能推出空字符 ε：将FIRST（D）加入FOLLOW（A） – 如果D能够推出空字符 ε：将FIRST（D）减去 ε 加入FOLLOW（A）并且将FOLLOW（B）加入FOLLOW（A） 求SELECT SELECT ( A→α) =FIRST ( α ),其中α !⇒ ε 若α ⇒ε ，则SELECT ( A→α) = (FIRST（α ） － {ε ) ∪FOLLOW(A)注意α在这里的是一个产生式，而不是一个符号 ３.判断是否是LL（１） 对每个非终结符A的两个不同产生式，A→α ，A→β ，满足SELECTC（A→α ）∩SELECT（A→β ）= ϕ其中α、β不能同时⇒ ε则称该文法是LL（１）的 ４.构造预测分析表

预测分析表M 如下矩阵形式：矩阵M •行标题用文法的非终结符表示。 •列标题用文法的终结符号和#表示。 •矩阵元素M[A, a]的内容是产生式A→α \alphaα（或→α \alphaα）表明当对A进行推导，面临输入符号a时，应采用候选α \alphaα进行推导。 出错处理标志（即表中空白项）表明A不该面临输入符号a。

加个S’的规则就行。

S’->E

E->aA | bB

A->cA | d

B->cB | d

给每个规则加一个点以后然后挪位置，挪一个位置就得到一个项目

1.S’->·E 2.S’->E· 3.E->·aA 4.E->a·A 5.E->aA· 6.A->·cA 7.A->c·A 8.A->cA· 9.A->·d

10.A->d· 11.E->·bB 12.E->b·B 13.E->bB· 14.B->·cB 15.B->c·B 16.B->cB· 17.B->·d 18.B->d·

把有S’的项目而且点在最左边的项目作为状态I0的核，放在开头。

S’->·E E->·aA E->·bB

然后看这个点后面的非终结符，是个E，接下来就去项目中找左部是E的而且点在最左边开头位置的项目，列在核的下面，这就是状态I0了，你可以画个框框然后标记一下。 接下来还是先看核里面点后的这个非终结符E，输入E（你可以理解为在箭弧上标了个E），把点向后移一位，得到S’->E·，这其实是得到了一个新的状态的核。当然另外两个也一样，输入点后面的符号，比如输入a得到E->a·A为核的新状态，输入b得到E->b·B为核的新状态。得到新状态的核了，就顺便把这个状态剩下的项目也列出来吧，就是看核的点后面的非终结符，找以这个非终结符为左部的点在最左边的项目。当然要是点后面没有东西就不用找了，新的状态记得标号哦。 是重复上面的工作，从每一个新状态出发，逐个输入每个项目点后面的符号，就是后移一位，又分别作为新的状态的核然后根据核找下面的同状态里的项目。找到找不动为止

把文法的所有产生式的项目都列出来，并使每个项目都作为NFA的一个状态。

1、找项目集规范族有S’->A·这种形状的那个状态Ik，就是第k个状态，则把分析表第k行的#列标上acc

2、按顺序（我一般是按状态序号顺序）分析状态的项目和GOTO函数，主要就是看每个项目的点后面的符号。

（1）要是是个终结符，看输入这个终结符后去的哪个状态，比如当前是状态I0，对于第二个项目E->·aA，输入a以后去了状态I2，那就在分析表中第0行的a列写上S2，意思就是状态Ik输入Vt后去了Ij状态。

（2）要是是个非终结符，这个更好理解，比如从状态Ik输入这个非终结符以后去了状态Ij，那就在GOTO表的第k行第Vn列写j。

3、你会发现有的项目的点是在最后，这就是分析表里面那些小r的来历了。先看这个项目所在的状态，再看点前面的规则是文法里面的第几个规则，比如说状态I10的A->d·里面的A->d就是文法的第4条规则，那就在分析表的第10行所有的终结符列包括#列写上r4，就是ACTION列的一行写满。即状态Ik的项目来自于文法的第j条规则，则分析表的第k行都是rj。

规则： 若B->b… 或 B->Cb… 则b加入FIRSTVT(B) 若B->A… 则FIRSTVT(A) 加入FIRSTVT(B)

规则： 若B=>…a 或 B=>…aC 则a加入LASTVT(B) 若B->…A 则LASTVT(A) 加入LASTVT(B)

算符优先分析表M 如下矩阵形式： •行标题用文法的终结符和#表示。 •列标题用文法的终结符和#表示。 •表中的元素为>…ab…或P->…aQb…的那么就直接填写=，注意顺序是左边等于右边，对应表是横着的等于竖着的，这里是（=），#号直接填写等于就好了。

然后是>和QaR这种有用的文法，终结符和非终结符在一起的那种。找到后根据以下两条： 1.a小于FIRSTVT(R）中元素，横着写 2.LASTVT（Q）中元素大于a，竖着写

判断标准：文法任一产生式右部都不含两个相继的非终结符为算符文法。 方法：利用上述得到的分析表，若两个终结符之间至多满足=，，三种关系之一（一个表格内部只填写一个符号），可以判断该文法为算符优先文法，反之不是。