C# 实现 LL(1) 文法判定：简明代码示例

以下是一个用 C# 实现的 LL(1) 文法最简判定代码，包含了文法的定义、FIRST 集和 FOLLOW 集的计算以及判定函数的实现。

using System;
using System.Collections.Generic;
using System.Linq;

class Grammar
{
    // 文法规则
    private Dictionary<string, List<string>> rules = new Dictionary<string, List<string>>();

    // FIRST 集
    private Dictionary<string, HashSet<string>> first = new Dictionary<string, HashSet<string>>();

    // FOLLOW 集
    private Dictionary<string, HashSet<string>> follow = new Dictionary<string, HashSet<string>>();

    // 添加规则
    public void AddRule(string left, string right)
    {
        if (!rules.ContainsKey(left))
            rules[left] = new List<string>();

        rules[left].Add(right);
    }

    // 计算 FIRST 集
    private void CalculateFirst()
    {
        foreach (var rule in rules)
            first[rule.Key] = new HashSet<string>();

        bool changed;
        do
        {
            changed = false;
            foreach (var rule in rules)
            {
                foreach (var right in rule.Value)
                {
                    if (right.Length == 0)
                    {
                        if (first[rule.Key].Add(""))
                            changed = true;
                    }
                    else if (char.IsLower(right[0]))
                    {
                        if (first[rule.Key].Add(right[0].ToString()))
                            changed = true;
                    }
                    else if (char.IsUpper(right[0]))
                    {
                        bool epsilon = true;
                        foreach (var c in right)
                        {
                            if (!first[c.ToString()].Contains(""))
                            {
                                epsilon = false;
                                if (first[rule.Key].UnionWith(first[c.ToString()]))
                                    changed = true;
                                break;
                            }
                            else
                            {
                                if (first[rule.Key].ExceptWith(first[c.ToString()]))
                                    changed = true;
                            }
                        }
                        if (epsilon && first[rule.Key].Add(""))
                            changed = true;
                    }
                }
            }
        } while (changed);
    }

    // 计算 FOLLOW 集
    private void CalculateFollow()
    {
        foreach (var rule in rules)
            follow[rule.Key] = new HashSet<string>();

        if (rules.ContainsKey("S"))
            follow["S"].Add("$");

        bool changed;
        do
        {
            changed = false;
            foreach (var rule in rules)
            {
                foreach (var right in rule.Value)
                {
                    for (int i = 0; i < right.Length; i++)
                    {
                        if (!char.IsUpper(right[i]))
                            continue;

                        var A = right[i].ToString();
                        var B = i == right.Length - 1 ? rule.Key : right[i + 1].ToString();

                        bool epsilon = true;
                        for (int j = i + 1; j < right.Length; j++)
                        {
                            if (!first[right[j].ToString()].Contains(""))
                            {
                                epsilon = false;
                                if (follow[A].UnionWith(first[right[j].ToString()]))
                                    changed = true;
                                break;
                            }
                            else
                            {
                                if (follow[A].ExceptWith(first[right[j].ToString()]))
                                    changed = true;
                            }
                        }
                        if (epsilon && follow[A].UnionWith(follow[rule.Key]))
                            changed = true;

                        if (i == right.Length - 1)
                        {
                            if (follow[A].UnionWith(follow[rule.Key]))
                                changed = true;
                        }
                        else if (first[B].Contains(""))
                        {
                            if (follow[A].UnionWith(follow[B]))
                                changed = true;
                        }
                    }
                }
            }
        } while (changed);
    }

    // 判断是否是 LL(1) 文法
    public bool IsLL1()
    {
        CalculateFirst();
        CalculateFollow();

        foreach (var rule in rules)
        {
            var P = rule.Key;
            var alpha = rule.Value;

            for (int i = 0; i < alpha.Count; i++)
            {
                var a = alpha[i][0].ToString();
                var A = first[a].Contains("") ? follow[P] : new HashSet<string>(first[a]);

                for (int j = i + 1; j < alpha.Count; j++)
                {
                    var b = alpha[j][0].ToString();
                    var B = first[b].Contains("") ? follow[P] : new HashSet<string>(first[b]);

                    if (A.Intersect(B).Any())
                        return false;
                }
            }
        }

        return true;
    }
}

class Program
{
    static void Main()
    {
        // 示例：文法 S->aSb|ε
        var grammar = new Grammar();
        grammar.AddRule("S", "aSb");
        grammar.AddRule("S", "");
        Console.WriteLine(grammar.IsLL1()); // 输出 True
    }
}

在这个实现中，我们首先定义了一个 Grammar 类来表示文法，并提供了添加规则、计算 FIRST 集、计算 FOLLOW 集和判断是否是 LL(1) 文法的方法。在添加规则时，我们使用了一个 Dictionary 来存储每个非终结符对应的产生式列表。在计算 FIRST 集和 FOLLOW 集时，我们使用了两个 Dictionary 分别存储每个非终结符的 FIRST 集和 FOLLOW 集。计算 FIRST 集和 FOLLOW 集的方法采用了迭代的方式，直到不再发生改变为止。

在判断是否是 LL(1) 文法时，我们首先计算了所有的 FIRST 集和 FOLLOW 集，然后对于每个非终结符的每个产生式，计算了它的 FIRST 集和后继产生式的 FIRST 集的交集。如果任意两个产生式的 FIRST 集的交集不为空，则该文法不是 LL(1) 文法，否则是 LL(1) 文法。