SLR(1)语法分析表构造算法实现(C#)

SLR(1)是一种自底向上的语法分析方法，用于判断输入串是否符合给定的语法规则。SLR(1)分析表是SLR(1)分析器的核心，它定义了分析器在不同状态下遇到不同输入符号时应该采取的动作。

以下是使用C#语言实现SLR(1)语法分析表构造算法的示例代码：

public void SLRAnaly()
{
    SLRAna = new Table[proitemset.Count][];
    for (int i = 0; i < proitemset.Count; i++)
    {
        SLRAna[i] = new Table[Echar.Count + Nchar.Count];
        for (int j = 0; j < Echar.Count + Nchar.Count; j++)
        {
            SLRAna[i][j] = new Table();
        }
    }

    // 遍历每个状态
    for (int i = 0; i < proitemset.Count; i++)
    {
        // 遍历每个终结符
        for (int j = 0; j < Echar.Count; j++)
        {
            bool flag = false;
            int index = -1;
            // 遍历移进项
            for (int k = 0; k < proitemset[i].Container.Count; k++)
            {
                int itemIndex = proitemset[i].Container[k];
                if (SLRobjNum[itemIndex].Right.Contains('.') && SLRobjNum[itemIndex].Right.IndexOf('.') < SLRobjNum[itemIndex].Right.Length - 1 && SLRobjNum[itemIndex].Right[SLRobjNum[itemIndex].Right.IndexOf('.') + 1] == Echar[j])
                {
                    flag = true;
                    index = k;
                    break;
                }
            }
            if (flag)
            {
                SLRAna[i][j] = new Table('S', proitemset[Move(proitemset[i], Echar[j])].Container[index + 1]);
            }
            else
            {
                SLRAna[i][j] = new Table();
            }
        }

        // 遍历每个非终结符
        for (int j = 0; j < Nchar.Count; j++)
        {
            int index = -1;
            // 遍历移进项
            for (int k = 0; k < proitemset[i].Container.Count; k++)
            {
                int itemIndex = proitemset[i].Container[k];
                if (SLRobjNum[itemIndex].Right.Contains('.') && SLRobjNum[itemIndex].Right.IndexOf('.') < SLRobjNum[itemIndex].Right.Length - 1 && SLRobjNum[itemIndex].Right[SLRobjNum[itemIndex].Right.IndexOf('.') + 1] == Nchar[j])
                {
                    index = k;
                    break;
                }
            }
            if (index != -1)
            {
                // 修改后的代码行
                SLRAna[i][Echar.Count + j] = new Table('S', proitemset[Move(proitemset[i], Nchar[j])][index + 1]);
            }
            else
            {
                SLRAna[i][Echar.Count + j] = new Table();
            }
        }

        // 遍历归约项
        for (int j = 0; j < Gy_obj.Count; j++)
        {
            int itemIndex = Gy_obj[j];
            if (proitemset[i].Container.Contains(itemIndex))
            {
                foreach (char c in Follow(SLRobjNum[itemIndex].Left))
                {
                    if (SLRAna[i][GetIndex(c)].error)
                    {
                        SLRAna[i][GetIndex(c)] = new Table('r', itemIndex);
                    }
                    else
                    {
                        Console.WriteLine('Conflict: state ' + i + ' ' + c + ' ' + SLRAna[i][GetIndex(c)].type + SLRAna[i][GetIndex(c)].id + ' r' + itemIndex);
                    }
                }
            }
        }
    }

    // 处理接受状态
    int acceptState = -1;
    for (int i = 0; i < proitemset.Count; i++)
    {
        if (proitemset[i].Container.Contains(0))
        {
            acceptState = i;
            break;
        }
    }
    SLRAna[acceptState][GetIndex('#')] = new Table('A', 0);
}

// 获取符号在分析表中的索引
private int GetIndex(char c)
{
    if (isFinalsymbol(c))
    {
        return Echar.IndexOf(c);
    }
    else
    {
        return Echar.Count + Nchar.IndexOf(c);
    }
}

// 求FOLLOW集
private List<char> Follow(string symbol)
{
    List<char> followSet = new List<char>();
    if (symbol == 'S')
    {
        followSet.Add('#');
    }
    foreach (SLRNode node in SLRproNum)
    {
        int index = node.Right.IndexOf(symbol);
        if (index != -1 && index < node.Right.Length - 1)
        {
            List<char> firstSet = First(node.Right.Substring(index + 1));
            if (firstSet.Contains('#'))
            {
                followSet.AddRange(Follow(node.Left));
                followSet.Remove('#');
            }
            followSet.AddRange(firstSet);
        }
    }
    return followSet;
}

// 求FIRST集
private List<char> First(string str)
{
    List<char> firstSet = new List<char>();
    if (str == '#')
    {
        firstSet.Add('#');
        return firstSet;
    }
    if (isFinalsymbol(str[0]))
    {
        firstSet.Add(str[0]);
        return firstSet;
    }
    foreach (SLRNode node in SLRproNum)
    {
        if (node.Left == str[0].ToString())
        {
            List<char> tempSet = First(node.Right);
            firstSet.AddRange(tempSet);
            if (tempSet.Contains('#'))
            {
                firstSet.Remove('#');
                firstSet.AddRange(First(str.Substring(1)));
            }
            return firstSet;
        }
    }
    return firstSet;
}

private List<int> Move(SLRitemsets itemset, char symbol)
{
    List<int> moveSet = new List<int>();
    foreach (int index in itemset.Container)
    {
        int dotIndex = SLRobjNum[index].Right.IndexOf('.');
        if (dotIndex != -1 && dotIndex < SLRobjNum[index].Right.Length - 1 && SLRobjNum[index].Right[dotIndex + 1] == symbol)
        {
            moveSet.Add(index + 1);
        }
    }
    return Closure(moveSet);
}

代码解释：

SLRAna 是一个二维数组，用于存储SLR(1)分析表。
proitemset 是一个包含所有项目集的列表。
Echar 是一个包含所有终结符的列表。
Nchar 是一个包含所有非终结符的列表。
SLRobjNum 是一个包含所有产生式的列表。
Gy_obj 是一个包含所有归约项的列表。
Move() 函数用于计算项目集在遇到某个符号时的转移。
Closure() 函数用于计算项目的闭包。
First() 函数用于计算符号串的FIRST集。
Follow() 函数用于计算符号的FOLLOW集。

错误修正：

在原始代码中，语句 SLRAna[i][Echar.Count + j] = new Table('S', proitemset[Move(proitemset[i], Nchar[j])].Container[index + 1]); 存在错误。因为 Move() 函数返回的是一个 List<int> 类型，而代码中却试图将其作为索引使用。

正确代码：

SLRAna[i][Echar.Count + j] = new Table('S', proitemset[Move(proitemset[i], Nchar[j])][index + 1]);

该代码使用索引 [index + 1] 访问 Move() 函数返回的列表中的元素，从而解决了该错误。

希望以上信息对您有所帮助。