LR(0) 分析器判别文法及项目族信息生成

private List productions = new List(); // 存储文法产生式 private List symbols = new List(); // 存储文法符号 private List states = new List(); // 存储状态 private List itemsets = new List(); // 存储项目族 private Dictionary<string, List> gotoTable = new Dictionary<string, List>(); // 存储GOTO表 private Dictionary<string, List> actionTable = new Dictionary<string, List>(); // 存储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 item0 = "S' -> .S";
itemsets.Add(item0);
states.Add("I0");

// 生成项目族
BuilditemFamily();

// 构建GOTO表
BuildGotoTable();

// 构建ACTION表
BuildActionTable();

// 输出GOTO表和ACTION表
OutputTables();

}

private void BuilditemFamily() { int i = 0; while (i < itemsets.Count) { string itemset = itemsets[i]; i++;

    // 获取该项目族中所有的项目
    List<string> items = itemset.Split(new string[] { "\r\n" }, StringSplitOptions.RemoveEmptyEntries).ToList();

    // 获取该项目族中所有的文法符号
    List<string> symbolsInItems = new List<string>();
    foreach (string item in items)
    {
        string[] parts = item.Split(' ');
        foreach (string part in parts)
        {
            if (!symbolsInItems.Contains(part))
            {
                symbolsInItems.Add(part);
            }
        }
    }

    // 对于每个文法符号，生成一个新的项目族
    foreach (string symbol in symbolsInItems)
    {
        List<string> newItems = new List<string>();
        foreach (string item in items)
        {
            string[] parts = item.Split(' ');
            for (int j = 0; j < parts.Length; j++)
            {
                if (parts[j] == symbol)
                {
                    string newItem = item.Replace(". " + symbol, symbol + " .");
                    if (!newItems.Contains(newItem))
                    {
                        newItems.Add(newItem);
                    }
                }
            }
        }

        // 如果新的项目族不为空且未被访问过，则加入到itemsets中
        if (newItems.Count > 0)
        {
            string newItemset = string.Join("\r\n", newItems) + "\r\n";
            if (!itemsets.Contains(newItemset))
            {
                itemsets.Add(newItemset);
                states.Add("I" + states.Count);
            }
        }
    }
}

}

private void BuildGotoTable() { for (int i = 0; i < itemsets.Count; i++) { List symbolsInItemset = new List(); string[] items = itemsets[i].Split(new string[] { "\r\n" }, StringSplitOptions.RemoveEmptyEntries); foreach (string item in items) { string[] parts = item.Split(' '); for (int j = 0; j < parts.Length; j++) { if (parts[j] == ".") { if (j < parts.Length - 1) { string symbol = parts[j + 1]; if (!symbolsInItemset.Contains(symbol)) { symbolsInItemset.Add(symbol); } } } } }

    foreach (string symbol in symbolsInItemset)
    {
        List<string> gotoItems = new List<string>();
        foreach (string item in items)
        {
            string[] parts = item.Split(' ');
            for (int j = 0; j < parts.Length; j++)
            {
                if (parts[j] == ".")
                {
                    if (j < parts.Length - 1)
                    {
                        if (parts[j + 1] == symbol)
                        {
                            string newItem = item.Replace(". " + symbol, symbol + " .");
                            if (!gotoItems.Contains(newItem))
                            {
                                gotoItems.Add(newItem);
                            }
                        }
                    }
                }
            }
        }

        if (gotoItems.Count > 0)
        {
            string gotoItemset = string.Join("\r\n", gotoItems) + "\r\n";
            if (!itemsets.Contains(gotoItemset))
            {
                itemsets.Add(gotoItemset);
                states.Add("I" + states.Count);
            }

            int fromState = i;
            int toState = itemsets.IndexOf(gotoItemset);
            if (!gotoTable.ContainsKey("I" + fromState))
            {
                gotoTable.Add("I" + fromState, new List<string>());
            }
            gotoTable["I" + fromState].Add(symbol + "=I" + toState);
        }
    }
}

}

private void BuildActionTable() { for (int i = 0; i < itemsets.Count; i++) { string[] items = itemsets[i].Split(new string[] { "\r\n" }, StringSplitOptions.RemoveEmptyEntries); foreach (string item in items) { string[] parts = item.Split(' '); for (int j = 0; j < parts.Length; j++) { if (parts[j] == ".") { if (j == parts.Length - 1) { // 形如A -> α.的项目 if (parts[0] == "S'") { if (!actionTable.ContainsKey("I" + i)) { actionTable.Add("I" + i, new List()); } actionTable["I" + i].Add("$=acc"); } else { string production = item.Replace(". ", ""); int index = productions.IndexOf(production); if (!actionTable.ContainsKey("I" + i)) { actionTable.Add("I" + i, new List()); } actionTable["I" + i].Add(parts[j - 1] + "=r" + index); } } else { // 形如A -> α.Bβ.的项目 string symbol = parts[j + 1]; List gotoItems = new List(); foreach (string gotoItem in itemsets) { string[] gotoParts = gotoItem.Split(' '); if (gotoParts[0] == symbol && gotoParts[1] == ".") { string newItem = gotoItem.Replace(". ", ""); if (!gotoItems.Contains(newItem)) { gotoItems.Add(newItem); } } }

                    if (gotoItems.Count > 0)
                    {
                        string gotoItemset = string.Join("\r\n", gotoItems) + "\r\n";
                        int nextState = itemsets.IndexOf(gotoItemset);
                        if (!actionTable.ContainsKey("I" + i))
                        {
                            actionTable.Add("I" + i, new List<string>());
                        }
                        actionTable["I" + i].Add(symbol + "=s" + nextState);
                    }
                }
            }
        }
    }
}

}

private void OutputTables() { // 输出GOTO表 richTextBox2.AppendText("GOTO表：\r\n"); foreach (KeyValuePair<string, List> entry in gotoTable) { richTextBox2.AppendText(entry.Key + ":\r\n"); foreach (string action in entry.Value) { richTextBox2.AppendText("\t" + action + "\r\n"); } }

// 输出ACTION表
richTextBox2.AppendText("ACTION表：\r\n");
foreach (KeyValuePair<string, List<string>> entry in actionTable)
{
    richTextBox2.AppendText(entry.Key + ":\r\n");
    foreach (string action in entry.Value)
    {
        richTextBox2.AppendText("\t" + action + "\r\n");
    }
}