2021-10-17 《编译原理》学习笔记：第6周

3.8.4 最长匹配

​ 尽可能地向前匹配。

​ 对于以下转移表而言：

ifififii

• 走到第一个接受状态后，希望满足最长匹配，尝试继续向前走
• 继续走可能会失败，所以维持一个栈，栈底是从最近的接受状态开始，上面是尝试步骤的状态
• 一旦失败，弹栈回滚到最近的接受状态上

3.8.5 跳转表

​ 顾名思义，跳转表使用跳转的方法（goto）进行跳转，不需要数据结构来辅助实现跳转：

nextToken() {
    state = 0;
    stack = [];
    goto q0;
}

q0:
c = getchar();
if (state is ACCEPT) clear(stack);
push(state);
if (c == 'a') goto q1;

q1:
c = getchar();
if (state is ACCEPT) clear(stack);
push(state);
if (c == 'b' || c == 'c') goto q1;

• 不需要数据结构实现跳转，而是通过内部的代码实现跳转
• 将每一个状态变成一段代码，将状态间的转移变成显式跳转
• 每段代码负责当前状态可识别字符和所作的转换

跳转表转移表不需要维护一个很大的数组，节约内存占内存每次仅仅执行一小段代码加载代码慢效率高

​ Flex 使用的是跳转表。

第四章 语法分析 4.1 语法分析器介绍 4.1.1 语法分析器的任务

1. 语法分析器的输入是记号流，输出是抽象语法树中间表示

2. 研究给定记号流输入是否是合法的

3. 判别是否合法需要一个标准，相当于隐含的第二种输入：语言的语法规则

4. 除了抽象语法树之外还有一个隐含的输出，就是是否合法，也就是 YES / NO

4.1.2 例子 4.2 上下文无关文法（CFG）

​ 自然语言是非常复杂的，只靠数学规则来描述表达能力还不够。

​ 为此我们引入上下文无关文法，它只负责从句型推导出句子，而不考虑上下文的正确性。

4.2.1 定义

​ 上下文无关文法 G 是一个四元组： G = ( T ,   N ,   P ,   S ) G=(T,\ N,\ P,\ S) G=(T, N, P, S)

• T：终结符集合

• N：非终结符集合

• P：一组产生式规则

  形式： X → β 1 β 2 … β n X\rightarrow\beta_{1}\beta_{2}\dots\beta_{n} X→β1​β2​…βn​，其中 X ∈ N ,   β i ∈ ( T ∪ N ) X\in N,\ \beta_{i}\in(T\cup N) X∈N, βi​∈(T∪N)

• S：唯一开始符， S ∈ N S\in N S∈N

4.2.2 举例

（1）例 1

• N = { S, N, V }
• T = { s, t, g, w, e, d }
• 产生式规则集合：7 个
• 开始符号：S

（2）例 2

• N = { E }
• T = { num, id, +, * }
• 产生式规则集合：4 个
• 开始符号：E

4.2.3 规则

​ 一般而言，我们使用：

• 大写表示非终结符
• 小写表示终结符
• 第 1 个非终结符（大写）认定为开始符号 E

​ 经常用的 BNF（Backus-Naur Form）范式：

• 非终结符要放到一对尖括号中：
• 所有的终结符要加上下划线：id
• 推导出：使用 ::=

4.2.4 推导

给定文法 G，从 G 的开始符号 S 开始，用产生式的右部替换左侧的非终结符。此过程不断重复，直到不出现非终结符为止。过程中的串称为句型，最终的串称为句子 / 语句。

（1）最左推导

​ 每次总是选择最左侧的符号进行替换。 S ⇒ N V N ⇒ s   V N ⇒ s   d   N ⇒ s   d   s \begin{aligned} S &\Rightarrow NVN\\ &\Rightarrow s\ VN\\ &\Rightarrow s\ d\ N\\ &\Rightarrow s\ d\ s \end{aligned} S​⇒NVN⇒s VN⇒s d N⇒s d s​ （2）最右推导

​ 每次总是选择最右侧的符号进行替换。

4.3 分析树与二义性 4.3.1 分析树

​ 将推导画成一棵树，这棵树的结构与推导的顺序无关。该树的特点有：

• 每个内部结点代表非终结符
• 每个叶子结点代表终结符
• 每一步推导代表如何从双亲结点生成它的直接孩子结点

4.3.2 二义性文法

​ 给定文法 G，如果存在句子 s，使得它有两个不同的分析树，那么 G 为二义性文法。

​ 对于二义性文法，程序的运行结果将不会每次都一致，因此我们需要进行文法的重写。

（1）二义性文法的示例

​ 采用最左推导和最右推导，得到两棵不同的分析树：

（2）重写二义性文法

​ 左递归文法：

​ 重写后，采用不同的推导顺序，语法分析树将保持一致：

​ 此分析树可保证加法的左结合。

​ 同理，右递归文法可以写成如下（运算为右结合）： E → T + E ∣ T T → F ∗ T ∣ F F → n u m ∣ i d \begin{array}{c r l} E&\rightarrow &T+E\\ &|&T\\ \\ T&\rightarrow &F*T\\ &|&F\\ \\ F&\rightarrow &num\\ &|&id \end{array} ETF​→∣→∣→∣​T+ETF∗TFnumid​

4.4 自顶向下分析 4.4.1 思想介绍

​ 语法分析：给定文法 G 和句子 s，回答 s 是否能够从 G 推导出来？

​ 基本算法思想：从 G 的开始符号出发，随意推导出某个句子 t，比较 t 和 s ；

• 若 t == s，则回答“是”

• 若 t != s，则需要回溯，重新开始

4.4.2 算法步骤

1. 从根开始构建语法树，并使树向叶子的方向增长；

2. 在每一步

   • 树的下边缘选择一个表示某个非终结符的结点
   • 用一个子树来扩展该结点
   • 子树表示了重写该非终结符时所用产生式的右侧部分

4.4.3 代码

tokens[];                                    // 词法分析器返回的记号数组
int i = 0;                                   // 指向数组下一个要匹配的记号位置
stack st = [S];                              // S 为开始符号
while (st != []) {
    if (st[top] is a terminal t)
        if (t == tokens[i++])
            pop();
        else backtrack();                    // 回溯：栈回滚、tokens 数组下标回滚
    else if (st[top] is a nonterminal T) {
        pop();
        push(the next right hand side of T); // 逆序压栈：右侧的先压栈
    }
}

4.4.4 算法讨论

​ 该算法效率较低，主要在于其回溯带来的时间消耗。

​ 因此我们需要线性时间的算法：

• 递归下降分析算法
• LL(1) 分析算法

4.4.5 使用前看符号

​ 选择产生式右侧替换 N 时，同时考虑下一个输入符号，称为前看符号。

4.5 递归下降分析算法 4.5.1 算法基本思想

1. 每个非终结符构造一个分析函数

   • 实际不一定为每个非终结符构造分析函数

2. 用前看符号指导产生式规则的选择

4.5.2 示例

​ 对以下的推导：

​ 采用的算法为：

parse_S() {                    // 分析函数
    parse_N();
    parse_V();
    parse_N();
}

parse_N() {                    // 分析函数
    token = tokens[i++];       // 根据前看符号
    switch(token) {
        case 's': case 't': case 'g': case 'w':
            return true;
        default:
            error("...");
    }
}

parse_V() {                    // 分析函数
    token = tokens[i++];
    switch(token) {
        case 'e': case 'd': 
            return true;
        default:
            error("...");
    }
}

4.5.3 算术表达式的递归下降分析

​ 利用该文法的特殊性，等价于： E :   T + T + ⋯ + T T :   F ∗ F ∗ ⋯ ∗ F \begin{aligned} E:\ &T+T+\dots+T\\ T:\ &F*F*\dots*F \end{aligned} E: T: ​T+T+⋯+TF∗F∗⋯∗F​ ​ 因此可以采用以下的算法：

parse_E() {
    parse_T();
    token = tokens[i++];
    while (token == '+') {
        parse_T();
        token = tokens[i++];
    }
}

parse_T() {
    parse_F();
    token = tokens[i++];
    while (token == '*') {
        parse_F();
        token = tokens[i++];
    }
}

parse_F() {
    token = tokens[i++];
    switch(token) {
        case '0': case '1': case '2': case '3': case '4':
        case '5': case '6': case '7': case '8': case '9':
            return true;
        default:
            error("...");
    }
}

4.5.4 思考

​ 给定如下的文法 G： A → a   B ∣ a B → b ∣ c \begin{array}{c r l} A&\rightarrow &a\ B\\ &|&a\\ \\ B&\rightarrow &b\\ &|&c\\ \end{array} AB​→∣→∣​a Babc​ ​ 使用递归下降分析算法的困难之处在于推导结果的复杂，可以改写文法为： A → a   A ′ A ′ → ε ∣ B B → b ∣ c \begin{array}{c r l} A&\rightarrow &a\ A'\\ \\ A'&\rightarrow &\varepsilon\\ &|&B\\ \\ B&\rightarrow &b\\ &|&c \end{array} AA′B​→→∣→∣​a A′εBbc​ ​ 代码为：

parse_A() {
    if (tokens[i++] == ‘a’)
        parse_A’();
    else
        return failure;
}

parse_A’() {
    token = tokens[i++];
    if (token == EOF)                // $ 或 #
        return success;
    else
        parse_B();
}

parse_B() {
    if (token==‘b’ || token==‘c’)
        return success;
    else
        return failure;
}

4.6 LL(1) 分析算法介绍

​ 从左（L）向右读入程序 / 输入串，最左（L）推导，采用一个（1）前看符号。

​ 算法基本思想：表驱动的分析算法

4.6.1 表驱动的LL(1) 分析器的架构 4.6.2 与自顶向下分析算法的比较

1. 构造 LL(1) 分析表，表示每一个非终结符所能推导的所有终结符集合
2. 表中空为推导不出，存在数字则表示对应的推导出的文法行号

4.6.3 LL(1) 分析法中栈的存储情况

​ 以句子 gdw 为例，使用上述文法进行匹配： S ⟶ N V N ⟶ g V N ⟶ V N ⟶ d N ⟶ N ⟶ w ⟶ \begin{array}{|c|} \\ \hline S\\ \hline \end{array} \longrightarrow \begin{array}{|c|} \\ \hline N\\ \hline V\\ \hline N\\ \hline \end{array} \longrightarrow \begin{array}{|c|} \\ \hline g\\ \hline V\\ \hline N\\ \hline \end{array} \longrightarrow \begin{array}{|c|} \\ \hline V\\ \hline N\\ \hline \end{array} \longrightarrow \begin{array}{|c|} \\ \hline d\\ \hline N\\ \hline \end{array} \longrightarrow \begin{array}{|c|} \\ \hline N\\ \hline \end{array} \longrightarrow \begin{array}{|c|} \\ \hline w\\ \hline \end{array} \longrightarrow \begin{array}{|c|} \\ \hline \\ \hline \end{array} S​​⟶NVN​​⟶gVN​​⟶VN​​⟶dN​​⟶N​​⟶w​​⟶​​

4.6.4 FIRST 集探究

（1）FIRST 集 F I R S T ( N ) = 从非终结符 N 开始推导出的句子开头的所有可能终结符集合 FIRST(N)=\text{从非终结符}N\text{开始推导出的句子开头的所有可能终结符集合} FIRST(N)=从非终结符N开始推导出的句子开头的所有可能终结符集合

​ 以上述文法为例：

• FIRST(N) = { s, t, g, w }
• FIRST(V) = { e, d }
• FIRST(S) = FIRST(N) = { s, t, g, w }

（2）FIRST 集的不动点算法

foreach (nonterminal N) {        // 初始化每个终结符
    FIRST(N) = {};
}

while (some set is changing) {   // 如果有任意集合改变，则继续循环
    // 对于每个关于 N 的推导式 p，查看 β1
    foreach (production p : N -> β1 ... βn) {  
        if (β1 == a)
            FIRST(N) ∪= {a};
        if (β1 == M)
            FIRST(N) ∪= FIRST(M);
    }
}

（3）示例 N / F I R S T 0 1 2 3 4 5 S { } { } { s ,   t ,   g ,   w } { s ,   t ,   g ,   w } N { } { s ,   t ,   g ,   w } { s ,   t ,   g ,   w } { s ,   t ,   g ,   w } V { } { e ,   d } { e ,   d } { e ,   d } \begin{array}{c} \hline N/FIRST & 0 & 1 & 2 & 3 & 4 & 5\\ \hline S & \{\} & \{\} & \{s,\ t,\ g,\ w\} & \{s,\ t,\ g,\ w\}\\ N & \{\} & \{s,\ t,\ g,\ w\} & \{s,\ t,\ g,\ w\} & \{s,\ t,\ g,\ w\} \\ V & \{\} & \{e,\ d\} & \{e,\ d\} & \{e,\ d\}\\ \hline \end{array} N/FIRSTSNV​0{}{}{}​1{}{s, t, g, w}{e, d}​2{s, t, g, w}{s, t, g, w}{e, d}​3{s, t, g, w}{s, t, g, w}{e, d}​45​

4.6.5 LL(1) 分析表的冲突

​ 若表中每个项最多只有一个元素，为 LL(1) 文法；

​ 否则发生冲突，不是 LL(1) 文法。

​ 例如：

​ 冲突检测：对 N 的两条产生式规则 N → β N\rightarrow\beta N→β 和 N → γ N\rightarrow\gamma N→γ，若 F I R S T ( β ) ∩ F I R S T ( γ ) ≠ { } FIRST(\beta)\cap FIRST(\gamma)\neq\{\} FIRST(β)∩FIRST(γ)​={} ​ 则发生冲突。

4.6.6 特殊情况下的例外

​ 对于下面的文法： Z → Y   X Y → c ∣ ε X → Y ∣ a \begin{array}{r r l} Z & \rightarrow & Y\ X\\\\ Y & \rightarrow & c\\ & | & \varepsilon\\\\ X & \rightarrow & Y\\ & | & a \end{array} ZYX​→→∣→∣​Y XcεYa​

​ 按照上述算法列出 FIRST 集： N / F I R S T 0 1 2 3 4 5 Z { } { } { c } { c } X { } { c } { c } { c } Y { } { c ,   a } { c ,   a } { c ,   a } \begin{array}{c} \hline N/FIRST & 0 & 1 & 2 & 3 & 4 & 5\\ \hline Z & \{\} & \{\} & \{c\} & \{c\}\\ X & \{\} & \{c\} & \{c\} & \{c\} \\ Y & \{\} & \{c,\ a\} & \{c,\ a\} & \{c,\ a\}\\ \hline \end{array} N/FIRSTZXY​0{}{}{}​1{}{c}{c, a}​2{c}{c}{c, a}​3{c}{c}{c, a}​45​ ​ 我们会发现，当 Y → ε ,   X → a Y\rightarrow\varepsilon,\ X\rightarrow a Y→ε, X→a 时，Z 的 FIRST 集还应该包含 a。说明我们之前的算法具有以下的漏洞：

• 忽略了非终结符 M 可能推导出空串 ε \varepsilon ε 的情况

4.7 LL(1) 分析表构造实现 4.7.1 NULLABLE 集合

（1）定义

​ 非终结符 X 属于集合 NULLABLE，当且仅当：

• X → ε X\rightarrow\varepsilon X→ε
• X → Y 1 Y 2 … Y n X\rightarrow Y_{1}Y_{2}\dots Y_{n} X→Y1​Y2​…Yn​
  • Y 1 、 Y 2 … Y n Y_{1}、Y_{2}\dots Y_{n} Y1​、Y2​…Yn​ 是 n 个非终结符，且均属于 NULLABLE

（2）算法

NULLABLE = {};

while (NULLABLE is still changing) {
    foreach (production p : X -> β) {
        if (β == ε)
            NULLABLE ∪= {X};
        if (β == Y1...Yn)
            if (Y1 in NULLABLE && ... && Yn in NULLABLE)
                NULLABLE ∪= {X};
    }
}

（3）示例

N U L L A B L E 0 1 2 3 { } { Y ,   X } { Y ,   X } \begin{array}{c} \hline NULLABLE & 0 & 1 & 2 & 3\\ \hline & \{\} & \{Y,\ X\} & \{Y,\ X\}\\ \hline \end{array} NULLABLE​0{}​1{Y, X}​2{Y, X}​3​

4.7.2 FIRST 集

（1）完整定义

​ 对于非终结符 X，其 FIRST 集归纳为以下情况：

• 若 X → a X\rightarrow a X→a
  • F I R S T ( X )   ∪ = { a } FIRST(X)\ \cup= \{a\} FIRST(X) ∪={a}
• 若 X → Y 1 Y 2 … Y n X\rightarrow Y_{1}Y_{2}\dots Y_{n} X→Y1​Y2​…Yn​
  • F I R S T ( X )   ∪ = F I R S T ( Y 1 ) FIRST(X)\ \cup= FIRST(Y_{1}) FIRST(X) ∪=FIRST(Y1​)
  • i f Y 1 ∈ N U L L A B L E , F I R S T ( X )   ∪ = F I R S T ( Y 2 ) if\quad Y_{1} \in NULLABLE,\quad FIRST(X)\ \cup= FIRST(Y_{2}) ifY1​∈NULLABLE,FIRST(X) ∪=FIRST(Y2​)
  • i f Y 1 , Y 2 ∈ N U L L A B L E , F I R S T ( X )   ∪ = F I R S T ( Y 3 ) if\quad Y_{1},Y_{2} \in NULLABLE,\quad FIRST(X)\ \cup= FIRST(Y_{3}) ifY1​,Y2​∈NULLABLE,FIRST(X) ∪=FIRST(Y3​)
  • …

（2）算法

foreach (nonterminal N) {        // 初始化每个非终结符
    FIRST(N) = {};
}

while (some set is changing) {   // 如果有任意集合改变，则继续循环
    // 对于每个关于 N 的推导式 p，查看 β1
    foreach (production p : N -> β1 ... βn) {  
        foreach (βi from β1  upto βn) {
            if (β1 == a) {               // 表示所有终结符
                FIRST(N) ∪= {a};
                break;
            }
            if (β1 == M) {               // 表示所有非终结符
                FIRST(N) ∪= FIRST(M);
                if (M not in NULLABLE)   // 如果碰到了不可能为空串的非终结符，则退出循环
                    break;
            }
        }
    }
}

（3）示例

N / F I R S T 0 1 2 3 4 Z { } { d } { d ,   c ,   a } { d ,   c ,   a } X { } { c } { c } { c } Y { } { c ,   a } { c ,   a } { c ,   a } \begin{array}{c} \hline N/FIRST & 0 & 1 & 2 & 3 & 4\\ \hline Z & \{\} & \{d\} & \{d,\ c,\ a\} & \{d,\ c,\ a\}\\ X & \{\} & \{c\} & \{c\} & \{c\} \\ Y & \{\} & \{c,\ a\} & \{c,\ a\} & \{c,\ a\}\\ \hline \end{array} N/FIRSTZXY​0{}{}{}​1{d}{c}{c, a}​2{d, c, a}{c}{c, a}​3{d, c, a}{c}{c, a}​4​

4.7.3 FOLLOW 集

（1）定义

​ FOLLOW 集包含了文法中 X 后面可能跟随的所有终结符。

​ 求 FOLLOW 集是为了考虑到下面这种文法： Z → Y X Y → X ∣ a X → b Z c ∣ ε \begin{array}{r r l} Z & \rightarrow & YX\\\\ Y & \rightarrow & X\\ & | & a\\\\ X & \rightarrow & bZc\\ & | & \varepsilon \end{array} ZYX​→→∣→∣​YXXabZcε​ ​ 按照之前的 FIRST 算法来看：

• N U L L A B L E = { X ,   Y ,   Z } NULLABLE=\{X,\ Y,\ Z\} NULLABLE={X, Y, Z}
• F I R S T ( X ) = b FIRST(X)=b FIRST(X)=b
• F I R S T ( Y ) = F I R S T ( X ) FIRST(Y)=FIRST(X) FIRST(Y)=FIRST(X) 或 a = { a ,   b } a=\{a,\ b\} a={a, b}
• F I R S T ( Z ) = F I R S T ( Y )   ∪   F I R S T ( X ) = { a ,   b } FIRST(Z)=FIRST(Y)\ \cup\ FIRST(X)=\{a,\ b\} FIRST(Z)=FIRST(Y) ∪ FIRST(X)={a, b}

​ 但实际上，在 Z 开头的句子中，遇到的第一个终结符也可能是 c：

​ 考虑 X → b Z c X\rightarrow bZc X→bZc，用 Z → Y X Z\rightarrow YX Z→YX 替换其中的 Z，并且 X、Y 都取空串 ε \varepsilon ε，得到 X → b c X\rightarrow bc X→bc。

​ 这一原因就在于 Z 可能也是 NULLABLE，当 Z 为空串时，以 Z 开头的句子第一个终结符就可以是 Z 后面的第一个终结符，因此需要 FOLLOW 集合来补足。

（2）算法

foreach (nonterminal N) {                 // 初始化
    FOLLOW(N) = {};
}

FOLLOW(S) = {#};                          // 在开始符号 S 中加入结束符 #

while (some set is still changing) {
    foreach (production p : N -> β1...βn) {
        temp = FOLLOW(N);                 // βn 的 FOLLOW 集合也是 N 的 FOLLOW 集合
        foreach (βi from βn downto β1) {  // 逆序
            if (βi == a)                  // 表示所有终结符
                temp = {a};
            if (βi == M) {                // 表示所有非终结符
                FOLLOW(M) ∪= temp;
                if (M is not NULLABLE)    // 如果 βi 不能为空串，temp 改变
                    temp = FIRST(M);
                else                      // 如果 βi 可以为空串，temp 取并集
                    temp ∪= FIRST(M);
            }
        }
    }
}

（3）示例

N U L L A B L E = { X ,   Y } NULLABLE=\{X,\ Y\} NULLABLE={X, Y}

X Y Z F I R S T { a ,   c } { c } { a ,   c ,   d } \begin{array}{c} \hline & X & Y & Z\\ \hline FIRST & \{a,\ c\} & \{c\} & \{a,\ c,\ d\}\\ \hline \end{array} FIRST​X{a, c}​Y{c}​Z{a, c, d}​​

N / F O L L O W 0 1 2 3 Z { # } { # } { # } Y { } { a ,   c ,   d } { a ,   c ,   d } X { } { a ,   c ,   d } { a ,   c ,   d } \begin{array}{c} \hline N/FOLLOW& 0 & 1 & 2 & 3\\ \hline Z & \{\#\} & \{\#\} & \{\#\}\\ Y & \{\} & \{a,\ c,\ d\} & \{a,\ c,\ d\}\\ X & \{\} & \{a,\ c,\ d\} & \{a,\ c,\ d\}\\ \hline \end{array} N/FOLLOWZYX​0{#}{}{}​1{#}{a, c, d}{a, c, d}​2{#}{a, c, d}{a, c, d}​3​

4.7.4 FIRST_S 集合

（1）定义

​ 算法更新后的 FIRST 集，表示每一行产生式匹配句子的第一个可能的终结符。

（2）算法

foreach (production p) {                // 初始化每个产生式
    FIRST_S(p) = {};
}

calculte_FIRST_S(production p : N -> β1...βn) {
    foreach (βi from β1 to βn) {
        if (βi == a) {                  // 表示所有终结符 
            FIRST_S(p) ∪= {a};
            return;
        } 
        if (βi == M) {                  // 表示所有非终结符
            FIRST_S(p) ∪= FIRST(M);
            if (M is not NULLABLE)
                return;
        }
    }
    FIRST_S(p) ∪= FOLLOW(N);           // 运行到这里，说明前面都可为空串
}

​ 若 FOLLOW 集考虑结束符 #，FIRST_S 相当于产生式的选择符号集 SELECT。

（3）示例

N U L L A B L E = { X ,   Y } NULLABLE=\{X,\ Y\} NULLABLE={X, Y}

X Y Z F I R S T { a ,   c } { c } { a ,   c ,   d } F O L L O W { a ,   c ,   d } { a ,   c ,   d } { } \begin{array}{c} \hline & X & Y & Z\\ \hline FIRST & \{a,\ c\} & \{c\} & \{a,\ c,\ d\}\\ FOLLOW & \{a,\ c,\ d\} & \{a,\ c,\ d\} & \{\}\\ \hline \end{array} FIRSTFOLLOW​X{a, c}{a, c, d}​Y{c}{a, c, d}​Z{a, c, d}{}​​

0 1 2 3 4 5 F I R S T _ S { d } { a ,   c ,   d } { c } { a ,   c ,   d } { a ,   c ,   d } { a } \begin{array}{c} \hline & 0 & 1 & 2 & 3 & 4 & 5\\ \hline FIRST\_S & \{d\} & \{a,\ c,\ d\} & \{c\} & \{a,\ c,\ d\} & \{a,\ c,\ d\} & \{a\}\\ \hline \end{array} FIRST_S​0{d}​1{a, c, d}​2{c}​3{a, c, d}​4{a, c, d}​5{a}​​

4.7.5 构造 LL(1) 分析表

0 1 2 3 4 5 F I R S T _ S { d } { a ,   c ,   d } { c } { a ,   c ,   d } { a ,   c ,   d } { a } Z Z Y Y X X \begin{array}{c} \hline & 0 & 1 & 2 & 3 & 4 & 5\\ \hline FIRST\_S & \{d\} & \{a,\ c,\ d\} & \{c\} & \{a,\ c,\ d\} & \{a,\ c,\ d\} & \{a\}\\ \hline & Z & Z & Y & Y & X & X\\ \end{array} FIRST_S​0{d}Z​1{a, c, d}Z​2{c}Y​3{a, c, d}Y​4{a, c, d}X​5{a}X​​

​ 得到包含冲突的分析表： a c d Z 1 1 0 , 1 Y 3 2 , 3 3 X 4 , 5 4 4 \begin{array}{|c|c|c|c|} \hline & a & c & d\\ \hline Z & 1 & 1 & 0,1\\ \hline Y & 3 & 2,3 & 3\\ \hline X & 4,5 & 4 & 4\\ \hline \end{array} ZYX​a134,5​c12,34​d0,134​​ ​ LL(1) 分析器：

tokens[];                                    // 词法分析器返回的记号数组
int i = 0;                                   // 指向数组下一个要匹配的记号位置
stack st = [S];                              // S 为开始符号
while (st != []) {
    if (st[top] is a terminal t)
        if (t == tokens[i++])
            pop();
        else error();                        // 报错
    else if (st[top] is a nonterminal T) {
        pop();
        push(table[T, tokens[i]]);           // 逆序压栈：右侧的先压栈
    }
}

4.8 LL(1) 分析冲突处理

​ 任何有左递归或首公因子的文法都不是 LL(1) 文法。

4.8.1 消除左递归

（1）左递归的两种情况

• 直接左递归 A → A β A\rightarrow A\beta A→Aβ

• 间接左递归 A → B β B → A α } ⇒ A → A α β \left. \begin{array}{l} A\rightarrow B\beta\\ B\rightarrow A\alpha \end{array} \quad \right\}\Rightarrow \quad A\rightarrow A\alpha\beta A→BβB→Aα​}⇒A→Aαβ

（2）消除直接左递归

​ 方法：引入新的非终结符，变为右递归。 S → S   a S → b ⟹ S → b   S ′ S ′ → a   S ′   ∣   ε \begin{array}{l} S \rightarrow S\ a\\ S\rightarrow b \end{array} \quad \Longrightarrow \quad \begin{array}{l} S\rightarrow b\ S'\\ S'\rightarrow a\ S'\ |\ \varepsilon \end{array} S→S aS→b​⟹S→b S′S′→a S′ ∣ ε​

• 一般形式 A → A α 1   ∣   A α 2   ∣   …   ∣ A α n   ∣   β 1   ∣   β 2   ∣   …   ∣   β m ⇓ A → β 1 A ′   ∣   β 2 A ′   ∣   …   ∣   β m A ′ A ′ → α 1 A ′   ∣   α 2 A ′   ∣   …   ∣ α n A ′   ∣   ε A\rightarrow A\alpha_{1}\ |\ A\alpha_{2}\ |\ \dots\ |A\alpha_{n}\ |\ \beta_{1}\ |\ \beta_{2}\ |\ \dots\ |\ \beta_{m}\\ \Downarrow\\ A\rightarrow \beta_{1}A'\ |\ \beta_{2}A'\ |\ \dots\ |\ \beta_{m}A'\\ A'\rightarrow \alpha_{1}A'\ |\ \alpha_{2}A'\ |\ \dots\ |\alpha_{n}A'\ |\ \varepsilon A→Aα1​ ∣ Aα2​ ∣ … ∣Aαn​ ∣ β1​ ∣ β2​ ∣ … ∣ βm​⇓A→β1​A′ ∣ β2​A′ ∣ … ∣ βm​A′A′→α1​A′ ∣ α2​A′ ∣ … ∣αn​A′ ∣ ε

（3）消除间接左递归

• 通过产生式非终结符置换，变为直接左递归
• 再消除直接左递归
• 去掉无用产生式（不可到达的非终结符）

4.8.2 提取公因子 4.8.3 小结

1. LL(1) 文法是右递归、无回溯的语法

   • 若文法中含有左递归的非终结符号，则它必然是非 LL(1) 文法。

2. LL(1) 分析表中每个项最多只有一个元素，否则叫做冲突，不是 LL(1) 类型的文法

   • 判断：相同左部的产生式的 First_S 集的交集是否为空

3. 转换为 LL(1) 文法的可能方法

   • 消除左递归
   • 提取左公因子

   但通过这些方法转换的文法未必一定是 LL(1) 文法

4.9 LL(1) 文法的递归下降分析算法 4.9.1 算法设计思路

1. 每遇到一个终结符，则判断当前读入的单词符号是否与该终结符相匹配

   • 若匹配，则继续读取下一个单词符号

   • 若不匹配，则进行错误处理

2. 每遇到一个非终结符，则调用相应的分析子程序

4.9.2 算法结构

（1）lookahead 变量

​ 全局量，存放当前所扫描单词符号的单词种别

​ 为了简洁，后面将文法中的终结符直接用来代表当前所扫描单词符号的单词种别。

（2）MatchToken() 函数

​ 用于匹配当前终结符和正在扫描的单词符号的函数：

void MatchToken(int expected)
{
    if (lookahead != expected) {
        printf(“syntax error\n”);
        exit(0);
    }
    else   // 若匹配，消掉当前单词符号，从词法分析程序读入下一个单词
        lookahead = getToken();   // 并将该单词符号的种别赋值给 lookahead
}

（3）Parse_A() 函数

void ParseA() {
    switch (lookahead) {
        case SELECT(A -> β1):
            ...       // 根据 β1 设计的分析过程
            break;
        ...
        case SELECT(A -> βn):
            ...       // 根据 βn 设计的分析过程
            break;
        default:
            printf(“syntax error\n”);
            exit(0);
    } 
}

​ 因为是 LL(1) 文法，所以 SELECT 集合是不相交的

4.9.3 示例

​ 对于下列文法： S → A   a   S   ∣   B   b   S   ∣   d A → a B → ε   ∣   c \begin{array}{l} S\rightarrow A\ a\ S\ |\ B\ b\ S\ |\ d\\ A\rightarrow a\\ B\rightarrow \varepsilon\ |\ c \end{array} S→A a S ∣ B b S ∣ dA→aB→ε ∣ c​ ​ SELECT 集（FIRST_S）： S E L E C T ( S → A a S ) = { a } S E L E C T ( S → B b S ) = { c , b } S E L E C T ( S → d ) = { d } S E L E C T ( A → a ) = { a } S E L E C T ( B → ε ) = { b } S E L E C T ( B → c ) = { c } \begin{array}{l} SELECT(S\rightarrow AaS) = \{a\}\\ SELECT(S\rightarrow BbS) = \{c, b\}\\ SELECT(S\rightarrow d) = \{d\}\\ SELECT(A\rightarrow a) = \{a\}\\ SELECT(B\rightarrow \varepsilon) = \{b\}\\ SELECT(B\rightarrow c) = \{c\} \end{array} SELECT(S→AaS)={a}SELECT(S→BbS)={c,b}SELECT(S→d)={d}SELECT(A→a)={a}SELECT(B→ε)={b}SELECT(B→c)={c}​ ​ 递归下降分析程序：

void Parse_S() {
    switch (lookahead) {
        case 'a':
            Parse_A();
            MatchToken('a');
            ParseS();
            break;
        case 'b': case 'c':
            Parse_B();
            MatchToken('b');
            Parse_S(); 
            break;
        case 'd':
            MatchToken('d');
            break;
        default:
            printf(“syntax error\n”);
            exit(0);
    } 
}

void Parse_A() {
    if (lookahead == 'a') 
        MatchToken('a');
    else {
        printf(“syntax error\n”);
        exit(0);
    } 
}

void Parse_B() {
    if (lookahead == 'c') 
        MatchToken('c');
    else if (lookahead == 'b') { }
    else {
        printf(“syntax error\n”);
        exit(0);
    } 
}