LL(1)文法判断工具 - 在线验证文法是否为LL(1)文法
这是一个使用C#语言编写的LL(1)文法判断工具，它能够帮助用户判断输入的文法是否为LL(1)文法。
功能介绍：
- 输入文法: 用户可以在文本框中输入文法规则，以换行符分隔每条规则。
- 判断: 点击“判断”按钮，程序将对输入的文法进行分析，并判断其是否为LL(1)文法。
- 结果显示: 程序会显示判断结果，并输出FIRST集合和FOLLOW集合。
代码实现：
public partial class Form4 : Form
{
public Form4()
{
InitializeComponent();
}
//--------------------预处理
private void groupBox1_Enter(object sender, EventArgs e)
{
}
private void button3_Click(object sender, EventArgs e)
{
richTextBox1.Text = '';
OpenFileDialog openFileDialog1 = new OpenFileDialog();
DialogResult dr = openFileDialog1.ShowDialog();
string filename = openFileDialog1.FileName;//获取或设置一个包含在文件对话框中选定的文件名字符串
if (dr == DialogResult.OK && !string.IsNullOrEmpty(filename))
{
StreamReader sr = new StreamReader(filename);
richTextBox1.Text = sr.ReadToEnd();
sr.Close();
}
}
private void Form4_Load(object sender, EventArgs e)
{
}
private void button4_Click(object sender, EventArgs e)
{
string text = richTextBox1.Text;
Dictionary<string, List<string>> production = new Dictionary<string, List<string>>();
string[] pro = text.Split('\n');
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);
}
Dictionary<string, List<string>> firsts = new Dictionary<string, List<string>>();
foreach (var item in production.Keys)
GetFirst(item, production, firsts);
Dictionary<string, List<string>> follows = new Dictionary<string, List<string>>();
foreach (var item in production.Keys)
GetFollow(item, production, firsts, follows);
if (JudgeLL1(production, firsts, follows))
{
MessageBox.Show('该文法是LL(1)文法\n');
foreach (var item in firsts)
{
richTextBox2.AppendText(item.Key + ': { ');
foreach (var s in item.Value)
richTextBox2.AppendText(s + ' ');
richTextBox2.AppendText('}
');
}
richTextBox2.AppendText('FOLLOW集：\n');
foreach (var item in follows)
{
richTextBox2.AppendText(item.Key + ': { ');
foreach (var s in item.Value)
richTextBox2.AppendText(s + ' ');
richTextBox2.AppendText('}
');
}
}
else
{
MessageBox.Show('该文法不是LL(1)文法，存在左递归或者存在FIRST集合有交集的情况！\n');
}
}
static void GetFirst(string symbol, Dictionary<string, List<string>> production, Dictionary<string, List<string>> firsts)
{
if (firsts.ContainsKey(symbol))
{
return;
}
firsts.Add(symbol, new List<string>());
foreach (var prod in production[symbol])
{
if (prod.Length > 0 && IsTerminal(prod[0]))
{
if (!firsts[symbol].Contains(prod[0].ToString()))
firsts[symbol].Add(prod[0].ToString());
continue;
}
else if (prod.Length > 0 && !IsTerminal(prod[0]))
{
GetFirst(prod[0].ToString(), production, firsts);
foreach (var f in firsts[prod[0].ToString()])
{
if (!firsts[symbol].Contains(f) && !f.Equals('#'))
firsts[symbol].Add(f);
}
}
if (prod.Length > 0 && !IsTerminal(prod[0]) && prod[0].ToString() == 'S' && prod[1].ToString() == '#' )
{
firsts[symbol].Add('#');
}
//如果第一个非终结符能推出#，递归计算第二个和后面的字符的 FIRST 集，并将结果加入该非终结符的 FIRST 集中
if (prod.Length > 0 && !IsTerminal(prod[0]) && !firsts[prod[0].ToString()].Contains('#'))
{
for (int j = 1; j < prod.Length; j++)
{
if (IsTerminal(prod[j]))
{
if (!firsts[symbol].Contains(prod[j].ToString()))
firsts[symbol].Add(prod[j].ToString());
break;
}
GetFirst(prod[j].ToString(), production, firsts);
foreach (var f in firsts[prod[j].ToString()])
{
if (!firsts[symbol].Contains(f) && !f.Equals('#'))
firsts[symbol].Add(f);
}
// 如果该非终结符的 FIRST 集没有包含空串，则可以结束循环
if (!firsts[prod[j].ToString()].Contains('#'))
{
break;
}
// 如果是最后一个字符且所有非终结符的 FIRST 集都含有空串，则将空串加入该非终结符的 FIRST 集中
if (j == prod.Length - 1)
{
if (!firsts[symbol].Contains('#'))
firsts[symbol].Add('#');
}
}
}
}
}
// 判断指定符号是否为终结符
static bool IsTerminal(char symbol)
{
return !char.IsUpper(symbol);
}
static void GetFollow(string symbol, Dictionary<string, List<string>> production, Dictionary<string, List<string>> firsts, Dictionary<string, List<string>> follows)
{
if (follows.ContainsKey(symbol))
{
return;
}
follows.Add(symbol, new List<string>());
// 将结束符号 # 加入起始符号 intial 的 FOLLOW 集
if (symbol == production.First().Key)
{
follows[symbol].Add('#');
}
// 遍历产生式，计算 FOLLOW 集
foreach (string key in production.Keys)
{
foreach (var prod in production[key])
{
for (int i = 0; i < prod.Length; i++)
{
if (prod[i].ToString() == symbol)
{
// 如果该非终结符在产生式末尾，则将产生式左边非终结符的 FOLLOW 集加入该非终结符的 FOLLOW 集中
if (i == prod.Length - 1)
{
if (key != symbol)
{
GetFollow(key, production, firsts, follows);
foreach (var f in follows[key])
{
if (!follows[symbol].Contains(f))
follows[symbol].Add(f);
}
}
}
// 如果该非终结符不在产生式末尾（即后面还跟着其他符号）
else
{
// 如果后面是终结符，则直接将其加入该非终结符的 FOLLOW 集中
if (IsTerminal(prod[i + 1]) && !follows[symbol].Contains(prod[i + 1].ToString()))
{
follows[symbol].Add(prod[i + 1].ToString());
}
// 如果后面是非终结符，则将该非终结符的 FIRST 集加入该非终结符的 FOLLOW 集中，若该非终结符能够推出空，还需将产生式左边的 FOLLOW 集加入
else
{
foreach (var f in firsts[prod[i + 1].ToString()])
{
if (f != '#' && !follows[symbol].Contains(f))
{
follows[symbol].Add(f);
}
}
if (firsts[prod[i + 1].ToString()].Contains('#') && key != symbol)
{
GetFollow(key, production, firsts, follows);
foreach (var f in follows[key])
{
if (!follows[symbol].Contains(f))
follows[symbol].Add(f);
}
}
}
}
}
}
}
}
}
static bool JudgeLL1(Dictionary<string, List<string>> production, Dictionary<string, List<string>> firsts, Dictionary<string, List<string>> follows)
{
// 判断是否存在左递归
if (HasLeftRecursion(production))
{
return false;
}
// 判断 FIRST 集合是否相交
foreach (var item1 in firsts)
{
foreach (var item2 in firsts)
{
if (item1.Key != item2.Key)
{
if (HasIntersection(item1.Value, item2.Value))
{
return false;
}
}
}
}
// 判断 FOLLOW 集合是否相交
foreach (var item1 in follows)
{
foreach (var item2 in follows)
{
if (item1.Key != item2.Key)
{
if (HasIntersection(item1.Value, item2.Value))
{
return false;
}
}
}
}
return true;
}
// 判断两个集合是否有交集
static bool HasIntersection(List<string> list1, List<string> list2)
{
foreach (var item1 in list1)
{
foreach (var item2 in list2)
{
if (item1 == item2)
{
return true;
}
}
}
return false;
}
// 判断是否存在左递归
static bool HasLeftRecursion(Dictionary<string, List<string>> production)
{
foreach (var item in production)
{
foreach (var prod in item.Value)
{
if (prod[0].ToString() == item.Key)
{
return true;
}
}
}
return false;
}
private void button6_Click(object sender, EventArgs e)
{
}
private void button5_Click(object sender, EventArgs e)
{
SaveFileDialog saveFileDialog = new SaveFileDialog();
saveFileDialog.Filter = 'Text files (*.txt)|*.txt|All files (*.*)|*.*';
saveFileDialog.FileName = 'Grammer.txt'; // 设置默认文件名
if (saveFileDialog.ShowDialog() == DialogResult.OK)
{
string filename = saveFileDialog.FileName;
File.WriteAllText(filename, richTextBox1.Text);
MessageBox.Show('文件已成功保存至：' + filename);
}
}
}
代码说明：
GetFirst函数用于计算每个非终结符的 FIRST 集合。GetFollow函数用于计算每个非终结符的 FOLLOW 集合。JudgeLL1函数用于判断输入的文法是否为 LL(1) 文法。它首先判断文法是否存在左递归，如果存在则直接返回false。然后它会判断每个非终结符的 FIRST 集合和 FOLLOW 集合是否相交，如果相交则也返回false。否则，该文法即为 LL(1) 文法，返回true。HasIntersection函数用于判断两个集合是否相交。HasLeftRecursion函数用于判断文法是否存在左递归。
使用方法：
- 将代码复制粘贴到 Visual Studio 中。
- 编译并运行程序。
- 在文本框中输入文法规则，以换行符分隔每条规则。
- 点击“判断”按钮，程序将对输入的文法进行分析，并判断其是否为LL(1)文法。
- 程序会显示判断结果，并输出FIRST集合和FOLLOW集合。
示例文法：
S->E
E->T|E+T
T->F|T*F
F->(E)|id
注意：
- 程序代码使用C#语言编写，需要安装Visual Studio或其他支持C#的IDE。
- 程序代码仅供参考，如有任何错误或不足之处，请指正。
更多信息：
希望这个LL(1)文法判断工具能够帮助你学习和理解LL(1)文法，以及编译原理中的相关知识。
原文地址: https://www.cveoy.top/t/topic/oxGo 著作权归作者所有。请勿转载和采集!