语法分析

自顶向下的分析

最左推导

lm表示的是最左

最右推导

自顶向下的语法分析采用最左推导方式

例子

自顶向下语法分析的通用形式

预测分析

文法转换

两个问题

消除直接左递归

消除直接左递归的一般形式

消除间接左递归

提取左公因子

LL(1)文法

S_文法

例子

非终结符的后继符号集follow

产生式的可选集select

串首终结符集first

比如求x的first集合，那么就是求的x—>字符串，所有字符串首字母构成的集合

LL(1)文法定义

判断一个文法是不是LL(1)的，只需要查看它们的同一非终结符的各个产生式的可选集select集互不相交就可以

first集和follow集的计算

计算文法符号x的first(x)

计算串X1X2……Xn的first集合

计算非终结符A的follow(A)

first集合不能有终结符$,可以有空串ε follow集合可以有终结符$,不可以有空串ε 计算需要反复

算法

例：表达式文法各产生式的select集

select的计算：

1. select(A->空)它的结果是A的follow集合
2. select(A->B)它的结果是A的first集合
3. select(A->a)它的结果就是a

预测分析表

递归的预测分析法

非递归的预测分析法

例

两种方法进行对比

预测分析法实现步骤

预测分析中的错误处理

预测分析中的错误检测

预测分析中的错误恢复

例子：

M表示预测分析表，A表示栈顶的非终结符，a表示当前输入符号。

自底向上的语法分析（考试不考）

例

移入-归约分析的工作过程

移入-归约分析器可采取的4种动作

移入-归约分析中的关键问题

分析完了之后，栈中没有推出起始符S

LR分析法

LR分析法的基本原理

LR分析表的结构

例子：

LR分析器的工作过程

LR分析算法

LR(0)项目

增广文法

文法中的项目

S已经归约出来了，就是(1)就是接收项目——看例子记住就行

例子：LR(0)自动机

LR(0)分析表构造算法——看不懂，不要看

CLOSURE()函数

goto函数

构造LR(0)自动机的状态集

LR(0)分析过程中的冲突

SLR分析

SLR分析法的基本思想

例子：

SLR分析表构造算法

SLR分析中的冲突

LR(1)分析法

LR(1)分析法的提出

规范LR(1)项目

等价LR(1)项目

例子：LR(1)自动机

赋值语句文法的LR(1)分析表

例：LR(1)自动机

LALR分析法

LALR分析的基本思想

例：合并同心项集

合并同心项集时产生归约-归约冲突的例子

这里合并状态6和状态9，因为它们的左部都是相同的 合并之后：

就会发现有归约-归约冲突

合并同心集后，虽然不产生冲动，但是可能会推迟错误的发现

LR分析中的错误处理

语法制导翻译

什么是语法制导翻译