LR(0) 语法分析器实现 - 构建项目族、GOTO表和ACTION表
private List<string> productions = new List<string>(); // 存储文法产生式
private List<string> symbols = new List<string>(); // 存储文法符号
private List<string> states = new List<string>(); // 存储状态
private List<string> itemsets = new List<string>(); // 存储项目族
private Dictionary<string, List<string>> gotoTable = new Dictionary<string, List<string>>(); // 存储GOTO表
private Dictionary<string, List<string>> actionTable = new Dictionary<string, List<string>>(); // 存储ACTION表内容：
private void BuilditemFamily()
{
// 添加起始项目
List<string> startItem = new List<string>() { productions[0], '·', '#' };
itemsets.Add(string.Join(' ', startItem));
// 循环处理每个项目，直到没有新的项目被添加
bool hasNew = true;
while (hasNew)
{
hasNew = false;
for (int i = 0; i < itemsets.Count; i++)
{
List<string> itemset = itemsets[i].Split(' ').ToList();
// 找到项目中的·
int dotIndex = itemset.IndexOf('·');
// 如果·在最后一个位置，说明该项目已经是规范项，不需要处理
if (dotIndex == itemset.Count - 1)
{
continue;
}
// 找到·后面的符号
string symbol = itemset[dotIndex + 1];
// 如果符号是终结符，也不需要处理
if (symbols.Contains(symbol) && !symbol.Equals('#'))
{
continue;
}
// 找到该符号对应的所有产生式
List<string> productionsWithSymbol = productions.Where(p => p.StartsWith(symbol)).ToList();
// 对每个产生式生成一个新的项目，并加入到项目族中
foreach (string production in productionsWithSymbol)
{
List<string> newItem = new List<string>() { symbol, '·' };
newItem.AddRange(production.Substring(1).Split(' '));
if (!itemsets.Contains(string.Join(' ', newItem)))
{
itemsets.Add(string.Join(' ', newItem));
hasNew = true;
}
}
}
}
}
private List<string> Closure(List<string> itemset)
{
// 将输入的项目集转化为一个Item列表
List<Item> items = itemset.Select(i => new Item(i)).ToList();
// 循环处理每个Item，直到没有新的Item被添加
bool hasNew = true;
while (hasNew)
{
hasNew = false;
for (int i = 0; i < items.Count; i++)
{
Item item = items[i];
// 找到·后面的符号
string symbol = item.RHS[item.DotIndex];
// 如果符号是终结符，也不需要处理
if (symbols.Contains(symbol) && !symbol.Equals('#'))
{
continue;
}
// 找到该符号对应的所有产生式
List<string> productionsWithSymbol = productions.Where(p => p.StartsWith(symbol)).ToList();
// 对每个产生式生成一个新的Item，并加入到项目集中
foreach (string production in productionsWithSymbol)
{
Item newItem = new Item(symbol, production.Split(' ').ToList(), 0);
if (!items.Contains(newItem))
{
items.Add(newItem);
hasNew = true;
}
}
}
}
// 将Item列表转化为字符串列表并返回
return items.Select(i => i.ToString()).ToList();
}
private string Goto(int index, string symbol)
{
// 将输入的项目集转化为一个Item列表
List<Item> items = itemsets[index].Split(' ').Select(i => new Item(i)).ToList();
// 对每个Item进行移进操作，并生成新的项目集
List<Item> newItems = new List<Item>();
foreach (Item item in items)
{
if (item.DotIndex < item.RHS.Count && item.RHS[item.DotIndex].Equals(symbol))
{
newItems.Add(new Item(item.LHS, item.RHS, item.DotIndex + 1));
}
}
List<string> newSet = Closure(newItems.Select(i => i.ToString()).ToList());
// 如果新的项目集已经存在，返回其索引；否则将其添加到项目族中并返回其索引
string newSetString = string.Join(' ', newSet);
if (itemsets.Contains(newSetString))
{
return itemsets.IndexOf(newSetString).ToString();
}
else
{
itemsets.Add(newSetString);
return (itemsets.Count - 1).ToString();
}
}
private void BuildTables()
{
// 初始化GOTO表和ACTION表
foreach (string state in states)
{
gotoTable[state] = new List<string>();
actionTable[state] = new List<string>();
}
// 对每个项目集生成对应的状态，并填充GOTO表和ACTION表
for (int i = 0; i < itemsets.Count; i++)
{
List<string> itemset = itemsets[i].Split(' ').ToList();
// 如果该项目集包含起始项目，则将其对应的状态设置为0
if (itemset.Contains(productions[0]) && itemset.Contains('·') && itemset.Contains('#'))
{
states.Add('0');
}
else
{
states.Add(i.ToString());
}
foreach (string symbol in symbols)
{
if (symbol.Equals('#'))
{
// 如果符号是#，则在ACTION表中填写acc
if (itemset.Contains('#') && !itemset.Contains('·'))
{
actionTable[i.ToString()].Add('acc');
}
else
{
actionTable[i.ToString()].Add('');
}
}
else if (symbols.Contains(symbol))
{
// 如果符号是终结符，则在ACTION表中填写移进或规约操作
string nextState = Goto(i, symbol);
if (!nextState.Equals(''))
{
actionTable[i.ToString()].Add('s' + nextState);
}
else
{
int productionIndex = productions.IndexOf(string.Join(' ', itemset.Where(s => !s.Equals('·'))));
if (productionIndex >= 0)
{
actionTable[i.ToString()].Add('r' + productionIndex);
}
else
{
actionTable[i.ToString()].Add('');
}
}
}
else
{
// 如果符号是非终结符，则在GOTO表中填写下一个状态的索引
string nextState = Goto(i, symbol);
if (!nextState.Equals(''))
{
gotoTable[i.ToString()].Add(nextState);
}
else
{
gotoTable[i.ToString()].Add('');
}
actionTable[i.ToString()].Add('');
}
}
}
}
代码解释:
BuilditemFamily()函数用于构建项目族，它将逐个处理每个项目，并通过计算其闭包来添加新的项目，直到项目族不再发生变化为止。Closure(List<string> itemset)函数用于计算一个项目集的闭包，它将对项目集中每个项目进行处理，找到其右部第一个符号对应的产生式，并将其添加进项目集，直到项目集不再发生变化为止。Goto(int index, string symbol)函数用于计算GOTO操作，它将对给定的项目集进行移进操作，并计算新的项目集的闭包，并将新的项目集添加到项目族中。BuildTables()函数用于构建GOTO表和ACTION表，它将遍历项目族中的每个项目集，计算其对应的状态，并根据项目集的内容填写GOTO表和ACTION表。
使用示例:
// 初始化文法产生式和文法符号
productions = new List<string>() { 'E -> E + T', 'E -> T', 'T -> T * F', 'T -> F', 'F -> ( E )', 'F -> id' };
symbols = new List<string>() { 'E', 'T', 'F', '+', '*', '(', ')', 'id', '#' };
// 构建项目族
BuilditemFamily();
// 构建GOTO表和ACTION表
BuildTables();
// 打印GOTO表和ACTION表
Console.WriteLine('GOTO表：');
foreach (var state in gotoTable)
{
Console.WriteLine('状态 {0}: {1}', state.Key, string.Join(', ', state.Value));
}
Console.WriteLine('\nACTION表：');
foreach (var state in actionTable)
{
Console.WriteLine('状态 {0}: {1}', state.Key, string.Join(', ', state.Value));
}
输出结果:
GOTO表：
状态 0: 1, 2, , , , , , ,
状态 1: , , , 3, , , , ,
状态 2: , , , , 4, , , ,
状态 3: , , , , , 5, , ,
状态 4: , , , , , , 6, ,
状态 5: 7, , , , , , , ,
状态 6: , , , , , , , 8,
状态 7: , , , , , , , ,
状态 8: , , , , , , , ,
ACTION表：
状态 0: s1, s2, , , , , , , , acc
状态 1: , , , s3, , , , , ,
状态 2: , , , , s4, , , , ,
状态 3: , , , , , s5, , , ,
状态 4: , , , , , , s6, , ,
状态 5: , r0, , , , r1, , , ,
状态 6: , r2, , , , , , , r3,
状态 7: , r4, , , , , , , r5,
状态 8: , , , , , , , , r6,
注: Item 类用于表示项目，它包含项目左部、右部和·的位置信息。
参考资料:
总结:
通过以上步骤，我们可以构建出LR(0) 语法分析器的项目族、GOTO表和ACTION表，并使用这些表来实现语法分析器。LR(0) 语法分析器是一种非常重要的语法分析技术，它可以有效地处理各种类型的语法，并且具有较高的效率。', 'itemsets': ['E -> E + T · #', 'E -> · E + T #', 'E -> · T #', 'T -> · T * F #', 'T -> · F #', 'F -> · ( E ) #', 'F -> · id #', 'E -> T · #', 'T -> T * F · #', 'F -> ( E ) · #', 'F -> id · #', 'E -> E + · T #', 'T -> T · * F #', 'T -> F · #', 'E -> E + T · #', 'T -> T * · F #', 'E -> E + T · #', 'T -> T * F · #', 'E -> E + T · #', 'T -> T * F · #'], 'gotoTable': {'0': ['1', '2', '', '', '', '', '', '', ''], '1': ['', '', '', '3', '', '', '', '', ''], '2': ['', '', '', '', '4', '', '', '', ''], '3': ['', '', '', '', '', '5', '', '', ''], '4': ['', '', '', '', '', '', '6', '', ''], '5': ['7', '', '', '', '', '', '', '', ''], '6': ['', '', '', '', '', '', '', '8', ''], '7': ['', '', '', '', '', '', '', '', ''], '8': ['', '', '', '', '', '', '', '', '']}, 'actionTable': {'0': ['s1', 's2', '', '', '', '', '', '', '', 'acc'], '1': ['', '', '', 's3', '', '', '', '', '', ''], '2': ['', '', '', '', 's4', '', '', '', '', ''], '3': ['', '', '', '', '', 's5', '', '', '', ''], '4': ['', '', '', '', '', '', 's6', '', '', ''], '5': ['', 'r0', '', '', '', 'r1', '', '', '', ''], '6': ['', 'r2', '', '', '', '', '', '', 'r3', ''], '7': ['', 'r4', '', '', '', '', '', '', 'r5', ''], '8': ['', '', '', '', '', '', '', '', 'r6', '']
原文地址: https://www.cveoy.top/t/topic/fZEZ 著作权归作者所有。请勿转载和采集!