• 日期: 2028-10-30
  • 标签: 常规
//构造项目集
public void Creteitemsets()
{
    //初始化
    SLRitemsets I0 = new SLRitemsets();
    I0.Container.Add(0);//将拓广文法的产生式加入项目集
    proitemset.Add(I0);//将I0加入项目集合

    int i = 0;
    while (i < proitemset.Count)
    {
        SLRitemsets I = proitemset[i];
        //寻找I中所有项目的点后面的符号，将其加入集合C中
        List<char> C = new List<char>();
        for (int j = 0; j < I.Container.Count; j++)
        {
            int index = SLRobjNum[I.Container[j]].Right.IndexOf('.');
            if (index == SLRobjNum[I.Container[j]].Right.Length - 1)//如果点在产生式最后，跳过
                continue;
            char ch = SLRobjNum[I.Container[j]].Right[index + 1];
            if (!exist(C, ch))
                C.Add(ch);
        }

        //对于集合C中的每个符号，构造新的项目集I'
        for (int j = 0; j < C.Count; j++)
        {
            SLRitemsets I_new = new SLRitemsets();
            for (int k = 0; k < I.Container.Count; k++)
            {
                int index = SLRobjNum[I.Container[k]].Right.IndexOf('.');
                if (index == SLRobjNum[I.Container[k]].Right.Length - 1)//如果点在产生式最后，跳过
                    continue;
                char ch = SLRobjNum[I.Container[k]].Right[index + 1];
                if (ch == C[j])
                {
                    SLRNode Lobj = new SLRNode(SLRobjNum[I.Container[k]].Left, CreObj(SLRobjNum[I.Container[k]].Right, index + 1));
                    int num = isexist(I_new.Container);
                    if (num == -1)//如果I'不存在，加入
                    {
                        I_new.Container.Add(SLRobjNum.Count);
                        SLRobjNum.Add(Lobj);
                    }
                    else//如果I'已存在，加入
                    {
                        I_new.Container.Add(num);
                    }
                }
            }
            //如果I'不存在于项目集合中，加入
            int num1 = isexist(I_new.Container);
            if (num1 == -1)
            {
                proitemset.Add(I_new);
                num1 = proitemset.Count - 1;
            }
            //构造DFA
            dfa[Pindex] = new DFA(i, C[j], num1);
            Pindex++;
        }
        i++;
    }
}

//获取LR0分析表
public Table[][] GET_ANA()
{
    int i, j;
    //获取非终结符的Follow集
    follow = GetFollow(Nchar, Echar, SLRproNum, SLRobjNum);

    //构造分析表
    SLRAna = new Table[proitemset.Count][];
    for (i = 0; i < proitemset.Count; i++)
    {
        SLRAna[i] = new Table[Echar.Count + Nchar.Count];
        for (j = 0; j < Echar.Count; j++)
        {
            SLRAna[i][j] = new Table();
        }
        for (j = 0; j < Nchar.Count; j++)
        {
            SLRAna[i][j + Echar.Count] = new Table();
        }
    }

    //填充分析表
    for (i = 0; i < proitemset.Count; i++)
    {
        for (j = 0; j < proitemset[i].Container.Count; j++)
        {
            int index = SLRobjNum[proitemset[i].Container[j]].Right.IndexOf('.');
            if (index == SLRobjNum[proitemset[i].Container[j]].Right.Length - 1)//如果点在产生式最后
            {
                if (SLRobjNum[proitemset[i].Container[j]].Left == "S'")
                {//接受状态
                    SLRAna[i][Echar.Count - 1] = new Table('A', -1);
                }
                else
                {//归约状态
                    int pro_index = Find_pro(SLRobjNum[proitemset[i].Container[j]]);
                    HashSet<char> follow_set = follow[SLRobjNum[proitemset[i].Container[j]].Left[0]];
                    foreach (char c in follow_set)
                    {
                        int col = FindID(Echar, c);
                        SLRAna[i][col] = new Table('R', pro_index);
                    }
                }
            }
            else
            {
                char ch = SLRobjNum[proitemset[i].Container[j]].Right[index + 1];
                if (isFinalsymbol(ch))
                {//移进状态
                    int col = FindID(Echar, ch);
                    int to = dfa[i * (Echar.Count + Nchar.Count) + col].to;
                    SLRAna[i][col] = new Table('S', to);
                }
            }
        }
    }

    return SLRAna;
}

//构造分析表
public void SLRAnaly()
{
    GET_ANA();
    RStr_ANA += "\r\n分析表：\r\n";
    RStr_ANA += "  |";
    for (int i = 0; i < Echar.Count; i++)
    {
        RStr_ANA += "  " + Echar[i] + "  |";
    }
    for (int i = 0; i < Nchar.Count; i++)
    {
        RStr_ANA += "  " + Nchar[i] + "  |";
    }
    RStr_ANA += "\r\n";
    for (int i = 0; i < proitemset.Count; i++)
    {
        RStr_ANA += i.ToString().PadLeft(2) + "|";
        for (int j = 0; j < Echar.Count + Nchar.Count; j++)
        {
            if (SLRAna[i][j].error)
                RStr_ANA += "      |";
            else
            {
                RStr_ANA += "  ";
                RStr_ANA += SLRAna[i][j].type.ToString();
                RStr_ANA += SLRAna[i][j].id.ToString().PadLeft(2);
                RStr_ANA += "  |";
            }
        }
        RStr_ANA += "\r\n";
    }
}

//分析句子
public void sen_Analyze(string text)
{
    Jz = new Analyze();
    Jz.Input_str = text.Split(' ').ToList();
    Jz.Input_str.Add("#");
    Jz.stack_state.Add("0");
    Jz.stack_symbol.Add("#");
    int index = 0;
    while (true)
    {
        int state = int.Parse(Jz.stack_state.Last());
        string symbol = Jz.stack_symbol.Last();
        int col = FindID(Echar, symbol[0]);
        if (!SLRAna[state][col].error)
        {
            if (SLRAna[state][col].type == 'S')
            {
                Jz.stack_state.Add(SLRAna[state][col].id.ToString());
                Jz.stack_symbol.Add(symbol);
                index++;
                Jz.Tran_pro.Add("");
                Jz.Input_str.RemoveAt(0);
            }
            else if (SLRAna[state][col].type == 'R')
            {
                int pro_index = SLRAna[state][col].id;
                SLRNode pro = SLRproNum[pro_index];
                for (int i = 0; i < pro.Right.Length; i++)
                {
                    Jz.stack_state.RemoveAt(Jz.stack_state.Count - 1);
                    Jz.stack_symbol.RemoveAt(Jz.stack_symbol.Count - 1);
                }
                Jz.stack_symbol.Add(pro.Left);
                Jz.Tran_pro.Add(pro.Left + "->" + pro.Right);
                int newState = int.Parse(Jz.stack_state.Last());
                col = FindID(Nchar, pro.Left[0]);
                Jz.stack_state.Add(SLRAna[newState][col + Echar.Count].id.ToString());
            }
            else if (SLRAna[state][col].type == 'A')
            {
                Success = true;
                break;
            }
        }
        else
        {
            Success = false;
            break;
        }
    }
    if (Success)
        RStr += "\r\n分析成功！\r\n";
    else
        RStr += "\r\n分析失败！\r\n";
    RStr += "状态栈：\r\n";
    for (int i = 0; i < Jz.stack_state.Count; i++)
        RStr += Jz.stack_state[i] + " ";
    RStr += "\r\n符号栈：\r\n";
    for (int i = 0; i < Jz.stack_symbol.Count; i++)
        RStr += Jz.stack_symbol[i] + " ";
    RStr += "\r\n输入串：\r\n";
    for (int i = 0; i < Jz.Input_str.Count; i++)
        RStr += Jz.Input_str[i] + " ";
    RStr += "\r\n所用产生式：\r\n";
    for (int i = 0; i < Jz.Tran_pro.Count; i++)
        RStr += Jz.Tran_pro[i] + "\r\n";
}

代码说明

  • Creteitemsets() 函数： 用于构建项目集，并构造 DFA 图。
  • GET_ANA() 函数： 获取 LR0 分析表，包括移进、归约、接受状态的填充。
  • SLRAnaly() 函数： 构造 SLR 分析表，并以字符串形式输出。
  • sen_Analyze(string text) 函数： 分析句子，并记录分析过程（状态栈、符号栈、输入串、所用产生式）。

代码示例

// 定义文法
string grammar = "E->E+T|T\r\nT->T*F|F\r\nF->(E)|id";

// 实例化 SLR1 分析器
SLR slr = new SLR();

// 构建产生式列表
slr.Buildprod(grammar);

// 构造 SLR 分析表
slr.SLRAnaly();

// 分析句子
slr.sen_Analyze("id + id * id");

// 输出分析结果
Console.WriteLine(slr.RStr);

输出结果

分析成功！
状态栈：
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 
符号栈：
# id + id * id # 
输入串：
# 
所用产生式：
E->T
T->F
F->id
E->E+T
T->F
F->id
E->T
T->T*F
F->id
E->E+T

注意

  • 该代码实现了 SLR1 分析器，但未包含获取 Follow 集的代码，需要自行实现 GetFollow() 函数。
  • 代码中使用了 Dictionary<char, HashSet<char>> 来存储 Follow 集，可以根据实际需求进行修改。
  • 为了简化代码，代码中省略了部分错误处理，实际应用中需要进行更完善的错误处理。

总结

本文提供了一个 SLR1 分析器的完整代码实现，并通过代码示例展示了分析过程。通过学习本代码，可以帮助理解 SLR1 分析器的原理和实现细节。

SLR1 分析器代码实现：项目集构建、分析表构造与句子分析

原文地址: https://www.cveoy.top/t/topic/f0ND 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录