SLR文法分析表构造：SLRAnaly()函数实现及相关函数解析

本文将介绍SLR文法分析表构造的实现方法，包括SLRAnaly()函数的具体代码，以及GetFollow()和GetFirst()等相关函数的解析。了解如何使用follow集解决移进-归约冲突和归约-归约冲突，并构建SLR分析表。

SLRAnaly() 构造函数

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

    LRAna = new Table[proitemset.Count][];
    for (int i = 0; i < proitemset.Count; i++)
        LRAna[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状态 
            LRAna[i][j] = tnode;

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

    for (int i = 0; i < Gy_itemset.Count; i++)//归约项目
    {
        int proNum = Find_pro(LRobjNum[proitemset[Gy_itemset[i]].Container[0]]);//找到原产生式序号
        List<int> follow = GetFollow(SLRproNum[proNum]);//获取该产生式左侧非终结符的follow集合
        for (int j = 0; j < follow.Count; j++)
        {
            int CID = FindID(Echar, follow[j]);
            LRAna[Gy_itemset[i]][CID] = new Table('r', proNum);//添加状态r
        }
    }
    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[dfa[i].to]);//获取该非终结符的follow集合
            for (int j = 0; j < follow.Count; j++)
            {
                int EID = FindID(Echar, follow[j]);
                LRAna[dfa[i].from][EID + Echar.Count] = new Table('N', dfa[i].to);//添加状态N
            }
        }
        else //不是归约项目 添加状态S
        {
            int CID = FindID(Echar, dfa[i].symbol);
            LRAna[dfa[i].from][CID] = new Table('S', dfa[i].to);//添加状态S
        }

    }
}

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;
    }
}

其他相关函数

FindID()： 用于根据符号查找其在终结符集合或非终结符集合中的序号。
isFinalsymbol()： 用于判断符号是否是终结符。
Find_pro()： 用于根据产生式左侧和右侧查找该产生式在产生式列表中的序号。
Union()： 用于合并两个列表，去除重复元素。

使用follow集进行冲突判断和解析

在SLRAnaly()函数中，我们使用follow集来判断和解析冲突。

移进-归约冲突： 当一个项目集同时包含移进项目和归约项目时，我们需要判断该项目集的follow集是否包含该移进项目的符号。如果包含，则说明存在移进-归约冲突。对于冲突的解析，我们选择归约操作，将该项目集对应的条目设置为归约状态。
归约-归约冲突： 当一个项目集同时包含多个归约项目时，我们需要判断每个归约项目的follow集是否包含该项目集的符号。如果包含，则说明存在归约-归约冲突。对于冲突的解析，我们可以选择优先级较高的产生式或根据其他规则进行选择。

通过使用follow集来判断和解析冲突，我们能够构建出SLR分析表，从而实现SLR文法的分析。