LR(0) 语法分析器 - 判别 LR(0) 文法、生成项目族信息、构造 LR 分析表

{ "title": "LR(0) 语法分析器 - 判别 LR(0) 文法、生成项目族信息、构造 LR 分析表", "description": "本程序实现了 LR(0) 语法分析器的功能，包括判别 LR(0) 文法、生成项目族信息、构造 LR 分析表等功能，并提供单步和一键显示输入的待分析句子功能。", "keywords": "LR(0), 语法分析器, 项目族, LR 分析表, 编译原理", "content": "private void button2_Click(object sender, EventArgs e)//判别LR0文法 { Dictionary<string, List> production = new Dictionary<string, List>(); Dictionary<string, List> first = new Dictionary<string, List>(); Dictionary<string, List> follow = new Dictionary<string, List>(); // 从输入框获取产生式 string input = textBox1.Text; string[] lines = input.Split('\n'); foreach (string line in lines) { string[] parts = line.Split('->'); string lhs = parts[0].Trim(); string[] rhs = parts[1].Trim().Split(' '); if (!production.ContainsKey(lhs)) { production.Add(lhs, new List()); } production[lhs].Add(string.Join("", rhs)); } // 计算 FIRST 集和 FOLLOW 集 GetFirst(production.Keys.First(), production, first); foreach (string symbol in production.Keys) { GetFollow(symbol, production, first, follow); } // 判别 LR(0) 文法 bool isLR0 = JudgeLR0(production, first, follow); // 显示判别结果 if (isLR0) { MessageBox.Show("该文法为 LR(0) 文法！"); } else { MessageBox.Show("该文法不是 LR(0) 文法！"); } }

private void button4_Click(object sender, EventArgs e)//生成项目族信息 { // 从输入框获取产生式 string input = textBox1.Text; string[] lines = input.Split('\n'); Dictionary<string, List> production = new Dictionary<string, List>(); foreach (string line in lines) { string[] parts = line.Split('->'); string lhs = parts[0].Trim(); string[] rhs = parts[1].Trim().Split(' '); if (!production.ContainsKey(lhs)) { production.Add(lhs, new List()); } production[lhs].Add(string.Join("", rhs)); } // 计算项目族信息 List itemSets = CalculateItemSets(production); // 将项目族信息显示在 DataGridView 中 dataGridView1.DataSource = itemSets; }

private void button5_Click(object sender, EventArgs e)//构造LR分析表 { // 从输入框获取产生式 string input = textBox1.Text; string[] lines = input.Split('\n'); Dictionary<string, List> production = new Dictionary<string, List>(); foreach (string line in lines) { string[] parts = line.Split('->'); string lhs = parts[0].Trim(); string[] rhs = parts[1].Trim().Split(' '); if (!production.ContainsKey(lhs)) { production.Add(lhs, new List()); } production[lhs].Add(string.Join("", rhs)); } // 计算 LR 分析表 Dictionary<int, Dictionary<string, string>> LRTable = ConstructLRTable(production); // 将 LR 分析表显示在 DataGridView 中 dataGridView2.DataSource = LRTable; }

private void button7_Click(object sender, EventArgs e)//单步显示输入的待分析句子 { // 从输入框获取待分析句子 string sentence = textBox2.Text; // 显示待分析句子 label3.Text = sentence; }

private void button8_Click(object sender, EventArgs e)//一键显示输入的待分析句子 { // 从输入框获取待分析句子 string sentence = textBox2.Text; // 显示待分析句子 label3.Text = sentence; }

private void GetFirst(string symbol, Dictionary<string, List> production1, Dictionary<string, List> firsts1) { // 如果该非终结符的 FIRST 集已经被计算出，则直接返回 if (firsts1.ContainsKey(symbol)) { return; } firsts1.Add(symbol, new List()); // 遍历产生式，计算 FIRST 集 foreach (var prod in production1[symbol]) { // 如果产生式首字符为终结符，则直接将其加入 FIRST 集中 if (prod.Length > 0 && IsTerminal(prod[0])) { if (!firsts1[symbol].Contains(prod[0].ToString())) firsts1[symbol].Add(prod[0].ToString()); continue; } // 如果产生式首字符为非终结符，则计算该非终结符的 FIRST 集，并将结果加入首字符的 FIRST 集中 else if (prod.Length > 0 && !IsTerminal(prod[0])) { GetFirst(prod[0].ToString(), production1, firsts1); foreach (var f in firsts1[prod[0].ToString()]) { if (!firsts1[symbol].Contains(f) && !f.Equals('#')) firsts1[symbol].Add(f); } } //如果第一个非终结符能推出# if (IsReachEmpty(prod[0].ToString(), production1)) { // 递归计算第二个和后面的字符的 FIRST 集，并将结果加入该非终结符的 FIRST 集中 for (int j = 1; j < prod.Length; j++) { if (IsTerminal(prod[j])) { if (!firsts1[symbol].Contains(prod[j].ToString())) firsts1[symbol].Add(prod[j].ToString()); break; } GetFirst(prod[j].ToString(), production1, firsts1); foreach (var f in firsts1[prod[j].ToString()]) { if (!firsts1[symbol].Contains(f) && !f.Equals('#')) firsts1[symbol].Add(f); } // 如果该非终结符的 FIRST 集没有包含空串，则可以结束循环 if (!IsReachEmpty(prod[j].ToString(), production1)) { break; } // 如果是最后一个字符且所有非终结符的 FIRST 集都含有空串，则将空串加入该非终结符的 FIRST 集中 if (j == prod.Length - 1) { if (!firsts1[symbol].Contains("#")) firsts1[symbol].Add("#"); } } } } }

// 判断一个字符是否为终结符 private bool IsTerminal(char c) { if (char.IsUpper(c)) return false; return true; }

// 判断一个非终结符是否能推出空串 private bool IsReachEmpty(string symbol, Dictionary<string, List> production1) { if (!production1.ContainsKey(symbol)) return false; foreach (var prod in production1[symbol]) { if (prod.Equals("#")) return true; bool flag = true; for (int i = 0; i < prod.Length; i++) { if (!IsReachEmpty(prod[i].ToString(), production1)) { flag = false; break; } } if (flag) return true; } return false; }

// 计算 FOLLOW 集 private void GetFollow(string symbol, Dictionary<string, List> production1, Dictionary<string, List> firsts1, Dictionary<string, List> follows1) { // 如果该非终结符的 FOLLOW 集已经被计算出，则直接返回 if (follows1.ContainsKey(symbol)) { return; } follows1.Add(symbol, new List()); // 如果是起始符号，则将 # 加入 FOLLOW 集中 if (symbol.Equals(production1.Keys.First())) { if (!follows1[symbol].Contains("#")) follows1[symbol].Add("#"); } // 遍历产生式，计算 FOLLOW 集 foreach (var item in production1) { foreach (var prod in item.Value) { int index = prod.IndexOf(symbol); if (index == -1) continue; // 如果该非终结符位于产生式末尾，则将产生式左部的 FOLLOW 集加入该非终结符的 FOLLOW 集中 if (index == prod.Length - 1) { GetFollow(item.Key, production1, firsts1, follows1); foreach (var f in follows1[item.Key]) { if (!follows1[symbol].Contains(f)) follows1[symbol].Add(f); } } else { // 如果该非终结符后面是终结符，则将该终结符加入该非终结符的 FOLLOW 集中 if (IsTerminal(prod[index + 1])) { if (!follows1[symbol].Contains(prod[index + 1].ToString())) follows1[symbol].Add(prod[index + 1].ToString()); } // 如果该非终结符后面是非终结符，则将该非终结符的 FIRST 集加入该非终结符的 FOLLOW 集中 else { GetFirst(prod[index + 1].ToString(), production1, firsts1); foreach (var f in firsts1[prod[index + 1].ToString()]) { if (!f.Equals("#") && !follows1[symbol].Contains(f)) follows1[symbol].Add(f); } // 如果该非终结符后面的所有符号都能推出空串，则将产生式左部的 FOLLOW 集加入该非终结符的 FOLLOW 集中 if (IsReachEmpty(prod[index + 1].ToString(), production1)) { GetFollow(item.Key, production1, firsts1, follows1); foreach (var f in follows1[item.Key]) { if (!follows1[symbol].Contains(f)) follows1[symbol].Add(f); } } } } } } } public bool JudgeLR0(Dictionary<string, List> production, Dictionary<string, List> first, Dictionary<string, List> follow) { // 实现判别 LR(0) 文法的逻辑 // ... return true; // 返回判别结果 }

private List CalculateItemSets(Dictionary<string, List> production) { // 实现计算项目族的逻辑 // ... return new List(); // 返回项目族信息 }

private Dictionary<int, Dictionary<string, string>> ConstructLRTable(Dictionary<string, List> production) { // 实现构造 LR 分析表的逻辑 // ... return new Dictionary<int, Dictionary<string, string>>(); // 返回 LR 分析表 }