• 日期: 2028-07-20
  • 标签: 常规
private List<string> productions = new List<string>(); // 存储文法产生式
private List<string> symbols = new List<string>(); // 存储文法符号
private List<string> states = new List<string>(); // 存储状态
private List<string> itemsets = new List<string>(); // 存储项目族
private Dictionary<string, List<string>> gotoTable = new Dictionary<string, List<string>>(); // 存储GOTO表
private Dictionary<string, List<string>> actionTable = new Dictionary<string, List<string>>(); // 存储ACTION表

private void button2_Click(object sender, EventArgs e)//判别LR0文法
{
    // 读取文法产生式
    string[] productionsArr = richTextBox1.Text.Split(new string[] { "\r\n" }, StringSplitOptions.RemoveEmptyEntries);
    productions.AddRange(productionsArr);

    // 获取文法符号
    foreach (string production in productions)
    {
        string[] parts = production.Split(' ');
        foreach (string part in parts)
        {
            if (!symbols.Contains(part))
            {
                symbols.Add(part);
            }
        }
    }

    // 初始化状态0
    string item = "S' -> .S";
    itemsets.Add(item);
    states.Add(GetClosure(item));


    BuilditemFamily();
    
}

private void button4_Click(object sender, EventArgs e)//生成项目族信息
{
    BuilditemFamily();
    // 显示状态和项目族信息
    DataTable dt = new DataTable();
dt.Columns.Add("State");
dt.Columns.Add("ItemSet");
    for (int i = 0; i < itemsets.Count; i++)
    {
        DataRow row = dt.NewRow();
        row["State"] = i;
        row["ItemSet"] = itemsets[i];
        dt.Rows.Add(row);
    }
    dataGridView1.DataSource = dt;
}
private void BuilditemFamily()
{
    int i = 0;
    while (i < itemsets.Count)
    {
        string itemset = itemsets[i];
        i++;

        // 获取该项目集的所有可移进符号
        List<string> shiftSymbols = GetShiftSymbols(itemset);
        foreach (string symbol in shiftSymbols)
        {
            // 计算移进后的项目集
            string newItemset = GetShiftItemset(itemset, symbol);
            if (!itemsets.Contains(newItemset))
            {
                itemsets.Add(newItemset);
                System.Diagnostics.Debug.WriteLine(newItemset);
                states.Add(GetClosure(newItemset));
            }

            // 添加GOTO表项
            int fromState = itemsets.IndexOf(itemset);
            int toState = itemsets.IndexOf(newItemset);
            string key = fromState + "," + symbol;
            string value = "S" + toState;
            if (!gotoTable.ContainsKey(key))
            {
                gotoTable[key] = new List<string>();
            }
            gotoTable[key].Add(value);
        }

        // 获取该项目集的所有规约符号
        List<string> reduceSymbols = GetReduceSymbols(itemset);
        foreach (string symbol in reduceSymbols)
        {
            // 添加ACTION表项
            int state = itemsets.IndexOf(itemset);
            string key = state + "," + symbol;
            string value = "r" + GetReduceProductionIndex(itemset, symbol);
            if (!actionTable.ContainsKey(key))
            {
                actionTable[key] = new List<string>();
            }
            actionTable[key].Add(value);
        }
    }
}

        // 获取闭包
        private string GetClosure(string item)
        {
            List<string> closure = new List<string>();
            closure.Add(item);

            int i = 0;
            while (i < closure.Count)
            {
                string item1 = closure[i];
                i++;

                string[] parts = item1.Split(' ');
                int dotIndex = parts.ToList().IndexOf('.');
                if (dotIndex != parts.Length - 1) // 不是最后一个符号
                {
                    string nextSymbol = parts[dotIndex + 1];
                    List<string> productionsWithNextSymbol = productions.Where(p => p.StartsWith(nextSymbol + " ")).ToList();
                    foreach (string production in productionsWithNextSymbol)
                    {
                        string newItem = nextSymbol + " -> ." + production.Split(new string[] { nextSymbol + " " }, StringSplitOptions.None)[1];
                        if (!closure.Contains(newItem))
                        {
                            closure.Add(newItem);
                        }
                    }
                }
            }

            return string.Join("\r\n", closure);
        }

        // 获取该项目集的所有可移进符号
        private List<string> GetShiftSymbols(string itemset)
        {
            List<string> shiftSymbols = new List<string>();

            string[] items = itemset.Split(new string[] { "\r\n" }, StringSplitOptions.RemoveEmptyEntries);
            foreach (string item in items)
            {
                string[] parts = item.Split(' ');
                int dotIndex = parts.ToList().IndexOf('.');
                if (dotIndex != parts.Length - 1) // 不是最后一个符号
                {
                    string nextSymbol = parts[dotIndex + 1];
                    if (!shiftSymbols.Contains(nextSymbol))
                    {
                        shiftSymbols.Add(nextSymbol);
                    }
                }
            }

            return shiftSymbols;
        }

        // 计算移进后的项目集
        private string GetShiftItemset(string itemset, string symbol)
        {
            List<string> newItems = new List<string>();

            string[] items = itemset.Split(new string[] { "\r\n" }, StringSplitOptions.RemoveEmptyEntries);
            foreach (string item in items)
            {
                string[] parts = item.Split(' ');
                int dotIndex = parts.ToList().IndexOf('.');
                if (dotIndex != parts.Length - 1) // 不是最后一个符号
                {
                    string nextSymbol = parts[dotIndex + 1];
                    if (nextSymbol == symbol)
                    {
                        string newItem = string.Join(" ", parts.Take(dotIndex)) + " " + nextSymbol + " ." + string.Join(" ", parts.Skip(dotIndex + 2));
                        newItems.Add(newItem);
                    }
                }
            }

            return string.Join("\r\n", newItems);
        }

        // 获取该项目集的所有规约符号
        private List<string> GetReduceSymbols(string itemset)
        {
            List<string> reduceSymbols = new List<string>();

            string[] items = itemset.Split(new string[] { "\r\n" }, StringSplitOptions.RemoveEmptyEntries);
            foreach (string item in items)
            {
                string[] parts = item.Split(' ');
                int dotIndex = parts.ToList().IndexOf('.');
                if (dotIndex == parts.Length - 1) // 是最后一个符号
                {
                    string reduceSymbol = parts[0];
                    if (!reduceSymbols.Contains(reduceSymbol))
                    {
                        reduceSymbols.Add(reduceSymbol);
                    }
                }
            }

            return reduceSymbols;
        }

        // 获取规约产生式在文法产生式列表中的索引
        private int GetReduceProductionIndex(string itemset, string symbol)
        {
            string[] items = itemset.Split(new string[] { "\r\n" }, StringSplitOptions.RemoveEmptyEntries);
            foreach (string item in items)
            {
                string[] parts = item.Split(' ');
                int dotIndex = parts.ToList().IndexOf('.');
                if (dotIndex == parts.Length - 1) // 是最后一个符号
                {
                    string reduceSymbol = parts[0];
                    if (reduceSymbol == symbol)
                    {
                        return productions.IndexOf(string.Join(" ", parts.Take(dotIndex)));
                    }
                }
            }

            return -1;
        }

代码功能：

  • 读取文法产生式，并存储在 productions 列表中。
  • 获取文法符号，并存储在 symbols 列表中。
  • 初始化状态 0，并构建闭包。
  • 构建项目族，并存储在 itemsets 列表中。
  • 计算 GOTO 表，并存储在 gotoTable 字典中。
  • 计算 ACTION 表，并存储在 actionTable 字典中。
  • 将状态和项目族信息显示在 dataGridView1 中。

使用方法：

  1. 将代码粘贴到 C# 项目中。
  2. 在 richTextBox1 中输入文法产生式，每行一个产生式，例如：
E -> E + T
E -> T
T -> T * F
T -> F
F -> ( E )
F -> id
  1. 点击 button2 按钮，构建 LR(0) 分析表。
  2. 点击 button4 按钮，将状态和项目族信息显示在 dataGridView1 中。

代码说明：

  • GetClosure() 方法用于计算项目集的闭包。
  • GetShiftSymbols() 方法用于获取项目集的所有可移进符号。
  • GetShiftItemset() 方法用于计算移进后的项目集。
  • GetReduceSymbols() 方法用于获取项目集的所有规约符号。
  • GetReduceProductionIndex() 方法用于获取规约产生式在文法产生式列表中的索引。
  • BuilditemFamily() 方法用于构建项目族、GOTO 表和 ACTION 表。

注意：

  • 该代码仅实现了 LR(0) 分析器的核心功能，未实现具体解析语法树的功能。
  • 代码中使用 System.Diagnostics.Debug.WriteLine() 输出调试信息，可以根据需要修改或删除。
  • 实际应用中，可以使用其他数据结构和算法来优化代码性能。

示例输出：

示例输出

LR(0) 文法分析器 C# 代码实现

原文地址: https://www.cveoy.top/t/topic/fZEu 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录