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 List terminals;/n List nonterminals;/n/n private void groupBox1_Enter(object sender, EventArgs e)/n {/n/n }/n/n private void button3_Click(object sender, EventArgs e)/n {/n richTextBox1.Text = /'/';/n OpenFileDialog openFileDialog1 = new OpenFileDialog();/n DialogResult dr = openFileDialog1.ShowDialog();/n string filename = openFileDialog1.FileName;//获取或设置一个包含在文件对话框中选定的文件名字符串/n if (dr == DialogResult.OK && !string.IsNullOrEmpty(filename))/n {/n StreamReader sr = new StreamReader(filename);/n richTextBox1.Text = sr.ReadToEnd();/n sr.Close();/n }/n }/n/n private void Form4_Load(object sender, EventArgs e)/n {/n/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 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 }/n/n private void button5_Click(object sender, EventArgs e)/n {/n SaveFileDialog saveFileDialog = new SaveFileDialog();/n saveFileDialog.Filter = /'Text files (.txt)|.txt|All files (.)|./';/n saveFileDialog.FileName = /'Grammer.txt/'; // 设置默认文件名/n if (saveFileDialog.ShowDialog() == DialogResult.OK)/n {/n string filename = saveFileDialog.FileName;/n File.WriteAllText(filename, richTextBox1.Text);/n MessageBox.Show(/'文件已成功保存至：/' + filename);/n }/n }/n/n private void button1_Click(object sender, EventArgs e)/n {/n // 获取所有的符号集合/n List symbols = new List();/n foreach (var item in production.Keys)/n {/n if (!symbols.Contains(item))/n symbols.Add(item);/n foreach (var prod in production[item])/n {/n foreach (var c in prod)/n {/n if (!symbols.Contains(c.ToString()))/n symbols.Add(c.ToString());/n }/n }/n }/n // 将符号集合按照终结符和非终结符分开/n nonterminals = new List();/n terminals = new List();/n foreach (var s in symbols)/n {/n if (char.IsUpper(s[0]))/n nonterminals.Add(s);/n else/n terminals.Add(s);/n }/n/n listView1.Columns.Clear();/n listView1.Items.Clear();/n listView1.View = View.Details;/n/n // 添加第一列/n listView1.Columns.Add(/'/', 30);/n/n // 添加终结符列/n foreach (var item in terminals)/n {/n listView1.Columns.Add(item, 30);/n }/n/n // 添加非终结符行/n foreach (var item in nonterminals)/n {/n ListViewItem lvi = new ListViewItem(item);/n lvi.SubItems.Add(/'/');/n foreach (var t in terminals)/n {/n lvi.SubItems.Add(/'/');/n }/n listView1.Items.Add(lvi);/n }/n/n // 填充表格/n foreach (var item in firsts)/n {/n int row = nonterminals.IndexOf(item.Key);/n foreach (var t in terminals)/n {/n int col = terminals.IndexOf(t);/n if(!item.Value.Contains(t))/n listView1.Items[row].SubItems[col + 1].Text = /'0/';/n else/n listView1.Items[row].SubItems[col + 1].Text = /'1/';/n }/n }/n }/n/n private void button2_Click(object sender, EventArgs e)/n {/n // 获取所有的符号集合/n List symbols = new List();/n foreach (var item in production.Keys)/n {/n if (!symbols.Contains(item))/n symbols.Add(item);/n foreach (var prod in production[item])/n {/n foreach (var c in prod)/n {/n if (!symbols.Contains(c.ToString()))/n symbols.Add(c.ToString());/n }/n }/n }/n // 将符号集合按照终结符和非终结符分开/n nonterminals = new List();/n terminals = new List();/n foreach (var s in symbols)/n {/n if (char.IsUpper(s[0]))/n nonterminals.Add(s);/n else/n terminals.Add(s);/n }/n/n foreach (var s in nonterminals)/n {/n System.Console.WriteLine(s);/n }/n/n foreach(var s in terminals)/n {/n System.Console.WriteLine(s);/n }/n/n listView2.Columns.Clear();/n listView2.Items.Clear();/n listView2.View = View.Details;/n/n // 添加第一列/n listView2.Columns.Add(/'/', 30);/n/n // 添加终结符列/n foreach (var item in terminals)/n {/n listView2.Columns.Add(item, 30);/n }/n/n // 添加非终结符行/n foreach (var item in nonterminals)/n {/n ListViewItem lvi = new ListViewItem(item);/n lvi.SubItems.Add(/'/');/n foreach (var t in terminals)/n {/n lvi.SubItems.Add(/'/');/n }/n listView2.Items.Add(lvi);/n }/n/n // 填充表格/n foreach (var item in follows)/n {/n int row = nonterminals.IndexOf(item.Key);/n foreach (var t in terminals)/n {/n int col = terminals.IndexOf(t);/n if (!item.Value.Contains(t))/n listView2.Items[row].SubItems[col + 1].Text = /'0/';/n else/n listView2.Items[row].SubItems[col + 1].Text = /'1/';/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 if (!item.Key.Equals(symbol))/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 // 如果该非终结符后面是终结符，则将该终结符加入该非终结符的 FOLLOW 集中/n else/n {/n // 如果该非终结符后面是非终结符，则将该非终结符的 FIRST 集加入该非终结符的 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 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 if (!item.Key.Equals(symbol))/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 }/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 }/