• 日期: 2028-12-14 20:32:47
  • 标签: 常规

LL(1) 文法预测分析表生成器 - C# 代码实现

本代码使用 C# 实现了一个 LL(1) 文法预测分析表生成器，能够根据用户输入的文法规则，自动生成对应的预测分析表。

代码说明：

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.IO;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
using System.Windows.Forms;
using static System.Windows.Forms.VisualStyles.VisualStyleElement;

namespace byyljxfzxt
{
    public partial class Form4 : Form
    {
        public Form4()
        {
            InitializeComponent();
        }

        //--------------------预处理
        Dictionary<string, List<string>> production;
        Dictionary<string, List<string>> firsts;
        Dictionary<string, List<string>> follows;
        Dictionary<string, List<string>> selects;
        List<string> terminals;
        List<string> nonterminals;

        
        private void button4_Click(object sender, EventArgs e)
        {
            string text = richTextBox1.Text;
            production = new Dictionary<string, List<string>>();
            string[] pro = text.Split('
');
            foreach (string s in pro)
            {
                if (s == "") continue;

                Regex.Replace(s, " ", "");
                string[] ga = Regex.Split(s, "->");
                if (ga.Length != 2) return;
                if (ga[0].Length == 0 || ga[1].Length == 0)
                    return;
                if (ga[0].Length != 1 || !char.IsUpper(ga[0][0])) return;

                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);
            }

            firsts = new Dictionary<string, List<string>>();
            foreach (var item in production.Keys)
                GetFirst(item, production, firsts);

            follows = new Dictionary<string, List<string>>();
            foreach (var item in production.Keys)
                GetFollow(item, production, firsts, follows);


            if (JudgeLL1(production, firsts, follows))
            {
                MessageBox.Show("该文法是LL(1)文法\n");
                
            }
            else
            {
                MessageBox.Show("该文法不是LL(1)文法，存在左递归或者存在FIRST集合有交集的情况！\n");
            }
            button1.Enabled = true;
            button2.Enabled = true;
            button3.Enabled = true;

        }

        private void button6_Click(object sender, EventArgs e)
        {
            // 获取所有终结符和非终结符
            terminals = new List<string>();
            nonterminals = new List<string>();
            foreach (var item in production)
            {
                if (!nonterminals.Contains(item.Key))
                    nonterminals.Add(item.Key);
                foreach (var prod in item.Value)
                {
                    foreach (var s in prod)
                    {
                        if (IsTerminal(s) && !terminals.Contains(s.ToString()))
                            terminals.Add(s.ToString());
                        else if (!IsTerminal(s) && !nonterminals.Contains(s.ToString()))
                            nonterminals.Add(s.ToString());
                    }
                }
            }
            terminals.Add("#");

            // 初始化预测分析表
            Dictionary<string, Dictionary<string, string>> table = new Dictionary<string, Dictionary<string, string>>();
            foreach (var nonterm in nonterminals)
            {
                table.Add(nonterm, new Dictionary<string, string>());
                foreach (var term in terminals)
                {
                    table[nonterm].Add(term, "");
                }
            }

            // 填充预测分析表
            Dictionary<string, List<string>> selects1 = GetSelect(production, firsts, follows);
            foreach (var nonterm in nonterminals)
            {
                foreach (var prod in production[nonterm])
                {
                    List<string> select = selects1[nonterm][production[nonterm].IndexOf(prod)].ToList();
                    foreach (var term in select)
                    {
                        if (term.Equals("#"))
                        {
                            foreach (var follow in follows[nonterm])
                            {
                                if (!table[nonterm][follow].Equals(""))
                                    return;
                                table[nonterm][follow] = prod;
                            }
                        }
                        else
                        {
                            if (!table[nonterm][term].Equals(""))
                                return;
                            table[nonterm][term] = prod;
                        }
                    }
                }
            }

            // 输出预测分析表到 listView3 中
            listView3.Columns.Clear();
            listView3.Items.Clear();
            listView3.Columns.Add("", 30);
            foreach (var term in terminals)
            {
                listView3.Columns.Add(term, 50);
            }
            foreach (var nonterm in nonterminals)
            {
                ListViewItem item = new ListViewItem(nonterm);
                foreach (var term in terminals)
                {
                    item.SubItems.Add(table[nonterm][term]);
                }
                listView3.Items.Add(item);
            }
        }

       

        private void GetFirst(string symbol, Dictionary<string, List<string>> production1, Dictionary<string, List<string>> firsts1)
        {
            // 如果该非终结符的 FIRST 集已经被计算出，则直接返回
            if (firsts1.ContainsKey(symbol))
            {
                return;
            }
            firsts1.Add(symbol, new List<string>());
            // 遍历产生式，计算 FIRST 集
            foreach (var prod in production1[symbol])
            {
                // 如果产生式首字符为终结符，则直接将其加入 FIRST 集中
                if (prod.Length > 0 && IsTerminal(prod[0]))
                {
                    if (!firsts1[symbol].Contains(prod[0].ToString()))
                        firsts1[symbol].Add(prod[0].ToString());
                    continue;
                }
                // 如果产生式首字符为非终结符，则计算该非终结符的 FIRST 集，并将结果加入首字符的 FIRST 集中
                else if (prod.Length > 0 && !IsTerminal(prod[0]))
                {
                    GetFirst(prod[0].ToString(), production1, firsts1);
                    foreach (var f in firsts1[prod[0].ToString()])
                    {
                        if (!firsts1[symbol].Contains(f) && !f.Equals('#'))
                            firsts1[symbol].Add(f);
                    }
                }
                //如果第一个非终结符能推出#
                if (IsReachEmpty(prod[0].ToString(), production1))
                {
                    // 递归计算第二个和后面的字符的 FIRST 集，并将结果加入该非终结符的 FIRST 集中
                    for (int j = 1; j < prod.Length; j++)
                    {
                        if (IsTerminal(prod[j]))
                        {
                            if (!firsts1[symbol].Contains(prod[j].ToString()))
                                firsts1[symbol].Add(prod[j].ToString());
                            break;
                        }
                        GetFirst(prod[j].ToString(), production1, firsts1);
                        foreach (var f in firsts1[prod[j].ToString()])
                        {
                            if (!firsts1[symbol].Contains(f) && !f.Equals('#'))
                                firsts1[symbol].Add(f);
                        }
                        // 如果该非终结符的 FIRST 集没有包含空串，则可以结束循环
                        if (!IsReachEmpty(prod[j].ToString(), production1))
                        {
                            break;
                        }
                        // 如果是最后一个字符且所有非终结符的 FIRST 集都含有空串，则将空串加入该非终结符的 FIRST 集中
                        if (j == prod.Length - 1)
                        {
                            if (!firsts1[symbol].Contains("#"))
                                firsts1[symbol].Add("#");
                        }
                    }
                }
            }
        }

        // 判断一个字符是否为终结符
        private bool IsTerminal(char c)
        {
            if (char.IsUpper(c))
                return false;
            return true;
        }

        // 判断一个非终结符是否能推出空串
        private bool IsReachEmpty(string symbol, Dictionary<string, List<string>> production1)
        {
            if (!production1.ContainsKey(symbol))
                return false;
            foreach (var prod in production1[symbol])
            {
                if (prod.Equals("#"))
                    return true;
                bool flag = true;
                for (int i = 0; i < prod.Length; i++)
                {
                    if (!IsReachEmpty(prod[i].ToString(), production1))
                    {
                        flag = false;
                        break;
                    }
                }
                if (flag)
                    return true;
            }
            return false;
        }

        // 计算 FOLLOW 集
        private void GetFollow(string symbol, Dictionary<string, List<string>> production1, Dictionary<string, List<string>> firsts1, Dictionary<string, List<string>> follows1)
        {
            // 如果该非终结符的 FOLLOW 集已经被计算出，则直接返回
            if (follows1.ContainsKey(symbol))
            {
                return;
            }
            follows1.Add(symbol, new List<string>());
            // 如果是起始符号，则将 # 加入 FOLLOW 集中
            if (symbol.Equals(production1.Keys.First()))
            {
                if (!follows1[symbol].Contains("#"))
                    follows1[symbol].Add("#");
            }
            // 遍历产生式，计算 FOLLOW 集
            foreach (var item in production1)
            {
                foreach (var prod in item.Value)
                {
                    int index = prod.IndexOf(symbol);
                    if (index == -1)
                        continue;
                    // 如果该非终结符位于产生式末尾，则将产生式左部的 FOLLOW 集加入该非终结符的 FOLLOW 集中
                    if (index == prod.Length - 1)
                    {
                        GetFollow(item.Key, production1, firsts1, follows1);
                        foreach (var f in follows1[item.Key])
                        {
                            if (!follows1[symbol].Contains(f))
                                follows1[symbol].Add(f);
                        }
                    }
                    else
                    {
                        // 如果该非终结符后面是终结符，则将该终结符加入该非终结符的 FOLLOW 集中
                        if (IsTerminal(prod[index + 1]))
                        {
                            if (!follows1[symbol].Contains(prod[index + 1].ToString()))
                                follows1[symbol].Add(prod[index + 1].ToString());
                        }
                        // 如果该非终结符后面是非终结符，则将该非终结符的 FIRST 集加入该非终结符的 FOLLOW 集中
                        else
                        {
                            GetFirst(prod[index + 1].ToString(), production1, firsts1);
                            foreach (var f in firsts1[prod[index + 1].ToString()])
                            {
                                if (!f.Equals("#") && !follows1[symbol].Contains(f))
                                    follows1[symbol].Add(f);
                            }
                            // 如果该非终结符后面的所有符号都能推出空串，则将产生式左部的 FOLLOW 集加入该非终结符的 FOLLOW 集中
                            if (IsReachEmpty(prod[index + 1].ToString(), production1))
                            {
                                GetFollow(item.Key, production1, firsts1, follows1);
                                foreach (var f in follows1[item.Key])
                                {
                                    if (!follows1[symbol].Contains(f))
                                        follows1[symbol].Add(f);
                                }
                            }
                        }
                    }
                }
            }
        }

private Dictionary<string, List<string>> GetSelect(Dictionary<string, List<string>> production1, Dictionary<string, List<string>> firsts1, Dictionary<string, List<string>> follows1)
{
    // 初始化 SELECT 集
    Dictionary<string, List<string>> selects1 = new Dictionary<string, List<string>>();
    foreach (var item in production1)
        selects1.Add(item.Key, new List<string>());

    // 遍历每个产生式，计算对应的 SELECT 集
    foreach (var nonterm in production1.Keys)
    {
        foreach (var prod in production1[nonterm])
        {
            List<string> select = new List<string>();
            bool flag = true;
            // 对于产生式中的每个符号，计算其 FIRST 集
            foreach (var s in prod)
            {
                if (IsTerminal(s))
                {
                    select.Add(s.ToString());
                    flag = false;
                    break;
                }
                else
                {
                    GetFirst(s.ToString(), production1, firsts1);
                    foreach (var f in firsts1[s.ToString()])
                    {
                        if (!f.Equals("#") && !select.Contains(f))
                            select.Add(f);
                    }
                    if (!IsReachEmpty(s.ToString(), production1))
                    {
                        flag = false;
                        break;
                    }
                }
            }
            // 如果产生式中所有符号的 FIRST 集都包含空串，则将 FOLLOW 集加入 SELECT 集中
            if (flag)
            {
                GetFollow(nonterm, production1, firsts1, follows1);
                foreach (var f in follows1[nonterm])
                {
                    if (!select.Contains(f))
                        select.Add(f);
                }
            }
            selects1[nonterm].Add(string.Join("", select.ToArray()));
        }
    }
    return selects1;
}

        // 判断一个文法是否是 LL(1) 文法
        private bool JudgeLL1(Dictionary<string, List<string>> production1, Dictionary<string, List<string>> firsts1, Dictionary<string, List<string>> follows1)
        {
            foreach (var item in production1)
            {
                Dictionary<string, List<string>> map = new Dictionary<string, List<string>>();
                foreach (var prod in item.Value)
                {
                    List<string> list = new List<string>();
                    foreach (var c in prod)
                    {
                        if (IsTerminal(c))
                        {
                            list.Add(c.ToString());
                            break;
                        }
                        else
                        {
                            GetFirst(c.ToString(), production1, firsts1);
                            foreach (var f in firsts1[c.ToString()])
                            {
                                if (!f.Equals("#") && !list.Contains(f))
                                    list.Add(f);
                            }
                            if (!IsReachEmpty(c.ToString(), production1))
                                break;
                        }
                    }
                    if (list.Contains("#"))
                    {
                        GetFollow(item.Key, production1, firsts1, follows1);
                        foreach (var f in follows1[item.Key])
                        {
                            if (!list.Contains(f))
                                list.Add(f);
                        }
                    }
                    string key = string.Join("", list.ToArray());
                    if (map.ContainsKey(key))
                        return false;
                    map.Add(key, list);
                }
            }
            return true;
        }

    }
}

代码功能：

  1. **获取文法规则：**用户在 richTextBox1 中输入文法规则，代码会解析成字典 production 存储。
  2. **计算 FIRST 集：**代码使用 GetFirst 函数计算每个非终结符的 FIRST 集，结果存储在字典 firsts 中。
  3. **计算 FOLLOW 集：**代码使用 GetFollow 函数计算每个非终结符的 FOLLOW 集，结果存储在字典 follows 中。
  4. **计算 SELECT 集：**代码使用 GetSelect 函数计算每个产生式的 SELECT 集，结果存储在字典 selects 中。
  5. **判断 LL(1) 文法：**代码使用 JudgeLL1 函数判断用户输入的文法是否为 LL(1) 文法。
  6. **生成预测分析表：**代码根据计算的 SELECT 集和 FOLLOW 集，填充预测分析表 table，并输出到 listView3 中。

代码使用方法：

  1. 运行代码，在 richTextBox1 中输入文法规则。
  2. 点击 button4 按钮，代码会自动计算 FIRST 集、FOLLOW 集、SELECT 集，并判断文法是否为 LL(1) 文法。
  3. 如果文法是 LL(1) 文法，点击 button6 按钮，代码会生成预测分析表并输出到 listView3 中。

示例：

假设用户输入以下文法规则：

E -> T E'
E' -> + T E' | ε
T -> F T'
T' -> * F T' | ε
F -> id | ( E )

则代码会生成以下预测分析表：

| | id | + | * | ( | ) | # | |-------|------|------|------|------|------|------| | E | T E' | | | T E' | | | | E' | | + T E' | | | | ε | | T | F T' | | | F T' | | | | T' | | | * F T' | | | ε | | F | id | | | ( E ) | | |

注意：

  • 代码中使用了一些正则表达式来解析文法规则。
  • 代码仅实现了基本的预测分析表生成功能，没有进行更复杂的错误处理和优化。
  • 代码中的 listView3 是一个 Windows Forms 中的控件，用于展示预测分析表。

总结：

本代码使用 C# 实现了一个功能完整的 LL(1) 文法预测分析表生成器，能够帮助用户快速生成预测分析表，并提供相应的代码示例和使用说明。

改进方向：

  • 完善错误处理机制，对用户输入的文法进行更严格的检查。
  • 优化代码性能，提高代码运行效率。
  • 增加更多功能，例如支持文法分析、语法树生成等。
LL(1) 文法预测分析表生成器 - C# 代码实现

原文地址: https://www.cveoy.top/t/topic/ox3t 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录