SLR 分析表构建 - C# 代码示例

public class SLR
{
    //产生式结点类
    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<int> Container
            = new List<int>(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 Table[][] SLRAna;//分析表
  
public void SLRAnaly()
    {
        //获取LR(0)的项目集族
        List<ItemSet> LR0ItemSets = isLR_0.getLR0().getItemSets();
        //获取终结符和非终结符集合
        List<string> terminals = isLR_0.getLR0().terminals;
        List<string> nonterminals = isLR_0.getLR0().nonterminal;
        //初始化分析表
        SLRAna = new Table[LR0ItemSets.Count][];
        for (int i = 0; i < LR0ItemSets.Count; i++)
        {
            SLRAna[i] = new Table[terminals.Count + nonterminals.Count];
            for (int j = 0; j < terminals.Count + nonterminals.Count; j++)
            {
                SLRAna[i][j] = new Table();
            }
        }
        //构造DFA
        int dfaCount = 0;
        for (int i = 0; i < LR0ItemSets.Count; i++)
        {
            ItemSet itemSet = LR0ItemSets[i];
            for (int j = 0; j < terminals.Count; j++)
            {
                string terminal = terminals[j];
                ItemSet nextItemSet = isLR_0.getLR0().go(itemSet, terminal);
                if (nextItemSet != null)
                {
                    int nextIndex = LR0ItemSets.IndexOf(nextItemSet);
                    if (nextIndex == -1)
                    {
                        nextIndex = LR0ItemSets.Count;
                        LR0ItemSets.Add(nextItemSet);
                    }
                    dfa[dfaCount++] = new DFA(i, terminal[0], nextIndex);
                }
            }
            for (int j = 0; j < nonterminals.Count; j++)
            {
                string nonterminal = nonterminals[j];
                ItemSet nextItemSet = isLR_0.getLR0().go(itemSet, nonterminal);
                if (nextItemSet != null)
                {
                    int nextIndex = LR0ItemSets.IndexOf(nextItemSet);
                    if (nextIndex == -1)
                    {
                        nextIndex = LR0ItemSets.Count;
                        LR0ItemSets.Add(nextItemSet);
                    }
                    dfa[dfaCount++] = new DFA(i, nonterminal[0], nextIndex);
                }
            }
        }
        //构造分析表
        for (int i = 0; i < LR0ItemSets.Count; i++)
        {
            ItemSet itemSet = LR0ItemSets[i];
            foreach (Item item in itemSet.items)
            {
                //对于每个规约项
                if (item.dotIndex == item.RHS.Count)
                {
                    if (item.LHS.Equals(isLR_0.getLR0().production.Keys.First() + '''))
                    {
                        //如果是S'->S#，则在#处填入acc
                        SLRAna[i][terminals.IndexOf('#')] = new Table('a', 0);
                    }
                    else
                    {
                        //否则在FOLLOW集中的终结符处填入规约项编号
                        foreach (string s in isLR_0.isLL_1_.follow.getfollows()[item.LHS])
                        {
                            SLRAna[i][terminals.IndexOf(s)] = new Table('r', getproconut(item));
                        }
                    }
                }
            }
            foreach (int j in itemSet.shiftItems)
            {
                //对于每个移进项
                Item item = itemSet.items[j];
                string symbol = item.RHS[item.dotIndex];
                int nextIndex = dfa[i * (terminals.Count + nonterminals.Count) + terminals.IndexOf(symbol)].to;
                if (terminals.Contains(symbol))
                {
                    //如果是终结符，则在对应位置填入S+状态编号
                    SLRAna[i][terminals.IndexOf(symbol)] = new Table('s', nextIndex);
                }
                else
                {
                    //如果是非终结符，则在对应位置填入状态编号
                    SLRAna[i][terminals.Count + nonterminals.IndexOf(symbol)] = new Table('g', nextIndex);
                }
            }
        }
    }
}