LL(1) 文法识别工具 - 判断文法是否为 LL(1) 文法

private void button4_Click(object sender, EventArgs e) { //读取文本框中的文法 string text = richTextBox1.Text;

//分割文法并创建LL1_1_对象
string[] pro = text.Split('\n');

//计算 FIRST 集合
Dictionary<string, List<string>> firsts = CalculateFirstSet(pro);

//计算 FOLLOW 集合
Dictionary<string, List<string>> follows = CalculateFollowSet(pro, firsts);

//输出 FIRST 集合和 FOLLOW 集合
richTextBox2.AppendText("FIRST 集合：\n");
foreach (var item in firsts)
{
    richTextBox2.AppendText(item.Key + " : ");
    foreach (var value in item.Value)
    {
        richTextBox2.AppendText(value + " ");
    }
    richTextBox2.AppendText("\n");
}

richTextBox2.AppendText("\nFOLLOW 集合：\n");
foreach (var item in follows)
{
    richTextBox2.AppendText(item.Key + " : ");
    foreach (var value in item.Value)
    {
        richTextBox2.AppendText(value + " ");
    }
    richTextBox2.AppendText("\n");
}

//判断是否是 LL(1) 文法
if (IsLL1Grammar(pro, firsts, follows))
{
    richTextBox2.AppendText("\n该文法是 LL(1) 文法");
}
else
{
    richTextBox2.AppendText("\n该文法不是 LL(1) 文法");
}

}

// 计算 FIRST 集合 private Dictionary<string, List> CalculateFirstSet(string[] productions) { Dictionary<string, List> firsts = new Dictionary<string, List>(); foreach (string production in productions) { string[] parts = production.Split('->'); string nonTerminal = parts[0].Trim(); string[] rightHandSide = parts[1].Split('|'); if (!firsts.ContainsKey(nonTerminal)) { firsts.Add(nonTerminal, new List()); } foreach (string rightSide in rightHandSide) { // 如果右部第一个符号是终结符 if (IsTerminal(rightSide[0])) { if (!firsts[nonTerminal].Contains(rightSide[0].ToString())) { firsts[nonTerminal].Add(rightSide[0].ToString()); } } // 如果右部第一个符号是非终结符 else { // 递归计算该非终结符的 FIRST 集合 Dictionary<string, List> tempFirsts = CalculateFirstSet(productions); if (tempFirsts.ContainsKey(rightSide[0].ToString())) { foreach (string terminal in tempFirsts[rightSide[0].ToString()]) { if (!firsts[nonTerminal].Contains(terminal)) { firsts[nonTerminal].Add(terminal); } } } } } } return firsts; }

// 计算 FOLLOW 集合 private Dictionary<string, List> CalculateFollowSet(string[] productions, Dictionary<string, List> firsts) { Dictionary<string, List> follows = new Dictionary<string, List>(); foreach (string production in productions) { string[] parts = production.Split('->'); string nonTerminal = parts[0].Trim(); string[] rightHandSide = parts[1].Split('|'); if (!follows.ContainsKey(nonTerminal)) { follows.Add(nonTerminal, new List()); } // 如果该非终结符是起始符号，则将 # 加入 FOLLOW 集合 if (nonTerminal == productions[0].Split('->')[0].Trim()) { if (!follows[nonTerminal].Contains("#")) { follows[nonTerminal].Add("#"); } } for (int i = 0; i < rightHandSide.Length; i++) { for (int j = 0; j < rightHandSide[i].Length; j++) { if (IsTerminal(rightHandSide[i][j])) { continue; } string currentNonTerminal = rightHandSide[i][j].ToString(); if (!follows.ContainsKey(currentNonTerminal)) { follows.Add(currentNonTerminal, new List()); } // 如果该非终结符不是右部最后一个符号 if (j < rightHandSide[i].Length - 1) { // 计算下一个符号的 FIRST 集合 if (IsTerminal(rightHandSide[i][j + 1])) { if (!follows[currentNonTerminal].Contains(rightHandSide[i][j + 1].ToString())) { follows[currentNonTerminal].Add(rightHandSide[i][j + 1].ToString()); } } else { foreach (string terminal in firsts[rightHandSide[i][j + 1].ToString()]) { if (!follows[currentNonTerminal].Contains(terminal)) { follows[currentNonTerminal].Add(terminal); } } } } // 如果该非终结符是右部最后一个符号 else { // 将产生式左部非终结符的 FOLLOW 集合加入该非终结符的 FOLLOW 集合 if (nonTerminal != currentNonTerminal) { foreach (string terminal in follows[nonTerminal]) { if (!follows[currentNonTerminal].Contains(terminal)) { follows[currentNonTerminal].Add(terminal); } } } } } } } return follows; }

// 判断是否是 LL(1) 文法 private bool IsLL1Grammar(string[] productions, Dictionary<string, List> firsts, Dictionary<string, List> follows) { foreach (string production in productions) { string[] parts = production.Split('->'); string nonTerminal = parts[0].Trim(); string[] rightHandSide = parts[1].Split('|'); for (int i = 0; i < rightHandSide.Length; i++) { for (int j = i + 1; j < rightHandSide.Length; j++) { // 比较两个产生式的 FIRST 集合 List firstSet1 = new List(); List firstSet2 = new List(); // 如果第一个产生式的第一个符号是终结符 if (IsTerminal(rightHandSide[i][0])) { firstSet1.Add(rightHandSide[i][0].ToString()); } // 如果第一个产生式的第一个符号是非终结符 else { firstSet1.AddRange(firsts[rightHandSide[i][0].ToString()]); } // 如果第二个产生式的第一个符号是终结符 if (IsTerminal(rightHandSide[j][0])) { firstSet2.Add(rightHandSide[j][0].ToString()); } // 如果第二个产生式的第一个符号是非终结符 else { firstSet2.AddRange(firsts[rightHandSide[j][0].ToString()]); } // 如果两个产生式的 FIRST 集合有交集，则不是 LL(1) 文法 if (firstSet1.Intersect(firstSet2).Any()) { return false; } } } } return true; }

// 判断是否是终结符 private bool IsTerminal(char symbol) { return !char.IsUpper(symbol);