• 日期: 2026-06-21
  • 标签: 常规

{
"title": "class analyse_sentence", "description": "使用 C# 实现的 LL(1) 预测分析算法，用于分析输入的文法字符串，并提供详细的分析过程。", "keywords": "LL(1), 预测分析, 文法分析, C#, 代码, 算法", "content": "class analyse_sentence { string text; Select select; Stack analyse; Stack input; public List result_analys; public List result_input; public List result_parse;

    public analyse_sentence(string text, Select select)
    {
        this.text = text;
        this.select = select;
        this.analyse = new Stack();
        input = new Stack();
        result_analys = new List<string>();
        result_input = new List<string>(); 
        result_parse = new List<string>();
        analyseresult();
    }

    void analyseresult()
    {
        var selects = select.getselects();
        analyse.push('#');
        analyse.push(selects.First().Key[0]);
        input.push('#');
        for (int i= text.Length-1; i>=0; i--)
            input.push(text[i]);
        result_analys.Add(analyse.getString());
        result_input.Add(input.getString());

        while (true)
        {
            //如果分析栈栈顶元素为终结符
            if (IsTerminal(analyse.peek()))
            {
                //当两个栈都只剩下#时，说明匹配成功
                if(analyse.peek() == input.peek() && analyse.length()==1 && input.length()==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;
                }
            }

            int flag = 0;
            string nofinal = analyse.peek().ToString();
            string final = input.peek().ToString();
            foreach(var parse in selects[nofinal])
            {
                if(parse.Value.Contains(final))
                {
                    result_parse.Add(nofinal+"->" + parse.Key);
                    analyse.pop();
                    //当推出的产生式不为空时，对分析栈进行添加
                    if (!parse.Key.Equals("#"))
                    {
                        addanalyse(parse.Key);
                    }
                    result_analys.Add(analyse.getString());
                    result_input.Add(input.getString());
                    flag = 1; break;
                }
            }
            //说明该非终结符中没有可推导出该终结符的产生式
            if (flag == 0)
            {
                result_parse.Add("失败");
                return;
            }
        }
    }

    void addanalyse(String t)
    {
        for(int i=t.Length-1; i>=0; i--)
        {
            analyse.push(t[i]);
        }
    }

    static bool IsTerminal(char symbol)
    {
        return !char.IsUpper(symbol);
    }
}

根据上述代码，在下列代码的基础上增加button7按钮功能对textBox1中输入的字符进行分析，button8按钮提供在listView4中单步显示分析信息，button9按钮提供在listView4中一键显示分析信息。 private void GetFirst(string symbol, Dictionary<string, List> production1, Dictionary<string, List> firsts1) { // 如果该非终结符的 FIRST 集已经被计算出，则直接返回 if (firsts1.ContainsKey(symbol)) { return; } firsts1.Add(symbol, new List()); // 遍历产生式，计算 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);
                            }
                        }
                    }
                }
            }
        }
    }

    // 判断一个文法是否是 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;
    }

    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 Analyse()
    {
        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.ToString());
                    result_input.Add(input.ToString());
                    continue;
                }
                else
                {
                    result_parse.Add("失败");
                    return;
                }
            }

            string nofinal = analyse.Peek().ToString();
            string final = input.Peek().ToString();

            // 如果分析表中没有该产生式，则匹配失败
            if (!table.ContainsKey(nofinal) || !table[nofinal].ContainsKey(final))
            {
                result_parse.Add("失败");
                return;
            }

            // 获取推导产生式
            string production = table[nofinal][final];
            result_parse.Add(nofinal + "->" + production);

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

            // 更新分析栈和输入栈的变化
            result_analys.Add(analyse.ToString());
            result_input.Add(input.ToString());
        }
    }

private void button7_Click(object sender, EventArgs e) { string text = textBox1.Text; analyze();

        // 在界面第二行之后展示步骤、分析串、剩余输入串、推导所用产生式或匹配
        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 analyze() { // 获取文法 string grammar = textBox2.Text;

// 将文法转换为产生式
Dictionary<string, List<string>> production = new Dictionary<string, List<string>>();
string[] lines = grammar.Split(new char[] { '\r', '\n' }, StringSplitOptions.RemoveEmptyEntries);
foreach (string line in lines)
{
    string[] tokens = line.Split(new char[] { ' ', '\t', '-', '>' }, StringSplitOptions.RemoveEmptyEntries);
    string nonterm = tokens[0];
    List<string> prods;
    if (!production.ContainsKey(nonterm))
    {
        prods = new List<string>();
        production.Add(nonterm, prods);
    }
    else
    {
        prods = production[nonterm];
    }
    for (int i = 1; i < tokens.Length; i++)
    {
        prods.Add(tokens[i]);
    }
}

// 获取非终结符和终结符
HashSet<string> nonterminals = new HashSet<string>();
HashSet<string> terminals = new HashSet<string>();
foreach (var item in production)
{
    nonterminals.Add(item.Key);
    foreach (var prod in item.Value)
    {
        foreach (var c in prod)
        {
            if (char.IsUpper(c))
            {
                nonterminals.Add(c.ToString());
            }
            else
            {
                terminals.Add(c.ToString());
            }
        }
    }
}
terminals.Remove("#");

// 计算 FIRST 集
Dictionary<string, List<string>> firsts = new Dictionary<string, List<string>>();
foreach (string nonterm in nonterminals)
{
    GetFirst(nonterm, production, firsts);
}

// 计算 FOLLOW 集
Dictionary<string, List<string>> follows = new Dictionary<string, List<string>>();
foreach (string nonterm in nonterminals)
{
    GetFollow(nonterm, production, firsts, follows);
}

// 判断文法是否为 LL(1) 文法
if (!JudgeLL1(production, firsts, follows))
{
    MessageBox.Show("该文法不是 LL(1) 文法！");
    return;
}

// 构造预测分析表
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, "");
    }
    if (follow
C# 文法分析器：LL(1) 预测分析算法实现

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

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