ch4.2

自顶向下分析 Top-Down Parsing

自顶向下解析可以看作是以前序方式构建解析树的问题，即采用最左推导方式，总是选择每个句型的最左非终结符进行替换。
左递归是指一个语法规则直接或间接地在最左边调用自己。左递归可能导致无限循环，例如 ：

1
2
3
4
5
6
7
8
9
10
11

bool A() {
    temp = cursor;
    cursor = temp;
    if (A()) { 
        cursor++;
        if (*cursor == 'b') return true;
    }
    cursor = temp;
    if (*cursor == 'a') return true;
    return false;
}

消除左递归（重要）

消除直接左递归
前提：该文法不含回路和

对于 ，可以转换为， （助记： 可以写成 ）另外例子：

左因子提取法（新PPT已删除）

如果某个非终结符的多个产生式右部有相同的前缀，那么递归下降解析器在遇到这个前缀时，会不知道该选择哪条产生式，可能需要回溯（回头检查之前的选择是否正确）。左因子提取的思路是提取公共前缀，重新组织产生式，使解析器不需要回溯即可解析。

预测分析 Predictive Parsing

预测分析是一种递归下降解析的方法，它不需要回溯。

LL(1):

• L: 从左到右扫描

• L: 进行最左推导

• 1: 每一步只看一个符号

使用条件：无左递归，无歧义为了构造和使用 LL(1) Parsing Table，我们需要首先计算 FIRST 和 FOLLOW 集合。

FIRST() （重要）

1. FIRST(α)表示一个符号串可能以α终结符开始

2. 如果 是终结符，则

3. 如果 是一个产生式，则

4. 

5. 终结符的FIRST()是它自己

示例：

FOLLOW()

1. FOLLOW(𝛼) 是 可能出现在 𝛼 右侧的终结符集合。

2. $ 属于 FOLLOW(S)，其中 $ 是字符串的结束标记，S 是开始符号

3. 如果有产生式 ，那么 FIRST(β) 去掉 （空串）加到 FOLLOW(B) 中。
   

4. 如果有产生式 或 （且 FIRST(β) 含有 ），那么 FOLLOW(A) 也要加到 FOLLOW(B) 中。
   

5. 重复计算以上规则，直到 FOLLOW 集合不再发生变化

示例：

LL(1) Parsing Table

构建步骤：

• step1：检查是否满足LL(1)基本条件

• step2：构建FIRST和FOLLOW

• step3：对于每个产生式

  • 计算 ，对于 中的每个终结符a，在分析表中 M[A,a] 填入 。
  • 如果 包含 （空串），则计算 ，并对于 中的每个终结符，在分析表中填入 。
  • 如果 包含 ，且 中包含 $（输入结束符），则在分析表中针对 $ 填入 。

M[A, a] 表示当当前栈顶是非终结符 A，且输入符号是 a 时，应该选择哪个产生式 A → α 进行推导。

示例：对于以下文法

1
2
3
4
5

E -> TE'
E' -> +TE' | ε                
T -> FT'
T' -> *FT' | ε
F -> id | (E)

构建 FIRST 和 FOLLOW：

构建 Parsing Table：

Bottom-up Parsing

RHS

补充

• 句型（sentential form）：如果S =>* α，那么 α 就是文法的句型，可能既包含非终结符号，又包含终结符号；可以是空串

• 句柄：和某个产生式体匹配的子串（非正式）

• 最右句型γ的一个句柄

  • 满足下述条件的产生式A→β及串β在γ中出现的位置
  • 条件：将这个位置上的β替换为A之后得到的串是γ的某个最右推导序列中出现在位于γ之前的最右句型

• 通俗地说句柄是最右推导的反向过程中被规约的那些部分

句柄的作用：对句柄的规约，代表了相应的最右推导中的一个反向步骤

例1：对于上下文无关文法：S→SS+|SS*|a，指出下列最右句型的句柄:

SSS+a*+
SS+a*a+
aaa*a++

答案：

句柄: SS+
句柄: SS+
句柄: a

例2：

例3：

• ← Previous Post
• Next Post →