C#实现预测分析表构建：LL(1)文法分析器
using System;
using System.Collections.Generic;
using System.Linq;
using System.Windows.Forms;
public class Select
{
// 存储 SELECT 集
private Dictionary<string, List<string>> selects1 = new Dictionary<string, List<string>>();
// 构造函数
public Select() { }
// 获取 SELECT 集
public Dictionary<string, List<string>> GetSelect(Dictionary<string, List<string>> production1, Dictionary<string, List<string>> firsts1, Dictionary<string, List<string>> follows1)
{
// 初始化 SELECT 集
selects1 = new Dictionary<string, List<string>>();
foreach (var item in production1)
selects1.Add(item.Key, new List<string>());
// 遍历每个产生式，计算对应的 SELECT 集
foreach (var nonterm in production1.Keys)
{
foreach (var prod in production1[nonterm])
{
List<string> select = new List<string>();
bool flag = true;
// 对于产生式中的每个符号，计算其 FIRST 集
foreach (var s in prod)
{
if (IsTerminal(s))
{
select.Add(s.ToString());
flag = false;
break;
}
else
{
GetFirst(s.ToString(), production1, firsts1);
foreach (var f in firsts1[s.ToString()])
{
if (!f.Equals('#') && !select.Contains(f))
select.Add(f);
}
if (!IsReachEmpty(s.ToString(), production1))
{
flag = false;
break;
}
}
}
// 如果产生式中所有符号的 FIRST 集都包含空串，则将 FOLLOW 集加入 SELECT 集中
if (flag)
{
GetFollow(nonterm, production1, firsts1, follows1);
foreach (var f in follows1[nonterm])
{
if (!select.Contains(f))
select.Add(f);
}
}
selects1[nonterm].Add(string.Join(" ", select.ToArray()));
}
}
return selects1;
}
// 判断字符是否为终结符
private bool IsTerminal(char symbol)
{
return !char.IsUpper(symbol);
}
// 计算符号的 FIRST 集
private void GetFirst(string symbol, Dictionary<string, List<string>> production1, Dictionary<string, List<string>> firsts1)
{
if (!firsts1.ContainsKey(symbol))
{
firsts1.Add(symbol, new List<string>());
if (IsTerminal(symbol[0]))
{
firsts1[symbol].Add(symbol);
}
else
{
foreach (var prod in production1[symbol])
{
bool flag = true;
foreach (var s in prod)
{
if (IsTerminal(s))
{
if (!firsts1[symbol].Contains(s.ToString()))
firsts1[symbol].Add(s.ToString());
flag = false;
break;
}
else
{
GetFirst(s.ToString(), production1, firsts1);
foreach (var f in firsts1[s.ToString()])
{
if (!f.Equals('#') && !firsts1[symbol].Contains(f))
firsts1[symbol].Add(f);
}
if (!IsReachEmpty(s.ToString(), production1))
{
flag = false;
break;
}
}
}
if (flag)
firsts1[symbol].Add('#');
}
}
}
}
// 判断符号的 FIRST 集是否包含空串
private bool IsReachEmpty(string symbol, Dictionary<string, List<string>> production1)
{
if (IsTerminal(symbol[0]))
return false;
foreach (var prod in production1[symbol])
{
bool flag = true;
foreach (var s in prod)
{
if (IsTerminal(s))
{
flag = false;
break;
}
else
{
if (!IsReachEmpty(s.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)
{
if (!follows1.ContainsKey(symbol))
{
follows1.Add(symbol, new List<string>());
if (symbol.Equals("S"))
follows1[symbol].Add("#");
foreach (var nonterm in production1.Keys)
{
foreach (var prod in production1[nonterm])
{
for (int i = 0; i < prod.Length; i++)
{
if (prod[i].ToString().Equals(symbol))
{
if (i == prod.Length - 1)
{
if (!nonterm.Equals(symbol))
{
GetFollow(nonterm, production1, firsts1, follows1);
foreach (var f in follows1[nonterm])
{
if (!follows1[symbol].Contains(f))
follows1[symbol].Add(f);
}
}
}
else
{
bool flag = true;
for (int j = i + 1; j < prod.Length; j++)
{
if (IsTerminal(prod[j]))
{
if (!follows1[symbol].Contains(prod[j].ToString()) && !prod[j].ToString().Equals('#'))
follows1[symbol].Add(prod[j].ToString());
flag = false;
break;
}
else
{
GetFirst(prod[j].ToString(), production1, firsts1);
foreach (var f in firsts1[prod[j].ToString()])
{
if (!f.Equals('#') && !follows1[symbol].Contains(f))
follows1[symbol].Add(f);
}
if (!IsReachEmpty(prod[j].ToString(), production1))
{
flag = false;
break;
}
}
}
if (flag)
{
if (!nonterm.Equals(symbol))
{
GetFollow(nonterm, production1, firsts1, follows1);
foreach (var f in follows1[nonterm])
{
if (!follows1[symbol].Contains(f))
follows1[symbol].Add(f);
}
}
}
}
}
}
}
}
}
}
// 构建预测分析表
public Dictionary<string, Dictionary<string, string>> GetPredictTable(Dictionary<string, List<string>> production1, Dictionary<string, List<string>> firsts1, Dictionary<string, List<string>> follows1)
{
// 初始化预测分析表
Dictionary<string, Dictionary<string, string>> predictTable = new Dictionary<string, Dictionary<string, string>>();
foreach (var item in production1)
{
predictTable.Add(item.Key, new Dictionary<string, string>());
foreach (var terminal in follows1.Keys)
{
predictTable[item.Key].Add(terminal, "");
}
}
// 遍历每个产生式，计算对应的 SELECT 集并填充预测分析表
selects1 = GetSelect(production1, firsts1, follows1);
foreach (var nonterm in selects1.Keys)
{
foreach (var prod in selects1[nonterm])
{
List<string> select = prod.Value.Split(' ').ToList();
foreach (var term in select)
{
if (!term.Equals("#"))
{
if (!predictTable[nonterm][term].Equals(""))
{
MessageBox.Show("该文法不是LL(1)文法！产生冲突：" + nonterm + " -> " + prod.Key);
return null;
}
else
{
predictTable[nonterm][term] = prod.Key;
}
}
else
{
foreach (var follow in follows1[nonterm])
{
if (!predictTable[nonterm][follow].Equals(""))
{
MessageBox.Show("该文法不是LL(1)文法！产生冲突：" + nonterm + " -> " + prod.Key);
return null;
}
else
{
predictTable[nonterm][follow] = prod.Key;
}
}
}
}
}
}
// 输出预测分析表到listView3中
// 此部分代码需要根据你的具体环境进行修改，此处仅提供示例
// listView3.Columns.Clear();
// listView3.Items.Clear();
// listView3.Columns.Add("");
// foreach (var terminal in follows1.Keys)
// {
// listView3.Columns.Add(terminal);
// }
// foreach (var nonterm in predictTable.Keys)
// {
// ListViewItem item = new ListViewItem(nonterm);
// foreach (var terminal in follows1.Keys)
// {
// item.SubItems.Add(predictTable[nonterm][terminal]);
// }
// listView3.Items.Add(item);
// }
return predictTable;
}
}
使用示例：
// 定义产生式
Dictionary<string, List<string>> production1 = new Dictionary<string, List<string>>
{
{ "S", new List<string> { "E" } },
{ "E", new List<string> { "T + E", "T" } },
{ "T", new List<string> { "F * T", "F" } },
{ "F", new List<string> { "( E )", "id" } }
};
// 初始化 FIRST 集和 FOLLOW 集
Dictionary<string, List<string>> firsts1 = new Dictionary<string, List<string>>();
Dictionary<string, List<string>> follows1 = new Dictionary<string, List<string>>();
// 构建 SELECT 集并生成预测分析表
Select select = new Select();
Dictionary<string, Dictionary<string, string>> predictTable = select.GetPredictTable(production1, firsts1, follows1);
// 输出预测分析表
// ...
说明：
- 代码中使用了递归的方式计算 FIRST 集和 FOLLOW 集，并根据 SELECT 集构建预测分析表。
GetPredictTable方法中包含了判断文法是否为 LL(1) 文法的逻辑，如果产生冲突，会弹出错误提示。GetSelect方法用于根据 FIRST 集和 FOLLOW 集计算每个产生式的 SELECT 集。IsTerminal方法用于判断字符是否为终结符。GetFirst方法用于计算符号的 FIRST 集。IsReachEmpty方法用于判断符号的 FIRST 集是否包含空串。GetFollow方法用于计算符号的 FOLLOW 集。- 示例代码中展示了如何使用代码构建预测分析表。
注意事项：
- 该代码仅用于示例目的，可能需要根据你的具体需求进行修改和完善。
- 使用该代码之前，请确保你已经了解了 LL(1) 文法相关的知识。
- 在实际应用中，建议使用专门的编译器生成工具或库来构建预测分析表，以保证代码的稳定性和可维护性。
原文地址: http://www.cveoy.top/t/topic/ox8s 著作权归作者所有。请勿转载和采集!