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;
isLL_1_ ll1 = new isLL_1_(text);
if (ll1.is_LL == 1)
{
MessageBox.Show("该文法是LL(1)文法\n");
foreach (var item in ll1.first.getfirsts())
{
richTextBox2.AppendText(item.Key + ": { ");
foreach (var s in item.Value)
richTextBox2.AppendText(s + " ");
richTextBox2.AppendText("}\n");
}
richTextBox2.AppendText("FOLLOW集：\n");
foreach (var item in ll1.follow.getfollows())
{
richTextBox2.AppendText(item.Key + ": { ");
foreach (var s in item.Value)
richTextBox2.AppendText(s + " ");
richTextBox2.AppendText("}\n");
}
}
else if (ll1.is_LL == 0)
{
MessageBox.Show("该文法不是LL(1)文法，产生式有误！\n");
}
else
{
MessageBox.Show("该文法不是LL(1)文法，存在左递归或者存在FIRST集合有交集的情况！\n");
}
}
private void button6_Click(object sender, EventArgs e)
{
string text = richTextBox1.Text;
isLL_1_ ll1 = new isLL_1_(text);
if (ll1.is_LL == 1)
{
richTextBox2.Text = "";
richTextBox2.AppendText("预测分析表：\n");
Dictionary<string, Dictionary<string, List<string>>> table = new Dictionary<string, Dictionary<string, List<string>>>();
foreach (var item in ll1.select.getselects())
{
table[item.Key] = new Dictionary<string, List<string>>();
foreach (var prod in item.Value)
{
var firsts = ll1.first.getfirsts()[prod];
if (firsts.Contains("#"))
{
firsts.Remove("#");
foreach (var f in ll1.follow.getfollows()[item.Key])
if (!firsts.Contains(f))
firsts
}
}
}
}
}
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);
}
}
}
class isLL_1_
{
public LL1Item LL1Item;
public Dictionary<string, List
public isLL_1_(String text)
{
LL1Item = new LL1Item(text);
if (LL1Item.creatproduction() == 1)
{
product = LL1Item.getproduction();
first = new First(LL1Item);
follow = new Follow(LL1Item, first);
select=new Select (LL1Item, first, follow);
Judge();
}
else
{
is_LL = 0;
}
}
public void Judge()
{
foreach(var nofinal in LL1Item.nofinal)
{
var pro = select.getselects()[nofinal];
//遍历该非终结符每个初始状态对应的selects集。
for (int i = 0; i < pro.Count - 1; i++)
{
foreach(var fin in pro.ElementAt(i).Value)
{
int j;
for (j = i + 1; j < pro.Count; j++)
if (!pro.ElementAt(j).Value.Contains(fin)) break;
if (j == pro.Count)
{
is_LL=-1;
return ;
}
}
}
}
}
}
class LL1Item
{
String text;
public string intinal;
public List
public LL1Item(string text)
{
this.text = text;
if (creatproduction() == 1)
{
is_reachempty();
intinal = production.First().Key;
createnofinal();
createfinial();
}
}
public void createnofinal()
{
nofinal = new List<string>();
foreach (var item in production.Keys)
nofinal.Add(item);
}
public void createfinial()
{
final = new List<string>();
foreach (var item in nofinal)
foreach (var item2 in production[item])
foreach (var item3 in item2)
if (!char.IsUpper(item3))
if (!final.Contains(item3.ToString()))
final.Add(item3.ToString());
if (!final.Contains("#"))
final.Add("#");
}
public int creatproduction()
{
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 0;
if (ga[0].Length == 0 || ga[1].Length == 0)
return 0;
if (ga[0].Length != 1 || !char.IsUpper(ga[0][0])) return 0;
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);
}
return 1;
}
public void is_reachempty()
{
Dictionary<string, List<string>> productions = new Dictionary<string, List<string>>();
foreach (var key in production.Keys)
{
productions.Add(key,new List<string>());
foreach (var value in production[key])
productions[key].Add(value);
}
int flag = 0;
//去除产生式中所有含终结符和#的项
foreach (var item in productions.Keys)
{
flag = 0;
for (int i = 0; i< productions[item].Count; i++)
{
if (productions[item][i].Equals("#"))
{
flag = 1;
break;
}
else
foreach (var newProd in productions[item][i])
//如果是终结符
if (!char.IsUpper(newProd))
{
flag = -1;
break;
}
if (flag == -1)
{
productions[item].RemoveAt(i);
i--;
}
}
//如果该非终结符可直接推出#
if (flag == 1)
{
productions[item]=new List<string>();
is_reach.Add(item, true);
}
//该非终结符的每个产生式中都含有终结符
else if (productions[item].Count == 0) is_reach.Add(item, false);
}
//判断产生式右部中的非终结符能否推出#
while (true)
{
flag = 0;
foreach (var item in productions.Keys)
{
if (is_reach.ContainsKey(item)) continue;
foreach (string s in productions[item])
{
foreach (var newProd in s)
{
if (is_reach.ContainsKey(newProd.ToString()))
//如果该非终结符能推出#，就将他从产生式中去除
if (is_reach[newProd.ToString()])
{
s.Replace(newProd.ToString(), "");
flag = 1;
}
}
if (s.Equals(""))
{
flag = 1;
is_reach.Add(item, true);
break;
}
}
}
//当产生式不再改变
if (flag == 0) { break; }
}
//添加非终结符的判断结果
foreach (var item in productions.Keys)
{
if (is_reach.ContainsKey(item)) continue;
is_reach.Add(item, false);
}
}
public Dictionary<string, List<string>> getproduction()
{
return production;
}
public Dictionary<string, bool> getisreach()
{
return is_reach;
}
}
class First
{
LL1Item LL1Item;
Dictionary<string, List
void GetFirst(string symbol)
{
// 如果该非终结符的 FIRST 集已经被计算出，则直接返回
if (firsts.ContainsKey(symbol))
{
return;
}
var production = LL1Item.getproduction();
var is_reach = LL1Item.getisreach();
firsts.Add(symbol, new List<string>());
// 遍历产生式，计算 FIRST 集
foreach (var prod in production[symbol])
{
// 如果产生式首字符为终结符，则直接将其加入 FIRST 集中
if (prod.Length > 0 && IsTerminal(prod[0]))
{
if (!firsts[symbol].Contains(prod[0].ToString()))
firsts[symbol].Add(prod[0].ToString());
continue;
}
// 如果产生式首字符为非终结符，则计算该非终结符的 FIRST 集，并将结果加入首字符的 FIRST 集中
else if (prod.Length > 0 && !IsTerminal(prod[0]))
{
GetFirst(prod[0].ToString());
foreach (var f in firsts[prod[0].ToString()])
{
if (!firsts[symbol].Contains(f)&&!f.Equals("#"))
firsts[symbol].Add(f);
}
}
//如果第一个非终结符能推出#
if (LL1Item.getisreach()[prod[0].ToString()])
{
// 递归计算第二个和后面的字符的 FIRST 集，并将结果加入该非终结符的 FIRST 集中
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());
foreach (var f in firsts[prod[j].ToString()])
{
if (!firsts[symbol].Contains(f) && !f.Equals("#"))
firsts[symbol].Add(f);
}
// 如果该非终结符的 FIRST 集没有包含空串，则可以结束循环
if (!is_reach[prod[j].ToString()])
{
break;
}
// 如果是最后一个字符且所有非终结符的 FIRST 集都含有空串，则将空串加入该非终结符的 FIRST 集中
if (j == prod.Length - 1)
{
if (!firsts[symbol].Contains("#"))
firsts[symbol].Add("#");
}
}
}
}
}
// 判断指定符号是否为终结符
static bool IsTerminal(char symbol)
{
return !char.IsUpper(symbol);
}
public Dictionary<string, List<string>> getfirsts()
{
return firsts;
}
}
class Follow
{
LL1Item LL1Item;
First first;
Dictionary<string, List
public Follow(LL1Item LL1Item, First first)
{
this.LL1Item = LL1Item;
this.first = first;
follows = new Dictionary<string, List<string>>();
foreach (var item in this.LL1Item.getproduction().Keys)
GetFollow(item);
}
void GetFollow(string symbol)
{
// 如果该非终结符的 FOLLOW 集已经被计算出，则直接返回
if (follows.ContainsKey(symbol))
{
return;
}
var grammar = LL1Item.getproduction();
var is_reach = LL1Item.getisreach();
follows.Add(symbol, new List<string>());
// 将结束符号 # 加入起始符号 intial 的 FOLLOW 集
if (symbol == LL1Item.intinal)
{
follows[symbol].Add("#");
}
// 遍历产生式，计算 FOLLOW 集
foreach (string key in LL1Item.nofinal)
{
foreach (var prod in grammar[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);
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 first.getfirsts()[prod[i + 1].ToString()])
{
if (f != "#")
{
if (!follows[symbol].Contains(f))
follows[symbol].Add(f);
}
}
if (first.getfirsts()[prod[i + 1].ToString()].Contains("#") && key != symbol)
{
GetFollow(key);
foreach (var f in follows[key])
{
if (!follows[symbol].Contains(f))
follows[symbol].Add(f);
}
}
}
}
}
}
}
}
}
static bool IsTerminal(char symbol)
{
return !char.IsUpper(symbol);
}
public Dictionary<string, List<string>> getfollows()
{
return follows;
}
}
原文地址: https://www.cveoy.top/t/topic/oxGc 著作权归作者所有。请勿转载和采集!