C# 实现 LR(0) 分析器：生成项目族信息和构造 LR 分析表
{ "title": "C# 实现 LR(0) 分析器：生成项目族信息和构造 LR 分析表", "description": "本文介绍如何使用 C# 语言实现 LR(0) 分析器，并展示了生成项目族信息和构造 LR 分析表的功能。代码示例详细解释了每个步骤，并提供了完整的代码实现。", "keywords": "LR(0) 分析器, C#, 项目族信息, LR 分析表, 编译原理", "content": "using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.IO; using System.Linq; using System.Text; using System.Text.RegularExpressions; using System.Threading.Tasks; using System.Windows.Forms; using static System.Windows.Forms.VisualStyles.VisualStyleElement; using static System.Windows.Forms.VisualStyles.VisualStyleElement.ToolBar;
namespace byyljxfzxt { public partial class Form5 : Form { public Form5() { InitializeComponent(); }
//--------------------预处理
Dictionary<string, List<string>> production;//产生式
Dictionary<string, List<string>> first;
Dictionary<string, List<string>> follow;
Dictionary<string, Dictionary<string, List<string>>> table;
private int step = 0; // 记录当前分析到第几步
private void button2_Click(object sender, EventArgs e)
{
string text = richTextBox1.Text;
production = new Dictionary<string, List<string>>();
string[] pro = text.Split('
'); foreach (string s in pro) { if (s == "") continue;
Regex.Replace(s, " ", "");
string[] ga = Regex.Split(s, "->");
if (ga.Length != 2) return;
if (ga[0].Length == 0 || ga[1].Length == 0)
return;
if (ga[0].Length != 1 || !char.IsUpper(ga[0][0])) return;
string[] ga2 = Regex.Split(ga[1], "\|");
if (!production.ContainsKey(ga[0]))
production.Add(ga[0], new List<string>());
foreach (string s1 in ga2)
production[ga[0]].Add(s1);
}
first = new Dictionary<string, List<string>>();
foreach (var item in production.Keys)
GetFirst(item, production, first);
follow = new Dictionary<string, List<string>>();
foreach (var item in production.Keys)
GetFollow(item, production, first, follow);
// 判断是否为LR(0)文法
if (JudgeLR0(production, first, follow))
{
MessageBox.Show("正确的LL(1)文法\n");
}
else
{
MessageBox.Show("该文法不是LL(1)文法，存在左递归或者存在FIRST集合有交集的情况！\n");
}
button4.Enabled = true;
button5.Enabled = true;
button6.Enabled = true;
}
private void button4_Click(object sender, EventArgs e)
{
// 清空dataGridView1
dataGridView1.Rows.Clear();
dataGridView1.Columns.Clear();
// 生成项目族信息
Dictionary<int, HashSet<string>> items = new Dictionary<int, HashSet<string>>();
int count = 0;
HashSet<string> init = new HashSet<string>();
init.Add("S'->.S");
items.Add(count, init);
Dictionary<string, HashSet<string>> closure = new Dictionary<string, HashSet<string>>();
BuildClosure(items[count], production, closure);
dataGridView1.Columns.Add("state", "状态");
dataGridView1.Columns.Add("items", "项目族信息");
dataGridView1.Rows.Add(count, string.Join("\n", items[count]));
// 构建LR(0)自动机
Dictionary<int, Dictionary<string, int>> dfa = new Dictionary<int, Dictionary<string, int>>();
BuildLR0(production, dfa, items, count, first, follow);
// 在dataGridView1中显示状态和项目族信息
foreach (var state in items)
{
dataGridView1.Rows.Add(state.Key, string.Join("\n", state.Value));
}
}
private void button5_Click(object sender, EventArgs e)
{
// 清空dataGridView2
dataGridView2.Rows.Clear();
dataGridView2.Columns.Clear();
// 生成LR分析表
Dictionary<int, Dictionary<string, int>> dfa = new Dictionary<int, Dictionary<string, int>>();
Dictionary<int, HashSet<string>> items = new Dictionary<int, HashSet<string>>();
int count = 0;
HashSet<string> init = new HashSet<string>();
init.Add("S'->.S");
items.Add(count, init);
Dictionary<string, HashSet<string>> closure = new Dictionary<string, HashSet<string>>();
BuildClosure(items[count], production, closure);
BuildLR0(production, dfa, items, count, first, follow);
table = new Dictionary<string, Dictionary<string, List<string>>>();
foreach (var state in dfa)
{
if (!table.ContainsKey(state.Key.ToString()))
{
table.Add(state.Key.ToString(), new Dictionary<string, List<string>>());
}
foreach (var item in state.Value)
{
string[] parts = item.Split(new string[] { "->", "." }, StringSplitOptions.RemoveEmptyEntries);
if (parts.Length != 2) continue;
string symbol = parts[1];
if (symbol.Length == 0)
{
// 接受状态
table[state.Key.ToString()].Add("#", new List<string>() { "acc" });
}
else
{
string next = symbol[0].ToString();
if (!table[state.Key.ToString()].ContainsKey(next))
{
table[state.Key.ToString()].Add(next, new List<string>());
}
// 查找下一个状态
if (dfa[state.Key].ContainsKey(next))
{
table[state.Key.ToString()][next].Add("s" + dfa[state.Key][next]);
}
}
}
}
// 构建LR分析表
foreach (var item in production)
{
foreach (var prod in item.Value)
{
string[] parts = prod.Split(new string[] { "->", "." }, StringSplitOptions.RemoveEmptyEntries);
if (parts.Length != 2) continue;
if (parts[1].Length == 0) continue;
foreach (var state in dfa)
{
foreach (var item2 in state.Value)
{
string[] parts2 = item2.Split(new string[] { "->", "." }, StringSplitOptions.RemoveEmptyEntries);
if (parts2.Length != 2) continue;
if (parts2[0] == item.Key && parts2[1] == prod)
{
// 查找FOLLOW集合中的所有符号
foreach (var followSymbol in follow[item.Key])
{
if (!table[state.Key.ToString()].ContainsKey(followSymbol))
{
table[state.Key.ToString()].Add(followSymbol, new List<string>());
}
table[state.Key.ToString()][followSymbol].Add("r" + production.Keys.ToList().IndexOf(item.Key));
}
}
}
}
}
}
// 在dataGridView2中显示LR分析表
// 设置表头
List<string> columnHeaders = new List<string>();
foreach (var item in table.Values)
{
foreach (var item2 in item.Keys)
{
if (!columnHeaders.Contains(item2))
{
columnHeaders.Add(item2);
}
}
}
for (int i = 0; i < columnHeaders.Count; i++)
{
dataGridView2.Columns.Add(columnHeaders[i], columnHeaders[i]);
}
// 设置行头
for (int i = 0; i < table.Count; i++)
{
dataGridView2.Rows.Add(i.ToString());
}
// 设置表内容
int rowIndex = 0;
foreach (var item in table)
{
int columnIndex = 0;
foreach (var item2 in item.Value)
{
foreach (var action in item2.Value)
{
dataGridView2.Rows[rowIndex].Cells[columnIndex].Value = action;
}
columnIndex++;
}
rowIndex++;
}
}
// 构建闭包
private void BuildClosure(HashSet<string> items, Dictionary<string, List<string>> production1, Dictionary<string, HashSet<string>> closure)
{
// 如果该非终结符的 FIRST 集已经被计算出，则直接返回
if (closure.ContainsKey(items.ToString()))
{
return;
}
closure.Add(items.ToString(), new HashSet<string>());
// 遍历产生式，计算 FIRST 集
foreach (var item in items)
{
string[] parts = item.Split(new string[] { "->", "." }, StringSplitOptions.RemoveEmptyEntries);
if (parts.Length != 2) continue;
string symbol = parts[1];
if (symbol.Length == 0) continue;
string next = symbol[0].ToString();
if (char.IsUpper(next[0]))
{
// 非终结符
if (!closure.ContainsKey(next))
{
closure[next] = new HashSet<string>();
}
foreach (var productionNext in production1[next])
{
closure[next].Add(next + "->." + productionNext);
}
}
}
// 扩展项目集
bool added = true;
while (added)
{
added = false;
foreach (var item in closure)
{
HashSet<string> newItems = new HashSet<string>();
foreach (var item2 in item.Value)
{
string[] parts = item2.Split(new string[] { "->", "." }, StringSplitOptions.RemoveEmptyEntries);
if (parts.Length != 2) continue;
string symbol = parts[1];
if (symbol.Length == 0) continue;
string next = symbol[0].ToString();
if (char.IsUpper(next[0]))
{
// 非终结符
if (!closure.ContainsKey(next))
{
closure[next] = new HashSet<string>();
}
foreach (var productionNext in production1[next])
{
newItems.Add(next + "->." + productionNext);
}
}
}
if (newItems.Count > 0)
{
item.Value.UnionWith(newItems);
added = true;
}
}
}
}
// 判断一个字符是否为终结符
private bool IsTerminal(char c)
{
if (char.IsUpper(c))
return false;
return true;
}
// 判断一个非终结符是否能推出空串
private bool IsReachEmpty(string symbol, Dictionary<string, List<string>> 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<string>> production1, Dictionary<string, List<string>> firsts1, Dictionary<string, List<string>> follows1)
{
// 如果该非终结符的 FOLLOW 集已经被计算出，则直接返回
if (follows1.ContainsKey(symbol))
{
return;
}
follows1.Add(symbol, new List<string>());
// 如果是起始符号，则将 # 加入 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<string>> production, Dictionary<string, List<string>> first, Dictionary<string, List<string>> follow)
{
// 构建DFA
Dictionary<int, Dictionary<string, int>> dfa = new Dictionary<int, Dictionary<string, int>>();
Dictionary<int, HashSet<string>> items = new Dictionary<int, HashSet<string>>();
int count = 0;
// 初始状态
HashSet<string> init = new HashSet<string>();
init.Add("S'->.S");
items.Add(count, init);
dfa.Add(count, new Dictionary<string, int>());
// 构建LR(0)自动机
BuildLR0(production, dfa, items, count, first, follow);
// 判断是否为LR(0)文法
foreach (var state in dfa)
{
foreach (var item in state.Value)
{
string symbol = item.Key;
int nextState = item.Value;
// 冲突
if (dfa[state.Key].ContainsKey(symbol) && dfa[state.Key][symbol] != nextState)
{
return false;
}
}
}
return true;
}
// 构建LR(0)自动机
private void BuildLR0(Dictionary<string, List<string>> production, Dictionary<int, Dictionary<string, int>> dfa, Dictionary<int, HashSet<string>> items, int count, Dictionary<string, List<string>> first, Dictionary<string, List<string>> follow)
{
// 构建项目集
Dictionary<string, HashSet<string>> closure = new Dictionary<string, HashSet<string>>();
foreach (var item in items[count])
{
string[] parts = item.Split(new string[] { "->", "." }, StringSplitOptions.RemoveEmptyEntries);
if (parts.Length != 2) continue;
string symbol = parts[1];
if (symbol.Length == 0) continue;
string next = symbol[0].ToString();
if (char.IsUpper(next[0]))
{
// 非终结符
if (!closure.ContainsKey(next))
{
closure[next] = new HashSet<string>();
}
foreach (var productionNext in production[next])
{
closure[next].Add(next + "->." + productionNext);
}
}
}
// 扩展项目集
bool added = true;
while (added)
{
added = false;
foreach (var item in closure)
{
HashSet<string> newItems = new HashSet<string>();
foreach (var item2 in item.Value)
{
string[] parts = item2.Split(new string[] { "->", "." }, StringSplitOptions.RemoveEmptyEntries);
if (parts.Length != 2) continue;
string symbol = parts[1];
if (symbol.Length == 0) continue;
string next = symbol[0].ToString();
if (char.IsUpper(next[0]))
{
// 非终结符
if (!closure.ContainsKey(next))
{
closure[next] = new HashSet<string>();
}
foreach (var productionNext in production[next])
{
newItems.Add(next + "->." + productionNext);
}
}
}
if (newItems.Count > 0)
{
item.Value.UnionWith(newItems);
added = true;
}
}
}
// 构建DFA
foreach (var item in closure)
{
bool found = false;
int nextState = -1;
foreach (var state in items)
{
if (state.Value.SetEquals(item.Value))
{
found = true;
nextState = state.Key;
break;
}
}
if (!found)
{
count++;
items.Add(count, item.Value);
dfa.Add(count, new Dictionary<string, int>());
nextState = count;
}
// 计算转移符号
Dictionary<string, HashSet<string>> symbols = new Dictionary<string, HashSet<string>>();
foreach (var item2 in item.Value)
{
string[] parts = item2.Split(new string[] { "->", "." }, StringSplitOptions.RemoveEmptyEntries);
if (parts.Length != 2) continue;
string symbol = parts[1];
if (symbol.Length == 0)
{
// 接受状态
if (!dfa[nextState].ContainsKey("#"))
{
dfa[nextState].Add("#", -1);
}
}
else
{
string next = symbol[0].ToString();
if (!symbols.ContainsKey(next))
{
symbols[next] = new HashSet<string>();
}
symbols[next].Add(item2);
}
}
// 构建下一个状态
foreach (var symbol in symbols)
{
string nextSymbol = symbol.Key;
HashSet<string> nextItems = new HashSet<string>();
foreach (var item2 in symbol.Value)
{
string[] parts = item2.Split(new string[] { "->", "." }, StringSplitOptions.RemoveEmptyEntries);
if (parts.Length != 2) continue;
string prod = parts[0];
string symbol2 = parts[1];
if (symbol2.Length == 0) continue;
string next = symbol2[0].ToString();
if (nextSymbol == next)
{
string nextItem = prod + symbol2[0] + "->." + symbol2.Substring(1);
nextItems.Add(nextItem);
}
}
if (nextItems.Count == 0) continue;
// 计算闭包
HashSet<string> nextClosure = new HashSet<string>();
foreach (var item2 in nextItems)
{
string[] parts = item2.Split(new string[] { "->", "." }, StringSplitOptions.RemoveEmptyEntries);
if (parts.Length != 2) continue;
string symbol2 = parts[1];
if (symbol2.Length == 0) continue;
string next = symbol2[0].ToString();
if (char.IsUpper(next[0]))
{
// 非终结符
if (!closure.ContainsKey(next))
{
closure[next] = new HashSet<string>();
}
foreach (var productionNext in production[next])
{
nextClosure.Add(next + "->." + productionNext);
}
}
}
// 扩展项目集
added = true;
while (added)
{
added = false;
foreach (var item2 in nextClosure)
{
string[] parts = item2.Split(new string[] { "->", "." }, StringSplitOptions.RemoveEmptyEntries);
if (parts.Length != 2) continue;
string symbol2 = parts[1];
if (symbol2.Length == 0) continue;
string next = symbol2[0].ToString();
if (char.IsUpper(next[0]))
{
// 非终结符
if (!closure.ContainsKey(next))
{
closure[next] = new HashSet<string>();
}
foreach (var productionNext in production[next])
{
if (!nextClosure.Contains(next + "->." + productionNext))
{
nextClosure.Add(next + "->." + productionNext);
added = true;
}
}
}
}
}
// 查找已有状态
found = false;
int nextState2 = -1;
foreach (var state in items)
{
if (state.Value.SetEquals(nextClosure))
{
found = true;
nextState2 = state.Key;
break;
}
}
if (!found)
{
count++;
items.Add(count, nextClosure);
dfa.Add(count, new Dictionary<string, int>());
nextState2 = count;
// 递归构建DFA
BuildLR0(production, dfa, items, count, first, follow);
}
// 添加转移
if (!dfa[nextState].ContainsKey(nextSymbol))
{
dfa[nextState].Add(nextSymbol, nextState2);
}
}
}
}
}
}
原文地址: https://www.cveoy.top/t/topic/fZCs 著作权归作者所有。请勿转载和采集!