语法分析——预测分析程序

LL(1)文法满足下面的条件：

1. 文法不含左递归
2. 对于文法中每一个非终结符A的各个产生式的候选首符集两两不相交。即，若A→α1|α2|...|αn，则FIRST(αi)∩FIRST(αj)=∅ ，其中（i≠j）
3. 对文法中的每个非终结符A，若它存在某个侯选首符集包含ε，则FIRST(A)∩FOLLOW(A)=∅

文法通过左递归消除、消除回溯、提取左公共因子可以满足LL(1)的条件，成为LL(1)文法。

预测分析程序实现步骤：

1. 构造文法非终结符的FIRST集
2. 构造文法非终结符的FOLLOW集
3. 构造文法的预测分析表
4. 构造控制程序

1、构造文法非终结符的FIRST集

假设A有n个侯选α1，α2，...，αn，即A→α1|α2|...|αn。侯选式α的FIRST集形式化描述：FIRST(α)={a | αa...,a∈}，若αε，则ε∈FIRST(α).。那么FIRST(A) = FIRST(α1)∪FIRST(α2)∪...∪FIRST(αn)

实现：

# 求FIRST(α) 用'@'表示'ε'
    def formula_first(self,str):
        first_keys = self.firstSET.keys()
        str_len = len(str)
        if str_len == 1:
            if str in self.terSymbol or str == '@':return [str]
            elif str in first_keys:
                return self.followSET.get(str)
            else:
                return []
        i = 0
        first_set = []
        while i < str_len - 1:
            if str[i] in self.terSymbol:
                if str[i] not in first_set:
                    first_set.append(str[i])
                return first_set
            if str[i+1] == "'":
                if str[i:i+2] in first_keys:
                    str_firstSet = self.firstSET.get(str[i:i+2])
                    for terSym in str_firstSet:
                        if terSym not in first_set:
                            first_set.append(terSym)
                    if '@' not in str_firstSet:
                        return first_set
                    else:
                        for index in range(len(first_set)):
                            if first_set[index] == '@':
                                del first_set[index]
                                break
                        i += 2
                else:
                    return first_set
            else:
                if str[i] in first_keys:
                    str_firstSet = self.