编译原理实验判断ll1文法

### 判断LL(1)文法的方法

为了判断一个给定的上下文无关文法是否为 LL(1)，需要满足特定条件。这些条件主要涉及文法规则中的 FIRST 和 FOLLOW 集合。

#### 定义FIRST集合
对于任何非终结符 A 的每一个产生式的右侧 α，计算其 FIRST(α)[^1]。如果存在 ε 生产，则需进一步考虑后续符号的影响。

#### 计算FOLLOW集合
针对每个非终结符 A，在整个文法范围内查找所有可能跟随在其后的终端符号，并形成 FOLLOW(A) 集合。

#### 检查冲突情况
当且仅当下面两个条件都成立时，该文法才是 LL(1):

- 对于同一个非终结符的不同生产规则，它们左侧相同的情况下，不同生产的右侧对应的 FIRST 集之间无交集；即不存在两个不同的产生式 \(A → α\) 和 \(A → β\), 使得 \(\text{FIRST}(α)\cap\text{FIRST}(β)=∅\)。

- 如果某个产生式可以推出空字符串 (ε)，那么此产生式的 FIRST 集与相应非终结符的 FOLLOW 集也应保持不相交；也就是说，如果有 \(A→α|ε\) ，则要求 \(\text{FIRST}(α)\cap\text{FOLLOW}(A)=∅\)。

通过上述方法来验证一个文法是不是 LL(1) 文法。这通常涉及到手工或借助工具完成对文法结构的具体分析过程。

def is_ll1(grammar):
    first_sets = compute_first_sets(grammar)
    follow_sets = compute_follow_sets(grammar)

    for non_terminal, productions in grammar.items():
        production_firsts = []
        
        for prod in productions:
            this_production_first = set()
            
            if 'epsilon' not in first_sets[prod]:
                this_production_first.update(first_sets[prod])
                
            elif 'epsilon' in first_sets[prod]:
                this_production_first.update(follow_sets[non_terminal])

            production_firsts.append(this_production_first)

        # Check intersection between all pairs of production's FIRST sets.
        for i in range(len(production_firsts)):
            for j in range(i + 1, len(production_firsts)):
                if production_firsts[i].intersection(production_firsts[j]):
                    return False
                
    return True