LL(1) 文法预测分析表生成算法实现 - C# 代码示例 - 常规

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;
    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)
    {
        //构造预测分析表
        Dictionary<string, Dictionary<string, string>> table = new Dictionary<string, Dictionary<string, string>>();
        foreach (var nonterminal in nonterminals)
        {
            table.Add(nonterminal, new Dictionary<string, string>());
            foreach (var terminal in terminals)
            {
                table[nonterminal].Add(terminal, "");
            }
        }

        selects = GetSelect(production, firsts, follows);
        foreach (var item in production)
        {
            string A = item.Key;
            foreach (var prod in item.Value)
            {
                foreach (var t in selects.Getselect()[A][prod])
                {
                    if (table[A][t] != "")
                    {
                        MessageBox.Show("该文法不是LL(1)文法，存在冲突！\n");
                        return;
                    }
                    table[A][t] = prod;
                }
            }
        }

        //输出预测分析表
        listView3.Clear();
        foreach (var terminal in terminals)
        {
            listView3.Columns.Add(terminal, 100, HorizontalAlignment.Center);
        }
        foreach (var nonterminal in nonterminals)
        {
            ListViewItem lvi = new ListViewItem(nonterminal);
            foreach (var terminal in terminals)
            {
                lvi.SubItems.Add(table[nonterminal][terminal]);
            }
            listView3.Items.Add(lvi);
        }
    }

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

  
}

} public Dictionary<string, Select> GetSelect(Dictionary<string, List> production, Dictionary<string, List> firsts, Dictionary<string, List> follows) { Dictionary<string, Select> selects = new Dictionary<string, Select>(); foreach (var nonterminal in production.Keys) { selects.Add(nonterminal, new Select(nonterminal, production, firsts, follows)); } return selects; }

public class Select { private string nonterminal; private Dictionary<string, List> production; private Dictionary<string, List> firsts; private Dictionary<string, List> follows; private Dictionary<string, List> selects;

public Select(string nonterminal, Dictionary<string, List<string>> production, Dictionary<string, List<string>> firsts, Dictionary<string, List<string>> follows)
{
    this.nonterminal = nonterminal;
    this.production = production;
    this.firsts = firsts;
    this.follows = follows;
    selects = new Dictionary<string, List<string>>();
    GetSelect();
}

public void GetSelect()
{
    foreach (var prod in production[nonterminal])
    {
        selects.Add(prod, new List<string>());
        bool flag = true;
        foreach (var symbol in prod)
        {
            if (IsTerminal(symbol))
            {
                selects[prod].Add(symbol.ToString());
                flag = false;
                break;
            }
            else
            {
                foreach (var f in firsts[symbol.ToString()])
                {
                    if (!f.Equals("#"))
                    {
                        selects[prod].Add(f);
                    }
                    else
                    {
                        flag = true;
                    }
                }
                if (!flag)
                {
                    break;
                }
            }
        }
        if (flag)
        {
            foreach (var f in follows[nonterminal])
            {
                selects[prod].Add(f);
            }
        }
    }
}

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

public Dictionary<string, List<string>> GetSelects()
{
    return selects;
}

}

private void button6_Click(object sender, EventArgs e) { //构造预测分析表 Dictionary<string, Dictionary<string, string>> table = new Dictionary<string, Dictionary<string, string>>(); foreach (var nonterminal in nonterminals) { table.Add(nonterminal, new Dictionary<string, string>()); foreach (var terminal in terminals) { table[nonterminal].Add(terminal, ""); } }

Dictionary<string, Select> selects = GetSelect(production, firsts, follows);
foreach (var item in production)
{
    string A = item.Key;
    foreach (var prod in item.Value)
    {
        foreach (var t in selects[A].GetSelects()[prod])
        {
            if (table[A][t] != "")
            {
                MessageBox.Show("该文法不是LL(1)文法，存在冲突！\n");
                return;
            }
            table[A][t] = prod;
        }
    }
}

//输出预测分析表
listView3.Clear();
foreach (var terminal in terminals)
{
    listView3.Columns.Add(terminal, 100, HorizontalAlignment.Center);
}
foreach (var nonterminal in nonterminals)
{
    ListViewItem lvi = new ListViewItem(nonterminal);
    foreach (var terminal in terminals)
    {
        lvi.SubItems.Add(table[nonterminal][terminal]);
    }
    listView3.Items.Add(lvi);
}