LR(0) 文法分析器实现 - 项目族构建与分析

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)//生成项目族信息
{
    itemsets.Clear();
    states.Clear();
    BuilditemFamily();
    // 显示状态和项目族信息
    dataGridView1.Columns.Clear();
    dataGridView1.Columns.Add("State", "状态");
    dataGridView1.Columns.Add("ItemSet", "项目族信息");
    for (int i = 0; i < itemsets.Count; i++)
    {
        dataGridView1.Rows.Add(i, itemsets[i]);
    }
}
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;
}

上述函数在dataGridView1上什么也不输出，可能是因为在调用BuilditemFamily()函数时，没有清空itemsets和states列表，导致新增的状态和项目族信息没有被正确添加。可以在调用前先清空这两个列表，如下所示：

private void button4_Click(object sender, EventArgs e)//生成项目族信息
{
    itemsets.Clear();
    states.Clear();
    BuilditemFamily();
    // 显示状态和项目族信息
    dataGridView1.Columns.Clear();
    dataGridView1.Columns.Add("State", "状态");
    dataGridView1.Columns.Add("ItemSet", "项目族信息");
    for (int i = 0; i < itemsets.Count; i++)
    {
        dataGridView1.Rows.Add(i, itemsets[i]);
    }
}