LR(0) 自动机构建算法实现
LR(0) 自动机构建算法实现
本文将介绍LR(0) 自动机构建算法的实现代码,并详细解释代码中的关键步骤和函数。
代码实现:
private void BuilditemFamily()
{
// 初始化
productions = richTextBox1.Lines.ToList(); // 读取文法产生式
symbols = GetSymbols(); // 获取文法符号
// 生成初始项目集
List<string> initSet = new List<string>();
initSet.Add($'{symbols[0]}->{symbols[1]}.'); // 添加初始项目
List<string> closure = LR0Closure(initSet); // 计算闭包
string initState = 'I0'; // 初始状态
itemsets.Add(GetItemSetString(initState, closure)); // 存储初始项目集
// 构建项目集族
int i = 0; // 当前状态编号
while (i < itemsets.Count)
{
string[] itemSet = itemsets[i].Split('\n'); // 当前项目集
Dictionary<string, List<string>> nextItemSets = new Dictionary<string, List<string>>(); // 存储当前项目集下一个状态对应的项目集
foreach (string item in itemSet)
{
string[] itemParts = item.Split('->'.ToCharArray(), StringSplitOptions.RemoveEmptyEntries);
string lhs = itemParts[0].Trim();
string rhs = itemParts[1].Trim();
if (rhs.IndexOf('.') == rhs.Length - 1) continue; // 点在末尾,无需计算下一个状态
string nextSymbol = rhs[rhs.IndexOf('.') + 1].ToString(); // 下一个文法符号
List<string> nextSet = LR0Goto(itemSet, nextSymbol); // 计算下一个状态对应的项目集
if (nextSet.Count > 0 && !nextItemSets.Values.Any(ns => ns.SequenceEqual(nextSet))) // 判断是否已经存在该状态对应的项目集
{
string nextState = $'I{itemsets.Count}'; // 生成状态编号
nextItemSets.Add(nextState, nextSet); // 存储状态和对应的项目集
itemsets.Add(GetItemSetString(nextState, nextSet)); // 存储项目集
}
}
// 构建转移表
foreach (KeyValuePair<string, List<string>> entry in nextItemSets)
{
string nextState = entry.Key;
List<string> nextSet = entry.Value;
string transition = GetTransitionSymbol(itemSet, nextSet);
int stateIndex = states.IndexOf(itemsets[i]);
if (stateIndex == -1) // 新状态,添加到状态列表
{
states.Add(itemsets[i]);
stateIndex = states.Count - 1;
}
int nextStateIndex = states.IndexOf(GetItemSetString(nextState, nextSet));
if (nextStateIndex == -1) // 新状态,添加到状态列表
{
states.Add(GetItemSetString(nextState, nextSet));
nextStateIndex = states.Count - 1;
}
// 添加转移
if (transition != '')
{
dataGridView1.Rows[stateIndex].Cells[symbols.IndexOf(transition)].Value = $'S{nextStateIndex}';
}
else
{
dataGridView1.Rows[stateIndex].Cells[symbols.IndexOf(nextSymbol)].Value = $'S{nextStateIndex}';
}
}
i++;
}
}
// 获取文法符号
private List<string> GetSymbols()
{
List<string> symbols = new List<string>();
symbols.Add(''); // 空符号
foreach (string production in productions)
{
string[] parts = production.Split('->'.ToCharArray(), StringSplitOptions.RemoveEmptyEntries);
string lhs = parts[0].Trim(); // 左部符号
if (!symbols.Contains(lhs)) symbols.Add(lhs);
string rhs = parts[1].Trim(); // 右部符号
foreach (char c in rhs)
{
if (!symbols.Contains(c.ToString())) symbols.Add(c.ToString());
}
}
return symbols;
}
// 计算LR(0)闭包
private List<string> LR0Closure(List<string> itemSet)
{
List<string> closure = new List<string>(itemSet);
bool changed = true;
while (changed)
{
changed = false;
List<string> newItems = new List<string>();
foreach (string item in closure)
{
string[] itemParts = item.Split('->'.ToCharArray(), StringSplitOptions.RemoveEmptyEntries);
string lhs = itemParts[0].Trim();
string rhs = itemParts[1].Trim();
if (rhs.IndexOf('.') == rhs.Length - 1) continue; // 点在末尾,无需计算闭包
string nextSymbol = rhs[rhs.IndexOf('.') + 1].ToString(); // 下一个文法符号
if (IsNonTerminal(nextSymbol))
{
foreach (string production in productions)
{
string[] parts = production.Split('->'.ToCharArray(), StringSplitOptions.RemoveEmptyEntries);
string productionLHS = parts[0].Trim();
string productionRHS = parts[1].Trim();
if (productionLHS == nextSymbol && !closure.Contains($'{nextSymbol}->{productionRHS}.'))
{
newItems.Add($'{nextSymbol}->{productionRHS}.');
changed = true;
}
}
}
}
closure.AddRange(newItems);
}
return closure;
}
// 计算LR(0)Goto
private List<string> LR0Goto(string[] itemSet, string symbol)
{
List<string> gotoSet = new List<string>();
foreach (string item in itemSet)
{
string[] itemParts = item.Split('->'.ToCharArray(), StringSplitOptions.RemoveEmptyEntries);
string lhs = itemParts[0].Trim();
string rhs = itemParts[1].Trim();
if (rhs.IndexOf('.') == rhs.Length - 1) continue; // 点在末尾,无需计算Goto
string nextSymbol = rhs[rhs.IndexOf('.') + 1].ToString(); // 下一个文法符号
if (nextSymbol == symbol)
{
string newItem = $'{lhs}->{rhs.Substring(0, rhs.IndexOf('.'))}{nextSymbol}.{rhs.Substring(rhs.IndexOf('.') + 2)}';
gotoSet.Add(newItem);
}
}
return LR0Closure(gotoSet);
}
// 判断符号是否为非终结符
private bool IsNonTerminal(string symbol)
{
return symbols.IndexOf(symbol) != -1 && Char.IsUpper(symbol[0]);
}
// 获取项目集字符串
private string GetItemSetString(string state, List<string> itemSet)
{
StringBuilder sb = new StringBuilder();
sb.AppendLine($'{state}:');
foreach (string item in itemSet)
{
sb.AppendLine($' {item}');
}
return sb.ToString();
}
// 获取状态转移符号
private string GetTransitionSymbol(string[] fromItemSet, List<string> toItemSet)
{
foreach (string fromItem in fromItemSet)
{
string[] fromParts = fromItem.Split('->'.ToCharArray(), StringSplitOptions.RemoveEmptyEntries);
string fromRHS = fromParts[1].Trim();
if (fromRHS.IndexOf('.') == fromRHS.Length - 1) continue; // 点在末尾,无需计算转移符号
string nextSymbol = fromRHS[fromRHS.IndexOf('.') + 1].ToString(); // 下一个文法符号
if (toItemSet.Any(t => t.Contains(nextSymbol) && t.IndexOf('.') == t.IndexOf(nextSymbol) - 1))
{
return nextSymbol;
}
}
return '';
}
代码解释:
-
BuilditemFamily()函数:- 该函数用于构建LR(0) 项目集族,并根据项目集族构建状态转移表。
- 代码首先读取文法产生式并获取文法符号。
- 然后生成初始项目集,并计算其闭包,得到初始状态的项目集。
- 接着,代码使用循环遍历每个状态的项目集,计算每个项目集的下一个状态对应的项目集。
- 最后,根据状态和其下一个状态的项目集,构建状态转移表。
-
GetSymbols()函数:- 该函数用于获取文法符号列表,包括非终结符和终结符。
- 代码遍历文法产生式,提取每个产生式的左部和右部符号,并将其添加到符号列表中。
-
LR0Closure()函数:- 该函数用于计算LR(0) 闭包,即在项目集中添加所有能够通过闭包规则添加的项目。
- 代码使用循环遍历项目集中的每个项目,找到点号后的符号,并根据该符号在文法产生式中的定义,添加新的项目到闭包中。
-
LR0Goto()函数:- 该函数用于计算LR(0) Goto,即根据当前状态和一个文法符号,计算下一个状态对应的项目集。
- 代码遍历当前状态的项目集,找到点号后的符号,如果该符号等于输入的文法符号,则将该项目移动点号到下一个位置,并添加到新的项目集中。
-
IsNonTerminal()函数:- 该函数用于判断一个符号是否为非终结符。
- 代码判断符号是否在符号列表中,并且首字母是否为大写,来判断是否为非终结符。
-
GetItemSetString()函数:- 该函数用于将一个项目集转换为字符串格式,方便显示和调试。
- 代码将状态编号和项目集中的每个项目拼接成一个字符串,并返回该字符串。
-
GetTransitionSymbol()函数:- 该函数用于获取两个项目集之间的转移符号。
- 代码遍历第一个项目集中的每个项目,找到点号后的符号,如果该符号能够转移到第二个项目集,则返回该符号。
代码中的错误:
代码中LR0Goto 函数的参数类型错误,应将List<string> 改为 string[]。
代码修改:
// 计算LR(0)Goto
private List<string> LR0Goto(string[] itemSet, string symbol)
{
// ...
}
总结:
本文介绍了LR(0) 自动机构建算法的实现代码,并详细解释了代码中的关键步骤和函数。通过阅读本文,读者可以了解LR(0) 自动机构建算法的具体实现过程,并能够根据需要进行代码的修改和扩展。
注意:
代码中的richTextBox1 和 dataGridView1 对应GUI界面中的控件,实际应用中需要根据具体情况进行修改。
原文地址: https://www.cveoy.top/t/topic/oHyh 著作权归作者所有。请勿转载和采集!