LL(1) 文法预测分析表生成器

using System;/nusing System.Collections.Generic;/nusing System.ComponentModel;/nusing System.Data;/nusing System.Drawing;/nusing System.IO;/nusing System.Linq;/nusing System.Text;/nusing System.Text.RegularExpressions;/nusing System.Threading.Tasks;/nusing System.Windows.Forms;/nusing static System.Windows.Forms.VisualStyles.VisualStyleElement;/n/nnamespace byyljxfzxt/n{/n public partial class Form4 : Form/n {/n public Form4()/n {/n InitializeComponent();/n }/n/n //--------------------预处理/n Dictionary<string, List> production;/n Dictionary<string, List> firsts;/n Dictionary<string, List> follows;/n Dictionary<string, List> selects;/n List terminals;/n List nonterminals;/n/n /n private void button4_Click(object sender, EventArgs e)/n {/n string text = richTextBox1.Text;/n production = new Dictionary<string, List>();/n string[] pro = text.Split('/n');/n foreach (string s in pro)/n {/n if (s == /'/') continue;/n/n Regex.Replace(s, /' /', /'/');/n string[] ga = Regex.Split(s, /'->/');/n if (ga.Length != 2) return;/n if (ga[0].Length == 0 || ga[1].Length == 0)/n return;/n if (ga[0].Length != 1 || !char.IsUpper(ga[0][0])) return;/n/n string[] ga2 = Regex.Split(ga[1], /'//|/');/n if (!production.ContainsKey(ga[0]))/n production.Add(ga[0], new List());/n foreach (string s1 in ga2)/n production[ga[0]].Add(s1);/n }/n/n firsts = new Dictionary<string, List>();/n foreach (var item in production.Keys)/n GetFirst(item, production, firsts);/n/n follows = new Dictionary<string, List>();/n foreach (var item in production.Keys)/n GetFollow(item, production, firsts, follows);/n/n/n if (JudgeLL1(production, firsts, follows))/n {/n MessageBox.Show(/'该文法是LL(1)文法//n/');/n /n }/n else/n {/n MessageBox.Show(/'该文法不是LL(1)文法，存在左递归或者存在FIRST集合有交集的情况！//n/');/n }/n button1.Enabled = true;/n button2.Enabled = true;/n button3.Enabled = true;/n/n }/n/n private void button6_Click(object sender, EventArgs e)/n {/n // 获取所有终结符和非终结符/n terminals = new List();/n nonterminals = new List();/n foreach (var item in production)/n {/n if (!nonterminals.Contains(item.Key))/n nonterminals.Add(item.Key);/n foreach (var prod in item.Value)/n {/n foreach (var s in prod)/n {/n if (IsTerminal(s) && !terminals.Contains(s.ToString()))/n terminals.Add(s.ToString());/n else if (!IsTerminal(s) && !nonterminals.Contains(s.ToString()))/n nonterminals.Add(s.ToString());/n }/n }/n }/n terminals.Add(/'#/');/n/n // 初始化预测分析表/n Dictionary<string, Dictionary<string, string>> table = new Dictionary<string, Dictionary<string, string>>();/n foreach (var nonterm in nonterminals)/n {/n table.Add(nonterm, new Dictionary<string, string>());/n foreach (var term in terminals)/n {/n table[nonterm].Add(term, /'/');/n }/n }/n/n // 填充预测分析表/n Dictionary<string, List> selects = GetSelect(production, firsts, follows);/n foreach (var nonterm in nonterminals)/n {/n foreach (var prod in production[nonterm])/n {/n List select = selects[nonterm][production[nonterm].IndexOf(prod)].Split(new char[] { '|' }).ToList();/n foreach (var term in select)/n {/n if (!string.IsNullOrEmpty(term))/n {/n if (table[nonterm][term] != /'/')/n {/n MessageBox.Show(/'该文法不是LL(1)文法，存在冲突！/');/n return;/n }/n table[nonterm][term] = prod;/n }/n else/n {/n foreach (var follow in follows[nonterm])/n {/n if (table[nonterm][follow] != /'/')/n {/n MessageBox.Show(/'该文法不是LL(1)文法，存在冲突！/');/n return;/n }/n table[nonterm][follow] = prod;/n }/n }/n }/n }/n }/n/n // 输出预测分析表到 listView3 中/n listView3.Columns.Clear();/n listView3.Columns.Add(/'/');/n foreach (var term in terminals)/n {/n listView3.Columns.Add(term);/n }/n foreach (var nonterm in nonterminals)/n {/n ListViewItem item = new ListViewItem(nonterm);/n foreach (var term in terminals)/n {/n item.SubItems.Add(table[nonterm][term]);/n }/n listView3.Items.Add(item);/n }/n }/n/n /n/n private void GetFirst(string symbol, Dictionary<string, List> production1, Dictionary<string, List> firsts1)/n {/n // 如果该非终结符的 FIRST 集已经被计算出，则直接返回/n if (firsts1.ContainsKey(symbol))/n {/n return;/n }/n firsts1.Add(symbol, new List());/n // 遍历产生式，计算 FIRST 集/n foreach (var prod in production1[symbol])/n {/n // 如果产生式首字符为终结符，则直接将其加入 FIRST 集中/n if (prod.Length > 0 && IsTerminal(prod[0]))/n {/n if (!firsts1[symbol].Contains(prod[0].ToString()))/n firsts1[symbol].Add(prod[0].ToString());/n continue;/n }/n // 如果产生式首字符为非终结符，则计算该非终结符的 FIRST 集，并将结果加入首字符的 FIRST 集中/n else if (prod.Length > 0 && !IsTerminal(prod[0]))/n {/n GetFirst(prod[0].ToString(), production1, firsts1);/n foreach (var f in firsts1[prod[0].ToString()])/n {/n if (!firsts1[symbol].Contains(f) && !f.Equals('#'))/n firsts1[symbol].Add(f);/n }/n }/n //如果第一个非终结符能推出#/n if (IsReachEmpty(prod[0].ToString(), production1))/n {/n // 递归计算第二个和后面的字符的 FIRST 集，并将结果加入该非终结符的 FIRST 集中/n for (int j = 1; j < prod.Length; j++)/n {/n if (IsTerminal(prod[j]))/n {/n if (!firsts1[symbol].Contains(prod[j].ToString()))/n firsts1[symbol].Add(prod[j].ToString());/n break;/n }/n GetFirst(prod[j].ToString(), production1, firsts1);/n foreach (var f in firsts1[prod[j].ToString()])/n {/n if (!firsts1[symbol].Contains(f) && !f.Equals('#'))/n firsts1[symbol].Add(f);/n }/n // 如果该非终结符的 FIRST 集没有包含空串，则可以结束循环/n if (!IsReachEmpty(prod[j].ToString(), production1))/n {/n break;/n }/n // 如果是最后一个字符且所有非终结符的 FIRST 集都含有空串，则将空串加入该非终结符的 FIRST 集中/n if (j == prod.Length - 1)/n {/n if (!firsts1[symbol].Contains(/'#/'))/n firsts1[symbol].Add(/'#/');/n }/n }/n }/n }/n }/n/n // 判断一个字符是否为终结符/n private bool IsTerminal(char c)/n {/n if (char.IsUpper(c))/n return false;/n return true;/n }/n/n // 判断一个非终结符是否能推出空串/n private bool IsReachEmpty(string symbol, Dictionary<string, List> production1)/n {/n if (!production1.ContainsKey(symbol))/n return false;/n foreach (var prod in production1[symbol])/n {/n if (prod.Equals(/'#/'))/n return true;/n bool flag = true;/n for (int i = 0; i < prod.Length; i++)/n {/n if (!IsReachEmpty(prod[i].ToString(), production1))/n {/n flag = false;/n break;/n }/n }/n if (flag)/n return true;/n }/n return false;/n }/n/n // 计算 FOLLOW 集/n private void GetFollow(string symbol, Dictionary<string, List> production1, Dictionary<string, List> firsts1, Dictionary<string, List> follows1)/n {/n // 如果该非终结符的 FOLLOW 集已经被计算出，则直接返回/n if (follows1.ContainsKey(symbol))/n {/n return;/n }/n follows1.Add(symbol, new List());/n // 如果是起始符号，则将 # 加入 FOLLOW 集中/n if (symbol.Equals(production1.Keys.First()))/n {/n if (!follows1[symbol].Contains(/'#/'))/n follows1[symbol].Add(/'#/');/n }/n // 遍历产生式，计算 FOLLOW 集/n foreach (var item in production1)/n {/n foreach (var prod in item.Value)/n {/n int index = prod.IndexOf(symbol);/n if (index == -1)/n continue;/n // 如果该非终结符位于产生式末尾，则将产生式左部的 FOLLOW 集加入该非终结符的 FOLLOW 集中/n if (index == prod.Length - 1)/n {/n GetFollow(item.Key, production1, firsts1, follows1);/n foreach (var f in follows1[item.Key])/n {/n if (!follows1[symbol].Contains(f))/n follows1[symbol].Add(f);/n }/n }/n else/n {/n // 如果该非终结符后面是终结符，则将该终结符加入该非终结符的 FOLLOW 集中/n if (IsTerminal(prod[index + 1]))/n {/n if (!follows1[symbol].Contains(prod[index + 1].ToString()))/n follows1[symbol].Add(prod[index + 1].ToString());/n }/n // 如果该非终结符后面是非终结符，则将该非终结符的 FIRST 集加入该非终结符的 FOLLOW 集中/n else/n {/n GetFirst(prod[index + 1].ToString(), production1, firsts1);/n foreach (var f in firsts1[prod[index + 1].ToString()])/n {/n if (!f.Equals(/'#/') && !follows1[symbol].Contains(f))/n follows1[symbol].Add(f);/n }/n // 如果该非终结符后面的所有符号都能推出空串，则将产生式左部的 FOLLOW 集加入该非终结符的 FOLLOW 集中/n if (IsReachEmpty(prod[index + 1].ToString(), production1))/n {/n GetFollow(item.Key, production1, firsts1, follows1);/n foreach (var f in follows1[item.Key])/n {/n if (!follows1[symbol].Contains(f))/n follows1[symbol].Add(f);/n }/n }/n }/n }/n }/n }/n }/n/nprivate Dictionary<string, List> GetSelect(Dictionary<string, List> production1, Dictionary<string, List> firsts1, Dictionary<string, List> follows1)/n{/n // 初始化 SELECT 集/n Dictionary<string, List> selects1 = new Dictionary<string, List>();/n foreach (var item in production1)/n selects1.Add(item.Key, new List());/n/n // 遍历每个产生式，计算对应的 SELECT 集/n foreach (var nonterm in production1.Keys)/n {/n foreach (var prod in production1[nonterm])/n {/n List select = new List();/n bool flag = true;/n // 对于产生式中的每个符号，计算其 FIRST 集/n foreach (var s in prod)/n {/n if (IsTerminal(s))/n {/n select.Add(s.ToString());/n flag = false;/n break;/n }/n else/n {/n GetFirst(s.ToString(), production1, firsts1);/n foreach (var f in firsts1[s.ToString()])/n {/n if (!f.Equals(/'#/') && !select.Contains(f))/n select.Add(f);/n }/n if (!IsReachEmpty(s.ToString(), production1))/n {/n flag = false;/n break;/n }/n }/n }/n // 如果产生式中所有符号的 FIRST 集都包含空串，则将 FOLLOW 集加入 SELECT 集中/n if (flag)/n {/n GetFollow(nonterm, production1, firsts1, follows1);/n foreach (var f in follows1[nonterm])/n {/n if (!select.Contains(f))/n select.Add(f);/n }/n }/n selects1[nonterm].Add(string.Join(/'/', select.ToArray()));/n }/n }/n return selects1;/n}/n/n // 判断一个文法是否是 LL(1) 文法/n private bool JudgeLL1(Dictionary<string, List> production1, Dictionary<string, List> firsts1, Dictionary<string, List> follows1)/n {/n foreach (var item in production1)/n {/n Dictionary<string, List> map = new Dictionary<string, List>();/n foreach (var prod in item.Value)/n {/n List list = new List();/n foreach (var c in prod)/n {/n if (IsTerminal(c))/n {/n list.Add(c.ToString());/n break;/n }/n else/n {/n GetFirst(c.ToString(), production1, firsts1);/n foreach (var f in firsts1[c.ToString()])/n {/n if (!f.Equals(/'#/') && !list.Contains(f))/n list.Add(f);/n }/n if (!IsReachEmpty(c.ToString(), production1))/n break;/n }/n }/n if (list.Contains(/'#/'))/n {/n GetFollow(item.Key, production1, firsts1, follows1);/n foreach (var f in follows1[item.Key])/n {/n if (!list.Contains(f))/n list.Add(f);/n }/n }/n string key = string.Join(/'/', list.ToArray());/n if (map.ContainsKey(key))/n return false;/n map.Add(key, list);/n }/n }/n return true;/n }/n/n }/