SLR1 分析表构造详解及代码实现

修改后的代码如下：

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

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

//分析表 结点 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);//终结符集合

Dictionary<char, HashSet> first = new Dictionary<char, HashSet>();//非终结符的First集 Dictionary<char, HashSet> follow = new Dictionary<char, HashSet>();//非终结符的Follow集

public string RStr = ""; public string RStr_obitemset = "";//输出返回 public string RStr_DFA = ""; public string RStr_ANA = "";

public Table[][] GET_ANA() { SLRAnaly(); RStr_ANA += "\r\nSLR1分析表:\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() { //计算First集和Follow集 ComputeFirst(); ComputeFollow();

//构造LR(0)项目集族
ConstructSLRItemsets();

//构造DFA
ConstructDFA();

//构造分析表
ConstructSLRTable();

}

//计算非终结符的First集 public void ComputeFirst() { //初始化First集 foreach (char c in Nchar) { first.Add(c, new HashSet()); }

//计算终结符的First集
foreach (char c in Echar)
{
    first.Add(c, new HashSet<char>() { c });
}

bool hasChanged = true;
while (hasChanged)
{
    hasChanged = false;
    //遍历所有产生式
    foreach (SLRNode node in SLRproNum)
    {
        int i = 0;
        bool canEmpty = true;
        while (i < node.Right.Length && canEmpty)
        {
            char symbol = node.Right[i];
            if (first[symbol].Contains('ε'))
            {
                //如果该符号可以推出空串，则继续计算下一个符号的First集
                i++;
            }
            else
            {
                //如果该符号不能推出空串，则将其First集加入当前符号的First集中，并停止计算
                int oldCount = first[node.Left].Count;
                first[node.Left].UnionWith(first[symbol]);
                if (first[node.Left].Count > oldCount)
                {
                    hasChanged = true;
                }
                canEmpty = false;
            }
        }
        if (canEmpty)
        {
            //如果产生式右侧所有符号都可以推出空串，则将空串加入当前符号的First集中
            int oldCount = first[node.Left].Count;
            first[node.Left].Add('ε');
            if (first[node.Left].Count > oldCount)
            {
                hasChanged = true;
            }
        }
    }
}

}

//计算非终结符的Follow集 public void ComputeFollow() { //初始化Follow集 foreach (char c in Nchar) { follow.Add(c, new HashSet()); }

//将#加入开始符号的Follow集中
follow[SLRproNum[0].Left].Add('#');

bool hasChanged = true;
while (hasChanged)
{
    hasChanged = false;
    //遍历所有产生式
    foreach (SLRNode node in SLRproNum)
    {
        for (int i = 0; i < node.Right.Length; i++)
        {
            char symbol = node.Right[i];
            if (Nchar.Contains(symbol))
            {
                //如果该符号是非终结符
                bool canEmpty = true;
                for (int j = i + 1; j < node.Right.Length && canEmpty; j++)
                {
                    char nextSymbol = node.Right[j];
                    if (first[nextSymbol].Contains('ε'))
                    {
                        //如果该符号之后的符号都可以推出空串，则将当前符号的Follow集加入之后符号的Follow集中
                        int oldCount = follow[symbol].Count;
                        follow[symbol].UnionWith(follow[node.Left]);
                        if (follow[symbol].Count > oldCount)
                        {
                            hasChanged = true;
                        }
                    }
                    else
                    {
                        //如果该符号之后的符号不能都推出空串，则将之后符号