LL(1) 文法识别工具：快速判断文法类型

private void button4_Click(object sender, EventArgs e)
{
    string text = richTextBox1.Text;
    isLL_1_ ll1 = new isLL_1_(text);
    if (ll1.is_LL == 0)
    {
        MessageBox.Show("输入的文法不符合要求，请重新输入！");
        return;
    }

    // 计算 FIRST 集合
    First first = new First(ll1.LL1Item);
    Dictionary<string, List<string>> firsts = first.getfirsts();

    // 计算 FOLLOW 集合
    Follow follow = new Follow(ll1.LL1Item, first);
    Dictionary<string, List<string>> follows = follow.getfollows();

    // 输出 FIRST 集合和 FOLLOW 集合
    string output = "";
    foreach (string key in firsts.Keys)
    {
        output += "FIRST('" + key + "') = { ";
        foreach (string value in firsts[key])
        {
            output += value + " ";
        }
        output += "}
";
    }
    output += "
";
    foreach (string key in follows.Keys)
    {
        output += "FOLLOW('" + key + "') = { ";
        foreach (string value in follows[key])
        {
            output += value + " ";
        }
        output += "}
";
    }
    richTextBox2.Text = output;

    // 判断是否是 LL(1) 文法
    if (ll1.is_LL == -1)
    {
        MessageBox.Show("该文法不是 LL(1) 文法！");
    }
    else
    {
        MessageBox.Show("该文法是 LL(1) 文法！");
    }
}

class isLL_1_
{
    public LL1Item LL1Item;
    public Dictionary<string, List<string>> product;
    public First first;
    public Follow follow;
    public Select select;
    public int is_LL = 1;

    public isLL_1_(String text)
    {
        LL1Item = new LL1Item(text);
        if (LL1Item.creatproduction() == 1)
        {
            product = LL1Item.getproduction();
            first = new First(LL1Item);
            follow = new Follow(LL1Item, first);
            select = new Select(LL1Item, first, follow);
            Judge();
        }
        else
        {
            is_LL = 0;
        }
    }

    public void Judge()
    {
        foreach (var nofinal in LL1Item.nofinal)
        {
            var pro = select.getselects()[nofinal];
            //遍历该非终结符每个初始状态对应的selects集。
            for (int i = 0; i < pro.Count - 1; i++)
            {
                foreach (var fin in pro.ElementAt(i).Value)
                {
                    int j;
                    for (j = i + 1; j < pro.Count; j++)
                        if (!pro.ElementAt(j).Value.Contains(fin)) break;
                    if (j == pro.Count)
                    {
                        is_LL = -1;
                        return;
                    }
                }
            }
        }
    }
}

class LL1Item
{
    String text;
    public string intinal;
    public List<string> final;
    public List<string> nofinal;
    Dictionary<string, List<string>> production;
    Dictionary<string, bool> is_reach = new Dictionary<string, bool>();

    public LL1Item(string text)
    {
        this.text = text;
        if (creatproduction() == 1)
        {
            is_reachempty();
            intinal = production.First().Key;
            createnofinal();
            createfinial();
        }
    }

    public void createnofinal()
    {
        nofinal = new List<string>();
        foreach (var item in production.Keys)
            nofinal.Add(item);
    }

    public void createfinial()
    {
        final = new List<string>();
        foreach (var item in nofinal)
            foreach (var item2 in production[item])
                foreach (var item3 in item2)
                    if (!char.IsUpper(item3))
                        if (!final.Contains(item3.ToString()))
                            final.Add(item3.ToString());
        if (!final.Contains("#"))
            final.Add("#");
    }

    public int creatproduction()
    {
        production = new Dictionary<string, List<string>>();
        string[] pro = text.Split('
');
        foreach (string s in pro)
        {
            if (s == "") continue;

            Regex.Replace(s, " ", "");
            string[] ga = Regex.Split(s, "->");
            if (ga.Length != 2) return 0;
            if (ga[0].Length == 0 || ga[1].Length == 0)
                return 0;
            if (ga[0].Length != 1 || !char.IsUpper(ga[0][0])) return 0;

            string[] ga2 = Regex.Split(ga[1], "\|");
            if (!production.ContainsKey(ga[0]))
                production.Add(ga[0], new List<string>());
            foreach (string s1 in ga2)
                production[ga[0]].Add(s1);
        }
        return 1;
    }

    public void is_reachempty()
    {
        Dictionary<string, List<string>> productions = new Dictionary<string, List<string>>();
        foreach (var key in production.Keys)
        {
            productions.Add(key, new List<string>());
            foreach (var value in production[key])
                productions[key].Add(value);
        }
        int flag = 0;
        //去除产生式中所有含终结符和#的项
        foreach (var item in productions.Keys)
        {
            flag = 0;
            for (int i = 0; i < productions[item].Count; i++)
            {
                if (productions[item][i].Equals("#"))
                {
                    flag = 1;
                    break;
                }
                else
                    foreach (var newProd in productions[item][i])
                        //如果是终结符
                        if (!char.IsUpper(newProd))
                        {
                            flag = -1;
                            break;
                        }
                if (flag == -1)
                {
                    productions[item].RemoveAt(i);
                    i--;
                }
            }
            //如果该非终结符可直接推出#
            if (flag == 1)
            {
                productions[item] = new List<string>();
                is_reach.Add(item, true);
            }
            //该非终结符的每个产生式中都含有终结符
            else if (productions[item].Count == 0) is_reach.Add(item, false);
        }
        //判断产生式右部中的非终结符能否推出#
        while (true)
        {
            flag = 0;
            foreach (var item in productions.Keys)
            {
                if (is_reach.ContainsKey(item)) continue;
                foreach (string s in productions[item])
                {
                    foreach (var newProd in s)
                    {
                        if (is_reach.ContainsKey(newProd.ToString()))
                            //如果该非终结符能推出#，就将他从产生式中去除
                            if (is_reach[newProd.ToString()])
                            {
                                s.Replace(newProd.ToString(), "");
                                flag = 1;
                            }
                    }
                    if (s.Equals(""))
                    {
                        flag = 1;
                        is_reach.Add(item, true);
                        break;
                    }
                }
            }
            //当产生式不再改变
            if (flag == 0) { break; }
        }
        //添加非终结符的判断结果
        foreach (var item in productions.Keys)
        {
            if (is_reach.ContainsKey(item)) continue;
            is_reach.Add(item, false);
        }
    }

    public Dictionary<string, List<string>> getproduction()
    {
        return production;
    }

    public Dictionary<string, bool> getisreach()
    {
        return is_reach;
    }
}

class First
{
    LL1Item LL1Item;
    Dictionary<string, List<string>> firsts;
    public First(LL1Item LL1Item)
    {
        this.LL1Item = LL1Item;
        firsts = new Dictionary<string, List<string>>();
        foreach (var item in this.LL1Item.getproduction().Keys)
            GetFirst(item);
    }

    void GetFirst(string symbol)
    {
        // 如果该非终结符的 FIRST 集已经被计算出，则直接返回
        if (firsts.ContainsKey(symbol))
        {
            return;
        }
        var production = LL1Item.getproduction();
        var is_reach = LL1Item.getisreach();
        firsts.Add(symbol, new List<string>());
        // 遍历产生式，计算 FIRST 集
        foreach (var prod in production[symbol])
        {
            // 如果产生式首字符为终结符，则直接将其加入 FIRST 集中
            if (prod.Length > 0 && IsTerminal(prod[0]))
            {
                if (!firsts[symbol].Contains(prod[0].ToString()))
                    firsts[symbol].Add(prod[0].ToString());
                continue;
            }
            // 如果产生式首字符为非终结符，则计算该非终结符的 FIRST 集，并将结果加入首字符的 FIRST 集中
            else if (prod.Length > 0 && !IsTerminal(prod[0]))
            {
                GetFirst(prod[0].ToString());
                foreach (var f in firsts[prod[0].ToString()])
                {
                    if (!firsts[symbol].Contains(f) && !f.Equals("#"))
                        firsts[symbol].Add(f);
                }
            }
            //如果第一个非终结符能推出#
            if (LL1Item.getisreach()[prod[0].ToString()])
            {
                // 递归计算第二个和后面的字符的 FIRST 集，并将结果加入该非终结符的 FIRST 集中
                for (int j = 1; j < prod.Length; j++)
                {
                    if (IsTerminal(prod[j]))
                    {
                        if (!firsts[symbol].Contains(prod[j].ToString()))
                            firsts[symbol].Add(prod[j].ToString());
                        break;
                    }
                    GetFirst(prod[j].ToString());
                    foreach (var f in firsts[prod[j].ToString()])
                    {
                        if (!firsts[symbol].Contains(f) && !f.Equals("#"))
                            firsts[symbol].Add(f);
                    }
                    // 如果该非终结符的 FIRST 集没有包含空串，则可以结束循环
                    if (!is_reach[prod[j].ToString()])
                    {
                        break;
                    }
                    // 如果是最后一个字符且所有非终结符的 FIRST 集都含有空串，则将空串加入该非终结符的 FIRST 集中
                    if (j == prod.Length - 1)
                    {
                        if (!firsts[symbol].Contains("#"))
                            firsts[symbol].Add("#");
                    }
                }
            }
        }
    }

    // 判断指定符号是否为终结符
    static bool IsTerminal(char symbol)
    {
        return !char.IsUpper(symbol);
    }

    public Dictionary<string, List<string>> getfirsts()
    {
        return firsts;
    }
}

class Follow
{
    LL1Item LL1Item;
    First first;
    Dictionary<string, List<string>> follows;

    public Follow(LL1Item LL1Item, First first)
    {
        this.LL1Item = LL1Item;
        this.first = first;
        follows = new Dictionary<string, List<string>>();
        foreach (var item in this.LL1Item.getproduction().Keys)
            GetFollow(item);
    }

    void GetFollow(string symbol)
    {
        // 如果该非终结符的 FOLLOW 集已经被计算出，则直接返回
        if (follows.ContainsKey(symbol))
        {
            return;
        }
        var grammar = LL1Item.getproduction();
        var is_reach = LL1Item.getisreach();
        follows.Add(symbol, new List<string>());

        // 将结束符号 # 加入起始符号 intial 的 FOLLOW 集
        if (symbol == LL1Item.intinal)
        {
            follows[symbol].Add("#");
        }

        // 遍历产生式，计算 FOLLOW 集
        foreach (string key in LL1Item.nofinal)
        {
            foreach (var prod in grammar[key])
            {
                for (int i = 0; i < prod.Length; i++)
                {
                    if (prod[i].ToString() == symbol)
                    {
                        // 如果该非终结符在产生式末尾，则将产生式左边非终结符的 FOLLOW 集加入该非终结符的 FOLLOW 集中
                        if (i == prod.Length - 1)
                        {
                            if (key != symbol)
                            {
                                GetFollow(key);
                                foreach (var f in follows[key])
                                {
                                    if (!follows[symbol].Contains(f))
                                        follows[symbol].Add(f);
                                }
                            }
                        }
                        // 如果该非终结符不在产生式末尾（即后面还跟着其他符号）
                        else
                        {
                            // 如果后面是终结符，则直接将其加入该非终结符的 FOLLOW 集中
                            if (IsTerminal(prod[i + 1]) && !follows[symbol].Contains(prod[i + 1].ToString()))
                            {
                                follows[symbol].Add(prod[i + 1].ToString());
                            }
                            // 如果后面是非终结符，则将该非终结符的 FIRST 集加入该非终结符的 FOLLOW 集中，若该非终结符能够推出空，还需将产生式左边的 FOLLOW 集加入
                            else
                            {
                                foreach (var f in first.getfirsts()[prod[i + 1].ToString()])
                                {
                                    if (f != "#")
                                    {
                                        if (!follows[symbol].Contains(f))
                                            follows[symbol].Add(f);
                                    }
                                }
                                if (first.getfirsts()[prod[i + 1].ToString()].Contains("#") && key != symbol)
                                {
                                    GetFollow(key);
                                    foreach (var f in follows[key])
                                    {
                                        if (!follows[symbol].Contains(f))
                                            follows[symbol].Add(f);
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    static bool IsTerminal(char symbol)
    {
        return !char.IsUpper(symbol);
    }

    public Dictionary<string, List<string>> getfollows()
    {
        return follows;
    }
}