SLR 分析表构造原理及代码实现

SLR 分析表是一种用于实现自底向上语法分析的表格驱动方法。该方法基于 LR(0) 文法，并通过判断文法是否为 SLR 文法来确保分析表的正确性。本文将详细介绍 SLR 分析表构造原理，并提供 C# 代码实现示例。

代码分析

class SLR_fourpro
{
    public int is_SLR = -1;
    public isLR_0_ islR0;
    SLR SLR;

    public SLR_fourpro(string text)
    {
        this.islR0 = new isLR_0_(text);
        if (islR0.is_LR != -2)
        {
            this.is_SLR = islR0.is_LR;
            return;
        }
        SLR = new SLR(islR0);
        is_SLR = SLR.judgeSLR() ? 1 : -2;
        if (is_SLR == 1)
        {
            SLR.buildtable();
        }
    }

    public SLR getSLR()
    {
        return SLR;
    }
}

class SLR
{
    isLR_0_ isLR_0;
    public List<string> terminals; // 终结符集合
    public List<string> nonterminal;// 非终结符集合
    public Dictionary<string, List<string>> production;//继承LL1中的原始产生式
    public Dictionary<string, List<List<string>>> productions; // 产生式规则（包含全部规则）

    public Dictionary<int, HashSet<string>> transitions; // 状态转移函数
    public Dictionary<ItemSet, int> stateNumbers; // 状态编号
    public Dictionary<int, ItemSet> states; // 状态集合
    public Dictionary<int, List<string>> table;

    public SLR(isLR_0_ isLR_0_)
    {
        isLR_0 = isLR_0_;
        terminals = isLR_0.getLR0().terminals;
        nonterminal = isLR_0.getLR0().nonterminal;
        productions = isLR_0.getLR0().productions;
        production = isLR_0.getLR0().production;
        transitions = isLR_0.getLR0().transitions;
        stateNumbers = isLR_0.getLR0().stateNumbers;
        states = isLR_0.getLR0().states;
    }

    public bool judgeSLR()
    {
        isLL_1_ isLL_1_ = isLR_0.isLL_1_;
        List<List<string>> back;
        List<string> put;

        foreach (var item in stateNumbers.Keys)
        {
            back = new List<List<string>>();
            put = new List<string>();
            foreach (var pro in item.items)
            {
                if (pro.dotIndex == pro.RHS.Count)
                {
                    if (!pro.LHS.Equals(productions.Keys.First() + '''))
                        back.Add(isLL_1_.follow.getfollows()[pro.LHS]);
                }
                else if (terminals.Contains(pro.RHS[pro.dotIndex])) put.Add(pro.RHS[pro.dotIndex]);
            }
            //看移进归约冲突能否解决
            if (back.Count > 0 && put.Count > 0)
            {
                //遍历每个归约项FOLLOW集
                foreach (var item1 in back)
                {
                    //遍历每个移进项FIRST集
                    foreach (var item2 in put)
                    {
                        if (item1.Contains(item2)) return false;
                    }
                }
            }
            //看归约归约冲突能否解决
            if (back.Count >= 2)
            {
                for (int i = 0; i < back.Count - 1; i++)
                {
                    //对之后的FOLLOW集进行查询
                    for (int j = i + 1; j < back.Count; j++)
                    {
                        //看当前FOLLOW与之后FOLLW集是否有交集
                        foreach (var item3 in back[i])
                            if (back[j].Contains(item3)) return false;
                    }
                }
            }
        }
        return true;
    }

    private int getproconut(Item item)
    {
        //获取对应的产生式编号
        int index = 1;
        if (item.dotIndex == item.RHS.Count)
        {
            foreach (var key in productions.Keys)
            {
                if (key.Equals(item.LHS))
                {
                    //查找当前左部中符合item的产生式
                    foreach (var item2 in productions[key])
                    {
                        if (item.RHS.Equals(item2)) return index;
                        else index++;
                    }
                }
                index += productions[key].Count;
            }
            return index;
        }
        return -1;
    }

    public void buildtable()
    {
        isLL_1_ isLL_1_ = isLR_0.isLL_1_;
        int flag = 0;
        table = new Dictionary<int, List<string>>();

        for (int i = 0; i < states.Count; i++)
        {
            //对每个状态经过终结符的情况进行判断
            List<string> strings = new List<string>();
            foreach (var symbol in terminals)
            {
                flag = 0;
                //包含移进项的
                if (transitions.ContainsKey(i))
                {
                    foreach (var item in transitions[i])
                    {
                        if (item[0].ToString().Equals(symbol))
                        {
                            strings.Add('S' + item.Substring(1));
                            flag = 1;
                            break;
                        }
                    }
                    foreach (var item in states[i].items)
                    {
                        if (item.dotIndex == item.RHS.Count && !item.LHS.Equals(production.Keys.First() + '''))
                        {
                            if (isLL_1_.follow.getfollows()[item.LHS].Contains(symbol))
                            {
                                flag = 1;
                                int index = getproconut(item);
                                strings.Add("r" + index);
                                break;
                            }
                        }
                    }
                    if (flag == 0)
                    {
                        if (states[i].items.First().LHS.Equals(production.Keys.First() + ''') && i != 0)
                        {
                            if (symbol.Equals("#")) strings.Add("acc");
                            else strings.Add("");
                        }
                        else strings.Add("");
                    }
                }
                //只有归约项的
                else
                {
                    if (states[i].items.First().LHS.Equals(production.Keys.First() + '''))
                    {
                        if (symbol.Equals("#")) strings.Add("acc");
                        else strings.Add("");
                    }
                    else
                    {
                        flag = 0;
                        foreach (var item in states[i].items)
                        {
                            //如果该终结集在FOLLOW集中则加入分析表
                            if (isLL_1_.follow.getfollows()[item.LHS].Contains(symbol) || symbol.Equals('#'))
                            {
                                flag = 1;
                                int index = getproconut(item);
                                strings.Add("r" + index);
                                break;
                            }
                        }
                        if (flag == 0) strings.Add("");
                    }
                }
            }
            //对每个状态经过非终结符的情况进行判断
            foreach (var t in nonterminal)
            {
                flag = 0;
                if (transitions.ContainsKey(i))
                {
                    foreach (var item in transitions[i])
                    {
                        if (item[0].ToString().Equals(t))
                        {
                            strings.Add(item.Substring(1));
                            flag = 1;
                            break;
                        }
                    }
                    if (flag == 0) strings.Add("");
                }
                else strings.Add("");
            }
            table.Add(i, strings);
        }
    }
}

SLR 分析表构造步骤

判断文法是否为 SLR 文法
- 使用 judgeSLR() 方法判断文法是否为 SLR 文法。
- 该方法遍历每个状态，对于每个状态中的每个归约项和移进项，分别判断是否存在移进-归约冲突或者归约-归约冲突。
- 如果存在冲突，则该文法不是 SLR 文法。
构建状态转移函数
- 状态转移函数由 isLR_0_ 类构建，该类使用 LR(0) 分析算法构建状态机。
- 状态转移函数是一个字典，键为状态编号，值为一个集合，包含该状态下所有可能的转移项。
生成 SLR 分析表
- 使用 buildtable() 方法生成 SLR 分析表。
- 该方法遍历每个状态，对于每个状态中的每个终结符和非终结符，分别判断是否存在移进项或者归约项。
- 如果存在移进项，则在对应的分析表项中填入 S 加上状态编号；如果存在归约项，则填入 r 加上产生式编号。
- 最终得到的分析表是一个二维字典，其中第一维表示状态编号，第二维表示终结符和非终结符。

代码解读

SLR_fourpro 类用于判断输入文法是否为 SLR 文法，并调用 SLR 类进行分析表构造。
SLR 类是 SLR 分析表的核心类，负责判断 SLR 文法、构建状态转移函数、生成分析表。
judgeSLR() 方法用于判断文法是否为 SLR 文法。
buildtable() 方法用于构建 SLR 分析表。
getproconut() 方法用于获取产生式编号。

总结

本文介绍了 SLR 分析表构造原理，并提供了 C# 代码实现示例。通过代码分析，您可以深入理解 SLR 分析表构造过程，包括判断 SLR 文法、构建状态转移函数、生成分析表等关键步骤。SLR 分析表是自底向上语法分析的一种重要方法，在编译器设计和程序语言解析中具有广泛应用。