写在前面：本文章参考了b占致爱意up主视频讲解，校课件和其他文章，难免有遗漏错误，还望指正。

目录

语法分析阐述

消除左递归（直接左递归）

消除回溯

LL（1）文法

优先关系表

LR（0）

​​​​​​LR（1）

LALR（1）

LR（0）、LR（1）、STR（1）、LALR（1）区别联系

why

        在编写产生式时，如果一个非终结符号可以推导出自身，那么就称为左递归（Left Recursion）。如果语法中存在左递归，（从左开始识别）则可能会导致语法分析器无法处理或者进入死循环等问题。因此，在设计文法时需要将左递归消除。如果采用自顶向下的分析方式，每次使用 A → Aa 的产生式时，都会再次展开 A，导致解析器陷入死循环。对于这种情况，我们需要将左递归消除，使得每个符号串只有一种展开方式。

how

        也就是说产生式1：不以P开头的字符串放在新建P`的前面，产生式2：P后面的字符串放在新建P`的前面，外加空串

why：

A → aBcd | abCd | abcD

在这里，上述三个产生式的前缀 ab 都是相同的，因此在解析符号串 abcd 时，解析器可能会尝试使用多个产生式，最终导致歧义性的出现。

 HOW

 类似于提公共因子

FIRST&FOLLOW阐述

        First 集合表示一个符号串中第一个终结符号的集合。它的作用是帮助我们判断对于一个非终结符号 A，它的产生式右侧的第一个符号能否推导出某个终结符号。这对于构建解析器或编译器很有用，因为它可以帮助我们确定在输入符号串的某个位置上应该使用哪个产生式来推导。

        Follow 集合表示一个符号串中后续终结符号的集合。它的作用是帮助我们判断在一个符号串中某个非终结符号 A 后面跟随的终结符号是什么。这对于处理语法错误、进行LL(1)分析等都非常有用。

字符串的FIRST集

个人理解，从左往右，若一个字符能推出ε就继续分析它右边的字符

字符的FIRST集

对每一文法符号X属于VT∪VN构造FIRST(X）

1. 若X是终结符，则FIRST(X)＝{X}。

2. 若X是非终结符，且有产生式X→a…，则把a加入到FIRST(X)中；若X→ε也是一条产生式，则把ε也加到FIRST(X)中。

3X→Y…是一个产生式且Y属于非终结符，则把FIRST(Y)中的所有非ε元素都加到FIRST(X)中；

4如果X→Y1Y2…Yk是一个产生式（1····k为字符下标），Y1，…，Yi-1都是非终结符，而且，对于任何j，1≤j≤i-1，FIRST(Yj)都含有ε， 则把FIRST(Yi)中的所有非ε元素都加到FIRST(X)中；特别是，若所有的FIRST(Yj)均含有ε，j＝1，2，…，k，则把e加到FIRST(X)中。

FIRST的求解从下往上，看产生式左边

FOLLOW集

 从上往下求解，看产生式左边

如果A->αBβ，first（β）/ε给followB（α，β是字符串），如果first（β）包括ε，那么要把FOLLOW（A）添加到FOLLOW（B），若B后面无字符，FOLLOW（A）添加到FOLLOW（B）（β为ε的一种特殊情况）

这个的话我觉得有点割裂，就是目标符号后面的为空，不为空把first后面符号串的放到followB中，假如能推导出空字那么把前面follow送到后面的

define：LL(1)文法。(自左向右, 最左推导, 向前看1步)

判断是否LL（1）文法

example

 分析过程建LL（1）分析表

具体规则：以对文法G的每个推导式A->α执行步骤为例

（1）对每个a ∈FIRST(α),把A->α加入到M[A,a]

（2）若ε∈FIRST(α),则对任何b∈FOLLOW(A),把A->ε加至M[A,b]中

example

根据预测表分析

FIRSTVT（每个产生式从左往右第一个终结符），LASTVT（每个产生式从右往左看第一个终结符），没有终结符就找非终结符对应的FIRSTVT或LASTVT

 算符优先文法规则

 优先关系图

define

 classification

扩展文法

添加一个新的非终结符S'作为文法的起始符号，使得S' → S （S为原先的文法开始符号）

项目族

 从上往下按顺序求解，每个项目中饭每条产生式中·后面的如果是非终结符就把I0状态中对应的产生式添加到这个项目，否则不作处理

 创建分析表

 LR0本质是自下而上进行规约，从左往右送入栈，当能用产生式规约就规约，比如A->a,出现a就规约成A，但是例如A->a,B->ab，就会造成移进规约冲突，就需要解决，STR（1）就是一种解决办法，根据FOLLOW集合往后面看一步

 STR（1）

首先值得强调的是，不需要消除左递归和提取左公因子，但是要加上扩广文法和拆分合并的产生式

之后就是建立项目族规范集，开始符号的向前搜素符为其FOLLOW集，之后的按照如下规则：

        点后面是非终结符时候，需要把该非终结符对应I0中添加到该状态，运用相同规则重新求向前搜索符号。

        写出分析表，点在最后的状态规约，一个状态经过非终结符GOTO到另外一个状态，一个状态经过终结符ACTION到另外一个状态，如果一个状态没有出路，就根据向前搜索符进行规约，序号为该产生式的初始位置。

 预测分析表

分析 

 LR（0）全写R（规约），LR（1）带向前搜索符判断，STR（1）根据FOLLOW判断

PS：后续有时间再跟上对应习题···