LL(1) 文法判断及 FIRST、FOLLOW 集求解工具
{ "title": "LL(1) 文法判断及 FIRST、FOLLOW 集求解工具", "description": "本工具可以判断给定文法是否为 LL(1) 文法，并计算该文法的 FIRST 和 FOLLOW 集。", "keywords": "LL(1) 文法, FIRST 集, FOLLOW 集, 文法分析, 编译原理", "content": "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)
{
}
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 LL1Item
{
string text;
public string initial;
public List<string> final;
public List<string> nonFinal;
Dictionary<string, List<string>> productions;
public LL1Item(string text)
{
this.text = text;
if (createProductions() == 1)
{
initial = productions.First().Key;
createNonFinal();
createFinal();
}
}
public void createNonFinal()
{
nonFinal = new List<string>();
foreach (var item in productions.Keys)
nonFinal.Add(item);
}
public void createFinal()
{
final = new List<string>();
foreach (var item in nonFinal)
foreach (var item2 in productions[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 createProductions()
{
productions = 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 (!productions.ContainsKey(ga[0]))
productions.Add(ga[0],new List<string>());
foreach (string s1 in ga2)
productions[ga[0]].Add(s1);
}
return 1;
}
public Dictionary<string, List<string>> getProductions()
{
return productions;
}
}
class First
{
LL1Item LL1Item;
Dictionary<string, List<string>> firsts;
public First(LL1Item LL1Item)
{
this.LL1Item = LL1Item;
firsts = new Dictionary<string, List<string>>();
foreach (var item in this.LL1Item.getProductions().Keys)
GetFirst(item);
}
void GetFirst(string symbol)
{
if (firsts.ContainsKey(symbol))
return;
var productions = LL1Item.getProductions();
firsts.Add(symbol, new List<string>());
foreach (var prod in productions[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());
foreach (var f in firsts[prod[0].ToString()])
{
if (!firsts[symbol].Contains(f))
firsts[symbol].Add(f);
}
}
//如果第一个非终结符能推出#
if (prod.Length > 0 && !IsTerminal(prod[0]) && firsts[prod[0].ToString()].Contains("#"))
{
// 递归计算第二个和后面的字符的 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))
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);
}
public Dictionary<string, List<string>> getfirsts()
{
return firsts;
}
}
class Follow
{
LL1Item LL1Item;
First first;
Dictionary<string, List<string>> follows;
public Follow(LL1Item LL1Item, First first)
{
this.LL1Item = LL1Item;
this.first = first;
follows = new Dictionary<string, List<string>>();
foreach (var item in this.LL1Item.getProductions().Keys)
GetFollow(item);
}
void GetFollow(string symbol)
{
// 如果该非终结符的 FOLLOW 集已经被计算出，则直接返回
if (follows.ContainsKey(symbol))
{
return;
}
var grammar = LL1Item.getProductions();
follows.Add(symbol, new List<string>());
// 将结束符号 # 加入起始符号 intial 的 FOLLOW 集
if (symbol == LL1Item.initial)
{
follows[symbol].Add("#");
}
// 遍历产生式，计算 FOLLOW 集
foreach (string key in LL1Item.nonFinal)
{
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;
}
}
class isLL_1_
{
public LL1Item LL1Item;
public Dictionary<string, List<string>> product;
public First first;
public Follow follow;
public Select select;
public int is_LL = 1;
public isLL_1_(String text)
{
LL1Item = new LL1Item(text);
if (LL1Item.createProductions() == 1)
{
product = LL1Item.getProductions();
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.nonFinal)
{
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 Select
{
LL1Item LL1Item;
First first;
Follow follow;
Dictionary<string, List<KeyValuePair<string, List<string>>>> selects = new Dictionary<string, List<KeyValuePair<string, List<string>>>>();
public Select(LL1Item LL1Item, First first, Follow follow)
{
this.LL1Item = LL1Item;
this.first = first;
this.follow = follow;
foreach (var item in LL1Item.getProductions().Keys)
GetSelect(item);
}
void GetSelect(string symbol)
{
selects.Add(symbol, new List<KeyValuePair<string, List<string>>>());
foreach (var prod in LL1Item.getProductions()[symbol])
{
var firsts = first.getfirsts()[prod[0].ToString()];
if (firsts.Contains("#"))
{
// 如果第一个非终结符的 FIRST 集包含 #，则需要添加 FOLLOW 集
foreach (var f in follow.getfollows()[symbol])
{
if (!selects[symbol].Any(x => x.Key == f))
{
selects[symbol].Add(new KeyValuePair<string, List<string>>(f, new List<string>() { prod }));
}
else
{
selects[symbol].First(x => x.Key == f).Value.Add(prod);
}
}
}
else
{
foreach (var f in firsts)
{
if (!selects[symbol].Any(x => x.Key == f))
{
selects[symbol].Add(new KeyValuePair<string, List<string>>(f, new List<string>() { prod }));
}
else
{
selects[symbol].First(x => x.Key == f).Value.Add(prod);
}
}
}
}
}
public Dictionary<string, List<KeyValuePair<string, List<string>>>> getselects()
{
return selects;
}
}
}
原文地址: https://www.cveoy.top/t/topic/oxGj 著作权归作者所有。请勿转载和采集!