LL(1)文法判断算法实现 - C# 代码详解

{/n/'title/': /'LL(1)文法判断算法实现 - C# 代码详解/',/n/'description/': /'本文提供一个C#实现的LL(1)文法判断算法，详细解释了代码逻辑，并分析了涉及的数据结构和关键函数。/',/n/'keywords/': /'LL(1)文法, 文法判断, C#, 算法, 数据结构, 产生式, FIRST集合, FOLLOW集合/',/n/'content/': /'///'private void button4_Click(object sender, EventArgs e)//n{//n//tstring text = richTextBox1.Text;//n//tproduction = new Dictionary<string, List>();///n//tstring[] pro = text.Split('//n');///n//tforeach (string s in pro)//n//t{//n//t/tif (s == ///'///') continue;//n//n//t/tRegex.Replace(s, ///' ///', ///'///');///n//t/tstring[] ga = Regex.Split(s, ///'->///');///n//t/tif (ga.Length != 2) return;//n//t/tif (ga[0].Length == 0 || ga[1].Length == 0)//n//t/t/treturn;//n//t/tif (ga[0].Length != 1 || !char.IsUpper(ga[0][0])) return;//n//n//t/tstring[] ga2 = Regex.Split(ga[1], ///'//|///');///n//t/tif (!production.ContainsKey(ga[0]))///n//t/t/tproduction.Add(ga[0], new List());///n//t/tforeach (string s1 in ga2)//n//t/t/tproduction[ga[0]].Add(s1);///n//t}//n//n//tfirsts = new Dictionary<string, List>();///n//tforeach (var item in production.Keys)//n//t/tGetFirst(item, production, firsts);///n//n//tfollows = new Dictionary<string, List>();///n//tforeach (var item in production.Keys)//n//t/tGetFollow(item, production, firsts, follows);///n//n//n//tif (JudgeLL1(production, firsts, follows))//n//t{//n//t/tMessageBox.Show(///'该文法是LL(1)文法//n///');///n//n//t}//n//telse//n//t{//n//t/tMessageBox.Show(///'该文法不是LL(1)文法，存在左递归或者存在FIRST集合有交集的情况！//n///');///n//t}//n//tbutton1.Enabled = true;//n//tbutton2.Enabled = true;//n//tbutton6.Enabled = true;//n//tbutton7.Enabled = true;//n//n}//nprivate bool JudgeLL1(Dictionary<string, List> production1, Dictionary<string, List> firsts1, Dictionary<string, List> follows1)//n{//n//tforeach (var item in production1)//n//t{//n//t/tDictionary<string, List> map = new Dictionary<string, List>();///n//t/tforeach (var prod in item.Value)//n//t/t{//n//t/t/tList list = new List();///n//t/t/tforeach (var c in prod)//n//t/t/t{//n//t/t/t/tif (IsTerminal(c))//n//t/t/t/t{//n//t/t/t/t/tlist.Add(c.ToString());///n//t/t/t/t/tbreak;//n//t/t/t/t}//n//t/t/t/telse//n//t/t/t/t{//n//t/t/t/t/tGetFirst(c.ToString(), production1, firsts1);///n//t/t/t/t/tforeach (var f in firsts1[c.ToString()])//n//t/t/t/t/t{//n//t/t/t/t/t/tif (!f.Equals(///'#///') && !list.Contains(f))//n//t/t/t/t/t/t/tlist.Add(f);///n//t/t/t/t/t}//n//t/t/t/t/tif (!IsReachEmpty(c.ToString(), production1))//n//t/t/t/t/t/tbreak;//n//t/t/t/t}//n//t/t/t}//n//t/t/tif (list.Contains(///'#///'))//n//t/t/t{//n//t/t/t/tGetFollow(item.Key, production1, firsts1, follows1);///n//t/t/t/tforeach (var f in follows1[item.Key])//n//t/t/t/t{//n//t/t/t/t/tif (!list.Contains(f))//n//t/t/t/t/t/tlist.Add(f);///n//t/t/t/t}//n//t/t/t}//n//t/t/tstring key = string.Join(///'///', list.ToArray());///n//t/t/tif (map.ContainsKey(key))//n//t/t/t/treturn false;//n//t/t/tmap.Add(key, list);///n//t/t}//n//t}//n//treturn true;//n}//n分析上述代码涉及到的数据结构内容：1. Dictionary<string, List> production: 存储文法产生式，每个非终结符对应一个产生式列表。//n//n2. Dictionary<string, List> firsts: 存储每个非终结符的FIRST集合。//n//n3. Dictionary<string, List> follows: 存储每个非终结符的FOLLOW集合。//n//n4. List list: 存储FIRST集合或者FOLLOW集合中的符号。//n//n5. Dictionary<string, List> map: 存储每个产生式的FIRST集合或者FOLLOW集合，并用字符串表示。/