SLR 文法分析表构造 - C# 代码实现 - 常规

public class SLRNode { public string Left; public string Right; public SLRNode(string Left, string Right) { this.Left = Left; this.Right = Right; } } //项目集类 public class SLRitemsets { public List Container = new List(100); //记录项目在项目集合中的序号 }

//DFA结点 public struct DFA { public int from; public char symbol; public int to; public DFA(int from, char symbol, int to) { this.from = from; this.symbol = symbol; this.to = to; } }

//分析表结点 public class Table { public bool error;//是否为ERROR public char type;//结点类型 public int id;//数值 public Table() { this.error = true; } public Table(char type, int id) { this.type = type; this.id = id; this.error = false; } } public DFA[] dfa = new DFA[100]; public int Pindex = 0; //dfa数组指针 public Table[][] SLRAna;//分析表 public Analyze Jz; public bool Success = false; public List SLRproNum = new List(50);//产生式列表 public List SLRobjNum = new List(50);//项目列表 public List proitemset = new List(100);//项目集合 public List Gy_obj = new List(50);//归约项目序号集合 public List Gy_itemset = new List(50);//含有归约项目的集合的序号的集合 public List Nchar = new List(50);//非终结符集合 public List Echar = new List(50);//终结符集合

    public string RStr = '';
    public string RStr_obitemset = '';//输出返回
    public string RStr_DFA = '';
    public string RStr_ANA = '';
        
        listView2.Clear();
        LR.Table[][] table;
        table = lr.GET_ANA();
        int xlen = table.GetLength(0);
        int ylen = table[1].Length;

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

        listView2.Columns.Add(' ');

        for (int i = 0; i < lr.Echar.Count; i++)//添加表头
        {
            string text = lr.Echar[i].ToString();
            listView2.Columns.Add(text,58);

        }
        for (int i = 0; i < lr.Nchar.Count; i++)//添加表头
        {
            string text = lr.Nchar[i].ToString();
            listView2.Columns.Add(text,58);
        }

        for (int i = 0; i < xlen; i++)
        {
            ListViewItem li = new ListViewItem(i.ToString());
            
            for (int j = 0; j < ylen; j++)
            {
                string st = '';
                if (table[i][j].error)
                    st = '-';
                else if (table[i][j].type == 'A')
                    st = 'AC';
                else
                    st = table[i][j].type.ToString() + table[i][j].id.ToString();
                li.SubItems.Add(st);

            }
            listView2.Items.Add(li);
        }

        listView2.GridLines = true;

} public Table[][] GET_ANA() { SLRAnaly(); RStr_ANA += '\r\nSLR0分析表:\r\n '; int i; for (i = 0; i < Echar.Count; i++) { RStr_ANA += Echar[i].ToString() + ' '; } for (i = 0; i < Nchar.Count; i++) { RStr_ANA += Nchar[i].ToString() + ' '; } RStr_ANA += '\r\n'; for (i = 0; i < proitemset.Count; i++) { RStr_ANA += i.ToString() + ' '; for (int j = 0; j < Echar.Count + Nchar.Count; j++) {

                if (SLRAna[i][j].error)
                {
                    RStr_ANA += '  ' + '    ';
                }
                else if (i == 1 && j == Echar.Count - 1)
                {
                    RStr_ANA += 'AC' + '    ';
                }
                else if (SLRAna[i][j].type != 'N')
                {
                    RStr_ANA += SLRAna[i][j].type.ToString() + SLRAna[i][j].id.ToString() + '    ';
                }
                else
                    RStr_ANA += SLRAna[i][j].id.ToString() + '    ';
            }
            RStr_ANA += '\r\n';
        }

        return SLRAna;

    }

public void SLRAnaly() { Table tnode = new Table();

        SLRAna = new Table[proitemset.Count][];
        for (int i = 0; i < proitemset.Count; i++)
            SLRAna[i] = new Table[Echar.Count + Nchar.Count];

        for (int i = 0; i < proitemset.Count; i++)//初始化 赋予ERROR属性
            for (int j = 0; j < Echar.Count + Nchar.Count; j++)//为终结符加r状态 
                SLRAna[i][j] = tnode;

        tnode = new Table('A', 0);
        SLRAna[1][FindID(Echar, '#')] = tnode;//项目集1必定是接受项目   构建[1][#]:acc的情况 先直接赋值好 dfa里没有

        for (int i = 0; i < Gy_itemset.Count; i++)
        {
            int proNum = Find_pro(SLRobjNum[proitemset[Gy_itemset[i]].Container[0]]);
            foreach (char c in Follow[Nchar[proNum]])//对于非终结符的follow集中的每个终结符
            {
                int j = FindID(Echar, c);
                if (j != -1)//如果该终结符在Echar中存在
                {
                    tnode = new Table('r', proNum);//归约项目 找到原产生式序号 添加状态r
                    SLRAna[Gy_itemset[i]][j] = tnode;
                }
            }
        }

        for (int i = 0; i < Pindex; i++)
        {
            if (isFinalsymbol(dfa[i].symbol))//symbol为非终结符  添加状态N
            {
                int CID = FindID(Nchar, dfa[i].symbol);
                foreach (char c in Follow[Nchar[CID]])//对于非终结符的follow集中的每个终结符
                {
                    int j = FindID(Echar, c);
                    if (j != -1)//如果该终结符在Echar中存在
                    {
                        tnode = new Table('N', dfa[i].to);
                        SLRAna[dfa[i].from][j + Echar.Count] = tnode;
                    }
                }
            }
            else //不是归约项目 添加状态S
            {
                int CID = FindID(Echar, dfa[i].symbol);
                tnode = new Table('S', dfa[i].to);
                SLRAna[dfa[i].from][CID] = tnode;
            }
        }
    }

上述是SLR文法的分析表的构造，请给出相应follow集代码。内容：以下是SLR文法中求解Follow集的代码：

public Dictionary<char, HashSet> Follow = new Dictionary<char, HashSet>();

public void GetFollow() { foreach (char c in Nchar) { Follow.Add(c, new HashSet()); } Follow[Nchar[0]].Add('#');//将#加入起始符号的follow集

bool flag = true;
while (flag)
{
    flag = false;
    for (int i = 0; i < SLRproNum.Count; i++)//遍历每个产生式
    {
        string right = SLRproNum[i].Right;
        for (int j = 0; j < right.Length; j++)//遍历产生式右部每个符号
        {
            char c = right[j];
            if (isNonterminal(c))//如果是非终结符
            {
                int k = j + 1;
                while (k < right.Length && isNonterminal(right[k]))//向后找第一个不是非终结符的符号
                {
                    k++;
                }
                if (k == right.Length)//如果该非终结符后面没有符号
                {
                    flag = flag || AddToFollow(SLRproNum[i].Left, Follow[SLRproNum[i].Left], Follow[c]);//将产生式左部的follow集加入该非终结符的follow集
                }
                else
                {
                    if (isNonterminal(right[k]))//如果后面是非终结符
                    {
                        flag = flag || AddToFollow(right[k], Follow[right[k]], Follow[c]);//将该非终结符的follow集加入后面非终结符的follow集
                    }
                    else//如果后面是终结符
                    {
                        Follow[c].Add(right[k]);//将该终结符加入该非终结符的follow集
                    }
                }
            }
        }
    }
}

}

public bool AddToFollow(char c, HashSet set, HashSet source) { int oldCount = set.Count; foreach (char ch in source) { set.Add(ch); } return oldCount != set.Count; }

其中，isNonterminal和isFinalsymbol为判断是否为非终结符和终结符的函数。