本程序实现根据给定的文法自动改造文法(消除左递归、消除回溯)、生成预测分析表,判断给定的句子是不是给定文法的合法句子、给定文法是不是LL1文法等。本文涉及到的知识有非递归的预测分析法文法转换LL(1) 文法FIRST集和FOLLOW集的计算自顶向下分析概述等,如本文中有不明白的地方可以先查看以上文章。

LL1预测分析法实现步骤

1)构造文法
2)改造文法:消除二义性、消除左递归、消除回溯
3)求每个变量的FIRST集和FOLLOW集,从而求得每个候选式的SELECT集
4)检查是不是 LL(1) 文法。若是,构造预测分析表(本文使用的判断方法不同,本文通过先构造分析表然后再看分析表中是否存在一个项目对应多个产生式的情况,如果存在则表明该文法不是LL1文法,反之是LL1文法)。
5)对于递归的预测分析,根据预测分析表为每一个非终结符编写一个过程;对于非递归的预测分析,实现表驱动的预测分析算法(在本文中使用非递归的预测分析法)。

递归的预测分析法vs.非递归的预测分析法

递归的预测分析法 非递归的预测分析法
程序规模 程序规模较大, 不需载入分析表 主控程序规模较小, 需载入分析表(表较小)
直观性 较好 较差
效率 较低 分析时间大约正比于待分 析程序的长度
自动生成 较难 较易

非递归的预测分析法

非递归的预测分析不需要为每个非终结符编写递归下降过程,而是根据预测分析表构造一个自动机,也叫表驱动的预测分析。

本程序使用到的主要函数如下:

no_left_recursion()函数:消除左递归的函数(实现起来可能会麻烦,需要理解)

no_flash_back()函数:消除回溯的函数(实现起来也比较麻烦,在网上也找不到相应的算法实现,只有理论性的东西)

first(X)函数:返回文法符号X的first集。

multi_first(β)函数:返回文法符号串β的first集。

follow(A)函数:返回非终结符A的follow集。

select(p)函数:返回产生式p的select集。

is_ll1()函数:判断给定的文法是否为LL1文法。

analysis_table()函数:构造并返回预测分析表M。

analyze(statement)函数:分析给定的句子,如果该句子是输入文法的一个合法句子则输出分析过程中用到的产生式。

消除左递归算法

  • 输入:不含循环推导(即形如A =>+ A的推导)和ε-产生式的文法G
  • 输出:等价的无左递归文法(产生式)
  • 方法:
按照某个顺序将非终结符号排序为A1,A2,… ,An .
 for ( 从1到n的每个i ) {
     for ( 从1到i -1的每个i ) {
        将每个形如Ai → Aj γ的产生式替换为产生式组 Ai → δ1 γ∣δ2 γ∣…∣δk γ ,
        其中Aj → δ1∣δ2∣… ∣δk ,是所有的Aj 产生式
    }
    消除Ai 产生式之间的立即左递归
 }

对应python代码

# 消除左递归:如果可以使用该函数则返回对应的等价无递归文法,否则返回None
    def no_left_recursion(self):
        vn = self.grammar["vn"]
        length = len(vn)
        production = self.production
        # 为了防止非终结符重复,消除左递归时引入中文作为非终结符
        ch = self.ch
        # 消除间接左递归
        for i in range(length):  # 遍历所有非终结符
            for j in range(i):  # 遍历前面的非终结符
                for k in production:
                    added_arr = []
                    if len(k.get("right")) == 0:  # 跳过空产生式
                        continue
                    if vn[i] == k.get("left") and vn[j] == k.get("right")[0]:
                        # 将每个形如Ai → Aj γ的产生式替换为产生式组 Ai → δ1 γ∣δ2 γ∣…∣δk γ
                        for li in production:
                            if li.get("left") == vn[j]:
                                right = li.get("right")
                                if len(k.get("right")) > 1:  # 表示γ 不为空
                                    new_right = right + k.get("right")[1:]
                                    added_arr.append({
                                        "left": vn[i],
                                        "right": new_right
                                    })
                                else:  # 长度为1,表示γ 为空
                                    added_arr.append({
                                        "left": vn[i],
                                        "right": right
                                    })
                        production.extend(added_arr)
                        production.remove(k)
            # 消除直接左递归
            flag = False  # 标识A是否存在左递归
            for p in production:
                left = p.get("left")
                right = p.get("right")
                if len(right) > 1:
                    if left == vn[i] and right[0] == vn[i]:
                        flag = True
                        break
            if flag:
                added_arr = []
                remove_arr = []
                for p in production:
                    left = p.get("left")
                    right = p.get("right")
                    if left == vn[i]:
                        if len(right) == 0:  # 产生式右部为空
                            added_arr.append({
                                "left": vn[i],
                                "right": right + ch
                            })
                            remove_arr.append(p)
                        else:  # 产生式右部非空
                            if right[0] == vn[i]:  # 表示左递归产生式
                                if len(right) > 1:
                                    added_arr.append({
                                        "left": ch,
                                        "right": right[1:] + ch
                                    })
                                    remove_arr.append(p)
                            else:  # 非左递归
                                added_arr.append({
                                    "left": vn[i],
                                    "right": right + ch
                                })
                                remove_arr.append(p)
                production.extend(added_arr)
                production.append({
                    "left": ch,
                    "right": ""
                })
                for r in remove_arr:
                    production.remove(r)
                vn.append(ch)
                ch = chr(ord(ch) + 1)  # 改变非终结符
        return production

提取左公因子算法(消除回溯)

  • 输入:文法G

  • 输出:等价的提取了左公因子的文法

  • 方法:

    对于每个非终结符A,找出它的两个或多个选项之间的最长公共前缀α。如果α ≠ ε,
    即存在一个非平凡的( nontrivial )公共前缀,那么将所有A-产生式
    A → α β1 | α β2 | … | α βn | γ1 | γ2 | … | γm
    替换为
    A → α A' | γ1 | γ2 | … | γm
    A' → β1 | β2 | … | βn
    其中, γi 表示所有不以α开头的产生式体; A'是一个新的非终结符。不断应用这个
    转换,直到每个非终结符的任意两个产生式体都没有公共前缀为止

对应python代码

   # 消除回溯
    def no_flash_back(self):
        production = []
        vn = self.grammar["vn"]
        for i in vn:  # 遍历所有非终结符
            temp = []  # 存放所有i非空产生式
            for j in self.production:
                if j.get("left") == i:
                    right = j.get("right")
                    if len(right) > 0:
                        temp.append(j)
            self.no_back(temp, i)  # 去除终结符i回溯
            production.extend(temp)

    # 去除产生式左部为left的非终结符的回溯
    def no_back(self, production, left):
        self.ch = chr(ord(self.ch) + 1)
        rights = []  # left对应的产生式右部
        for i in production:  # 遍历所有产生式,将其右部添加到rights
            if i.get("left") == left:
                rights.append(i.get("right"))
        f_set = set()  # 获取第一个字符
        for i in rights:
            if len(i) > 0:
                f_set.add(i[0])
            else:
                f_set.add("")
        f_list = []
        for i in rights:
            if len(i) > 0:
                f_list.append(i[0])
            else:
                f_list.append("")
        for i in f_set:
            count = f_list.count(i)
            if count > 1:  # 说明有公共前缀,则需要将有该前缀的产生式右部更改
                # 例如A→a|ab|ac|abc|acb|b 更改为 A→aS|b ,其中S→ε|b|c|bc|cb
                added_arr = []  # 需要添加到产生式中的列表(数组) 例如S→ε
                remove_arr = []  # 需要删除的产生式列表例如:A→a
                is_first = True  # 由于项A→aS需要添加到产生式中且只需要一次,这个就是标识是否已经添加了该产生式
                for j in production:  # 遍历所有的left产生式
                    if j.get("left") == left:  # 获取当前需要处理的非终结符产生式
                        right = j.get("right")  # 获取产生式右部
                        length = len(right)
                        if length > 0 and right[0] == i:  # A→a|ab...
                            if is_first:
                                added_arr.append({
                                    "left": left,
                                    "right": right[0] + self.ch
                                })
                                self.grammar["vn"].append(self.ch)
                                is_first = False
                            if length == 1:  # A→a
                                added_arr.append({
                                    "left": self.ch,
                                    "right": ""
                                })
                                remove_arr.append(j)
                            else:  # A→ab
                                added_arr.append({
                                    "left": self.ch,
                                    "right": right[1:]
                                })
                                remove_arr.append(j)
                production.extend(added_arr)
                for r in remove_arr:
                    production.remove(r)
                self.no_back(production, self.ch)  # 由于新添加的非终结符也可能回溯,所以也需要去除

计算文法符号X的FIRST(X)

不断应用下列规则,直到没有新的终结符或ε可以被加入到任何FIRST集合中为止

  • 如果X是一个终结符,那么FIRST ( X ) = { X }
  • 如果X是一个非终结符,且 X→Y1…Yk∈P (k≥1),那么如果对于某个i,a在FIRST (Yi ) 中且ε 在所有的FIRST(Y1) , … , FIRST(Yi-1)中(即Y1...Yi-1 => * ε ),就把a加入到FIRST( X )中。如果对于所有的 j = 1,2, . . . , k,ε在FIRST(Yj)中,那么将ε加入到FIRST( X )
  • 如果 X→ε∈P,那么将ε加入到FIRST( X )中

对应的python代码

 # 求文法符号x的first集合
    def first(self, x):
        result = []  # 所求的first集
        if x in self.grammar["vt"]:  # 终结符的first集为该终结符组成的集合
            result.append(x)
        elif x in self.grammar["vn"]:  # 非终结符
            for i in self.production:  # 遍历所有产生式
                if i.get("left") == x:  # 该产生式左部为所求x
                    right = i.get("right")  # 获取产生式右部
                    if right == "":  # 产生式右部为空,直接将空添加到first集中
                        result.append("")
                    else:
                        s = right[0]  # 产生式右部不为空则需要考虑第一个符号
                        if s in self.grammar["vt"]:  # 如果是终结符则直接添加到first集中
                            result.append(s)
                        else:  # 如果是非终结符,则需要判断其是否可以推导出空串
                            length = len(right)  # 获取产生式右部长度
                            for ly in range(length):  # 遍历产生式右部所有的文法符号
                                if "" in self.first(right[ly]):  # 如果yi可以推导出空串则后面一个(yi+1)文法符号的first集添加到first集中
                                    if ly != length - 1:  # 当然不能超出索引范围
                                        temp = self.first(right[ly + 1])
                                        if "" in temp:  # 如果有空串则去掉
                                            temp.remove("")
                                        result.extend(temp)
                                    else:  # 表明产生式右部所有的文法符号都可以推导出空串,将空串添加到first集中
                                        result.append("")
                                else:  # 如果yi不能推导出空串则需要跳出循环,在此之前需要把当前文法符号的first集添加到first集中
                                    temp = self.first(right[ly])
                                    result.extend(temp)
                                    break
        return list(set(result))  # 去除重复元素

计算串X1X2 …Xn的FIRST 集合

  • 向FIRST(X1X2…Xn)加入FIRST(X1)中所有的非ε符号
  • 如果ε在FIRST(X1)中,再加入FIRST(X2)中的所有非ε符号;
  • 如果ε在FIRST(X1)和FIRST(X2)中,再加入FIRST(X3)中的所有非ε符号,以此类推
  • 最后,如果对所有的i,ε都在FIRST(Xi)中,那么将ε加入到
    FIRST(X1X2…Xn) 中

对应的python代码

 # 求文法符号串x的first集合
    def multi_first(self, x):
        result = []
        first_0 = self.first(x[0])
        result.extend(first_0)  # 将第一个文法符号的first集添加到first集中
        if "" in first_0:  # 如果第一个文法符号的first集中存在空串
            first_0.remove("")  # 将空串删除
            result.extend(first_0)  # 将第一个文法符号的first集添加到first集中
            length = len(x)
            for i in range(0, length):  # 遍历所有的文法符号
                if "" in self.first(x[i]):  # 如果空串在某个文法符号的first集中,则需要将其后面文法符号的first集中非空元素添加到first集中
                    if (i + 1) != length:  # 不是最后一个文法符号
                        temp = self.first(x[i + 1])
                        temp.remove("")
                        result.extend(temp)
                    else:  # 此处表明所有文法符号的first集中都存在空串,需要将空串添加到first集中
                        result.append("")
                else:
                    break
        else:  # 没有空串的话就直接添加到first集中
            result.extend(first_0)
        return list(set(result))  # 去除重复元素  

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

  • FOLLOW(A):可能在某个句型中紧跟在A后边的终结符a的集合
  • FOLLOW(A)={a| S => αAaβ, a∈VT,α,β∈(VT∪VN)}
  • 如果A是某个句型的的最右符号,则将结束符“$”添加到FOLLOW(A)中

算法

不断应用下列规则,直到没有新的终结符可以被加入到任何FOLLOW集合中为止

  • 将$放入FOLLOW( S )中,其中S是开始符号,$是输入右端的结束标记
  • 如果存在一个产生式A→αBβ,那么FIRST ( β )中除ε 之外的所有符号都在FOLLOW( B )中
  • 如果存在一个产生式A→αB,或存在产生式A→αBβ且FIRST ( β ) 包含ε,那么 FOLLOW( A )中的所有符号都在FOLLOW( B )中
# 求文法符号x的follow集
    def follow(self, x):
        result = []  # follow集合
        if x == "S'":  # 如果是文法开始符号则将$添加到follow集中
            result.append("$")
        for i in self.production:  # 遍历所有的产生式
            right = i.get("right")  # 获取产生式右部
            length = len(right)
            for j in range(length):
                if right[j] == x:  # 找到文法符号的位置
                    if (j + 1) == length:  # 如果文法符号在末尾,则将产生式左部文法符号的follow集添加到follow集中
                        if i.get("left") == x:  # 如果最后为x的话会进入无限循环,所以要跳出T' → *FT'
                            break
                        result.extend(self.follow(i.get("left")))
                    else:
                        temp = self.multi_first(right[j + 1:])  # 将其后的文法符号串的first集非空元素添加到follow集中
                        if "" in temp:  # 存在空串
                            temp.remove("")
                            result.extend(temp)
                            result.extend(self.follow(i.get("left")))
                        else:  # 不存在空串直接添加
                            result.extend(temp)
                    break  # 操作完需要跳出循环
        return list(set(result))  # 可能存在重复元素,所以使用set去重

产生式的可选集

产生式A→β的可选集是指可以选用该产生式进行推导时对应的输入符号的集合,记为SELECT( A→β )

  • SELECT( A→aβ ) = { a }

  • SELECT( A→ε )=FOLLOW( A )

  • 如果 ε∉FIRST(α), 那么SELECT(A→α)= FIRST(α)

  • 如果 ε∈FIRST(α), 那么SELECT(A→α)=( FIRST(α)-{ε})∪FOLLOW(A)

# 返回产生式p的select集
    def select(self, p):
        alf = p.get("right")
        a = p.get("left")
        if alf == "":  # SELECT( A→ε )=FOLLOW( A )
            return self.follow(a)
        if alf[0] in self.grammar["vt"]:  # SELECT( A→aβ ) = { a }
            return [alf[0]]
        m_alf = self.multi_first(alf)
        if "" not in m_alf:  # 如果空串不在在first(α)中则SELECT(A→α)= FIRST(α)
            return m_alf
        else:  # 如果空串在first(α)中则SELECT(A→α)=( FIRST(α)-{ε} )∪FOLLOW(A)
            m_alf.remove("")
            m_alf.extend(self.follow(a))
            return m_alf

is_ll1函数

根据构造的分析表判断是否为LL1文法,如果某个位置对应两条以上产生式则表明该文法不是LL1文法,反之则是。

对应python代码

    def is_ll1(self):
        for i in self.analysis_table():
            for j in i:
                if len(j) > 1:
                    return False
        return True

analysis_table()函数

构造预测分析表M,方法也很简单,首先获得产生式的select集,然后将产生式添加到左部和select集元素对应的项目上即可。

对应python代码

    def analysis_table(self):
        table = []  # 分析表:二位数组,每一行表示非终结符,每一列表示终结符,而每个元素则是一个数组,存放产生式
        vn = self.grammar["vn"]
        vt = self.grammar["vt"]
        len1 = len(vn)
        len2 = len(vt)
        for i in range(len1):  # 初始化table
            temp = []
            for j in range(len2):
                temp.append([])
            table.append(temp)
        for i in self.production:  # 遍历所有产生式,将其添加到table中
            left = i.get("left")
            s = self.select(i)  # 获取产生式select集
            for j in s:  # 遍历select集
                table[vn.index(left)][vt.index(j)].append(i)
        return table

analyze()函数

分析某个句子是否为给定文法的合法句子。

    def analyze(self, statement):
        table = self.analysis_table()
        vt = self.grammar["vt"]
        vn = self.grammar["vn"]
        stack = ["$", self.grammar["start"]]
        for i in statement:  # 遍历输入的每个符号
            while True:
                top = stack[len(stack) - 1]  # 栈顶符号
                if top in vn:  # 栈顶符号是终结符则需要选择产生式替换栈顶符号
                    p = table[vn.index(top)][vt.index(i)][0]
                    stack.pop()
                    right = p.get("right")
                    length = len(right)
                    for j in range(length - 1, -1, -1):
                        stack.append(right[j])
                    print(p.get("left") + "→" + p.get("right"))
                elif top in vt:
                    if top == i:  # 匹配成功
                        stack.pop()  # 弹出栈顶符号,并跳出循环接收下一个字符
                        break
                    else:  # 匹配错误
                        raise Exception("匹配错误")
                else:  # 不是终结符也不是非终结符表示输入符号非法
                    raise Exception("输入符号非法")

完整源代码可以在微信公众号小海电脑回复LL1语法分析获取。

最后修改日期:2020年6月7日

留言

撰写回覆或留言