编译原理复习四

这是我参与更文挑战的第23天，活动详情查看： 更文挑战

第四章：语法分析

4.1、语法分析分类

• 自顶向下：$LL(1)$分析
• 自底向上：简单优先分析、算符优先分析、$LR$分析

4.2、确定的自顶向下分析思想（不确定不考虑）

• **First集：**产生式右部第一个终结符集

• **Follow集：**非终结符右边紧跟着的终结符集

• Select集：

  1. A->$\alpha$，($A \in V_N$，$\alpha \in V^*$) $\alpha$不能推出空字符，则：$Select(A->\alpha)=First(\alpha)$
  2. 如果$\alpha$能够推出空字符，则：$Select(A->\alpha)=(First(\alpha)-\epsilon)) \cup Follow(A)$

4.3、判断是否为$LL(1)$文法的充要条件

任何两个产生式的Select集的交集为空

4.4、$LL(1)$的含义

• 第1个L表示自顶向下分析是从左到右扫描输入串
• 第2个L表示分析过程中将用最左推导
• 1表示只需向右看一个符号便可决定如何推导（即：选择哪个产生式进行推导）

类似的还有$LL(k)$文法

4.5、**$LL(1)$文法的判别

1. 求出所有能推出$\epsilon$ 的非终结符（直到所有的非终结符都能判断出是否能推出$\epsilon$ 时结束）
2. 计算First集合
3. 计算Follow集合
4. 计算Select集合

例题：

4.6、$LL(1)$文法的充要条件

• 无左公共因子
• 无左递归
• 无$\epsilon$产生式

非$LL(1)$文法

• 含有左递归
• 含左公共因子

不一定所有的语言都有$LL(1)$文法，左递归和左公共因子不能全消除（考判断题）

也就是不是所有的非$LL(1)$文法可以转换为$LL(1)$文法

4.7、含有左递归的文法绝对不是$LL(1)$文法（判断题）

4.8、左递归

• 直接左递归：$A->A\beta$
• 间接左递归：$A->B\beta, B->A\alpha$

4.9、消除左递归

消除直接左递归：

$S->Sa$,$S->b$

$S->bS’,S’->aS’|\epsilon$

消除间接左递归：

例如：

1. A->aB
2. A->Bb
3. B->Ac
4. B->d

间接左递归–>直接左递归：

1. B->aBc
2. B->Bbc
3. B->d

消除直接左递归：

1. B->dB’
2. B->aBcB’
3. B’->bcB’
4. B’->$\epsilon$

4.10、**表驱动$LL(1)$分析程序

解题步骤：

1. 判断文法是否为$LL(1)$文法
2. 构造预测分析表

组成部分：

1. 预测分析程序
2. 先进后出栈
3. 预测分析表