SLR 文法分析表构造实现

本文介绍了如何使用 follow 集来构造 SLR 文法分析表，并详细阐述了 SLRAnaly()、getfollow()、getfirst() 及其相关函数的实现过程。

SLRAnaly() 函数修改

原 LRAnaly() 函数中，分析表构建依赖于 DFA 结点和 LR(0) 规范族中的项目集。为了构造 SLR 分析表，我们需要根据 follow 集进行判断，解决移进-归约冲突和归约-归约冲突。

以下是 SLRAnaly() 函数的修改代码：

public void SLRAnaly()
{
    Table tnode = new Table();

    SLRAna = new Table[proitemset.Count][];
    for (int i = 0; i < proitemset.Count; i++)
        SLRAna[i] = new Table[Echar.Count + Nchar.Count];

    for (int i = 0; i < proitemset.Count; i++)//初始化 赋予ERROR属性
        for (int j = 0; j < Echar.Count + Nchar.Count; j++)//为终结符加r状态 
            SLRAna[i][j] = tnode;

    tnode = new Table('A', 0);
    SLRAna[1][FindID(Echar, '#')] = tnode;//项目集1必定是接受项目   构建[1][#]:acc的情况 先直接赋值好 dfa里没有

    for (int i = 0; i < Gy_itemset.Count; i++)//归约项目 
    {
        List<int> follow = GetFollow(SLRproNum[SLRobjNum[proitemset[Gy_itemset[i]].Container[0]].Left]);//获取该项的follow集合
        for (int j = 0; j < follow.Count; j++)
        {
            tnode = new Table('r', Find_pro(LRobjNum[proitemset[Gy_itemset[i]].Container[0]]));//找到原产生式序号 添加状态r
            SLRAna[Gy_itemset[i]][FindID(Echar, follow[j])] = tnode;
        }
    }
    for (int i = 0; i < Pindex; i++)
    {
        if (isFinalsymbol(dfa[i].symbol))//symbol为非终结符  添加状态N
        {
            int CID = FindID(Nchar, dfa[i].symbol);
            List<int> follow = GetFollow(SLRproNum[SLRobjNum[proitemset[dfa[i].from]].Left]);//获取该项的follow集合
            for (int j = 0; j < follow.Count; j++)
            {
                tnode = new Table('N', dfa[i].to);
                SLRAna[dfa[i].from][FindID(Echar, follow[j]) + Echar.Count] = tnode;
            }
        }
        else //不是归约项目 添加状态S
        {
            int CID = FindID(Echar, dfa[i].symbol);
            tnode = new Table('S', dfa[i].to);
            SLRAna[dfa[i].from][CID] = tnode;
        }
    }
}

getfollow() 函数实现

public List<int> GetFollow(SLRNode node)
{
    List<int> follow = new List<int>();
    if (node.Left == "S'" )
        follow.Add('#');
    for (int i = 0; i < SLRproNum.Count; i++)
    {
        for (int j = 0; j < SLRproNum[i].Right.Length; j++)
        {
            if (SLRproNum[i].Right[j] == node.Left[0])//找到该非终结符的产生式
            {
                if (j == SLRproNum[i].Right.Length - 1)//如果该非终结符在产生式末尾
                {
                    if (SLRproNum[i].Left != node.Left)//如果该产生式左侧非终结符不是当前非终结符
                        follow = Union(follow, GetFollow(SLRproNum[i]));//递归调用获取左侧非终结符的follow集合
                }
                else
                {
                    List<int> first = GetFirst(SLRproNum[i].Right.Substring(j + 1));//获取该非终结符后面的符号串的first集合
                    if (first.Contains(-1))//如果该符号串可以推导为空
                    {
                        first.Remove(-1);//将-1去掉
                        if (SLRproNum[i].Left != node.Left)//如果该产生式左侧非终结符不是当前非终结符
                            follow = Union(follow, Union(first, GetFollow(SLRproNum[i])));//递归调用获取左侧非终结符的follow集合，并将first集合加入
                        else//如果该产生式左侧非终结符是当前非终结符
                            follow = Union(follow, first);//将first集合加入
                    }
                    else//如果该符号串不能推导为空
                    {
                        follow = Union(follow, first);//将first集合加入
                    }
                }
            }
        }
    }
    return follow;
}

getfirst() 函数实现

public List<int> GetFirst(string str)
{
    List<int> first = new List<int>();
    if (str.Length == 0)//如果符号串为空
    {
        first.Add(-1);//将-1加入
        return first;
    }
    else if (isFinalsymbol(str[0]))//如果符号串的第一个符号是终结符
    {
        first.Add(str[0]);//将该终结符加入
        return first;
    }
    else//如果符号串的第一个符号是非终结符
    {
        for (int i = 0; i < SLRproNum.Count; i++)
        {
            if (SLRproNum[i].Left == str[0].ToString())//找到该非终结符的产生式
            {
                List<int> subfirst = GetFirst(SLRproNum[i].Right);//递归调用获取产生式右侧符号串的first集合
                if (subfirst.Contains(-1))//如果该符号串可以推导为空
                {
                    subfirst.Remove(-1);//将-1去掉
                    first = Union(first, subfirst);//将first集合加入
                    if (str.Length > 1)//如果符号串长度大于1
                    {
                        List<int> subfirst2 = GetFirst(str.Substring(1));//递归调用获取除第一个符号外的符号串的first集合
                        first = Union(first, subfirst2);//将第二个符号串的first集合加入
                    }
                }
                else//如果该符号串不能推导为空
                {
                    first = Union(first, subfirst);//将first集合加入
                }
            }
        }
        return first;
    }
}

Union() 函数实现

public List<int> Union(List<int> list1, List<int> list2)
{
    List<int> result = new List<int>();
    for (int i = 0; i < list1.Count; i++)
    {
        if (!result.Contains(list1[i]))
            result.Add(list1[i]);
    }
    for (int i = 0; i < list2.Count; i++)
    {
        if (!result.Contains(list2[i]))
            result.Add(list2[i]);
    }
    return result;
}

调用步骤

调用 SLRAnaly() 函数，构造 SLR 分析表。
使用构造好的 SLR 分析表进行语法分析。

总结

通过以上代码实现，我们可以使用 follow 集来构造 SLR 文法分析表，解决移进-归约冲突和归约-归约冲突，从而实现 SLR 分析。

注意： 以上代码示例中，Find_pro()、FindID()、isFinalsymbol() 等函数的具体实现需要根据实际情况进行调整。