编译原理-LL1文法详细讲解

作者: wo883721 | 来源:发表于2021-08-19 09:10 被阅读0次

本篇文章内的源码: 这里

一. `CFG` 分析树

我们知道2型文法(CFG)，它的每个产生式类型都是 α→β,其中 α ∈ VN,β ∈ (VN∪VT)*。

即产生式左部是一个非终结符，产生式的右部是多个文法符号组成的文法符号串。

例如, 一个表达式的文法:

文法G
1. E -> E + E
2. E -> E * E
3. E -> (E)
4. E -> id

最终推导出 id + (id + id) 的句子，那么它的推导过程就会构成一颗树，即CFG 分析树：

cfg.png

从分析树可以看出，我们从文法开始符号起，不断地利用产生式的右部替换产生式左部的非终结符，最终推导出我们想要的句子。这种方式我们称为自顶向下分析法。

二. 自顶向下分析

从文法开始符号起，不断用非终结符的候选式(即产生式)替换当前句型中的非终结符，最终得到相应的句子。
在每一步推导过程中，我们需要做两个选择:

替换当前句型中的哪个非终结符。
用该非终结符的哪个候选式进行替换。

这个是自顶向下分析法最需要处理的两个问题。

2.1 处理选择那个非终结符问题

因为一个句型中，可能存在多个非终结符，我们就不确定选择那一个非终结符进行替换。
对于这种情况，我们就需要做强制规定，每次都选择句型中第一个非终结符进行替换(或者每次都选择句型中最后一个非终结符进行替换)。

最左推导（Left-most Derivation）

最左推导.png
最右推导（Right-most Derivation）

最右推导.png

自顶向下的语法分析采用最左推导方式，即总是选择每个句型的最左非终结符进行替换。

2.2 处理选择非终结符那个候选式问题

最终的结果是要推导出一个特定句子(例如 id + (id + id))。
我们将特定句子看成一个输入字符串，而每一个非终结符对应一个处理方法，这个处理方法用来匹配输入字符串的部分，算法如下:

    void A(输入字符串s, 读取位置pos) {
        选择一个 A 的产生式，例如 A -> X1X2X3...XK;
        新的读取位置newPos = pos;
        for (i = 1 to k) {
                if (newPos 大于等于输入字符串s长度) {
                    // 说明这个产生式不匹配，抛出一个错误
                }
            当前输入符号α = s[newPos];
            if (Xi 是一个非终结符) {
                // 递归调用 Xi 的方法，将输入字符串s, 当前读取位置newPos
                // 返回的值，表示 Xi 读取的匹配字符后的位置
                newPos = Xi(s, newPos);
            } else if (Xi 等于当前输入符号α) {
                newPos++;
            } else {
                // Xi 不是一个非终结符，也不是输入符号α，
                // 那么说明匹配错误，抛出一个错误
            }
        }
        return newPos;
    }

方法解析:

方法传入参数是输入字符串 s 以及已经读取位置 pos。
选择当前非终结符的一个候选式。
遍历被选择候选式所有字符。
如果字符 Xi 是非终结符，那么调用这个非终结符Xi 对应处理方法，让它匹配一部分输入字符串，并返回匹配后的新位置。

例如对于 id + (id + id) ；E => E + E => id + E; 刚开始选择 E + E 的产生式，因为 E 是一个非终结符，要调用 E() 处理方法，最后它选择了 id 的产生式，匹配了 id + (id + id) 一部分 id，然后返回新位置 newPos = 1。

如果字符 Xi 是终结符，就与当前输入符号α 进行比较。
- 如果相等，表示匹配成功这个字符，newPos 加一，读取下一个字符。
- 如果不相等，说明匹配错误，当前选择的产生式不符合，抛出一个错误，再选择下一个候选式进行匹配。
如果此候选式的所有字符都能匹配完成，那么就返回新位置 newPos。
如果当前非终结符所有候选式都不能匹配完成，说明此非终结符上一个非终结符候选式选择错误。
如果文法开始符号 S 的处理方法，接收输入字符串s 后，返回的 newPos 值等于输入字符串s 长度，那么就成功完成语法分析。

这种方式称为递归下降分析(Recursive-Descent Parsing)：

由一组过程组成，每个过程对应一个非终结符。
从文法开始符号S对应的过程开始，其中递归调用文法中其它非终结符对应的过程。如果S对应的过程体恰好扫描了整个输入串，则成功完成语法分析。

当选择的候选式不正确，就需要回溯(backtracking)，重新选择候选式，进行下一次尝试匹配。因为要不断的回溯，导致分析效率比较低。

那么如果我们能够确定候选式，语法分析的时候不需要回溯，那么分析效率就会大大提高。

这种方式叫做预测分析(Predictive Parsing)：

预测分析是递归下降分析技术的一个特例，通过在输入中向前看固定个数（通常是一个）符号来选择正确的A-产生式。
可以对某些文法构造出向前看k个输入符号的预测分析器，该类文法有时也称为LL(k) 文法类；
预测分析不需要回溯，是一种确定的自顶向下分析方法。

三. 实现预测分析

要实现预测分析，我们必须保证从文法开始符号起，每一个推导过程中，当前句型最左非终结符 A 对于当前输入字符 a,只能得到唯一的 A 候选式。

3.1 S_文法 (简单确定性文法)

根据上面的解决方法，我们首先想到，如果非终结符 A 的候选式只有一个以终结符 a 开头候选式不就行了么。
进而我们可以得出，如果一个非终结符A，它的候选式都是以终结符开头，并且这些终结符都各不相同，那么本身就符合预测分析了。

这就是S_文法，满足下面两个条件:

每个产生式的右部都以终结符开始。
同一非终结符的各个候选式的首终结符都不同。

例子:

文法G
1. S -> aA   | bAB
2. A -> a    | c
3. B -> b    | c

这就是一个典型的S_文法，它的每一个非终结符遇到任一终结符得到候选式是确定的。如 S -> aA | bAB, 只有遇到终结符 a 和 b 的时候，才能返回 S 的候选式，遇到其他终结符时，直接报错，匹配不成功。

虽然S_文法可以实现预测分析，但是从它的定义上看，S_文法不支持空产生式(ε产生式)，极大地限制了它的应用。

3.2 空产生式

什么是空产生式(ε产生式)？

如果一个非终结符 A 有空候选式(即空产生式)，那么在匹配的时候，就可以跳过这个非终结符 A，匹配句型中 A 后面的字符。

例子

文法G：
1. S -> aA | bAB
2. A -> a  | c | ε
3. B -> b  | c

这里 A 有了空产生式，那么S的产生式组 S -> aA | bAB，就可以是 a | bB,这样a,bb,bc 就变成这个文法G的新句子了。

根据预测分析的定义，非终结符对于任一终结符得到的产生式是确定的，要么能获取唯一的产生式，要么不匹配直接报错。

那么空产生式何时被选择呢？

仔细观察，我们发现 A -> ε空产生式的选择，取决于A 后面的字符，如产生式 S -> bAB,
A -> ε空产生式的选择取决于非终结符 B 能匹配的终结符集合，这里是[b, c]。

3.3 后继符号集

由此可以引入非终结符A的后继符号集的概念:
定义: 由文法G推导出来的所有句型，可以出现在非终结符A后边的终结符a的集合，就是这个非终结符A 的后继符号集，记为FOLLOW(A)。

注: 这里指的是文法G推导出来的所有句型。如何计算这个后继符号集，我们下面介绍。

因此对于 A -> ε空产生式，只要遇到非终结符A的后继符号集中的字符，可以选择这个空产生式。
那么对于 A -> a 这样的产生式，只要遇到终结符 a 就可以选择了。

3.4 可选集

由此我们引入的产生式可选集概念:
定义: 在进行推导时，选用非终结符 A 一个产生式 A→β 对应的输入符号的集合，记为SELECT(A→β)

SELECT( A→aβ ) = { a }

如果产生式右部首字符是终结符，那么这个产生式的可选集就只包含这个终结符。

SELECT( A→ε ) = FOLLOW( A )

如果是一个空产生式，那么这个产生式的可选集就是这个产生式左部非终结符的后继符号集。

因为预测分析要求非终结符 A 对于输入字符 a,只能得到唯一的 A 候选式。
那么对于一个文法 G 的所有产生式组，要求有相同左部的产生式，它们的可选集不相交。

这样分析，例子中的文法就不符合要求。因为 FOLLOW( A ) 中包含终结符 c, 而又存在 A -> ε 这个产生式，所以可选集相交了。

S_文法天然满足这个要求，因为它同一非终结符的各个候选式的首终结符都不同。

3.5 q_文法

在 S_文法基础上，我们允许有空产生式，但是要做限制:

每个产生式的右部或为ε ，或以终结符开始。
具有相同左部的产生式有不相交的可选集。

将上面例子中的文法改造:

文法G：
1. S -> aA | bAB
2. A -> a  | ε
3. B -> b  | c

将原来 A -> c 这个产生式除去，那么这个文法所有相同左部产生式的可选集不相交；这就符合q_文法了。

但是q_文法的产生式不能是非终结符打头，这就限制了其应用，因此引入LL(1)文法。

3.6 LL(1)文法

LL(1)文法允许产生式的右部首字符是非终结符，那么怎么得到这个产生式可选集。
我们知道对于产生式:

A→aβ : a 是终结符，那么这个产生式的可选集SELECT( A→aβ ) 就是 { a }。
A→ε : 空产生式对应的可选集SELECT( A→ε ) 就是 FOLLOW( A )。
A→BCDe : B,C,D都是非终结符，e 是终结符，以非终结符开头，那么它的可选集SELECT( A→BCDe) 是什么呢?就是文法符号串BCDe 的串首终结符集FIRST(BCDe)。

3.6.1 串首终结符集

定义: 给定一个文法符号串α， α的串首终结符集FIRST(α)被定义为可以从α推导出的所有串首终结符构成的集合。

串首终结符意思就是符号串的首字符是终结符，所以由 α 推导出的所有首字母是终结符的文法符号串，这些终结符首字母组成的集合就是FIRST(α)。

定义已经了解清楚了，那么该如何求呢？
例如一个文法符号串 BCDe, 其中 B C D 都是非终结符，e 是终结符。

仔细思考一下，你会发现:

要想求文法符号串 BCDe 推导出多少个串首终结符，要先求非终结符B 能够推导出多少个串首终结符，这个由 B 产生式组来求解。

如果 B 能够推导出空串ε，即(B =>+ ε)，那么代表 B 是可以消除的，文法符号串 BCDe相当于文法符号串CDe，所以也要求非终结符C 能够推导出多少个串首终结符。

因此对于一个文法符号串 X1X2 … Xn，求解串首终结符集 FIRST(X1X2 … Xn)算法:

遍历这个文法符号串，然后判断当前文法符号串中的字符 Xi (i属于1到n)。

如果 Xi 是终结符，那么它的串首终结符集FIRST(Xi)中就只有它自己，将FIRST(Xi)加入FIRST(X1X2 … Xn) 中；因为FIRST(Xi)也不可能包含空串 ε，不用再向下遍历，循环到此为止，得到最终的串首终结符集FIRST(X1X2 … Xn)。

如果 Xi 是非终结符，那么就将它的串首终结符集FIRST(Xi)加入FIRST(X1X2 … Xn) 中。

如果FIRST(Xi)包含空串ε，那么再向下遍历一个字符；但是如果 Xi 已经是最后一个字符了，那就说明整个文法符号串 X1X2 … Xn可以推导出空串ε，因此将空串ε加到FIRST(X1X2 … Xn) 中。

如果FIRST(Xi)不包含空串ε，不用再向下遍历，循环到此为止，得到最终的串首终结符集FIRST(X1X2 … Xn)。

但是这里有一个关键点，如何求非终结符的串首终结符集？

如求非终结符A 的串首终结符集FIRST(A)，其实就是看这个非终结符A 能够推导的所有首字符是终结符的文法符号串，那么就是看这个非终结符A 的产生式组。

因此对于一个非终结符 A, 求解串首终结符集FIRST(A)算法:

遍历非终结符A的所有产生式:

A→aβ : a 是终结符，那么这个产生式推导的所有文法符号串，它们的首字符只能是终结符a，因此将这个a添加到FIRST(A)中。

A→ε : 非终结符A 能够推导出空串ε,那么将这个空串 ε 添加到FIRST(A)中。

A→Bβ : 产生式右部首字符是非终结符，那么就将 FIRST(Bβ) 添加到 FIRST(A)中。

这里大家可能有个疑惑，怎么能将 FIRST(Bβ) 添加到 FIRST(A)中，如果问文法符号串 Bβ 中包含非终结符 A ，就产生了循环调用的情况，该怎么办?

如果非终结符 A 的产生式组中，有包含A 的产生式，那么在计算 FIRST(A) 时候:

先计算不包含 A 的其他产生式，得到一个 FIRST(A)。

然后计算包含 A 的产生式，遇到 A 的时候跳过，判断之前的FIRST(A)包不包含空串 ε,来决定是否将产生式 A 后面的文法符号串的串首终结符集加入 FIRST(A) 中。

对于串首终结符集，我想大家疑惑的点就是，串首终结符集到底是针对文法符号串的，还是针对非终结符的，这个容易弄混。
其实我们应该知道，非终结符本身就属于一个特殊的文法符号串。
而求解文法符号串的串首终结符集，其实就是要知道文法符号串中每个字符的串首终结符集:

对于终结符，它的串首终结符集就是它自己。
对于非终结符，它的串首终结符集是要通过它对应的产生式组计算得来的。
再判断当前字符对应的串首终结符集包不包含空串，来决定要不要添加文法符号串中下一个字符的串首终结符集。

串首终结符集算法的具体实现请看 First集和Follow集

3.6.2 后继符号集

上面章节我们知道了，对于非终结符A的后继符号集:
就是由文法G推导出来的所有句型，可以出现在非终结符A后边的终结符的集合，记为FOLLOW(A)。

仔细想一下，什么样的终结符可以出现在非终结符A后面，应该是在产生式中就位于A后面的终结符。例如 S -> Aa，那么终结符 a 肯定属于FOLLOW(A)。

因此求非终结符A的后继符号集算法：

遍历文法所有的产生式，判断产生式右部中是否包含非终结符A:

S -> αAβ : 包含非终结符A，其中 α 和 β 都属于文法符号串，那么就将文法符号串β 的串首终结符集FIRST(β) 中除了空串ε外的所有终结符添加到FOLLOW(A)。如果FIRST(β)存在空串ε，那么就需要将FOLLOW(S) 也添加到FOLLOW(A)中。
注意：这里的 β 是文法符号串，不要把它当成一个特定的非终结符。

S -> αA : 包含非终结符A, 其中 α 属于文法符号串，那么将FOLLOW(S) 添加到FOLLOW(A)中。

如果非终结符 A 是产生式结尾，那么说明这个产生式左部非终结符后面能出现的终结符，也都可以出现在非终结符 A后面。

刚开始的时候，需要将结束符号 $ 添加到文法开始符号S 的后继符号集FOLLOW(S) 中。

后继符号集中是不会包含空串ε的。

后继符号集算法的具体实现请看 First集和Follow集

3.6.3 可选集

我们可以求出LL(1)文法中每个产生式可选集:

A→aβ : a 是终结符，β 是文法符号串，那么这个产生式的可选集SELECT(A→aβ) 就是这个终结符，即{a}。
A→ε : 空产生式对应的可选集SELECT(A→ε) 就是A的后继符号集，即 FOLLOW(A)。
A→Bβ : B 是非终结符，β 是文法符号串，那么这个产生式的可选集SELECT(A→Bβ) 就是文法符号串Bβ的串首终结符集，即FIRST(Bβ)。

注意，如果FIRST(Bβ)包含空串ε，即文法符号串Bβ能推导出空串ε，那么还要将A的后继符号集添加到产生式对应的可选集中。

可选集算法的具体实现请看求可选集

3.6.4 预测分析表

根据产生式可选集，我们可以构建一个预测分析表，表中的每一行都是一个非终结符，表中的每一列都是一个终结符，包括结束符号 $，而表中的值就是产生式。
这样进行语法推导的时候，非终结符遇到当前输入字符，就可以从预测分析表中获取对应的产生式了。

3.6.5 表驱动的预测分析法

有了预测分析表，我们就可以进行预测分析了，具体流程:

输入: 一个文法符号串 w 和 文法的预测分析表 M

输出：如果w在L(G)中，输出w的最左推导，否则给出错误提示

方法：最初，语法分析器格局如下：输入缓冲区是w$，G的开始符号位于栈顶，器下面是$。下面的程序使用预测分析表M生成了处理输入预测分析过程：

设置ip使它指向w的第一个符号，其中ip是输入指针；
令X=栈顶符号；
while(X != $) { // 栈非空
    if (X 等于ip所指向的符号a)执行栈弹出操作，将ip向前移动一个位置；
    else if（M 是一个终结符号） error();
    else if（M[X，a]是一个报错条目） error();
    else if（M[X，a]= X -> Y1Y2...Yk） {
        输出产生式  X -> Y1Y2...Yk;
        弹出栈顶符号；
        将 Yk...Y2,Y1亚入栈中，其中Y1位于栈顶。
    }
    令X = 栈顶符号
}

可以这么理解：

从文法开始符号起，用它和文法符号串w第一次字符从预测分析表获取对应的产生式。
将这个产生式倒序存入栈中，因为栈是后进先出，倒序就保证了放入的产生式右部第一字符在栈顶，判断一下这个字符:
- 如果与当前文法符号串输入字符相同，那说明匹配，那么栈中弹出这个字符，并读取文法符号串下一次字符。
- 如果与当前文法符号串输入字符不相同，且是一个终结符，那说明语法匹配不成功，直接报错。
- 如果当前文法符号串是个非终结符，那么用它和当前输入符号从预测分析表获取对应的产生式，获取不到直接报错，获取到了，就重复之前步骤。

预测分析法算法的具体实现请看预测分析算法

四. 改造文法

我们知道要实现预测分析，要求相同左部的产生式，它们的可选集是不相交。
但是有的文法结构不符合这个要求，要进行改造。

4.1 提取公因子算法

如果相同左部的多个产生式有共同前缀，那么它们的可选集必然相交。
例如:

文法G
1.  S -> aAa | aBb
2.  A -> c
3.  B -> d

非终结符S 的两个产生式的可选集都是{a}，那么就不能进行预测分析。

那么如何进行改造呢？
其实很简单，进行如下转换:

文法G
1.  S -> aS'
2.  S' -> Aa | Bb
3.  A -> c
4.  B -> d

如此文法的相同左部的产生式，它们的可选集是不相交，符合现预测分析。

其实就是通过改写产生式来推迟决定，等读入了足够多的输入，获得足够信息后再做出正确的选择。

这种改造方法称为提取公因子算法。

提取公因子算法理解起来非常简单，但是想用代码实现，其实还是比较困难的，请看我的另一篇文章，写了一种提取公因子算法的代码实现。

4.2 左递归

当我们自顶向下的语法分析时，就需要采用最左推导方式。
而这个时候，如果产生式左部和产生式右部首字符一样(即A→Aα)，那么推导就可能陷入无限循环。
例如:

文法G
1.  S -> Sa | b

推导
S => Sa => Saa => ... => Sa...a

因此对于:

含有 A→Aα 形式产生式的文法称为是直接左递归。
如果文法中一个非终结符A,存在一步以上的推导，形成了 A =>+ Aα,称为间接左递归。

例如：A→Bβ 和 B -> Aβ 可以得到 A => Bβ => Aββ

文法中不能包含这两种形式，不然最左推导就没办法进行。

那有人问了，如果产生式右部中间包含和产生式左部相同的字符，允不允许呢？

大多数情况下，是允许的，因为我们采用的是最左推导，只要这个产生式右部在这个非终结符之前有其他终结符(即A→αA)，那么就可以确定推导时，用不用这个产生。

如果产生式右部在这个非终结符之前是非终结符(即A→BAβ),那么就要看 B 能不能推导出空串ε 了，如果可以，那么最终还是会推导出 A =>+ Aβ, 也属于间接左递归。

4.2.1 直接左递归

例如:

文法G
1.  S -> Sa | b

它能够推导出如下:

S => b
或者
S => Sa
  => Saa 
  ... 
  => Sa...a 
  => ba..a

你会惊奇的发现，它能推导出 b 和 (a)* (即由0个a或者无数个a生成的文法符号串)。其实就可以改造成:

文法G
1.  S -> bS'
2.  S' -> aA' | ε

S' 就可以表示 (a)* ，因此S'必须有空产生式 S' -> ε，否则就得不到0个a的空串。

因此消除直接左递归 算法的一般形式：

  A -> Aα1 | Aα2 | ... | Aαn | β1 | β2 | ... | βm
(其中这里数字表示下标，而不是一个终结符, α 和 β都是文法符号串)
         (αi != ε, 且 βi 不以A开头)
                改造成
A -> β1A' | β2A' | ... | βmA'
A' ->  Aα1A' | Aα2A' | ... | AαnA' |  ε

消除直接左递归的算法比较简单，具体实现请看消除左递归

4.2.2 间接左递归

例如:

文法G:
1. S -> Aa | b
2. A -> c | Sd

间接左递归
S => Aa
  => Sda
  => Aada
  => Sdada

消除间接左递归的方法就是直接带入消除，即

文法G:
1. S -> Aa | b
2. A -> c | Aad | bd

即将能形成间接左递归产生式中的非终结符，替换成这个非终结符的产生式组。

消除间接左递归算法：

按照某个顺序将非终结符进行排序，为A1,A2,...,An
for (从1到n的每个i) {
      for (从1到i-1的每个j) {
            将每个形如Ai -> Ajβ的产生式,用Aj 的产生式组Aj -> α1 | α2 | ... | αk 替换；
            得到产生式 Ai -> Ajβ 替换后的产生式组 Ai -> α1β | α2β | ... | αkβ。
    }
}

这个算法看起来描述很多，其实理解起来很简单：

先将这些非终结符进行排序，然后开始遍历这些非终结符的产生式组
判断当前非终结符Ai的每一个产生式右部首字符，是不是前面已经遍历过的非终结符Aj 。

这个就是为什么需要对非终结符进行排序
如果是那么就会形成间接左递归，就要用前面非终结符Aj的产生式组当前非终结符Ai这个产生式中的非终结符Aj，这样当前这个产生式变成了多个产生式了。

消除间接左递归的算法，具体实现请看消除左递归

思考: 我们通过 Ai -> Ajβ 来判断是不是间接左递归，那如果有产生式 Ai -> BAjβ 且 B -> ε,那么它是不是间接左递归呢？
间接地我们可以推出如果一个产生式 Ai -> αAjβ 且 FIRST(α) 包括空串ε，那么这个产生式是不是间接左递归。

这个也属于间接左递归，此时要消除间接左递归，要先求串首终结符集 FIRST(α)的值。

编译原理-LL1文法详细讲解

一. `CFG` 分析树

二. 自顶向下分析

2.1 处理选择那个非终结符问题

2.2 处理选择非终结符那个候选式问题

三. 实现预测分析

3.1 S_文法 (简单确定性文法)

3.2 空产生式

3.3 后继符号集

3.4 可选集

3.5 q_文法

3.6 LL(1)文法

3.6.1 串首终结符集

3.6.2 后继符号集

3.6.3 可选集

3.6.4 预测分析表

3.6.5 表驱动的预测分析法

四. 改造文法

4.1 提取公因子算法

4.2 左递归

4.2.1 直接左递归

4.2.2 间接左递归

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

编译原理-LL1文法详细讲解

一. CFG 分析树

二. 自顶向下分析

2.1 处理选择那个非终结符问题

2.2 处理选择非终结符那个候选式问题

三. 实现预测分析

3.1 S_文法 (简单确定性文法)

3.2 空产生式

3.3 后继符号集

3.4 可选集

3.5 q_文法

3.6 LL(1)文法

3.6.1 串首终结符集

3.6.2 后继符号集

3.6.3 可选集

3.6.4 预测分析表

3.6.5 表驱动的预测分析法

四. 改造文法

4.1 提取公因子算法

4.2 左递归

4.2.1 直接左递归

4.2.2 间接左递归

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

一. `CFG` 分析树