LR(0) 文法项目集族构建算法实现
private void BuilditemFamily()
{
// 初始化
productions = richTextBox1.Lines.ToList();
productions.RemoveAll(x => x == ''); // 去除空行
symbols = GetSymbols(productions);
states.Clear();
itemsets.Clear();
// 生成初始项目集
List<string> initialItemset = new List<string>();
initialItemset.Add($'{productions[0].Split(' ')[0]}->{productions[0].Split(' ')[1]}.'); // 第一个产生式的初始项目
HashSet<string> closure = GetClosure(initialItemset);
states.Add('I0');
itemsets.Add(string.Join('\n', closure));
// 构建项目集族
int curStateIndex = 0;
while (curStateIndex < states.Count)
{
string curState = states[curStateIndex];
HashSet<Item> curItemSet = GetItemSet(itemsets[curStateIndex]);
Dictionary<string, HashSet<Item>> goToDict = GetGoToDict(curItemSet);
foreach (string symbol in symbols)
{
if (goToDict.ContainsKey(symbol))
{
HashSet<Item> goToItemSet = goToDict[symbol];
string goToItemSetStr = string.Join('\n', goToItemSet);
if (!states.Contains(goToItemSetStr))
{
states.Add(goToItemSetStr);
itemsets.Add(goToItemSetStr);
}
}
}
curStateIndex++;
}
}
// 获取文法符号集合
private List<string> GetSymbols(List<string> productions)
{
List<string> symbols = new List<string>();
foreach (string production in productions)
{
string[] productionArr = production.Split(' ');
foreach (string symbol in productionArr)
{
if (!symbols.Contains(symbol))
{
symbols.Add(symbol);
}
}
}
symbols.Remove('->'); // 去除产生式符号
return symbols;
}
// 获取项目集的闭包
private HashSet<string> GetClosure(List<string> itemset)
{
HashSet<Item> closureItemSet = new HashSet<Item>();
foreach (string item in itemset)
{
string[] itemArr = item.Split('.');
string lhs = itemArr[0];
string[] rhsArr = itemArr[1].Split(' ');
int dotIndex = itemArr[1].IndexOf('.') + 1;
HashSet<string> lookahead = new HashSet<string>();
if (dotIndex < itemArr[1].Length)
{
lookahead = GetFirst(itemArr[1].Substring(dotIndex));
}
Item closureItem = new Item(lhs, rhsArr.ToList(), dotIndex);
closureItemSet.Add(closureItem);
foreach (string production in productions)
{
if (production.StartsWith(lhs))
{
string[] productionArr = production.Split(' ');
Item newItem = new Item(lhs, productionArr.ToList().GetRange(1, productionArr.Length - 1), 0);
if (!closureItemSet.Contains(newItem))
{
foreach (string lookaheadSymbol in lookahead)
{
newItem.RHS.Add(lookaheadSymbol);
closureItemSet.Add(newItem);
newItem.RHS.RemoveAt(newItem.RHS.Count - 1);
}
}
}
}
}
HashSet<string> closureStrSet = new HashSet<string>();
foreach (Item closureItem in closureItemSet)
{
closureStrSet.Add(closureItem.ToString());
}
return closureStrSet;
}
// 获取项目集
private HashSet<Item> GetItemSet(string itemsetStr)
{
HashSet<Item> itemSet = new HashSet<Item>();
string[] itemArr = itemsetStr.Split('\n');
foreach (string item in itemArr)
{
string[] itemParts = item.Split('.');
string lhs = itemParts[0];
string[] rhsArr = itemParts[1].Split(' ');
int dotIndex = itemParts[1].IndexOf('.') + 1;
itemSet.Add(new Item(lhs, rhsArr.ToList(), dotIndex));
}
return itemSet;
}
// 获取一个符号的FIRST集
private HashSet<string> GetFirst(string symbol)
{
HashSet<string> firstSet = new HashSet<string>();
if (symbol == '') // 空串
{
firstSet.Add('');
return firstSet;
}
string firstSymbol = symbol.Split(' ')[0];
if (IsTerminal(firstSymbol)) // 终结符
{
firstSet.Add(firstSymbol);
return firstSet;
}
foreach (string production in productions) // 非终结符
{
if (production.StartsWith(firstSymbol))
{
string[] productionArr = production.Split(' ');
if (productionArr.Length == 1) // 产生式为A->空
{
if (symbol.Length == firstSymbol.Length) // 第一个符号为A
{
firstSet.Add('');
}
else // 第一个符号不为A
{
HashSet<string> nextFirstSet = GetFirst(symbol.Substring(firstSymbol.Length + 1));
foreach (string nextFirstSymbol in nextFirstSet)
{
firstSet.Add(nextFirstSymbol);
}
}
}
else // 产生式为A->BCD...
{
HashSet<string> nextFirstSet = GetFirst(symbol.Substring(firstSymbol.Length + 1));
foreach (string nextFirstSymbol in nextFirstSet)
{
firstSet.Add(nextFirstSymbol);
}
if (nextFirstSet.Contains('')) // B可以推出空
{
HashSet<string> restFirstSet = GetFirst(symbol.Substring(firstSymbol.Length + 1 + ' '.Length));
foreach (string restFirstSymbol in restFirstSet)
{
firstSet.Add(restFirstSymbol);
}
}
}
}
}
return firstSet;
}
// 判断一个符号是否为终结符
private bool IsTerminal(string symbol)
{
foreach (string production in productions)
{
if (production.StartsWith(symbol))
{
string[] productionArr = production.Split(' ');
if (productionArr.Length == 1) // 产生式为A->空
{
return false;
}
else // 产生式为A->BCD...
{
for (int i = 1; i < productionArr.Length; i++)
{
if (productionArr[i] == symbol)
{
return false;
}
}
}
}
}
return true;
}
// 获取所有项集的GOTO函数字典
private Dictionary<string, HashSet<Item>> GetGoToDict(HashSet<Item> itemSet)
{
Dictionary<string, HashSet<Item>> goToDict = new Dictionary<string, HashSet<Item>>();
foreach (Item item in itemSet)
{
if (item.dotIndex < item.RHS.Count)
{
string nextSymbol = item.RHS[item.dotIndex];
List<string> newRHS = new List<string>(item.RHS);
newRHS[item.dotIndex] = '.';
newRHS.Insert(item.dotIndex + 1, nextSymbol);
HashSet<string> lookahead = new HashSet<string>();
if (item.dotIndex + 1 < item.RHS.Count)
{
lookahead = GetFirst(string.Join(' ', item.RHS.GetRange(item.dotIndex + 1, item.RHS.Count - item.dotIndex - 1)));
}
else
{
lookahead.Add('$');
}
Item newItem = new Item(item.LHS, newRHS, item.dotIndex + 1);
foreach (string lookaheadSymbol in lookahead)
{
newItem.RHS.Add(lookaheadSymbol);
if (!goToDict.ContainsKey(nextSymbol))
{
goToDict[nextSymbol] = new HashSet<Item>();
}
goToDict[nextSymbol].Add(newItem);
newItem.RHS.RemoveAt(newItem.RHS.Count - 1);
}
}
}
return goToDict;
}
// 项目类
private class Item
{
public string LHS { get; set; }
public List<string> RHS { get; set; }
public int dotIndex { get; set; }
public Item(string lhs, List<string> rhs, int dotIndex)
{
this.LHS = lhs;
this.RHS = rhs;
this.dotIndex = dotIndex;
}
public override string ToString()
{
List<string> tempRHS = new List<string>(RHS);
tempRHS.Insert(dotIndex, '.');
return $'{LHS}->{string.Join('', tempRHS)}';
}
}
原文地址: https://www.cveoy.top/t/topic/oHyK 著作权归作者所有。请勿转载和采集!