LL(1) 文法判定工具 - C# 代码实现

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.IO;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
using System.Windows.Forms;
using static System.Windows.Forms.VisualStyles.VisualStyleElement;

namespace byyljxfzxt
{
    public partial class Form4 : Form
    {
        public Form4()
        {
            InitializeComponent();
        }

        //--------------------预处理
        Dictionary<string, List<string>> production;
        Dictionary<string, List<string>> firsts;
        Dictionary<string, List<string>> follows;
        List<string> terminals;
        List<string> nonterminals;

        private void groupBox1_Enter(object sender, EventArgs e)
        {

        }

        private void button3_Click(object sender, EventArgs e)
        {
            richTextBox1.Text = "";
            OpenFileDialog openFileDialog1 = new OpenFileDialog();
            DialogResult dr = openFileDialog1.ShowDialog();
            string filename = openFileDialog1.FileName;//获取或设置一个包含在文件对话框中选定的文件名字符串
            if (dr == DialogResult.OK && !string.IsNullOrEmpty(filename))
            {
                StreamReader sr = new StreamReader(filename);
                richTextBox1.Text = sr.ReadToEnd();
                sr.Close();
            }
        }

        private void Form4_Load(object sender, EventArgs e)
        {

        }

        private void button4_Click(object sender, EventArgs e)
        {
            string text = richTextBox1.Text;
            production = new Dictionary<string, List<string>>();
            string[] pro = text.Split('\n');
            foreach (string s in pro)
            {
                if (s == "") continue;

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

                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);
            }

            firsts = new Dictionary<string, List<string>>();
            foreach (var item in production.Keys)
                GetFirst(item, production, firsts);

            follows = new Dictionary<string, List<string>>();
            foreach (var item in production.Keys)
                GetFollow(item, production, firsts, follows);

            if (JudgeLL1(production, firsts, follows))
            {
                MessageBox.Show("该文法是LL(1)文法\n");
                
            }
            else
            {
                MessageBox.Show("该文法不是LL(1)文法，存在左递归或者存在FIRST集合有交集的情况！\n");
            }
            button1.Enabled = true;
            button2.Enabled = true;
            button3.Enabled = true;

        }

        private void button6_Click(object sender, EventArgs e)
        {
            
        }

        private void button5_Click(object sender, EventArgs e)
        {
            SaveFileDialog saveFileDialog = new SaveFileDialog();
            saveFileDialog.Filter = "Text files (*.txt)|*.txt|All files (*.*)|*.*";
            saveFileDialog.FileName = "Grammer.txt"; // 设置默认文件名
            if (saveFileDialog.ShowDialog() == DialogResult.OK)
            {
                string filename = saveFileDialog.FileName;
                File.WriteAllText(filename, richTextBox1.Text);
                MessageBox.Show("文件已成功保存至：" + filename);
            }
        }

        private void button1_Click(object sender, EventArgs e)
        {
            // 获取所有的符号集合
            List<string> symbols = new List<string>();
            foreach (var item in production.Keys)
            {
                if (!symbols.Contains(item))
                    symbols.Add(item);
                foreach (var prod in production[item])
                {
                    foreach (var c in prod)
                    {
                        if (!symbols.Contains(c.ToString()))
                            symbols.Add(c.ToString());
                    }
                }
            }
            // 将符号集合按照终结符和非终结符分开
            nonterminals = new List<string>();
            terminals = new List<string>();
            foreach (var s in symbols)
            {
                if (char.IsUpper(s[0]))
                    nonterminals.Add(s);
                else
                    terminals.Add(s);
            }

            listView1.Columns.Clear();
            listView1.Items.Clear();
            listView1.View = View.Details;

            // 添加第一列
            listView1.Columns.Add("", 30);

            // 添加终结符列
            foreach (var item in terminals)
            {
                listView1.Columns.Add(item, 30);
            }

            // 添加非终结符行
            foreach (var item in nonterminals)
            {
                ListViewItem lvi = new ListViewItem(item);
                lvi.SubItems.Add("");
                foreach (var t in terminals)
                {
                    lvi.SubItems.Add("");
                }
                listView1.Items.Add(lvi);
            }

            // 填充表格
            foreach (var item in firsts)
            {
                int row = nonterminals.IndexOf(item.Key);
                foreach (var t in terminals)
                {
                    int col = terminals.IndexOf(t);
                    if(!item.Value.Contains(t))
                        listView1.Items[row].SubItems[col + 1].Text = "0";
                    else
                        listView1.Items[row].SubItems[col + 1].Text = "1";
                }
            }
        }

        private void button2_Click(object sender, EventArgs e)
        {
            // 获取所有的符号集合
            List<string> symbols = new List<string>();
            foreach (var item in production.Keys)
            {
                if (!symbols.Contains(item))
                    symbols.Add(item);
                foreach (var prod in production[item])
                {
                    foreach (var c in prod)
                    {
                        if (!symbols.Contains(c.ToString()))
                            symbols.Add(c.ToString());
                    }
                }
            }
            // 将符号集合按照终结符和非终结符分开
            nonterminals = new List<string>();
            terminals = new List<string>();
            foreach (var s in symbols)
            {
                if (char.IsUpper(s[0]))
                    nonterminals.Add(s);
                else
                    terminals.Add(s);
            }

            foreach (var s in nonterminals)
            {
               System.Console.WriteLine(s);
            }

            foreach(var s in terminals)
            {
                System.Console.WriteLine(s);
            }

            listView2.Columns.Clear();
            listView2.Items.Clear();
            listView2.View = View.Details;

            // 添加第一列
            listView2.Columns.Add("", 30);

            // 添加终结符列
            foreach (var item in terminals)
            {
                listView2.Columns.Add(item, 30);
            }

            // 添加非终结符行
            foreach (var item in nonterminals)
            {
                ListViewItem lvi = new ListViewItem(item);
                lvi.SubItems.Add("");
                foreach (var t in terminals)
                {
                    lvi.SubItems.Add("");
                }
                listView2.Items.Add(lvi);
            }

            // 填充表格
            foreach (var item in follows)
            {
                int row = nonterminals.IndexOf(item.Key);
                foreach (var t in terminals)
                {
                    int col = terminals.IndexOf(t);
                    if (!item.Value.Contains(t))
                        listView2.Items[row].SubItems[col + 1].Text = "0";
                    else
                        listView2.Items[row].SubItems[col + 1].Text = "1";
                }
            }
        }


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

        // 判断一个字符是否为终结符
        private bool IsTerminal(char c)
        {
            if (char.IsUpper(c))
                return false;
            return true;
        }

        // 判断一个非终结符是否能推出空串
        private bool IsReachEmpty(string symbol, Dictionary<string, List<string>> production1)
        {
            if (!production1.ContainsKey(symbol))
                return false;
            foreach (var prod in production1[symbol])
            {
                if (prod.Equals("#"))
                    return true;
                bool flag = true;
                for (int i = 0; i < prod.Length; i++)
                {
                    if (!IsReachEmpty(prod[i].ToString(), production1))
                    {
                        flag = false;
                        break;
                    }
                }
                if (flag)
                    return true;
            }
            return false;
        }

        // 计算 FOLLOW 集
        private void GetFollow(string symbol, Dictionary<string, List<string>> production1, Dictionary<string, List<string>> firsts1, Dictionary<string, List<string>> follows1)
        {
            // 如果该非终结符的 FOLLOW 集已经被计算出，则直接返回
            if (follows1.ContainsKey(symbol))
            {
                return;
            }
            follows1.Add(symbol, new List<string>());
            // 如果是起始符号，则将 $ 加入 FOLLOW 集中
            if (symbol.Equals(production1.Keys.First()))
            {
                if (!follows1[symbol].Contains("$"))
                    follows1[symbol].Add("$");
            }
            // 遍历产生式，计算 FOLLOW 集
            foreach (var item in production1)
            {
                foreach (var prod in item.Value)
                {
                    int index = prod.IndexOf(symbol);
                    if (index == -1)
                        continue;
                    // 如果该非终结符位于产生式末尾，则将产生式左部的 FOLLOW 集加入该非终结符的 FOLLOW 集中
                    if (index == prod.Length - 1)
                    {
                        GetFollow(item.Key, production1, firsts1, follows1);
                        foreach (var f in follows1[item.Key])
                        {
                            if (!follows1[symbol].Contains(f))
                                follows1[symbol].Add(f);
                        }
                    }
                    else
                    {
                        // 如果该非终结符后面是终结符，则将该终结符加入该非终结符的 FOLLOW 集中
                        if (IsTerminal(prod[index + 1]))
                        {
                            if (!follows1[symbol].Contains(prod[index + 1].ToString()))
                                follows1[symbol].Add(prod[index + 1].ToString());
                        }
                        // 如果该非终结符后面是非终结符，则将该非终结符的 FIRST 集加入该非终结符的 FOLLOW 集中
                        else
                        {
                            GetFirst(prod[index + 1].ToString(), production1, firsts1);
                            foreach (var f in firsts1[prod[index + 1].ToString()])
                            {
                                if (!f.Equals("#") && !follows1[symbol].Contains(f))
                                    follows1[symbol].Add(f);
                            }
                            // 如果该非终结符后面的所有符号都能推出空串，则将产生式左部的 FOLLOW 集加入该非终结符的 FOLLOW 集中
                            if (IsReachEmpty(prod[index + 1].ToString(), production1))
                            {
                                GetFollow(item.Key, production1, firsts1, follows1);
                                foreach (var f in follows1[item.Key])
                                {
                                    if (!follows1[symbol].Contains(f))
                                        follows1[symbol].Add(f);
                                }
                            }
                        }
                    }
                }
            }
        }

        // 判断一个文法是否是 LL(1) 文法
        private bool JudgeLL1(Dictionary<string, List<string>> production1, Dictionary<string, List<string>> firsts1, Dictionary<string, List<string>> follows1)
        {
            foreach (var item in production1)
            {
                Dictionary<string, List<string>> map = new Dictionary<string, List<string>>();
                foreach (var prod in item.Value)
                {
                    List<string> list = new List<string>();
                    foreach (var c in prod)
                    {
                        if (IsTerminal(c))
                        {
                            list.Add(c.ToString());
                            break;
                        }
                        else
                        {
                            GetFirst(c.ToString(), production1, firsts1);
                            foreach (var f in firsts1[c.ToString()])
                            {
                                if (!f.Equals("#") && !list.Contains(f))
                                    list.Add(f);
                            }
                            if (!IsReachEmpty(c.ToString(), production1))
                                break;
                        }
                    }
                    if (list.Contains("#"))
                    {
                        GetFollow(item.Key, production1, firsts1, follows1);
                        foreach (var f in follows1[item.Key])
                        {
                            if (!list.Contains(f))
                                list.Add(f);
                        }
                    }
                    string key = string.Join("", list.ToArray());
                    if (map.ContainsKey(key))
                        return false;
                    map.Add(key, list);
                }
            }
            return true;
        }

    }
}

在上述代码中加入对终结符#的判断和使用内容：GetFollow方法来计算FOLLOW集合，修改后的代码如下：

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