C#实现LR(0)文法分析表生成算法

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;
using System.Windows.Forms;

namespace byyljxfzxt
{
    public partial class Form5 : Form
    {
        // ... 其他代码 ...

        private void button4_Click(object sender, EventArgs e)
        {
            // 初始化FIRST集、FOLLOW集和分析表
            Dictionary<string, List<string>> first = new Dictionary<string, List<string>>();
            Dictionary<string, List<string>> follow = new Dictionary<string, List<string>>();
            Dictionary<string, Dictionary<string, List<string>>> table = new Dictionary<string, Dictionary<string, List<string>>>();

            // 计算FIRST集
            foreach (var item in production)
            {
                string left = item.Key;
                List<string> rightList = item.Value;
                if (!first.ContainsKey(left))
                    first.Add(left, new List<string>());

                foreach (string right in rightList)
                {
                    // 处理形如 A -> a 的产生式
                    if (right.Length == 1 && !char.IsUpper(right[0]))
                    {
                        if (!first[left].Contains(right))
                            first[left].Add(right);
                    }
                    // 处理形如 A -> BCD 的产生式
                    else if (right.Length > 1)
                    {
                        for (int i = 0; i < right.Length; i++)
                        {
                            string beta = right.Substring(i);

                            // 处理形如 A -> aBCD 的产生式
                            if (!char.IsUpper(right[i]))
                            {
                                if (!first[left].Contains(right[i].ToString()))
                                    first[left].Add(right[i].ToString());
                                break;
                            }
                            // 处理形如 A -> BCD 的产生式
                            else if (char.IsUpper(right[i]))
                            {
                                if (!first.ContainsKey(right[i].ToString()))
                                    break;
                                else
                                {
                                    // 将 FIRST(B) 加入 FIRST(A)
                                    if (!first[left].ContainsRange(first[right[i].ToString()]))
                                        first[left].AddRange(first[right[i].ToString()]);

                                    // 如果 FIRST(B) 中不包含 ε，则不再计算后面的符号
                                    if (!first[right[i].ToString()].Contains('ε'))
                                        break;
                                    // 如果 FIRST(B) 中包含 ε 且 B 是最后一个符号，则将 ε 加入 FIRST(A)
                                    else if (i == right.Length - 1)
                                    {
                                        if (!first[left].Contains('ε'))
                                            first[left].Add('ε');
                                    }
                                }
                            }
                        }
                    }
                }
            }

            // 计算FOLLOW集
            foreach (var item in production)
            {
                string left = item.Key;
                if (!follow.ContainsKey(left))
                    follow.Add(left, new List<string>());
            }
            follow[production.First().Key].Add('$');

            bool isChanged = true;
            while (isChanged)
            {
                isChanged = false;
                foreach (var item in production)
                {
                    string left = item.Key;
                    List<string> rightList = item.Value;
                    foreach (string right in rightList)
                    {
                        for (int i = 0; i < right.Length; i++)
                        {
                            string beta = right.Substring(i + 1);
                            // 处理形如 A -> BCD 的产生式
                            if (char.IsUpper(right[i]))
                            {
                                if (!follow.ContainsKey(right[i].ToString()))
                                    break;
                                else
                                {
                                    // 处理形如 A -> BC 的产生式
                                    if (beta.Length == 0)
                                    {
                                        if (!follow[right[i].ToString()].ContainsRange(follow[left]))
                                        {
                                            follow[right[i].ToString()].AddRange(follow[left]);
                                            isChanged = true;
                                        }
                                    }
                                    // 处理形如 A -> BCD 的产生式
                                    else
                                    {
                                        // 处理形如 A -> BCa 的产生式
                                        if (!char.IsUpper(beta[0]))
                                        {
                                            if (!follow[right[i].ToString()].Contains(beta[0].ToString()))
                                            {
                                                follow[right[i].ToString()].Add(beta[0].ToString());
                                                isChanged = true;
                                            }
                                        }
                                        // 处理形如 A -> BCD 的产生式
                                        else
                                        {
                                            if (!first.ContainsKey(beta[0].ToString()))
                                                break;
                                            else
                                            {
                                                // 如果 FIRST(C) 中不包含 ε，则将 FIRST(C) 加入 FOLLOW(B)
                                                if (!first[beta[0].ToString()].Contains('ε'))
                                                {
                                                    if (!follow[right[i].ToString()].ContainsRange(first[beta[0].ToString()]))
                                                    {
                                                        follow[right[i].ToString()].AddRange(first[beta[0].ToString()]);
                                                        isChanged = true;
                                                    }
                                                }
                                                // 如果 FIRST(C) 中包含 ε，则将 FIRST(C)-ε 加入 FOLLOW(B)，并将 FOLLOW(A) 加入 FOLLOW(B)
                                                else
                                                {
                                                    if (!follow[right[i].ToString()].ContainsRange(first[beta[0].ToString()].Except(new List<string>() { 'ε' })))
                                                    {
                                                        follow[right[i].ToString()].AddRange(first[beta[0].ToString()].Except(new List<string>() { 'ε' }));
                                                        isChanged = true;
                                                    }
                                                    if (!follow[right[i].ToString()].ContainsRange(follow[left]))
                                                    {
                                                        follow[right[i].ToString()].AddRange(follow[left]);
                                                        isChanged = true;
                                                    }
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }

            // 构造分析表
            foreach (var item in production)
            {
                string left = item.Key;
                List<string> rightList = item.Value;
                foreach (string right in rightList)
                {
                    List<string> temp = new List<string>();
                    if (right == 'ε')
                    {
                        foreach (string s in follow[left])
                        {
                            if (!temp.Contains(s))
                                temp.Add(s);
                        }
                    }
                    else
                    {
                        for (int i = 0; i < right.Length; i++)
                        {
                            string beta = right.Substring(i + 1);
                            // 处理形如 A -> BCD 的产生式
                            if (char.IsUpper(right[i]))
                            {
                                if (!first.ContainsKey(right[i].ToString()))
                                    break;
                                else
                                {
                                    // 如果 FIRST(B) 中不包含 ε，则直接将 FIRST(B) 加入分析表
                                    if (!first[right[i].ToString()].Contains('ε'))
                                    {
                                        foreach (string s in first[right[i].ToString()])
                                        {
                                            if (!temp.Contains(s))
                                                temp.Add(s);
                                        }
                                        break;
                                    }
                                    // 如果 FIRST(B) 中包含 ε，则将 FIRST(B)-ε 加入分析表，并将 FOLLOW(A) 加入分析表
                                    else
                                    {
                                        foreach (string s in first[right[i].ToString()].Except(new List<string>() { 'ε' }))
                                        {
                                            if (!temp.Contains(s))
                                                temp.Add(s);
                                        }
                                        if (i == right.Length - 1)
                                        {
                                            foreach (string s in follow[left])
                                            {
                                                if (!temp.Contains(s))
                                                    temp.Add(s);
                                            }
                                        }
                                    }
                                }
                            }
                            // 处理形如 A -> aB 或 A -> a 的产生式
                            else
                            {
                                if (!temp.Contains(right[i].ToString()))
                                    temp.Add(right[i].ToString());
                                break;
                            }
                        }
                    }
                    if (!table.ContainsKey(left))
                        table.Add(left, new Dictionary<string, List<string>>());
                    foreach (string s in temp)
                    {
                        if (!table[left].ContainsKey(s))
                            table[left].Add(s, new List<string>());
                        table[left][s].Add(right);
                    }
                }
            }

            // 输出分析表
            listView3.Items.Clear();
            foreach (var item in table)
            {
                string left = item.Key;
                Dictionary<string, List<string>> rightDict = item.Value;
                foreach (var subItem in rightDict)
                {
                    string right = string.Join('|', subItem.Value);
                    string action = '';
                    if (right == 'ε')
                        action = 'acc';
                    else
                        action = 'shift';
                    string content = '(' + left + ',' + subItem.Key + ',' + action + right + ')';
                    listView3.Items.Add(content);
                }
            }
        }
        // ... 其他代码 ...
    }
}