LL(1) 文法分析工具 - 检查文法是否为 LL(1) 并生成 FIRST 和 FOLLOW 集合
using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.IO; using System.Linq; using System.Text; using System.Text.RegularExpressions; using System.Threading.Tasks; using System.Windows.Forms; using static System.Windows.Forms.VisualStyles.VisualStyleElement;
namespace byyljxfzxt { public partial class Form4 : Form { public Form4() { InitializeComponent(); }
//--------------------预处理
Dictionary<string, List<string>> production;
Dictionary<string, List<string>> firsts;
Dictionary<string, List<string>> follows;
List<string> terminals;
List<string> nonterminals;
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;
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);
}
firsts = new Dictionary<string, List<string>>();
foreach (var item in production.Keys)
GetFirst(item, production, firsts);
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");
}
else
{
MessageBox.Show("该文法不是LL(1)文法，存在左递归或者存在FIRST集合有交集的情况！\n");
}
button1.Enabled = true;
button2.Enabled = true;
button3.Enabled = true;
}
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);
}
}
private void button1_Click(object sender, EventArgs e)
{
// 获取所有的符号集合
List<string> symbols = new List<string>();
foreach (var item in production.Keys)
{
if (!symbols.Contains(item))
symbols.Add(item);
foreach (var prod in production[item])
{
foreach (var c in prod)
{
if (!symbols.Contains(c.ToString()))
symbols.Add(c.ToString());
}
}
}
// 将符号集合按照终结符和非终结符分开
nonterminals = new List<string>();
terminals = new List<string>();
foreach (var s in symbols)
{
if (char.IsUpper(s[0]))
nonterminals.Add(s);
else
terminals.Add(s);
}
listView1.Columns.Clear();
listView1.Items.Clear();
listView1.View = View.Details;
// 添加第一列
listView1.Columns.Add("", 30);
// 添加终结符列
foreach (var item in terminals)
{
listView1.Columns.Add(item, 30);
}
// 添加非终结符行
foreach (var item in nonterminals)
{
ListViewItem lvi = new ListViewItem(item);
lvi.SubItems.Add("");
foreach (var t in terminals)
{
lvi.SubItems.Add("");
}
listView1.Items.Add(lvi);
}
// 填充表格
foreach (var item in firsts)
{
int row = nonterminals.IndexOf(item.Key);
foreach (var t in terminals)
{
int col = terminals.IndexOf(t);
if(!item.Value.Contains(t))
listView1.Items[row].SubItems[col + 1].Text = "0";
else
listView1.Items[row].SubItems[col + 1].Text = "1";
}
}
}
private void button2_Click(object sender, EventArgs e)
{
// 获取所有的符号集合
List<string> symbols = new List<string>();
foreach (var item in production.Keys)
{
if (!symbols.Contains(item))
symbols.Add(item);
foreach (var prod in production[item])
{
foreach (var c in prod)
{
if (!symbols.Contains(c.ToString()))
symbols.Add(c.ToString());
}
}
}
// 将符号集合按照终结符和非终结符分开
nonterminals = new List<string>();
terminals = new List<string>();
foreach (var s in symbols)
{
if (char.IsUpper(s[0]))
nonterminals.Add(s);
else
terminals.Add(s);
}
foreach (var s in nonterminals)
{
System.Console.WriteLine(s);
}
foreach(var s in terminals)
{
System.Console.WriteLine(s);
}
listView2.Columns.Clear();
listView2.Items.Clear();
listView2.View = View.Details;
// 添加第一列
listView2.Columns.Add("", 30);
// 添加终结符列
foreach (var item in terminals)
{
listView2.Columns.Add(item, 30);
}
// 添加非终结符行
foreach (var item in nonterminals)
{
ListViewItem lvi = new ListViewItem(item);
lvi.SubItems.Add("");
foreach (var t in terminals)
{
lvi.SubItems.Add("");
}
listView2.Items.Add(lvi);
}
// 填充表格
foreach (var item in follows)
{
int row = nonterminals.IndexOf(item.Key);
foreach (var t in terminals)
{
int col = terminals.IndexOf(t);
if (!item.Value.Contains(t))
listView2.Items[row].SubItems[col + 1].Text = "0";
else
listView2.Items[row].SubItems[col + 1].Text = "1";
}
}
}
private void GetFirst(string symbol, Dictionary<string, List<string>> production1, Dictionary<string, List<string>> firsts1)
{
// 如果该非终结符的 FIRST 集已经被计算出，则直接返回
if (firsts1.ContainsKey(symbol))
{
return;
}
firsts1.Add(symbol, new List<string>());
// 遍历产生式，计算 FIRST 集
foreach (var prod in production1[symbol])
{
// 如果产生式首字符为终结符，则直接将其加入 FIRST 集中
if (prod.Length > 0 && IsTerminal(prod[0]))
{
if (!firsts1[symbol].Contains(prod[0].ToString()))
firsts1[symbol].Add(prod[0].ToString());
continue;
}
// 如果产生式首字符为非终结符，则计算该非终结符的 FIRST 集，并将结果加入首字符的 FIRST 集中
else if (prod.Length > 0 && !IsTerminal(prod[0]))
{
GetFirst(prod[0].ToString(), production1, firsts1);
foreach (var f in firsts1[prod[0].ToString()])
{
if (!firsts1[symbol].Contains(f) && !f.Equals('#'))
firsts1[symbol].Add(f);
}
}
//如果第一个非终结符能推出#
if (IsReachEmpty(prod[0].ToString(), production1))
{
// 递归计算第二个和后面的字符的 FIRST 集，并将结果加入该非终结符的 FIRST 集中
for (int j = 1; j < prod.Length; j++)
{
if (IsTerminal(prod[j]))
{
if (!firsts1[symbol].Contains(prod[j].ToString()))
firsts1[symbol].Add(prod[j].ToString());
break;
}
GetFirst(prod[j].ToString(), production1, firsts1);
foreach (var f in firsts1[prod[j].ToString()])
{
if (!firsts1[symbol].Contains(f) && !f.Equals('#'))
firsts1[symbol].Add(f);
}
// 如果该非终结符的 FIRST 集没有包含空串，则可以结束循环
if (!IsReachEmpty(prod[j].ToString(), production1))
{
break;
}
// 如果是最后一个字符且所有非终结符的 FIRST 集都含有空串，则将空串加入该非终结符的 FIRST 集中
if (j == prod.Length - 1)
{
if (!firsts1[symbol].Contains("#"))
firsts1[symbol].Add("#");
}
}
}
}
}
// 判断一个字符是否为终结符
private bool IsTerminal(char c)
{
if (char.IsUpper(c))
return false;
if (c.Equals('#'))
return false;
return true;
}
// 判断一个非终结符是否能推出空串
private bool IsReachEmpty(string symbol, Dictionary<string, List<string>> production1)
{
if (!production1.ContainsKey(symbol))
return false;
foreach (var prod in production1[symbol])
{
if (prod.Equals("#"))
return true;
bool flag = true;
for (int i = 0; i < prod.Length; i++)
{
if (!IsReachEmpty(prod[i].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)
{
// 如果该非终结符的 FOLLOW 集已经被计算出，则直接返回
if (follows1.ContainsKey(symbol))
{
return;
}
follows1.Add(symbol, new List<string>());
// 如果是起始符号，则将 $ 加入 FOLLOW 集中
if (symbol.Equals(production1.Keys.First()))
{
if (!follows1[symbol].Contains("$"))
follows1[symbol].Add("$");
}
// 遍历产生式，计算 FOLLOW 集
foreach (var item in production1)
{
foreach (var prod in item.Value)
{
int index = prod.IndexOf(symbol);
if (index == -1)
continue;
// 如果该非终结符位于产生式末尾，则将产生式左部的 FOLLOW 集加入该非终结符的 FOLLOW 集中
if (index == prod.Length - 1)
{
GetFollow(item.Key, production1, firsts1, follows1);
foreach (var f in follows1[item.Key])
{
if (!follows1[symbol].Contains(f))
follows1[symbol].Add(f);
}
}
else
{
// 如果该非终结符后面是终结符，则将该终结符加入该非终结符的 FOLLOW 集中
if (IsTerminal(prod[index + 1]))
{
if (!follows1[symbol].Contains(prod[index + 1].ToString()))
follows1[symbol].Add(prod[index + 1].ToString());
}
// 如果该非终结符后面是非终结符，则将该非终结符的 FIRST 集加入该非终结符的 FOLLOW 集中
else
{
GetFirst(prod[index + 1].ToString(), production1, firsts1);
foreach (var f in firsts1[prod[index + 1].ToString()])
{
if (!f.Equals("#") && !follows1[symbol].Contains(f))
follows1[symbol].Add(f);
}
// 如果该非终结符后面的所有符号都能推出空串，则将产生式左部的 FOLLOW 集加入该非终结符的 FOLLOW 集中
if (IsReachEmpty(prod[index + 1].ToString(), production1))
{
GetFollow(item.Key, production1, firsts1, follows1);
foreach (var f in follows1[item.Key])
{
if (!follows1[symbol].Contains(f))
follows1[symbol].Add(f);
}
}
}
}
}
}
}
// 判断一个文法是否是 LL(1) 文法
private bool JudgeLL1(Dictionary<string, List<string>> production1, Dictionary<string, List<string>> firsts1, Dictionary<string, List<string>> follows1)
{
foreach (var item in production1)
{
Dictionary<string, List<string>> map = new Dictionary<string, List<string>>();
foreach (var prod in item.Value)
{
List<string> list = new List<string>();
foreach (var c in prod)
{
if (IsTerminal(c))
{
list.Add(c.ToString());
break;
}
else
{
GetFirst(c.ToString(), production1, firsts1);
foreach (var f in firsts1[c.ToString()])
{
if (!f.Equals("#") && !list.Contains(f))
list.Add(f);
}
if (!IsReachEmpty(c.ToString(), production1))
break;
}
}
if (list.Contains("#"))
{
GetFollow(item.Key, production1, firsts1, follows1);
foreach (var f in follows1[item.Key])
{
if (!list.Contains(f))
list.Add(f);
}
}
string key = string.Join("", list.ToArray());
if (map.ContainsKey(key))
return false;
map.Add(key, list);
}
}
return true;
}
}
原文地址: https://www.cveoy.top/t/topic/fXET 著作权归作者所有。请勿转载和采集!