• 日期: 2026-03-24 10:27:34
  • 标签: 常规

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;
    Dictionary<string, Dictionary<string, string>> table;
    List<string> terminals;
    List<string> nonterminals;

Stack analyse; // 分析栈 Stack input; // 输入栈 List result_analys; // 分析栈的每一步变化 List result_input; // 输入栈的每一步变化 List result_parse; // 每一步分析的结果，包括推导所用产生式或匹配成功/失败的信息

    private void button4_Click(object sender, EventArgs e)
    {
        string text = richTextBox1.Text;
        production = 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;
            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;
        button6.Enabled = true;

    }

    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("#");
                    }
                }
            }
        }
    }

    // 计算 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 void GetSelect(Dictionary<string, List<string>> production1, Dictionary<string, List<string>> firsts1, Dictionary<string, List<string>> follows1)
    {
        //对非终结符的每个产生式获取select值
        //如果该产生式第一个字符为终结符
        //如果该产生式第一个字符为非终结符
        // 对每个非终结符进行操作
        // 对每个非终结符进行遍历
        foreach (var nonterm in nonterminals)
        {
            // 获取该非终结符的所有产生式
            var productions = production1[nonterm];

            // 遍历该非终结符的所有产生式
            foreach (var prod in productions)
            {
                // 初始化该产生式的 select 值
                List<string> select = new List<string>();

                // 如果该产生式的第一个字符为终结符，直接将该字符加入 select
                if (IsTerminal(prod[0]))
                {
                    if (prod[0].Equals('#'))
                    {
                        // 如果该产生式的第一个字符为 #，将 follow(nonterm) 加入 select
                        select.AddRange(follows1[nonterm]);
                    }
                    else
                    {
                        // 如果该产生式的第一个字符为其他终结符，将该终结符加入 select
                        select.Add(prod[0].ToString());
                    }
                }
                else
                {
                    // 如果该产生式的第一个字符为非终结符，将该非终结符的 first 集加入 select
                    select.AddRange(firsts1[prod[0].ToString()]);

                    // 如果该非终结符的 first 集中包含空串，将 follow(nonterm) 加入 select
                    if (select.Contains("#"))
                    {
                        select.Remove("#");
                        select.AddRange(follows1[nonterm]);
                    }
                }

                // 将该产生式的 select 值加入预测分析表中
                foreach (var term in select)
                {
                    table[nonterm][term] = prod;
                }
            }
        }

    }

private void button7_Click(object sender, EventArgs e) { // 判断输入是否为空 if (string.IsNullOrWhiteSpace(textBox1.Text)) { MessageBox.Show("输入为空，分析失败"); return; }

       // 初始化分析器
        Analyse(textBox1.Text, selects);

        listView4.Columns.Clear();
        listView4.Items.Clear();
        listView4.View = View.Details;


        listView4.Columns.Add("步骤", 60, HorizontalAlignment.Center);
        listView4.Columns.Add("分析串", 60, HorizontalAlignment.Center);
        listView4.Columns.Add("剩余输入串", 80, HorizontalAlignment.Center);
        listView4.Columns.Add("推导所用产生式或匹配", 150, HorizontalAlignment.Center);
        button8.Enabled = true;
        button9.Enabled = true;
    }
}

}

private void Analyse(string text, Dictionary<string, List> selects) { // 初始化分析器 analyse = new Stack(); input = new Stack(); result_analys = new List(); result_input = new List(); result_parse = new List();

// 将 # 和文本串压入输入栈
input.Push('#');
for (int i = text.Length - 1; i >= 0; i--)
{
    input.Push(text[i]);
}

// 将 # 和文法的起始符号压入分析栈
analyse.Push('#');
analyse.Push(production.Keys.First()[0]);

// 记录分析栈和输入栈的初始状态
result_analys.Add(analyse.getString());
result_input.Add(input.getString());

// 分析
while (true)
{
    // 如果分析栈栈顶元素为终结符
    if (IsTerminal(analyse.Peek()))
    {
        // 当两个栈都只剩下 # 时，说明匹配成功
        if (analyse.Peek() == input.Peek() && analyse.Count == 1 && input.Count == 1)
        {
            result_parse.Add("成功");
            return;
        }
        if (analyse.Peek() == input.Peek())
        {
            result_parse.Add(''' + analyse.Peek() + ''' + "匹配");
            analyse.Pop();
            input.Pop();
            result_analys.Add(analyse.getString());
            result_input.Add(input.getString());
            continue;
        }
        else
        {
            result_parse.Add("失败");
            return;
        }
    }

    // 获取当前分析栈栈顶的非终结符
    string nonterm = analyse.Peek().ToString();

    // 获取当前输入栈栈顶的终结符
    string term = input.Peek().ToString();

    // 获取该非终结符的 select 集
    List<string> select = selects[nonterm][term];

    // 如果 select 集为空，则说明该非终结符无法匹配当前输入符号，分析失败
    if (select.Count == 0)
    {
        result_parse.Add("失败");
        return;
    }

    // 如果 select 集包含多个产生式，则说明该文法不是 LL(1) 文法，分析失败
    if (select.Count > 1)
    {
        result_parse.Add("失败");
        return;
    }

    // 获取该非终结符和当前输入符号所对应的产生式
    string prod = selects[nonterm][term][0];

    // 将该产生式推入分析栈中
    analyse.Pop();
    if (!prod.Equals("#"))
    {
        for (int i = prod.Length - 1; i >= 0; i--)
        {
            analyse.Push(prod[i]);
        }
    }

    // 记录分析栈和输入栈的变化
    result_parse.Add(nonterm + "->" + prod);
    result_analys.Add(analyse.getString());
    result_input.Add(input.getString());

    // 如果该产生式推出了空串，则不需要弹出输入栈的符号
    if (!prod.Equals("#"))
    {
        input.Pop();
    }
}
LL(1) 语法分析器：使用预测分析表进行句子分析

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

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