SLR(1)分析器：从代码实现到原理详解

//获取非终结符的Follow集 public Dictionary<char, HashSet> GetFollow(List Nchar, List Echar, List SLRproNum, List SLRobjNum) { Dictionary<char, HashSet> follow = new Dictionary<char, HashSet>();//非终结符的Follow集 //初始化 for (int i = 0; i < Nchar.Count; i++) { HashSet set = new HashSet(); follow.Add(Nchar[i], set); } follow['S''].Add('#');

//计算非终结符的Follow集
bool flag = true;
while (flag)
{
    flag = false;
    for (int i = 0; i < SLRproNum.Count; i++)
    {
        string right = SLRproNum[i].Right;
        char left = SLRproNum[i].Left[0];
        for (int j = 0; j < right.Length; j++)
        {
            if (right[j] >= 'A' && right[j] <= 'Z')
            {
                if (j == right.Length - 1)
                {//情况1
                    if (follow[right[j]].Except(follow[left]).Count() > 0)
                    {
                        follow[left].UnionWith(follow[right[j]]);
                        flag = true;
                    }
                }
                else
                {
                    if (isFinalsymbol(right[j + 1]))
                    {//情况2
                        if (follow[right[j]].Add(right[j + 1]))n                            {
                            flag = true;
                        }
                    }
                    else
                    {//情况3
                        int k = j + 2;
                        bool exit = false;
                        while (k <= right.Length)
                        {
                            if (k == right.Length)
                            {
                                if (follow[right[j]].Except(follow[left]).Count() > 0)
                                {
                                    follow[left].UnionWith(follow[right[j]]);
                                    flag = true;
                                }
                                exit = true;
                                break;
                            }
                            if (isFinalsymbol(right[k]))
                            {
                                if (follow[right[j]].Add(right[k]))
                                {
                                    flag = true;
                                }
                                exit = true;
                                break;
                            }
                            k++;
                        }
                        if (!exit)
                        {
                            if (follow[right[j]].Except(follow[left]).Count() > 0)
                            {
                                follow[left].UnionWith(follow[right[j]]);
                                flag = true;
                            }
                        }
                    }
                }
            }
        }
    }
}

return follow;

}

//分析句子 public void sen_Analyze(string text) { Jz = new Analyze();//分析句子 char ch; Jz.stack_symbol.Add('#'); Jz.stack_state.Add('0'); Jz.Input_str = new List(text.Length + 1); for (int i = 0; i < text.Length; i++) { Jz.Input_str.Add(text[i].ToString()); } Jz.Input_str.Add('#'); int ip = 0;//输入串指针 int top = 0;//栈顶指针 ch = Jz.Input_str[ip][0]; int symbol_id = FindID(Echar, ch);//符号在终结符表中的位置 int state_id; string temp = ''; bool analyze_success = false;

while (!analyze_success)
{
    state_id = Convert.ToInt32(Jz.stack_state[top]);//栈顶状态
    if (SLRAna[state_id][symbol_id].type == 'S')//移进
    {
        Jz.stack_state.Add(SLRAna[state_id][symbol_id].id.ToString());
        Jz.stack_symbol.Add(ch.ToString());
        ip++;
        ch = Jz.Input_str[ip][0];
        symbol_id = FindID(Echar, ch);
        top++;
        Jz.Tran_pro.Add(' ');
    }
    else if (SLRAna[state_id][symbol_id].type == 'R')//归约
    {
        int num = SLRproNum[SLRAna[state_id][symbol_id].id].Right.Length;//产生式右部长度
        //弹出栈顶的num个符号
        for (int i = 0; i < num; i++)
        {
            Jz.stack_state.RemoveAt(Jz.stack_state.Count - 1);
            Jz.stack_symbol.RemoveAt(Jz.stack_symbol.Count - 1);
            top--;
        }
        //将产生式左部符号压入符号栈
        Jz.stack_symbol.Add(SLRproNum[SLRAna[state_id][symbol_id].id].Left);
        //将GOTO表中对应状态压入状态栈
        state_id = Convert.ToInt32(Jz.stack_state[top]);
        symbol_id = FindID(Nchar, SLRproNum[SLRAna[state_id][symbol_id].id].Left[0]) + Echar.Count;
        Jz.stack_state.Add(SLRAna[state_id][symbol_id].id.ToString());
        top++;
        Jz.Tran_pro.Add(SLRproNum[SLRAna[state_id][symbol_id].id].Left + '→' + SLRproNum[SLRAna[state_id][symbol_id].id].Right);
    }
    else if (SLRAna[state_id][symbol_id].type == 'A')//接受
    {
        Success = true;
        analyze_success = true;
        Jz.Tran_pro.Add('acc');
    }
    else//出错
    {
        Success = false;
        analyze_success = true;
        Jz.Tran_pro.Add('error');
    }
}

}