SLR1 文法分析器构造中 ComputeFirst() 和 ComputeFollow() 函数的错误分析与修正

SLR1 文法分析器构造中 ComputeFirst() 和 ComputeFollow() 函数的错误分析与修正

本文将分析 SLR1 文法分析器构造中 ComputeFirst() 和 ComputeFollow() 函数存在的错误，并提供改正后的代码。

错误分析与修正

ComputeFirst() 函数的错误:

1. 非终结符的 First 集初始化: 对于每个非终结符，其 First 集应该初始化为一个包含空集 ('ε') 的 HashSet。
2. 空集推导: 当一个产生式右部的所有符号都能推出空集时，应该将空集加入该产生式左部符号的 First 集中。

改正后的 ComputeFirst() 函数代码如下:

public void ComputeFirst()
{
    // 初始化 First 集
    foreach (char c in Nchar)
    {
        first.Add(c, new HashSet<char>() { 'ε' });
    }
    foreach (char c in Echar)
    {
        first.Add(c, new HashSet<char>() { c });
    }
    // 计算 First 集
    bool flag = true;
    while (flag)
    {
        flag = false;
        foreach (SLRNode node in SLRproNum)
        {
            HashSet<char> temp = new HashSet<char>();
            bool canEpsilon = true;
            foreach (char c in node.Right)
            {
                if (Echar.Contains(c))
                {
                    temp.UnionWith(first[c]);
                    if (!first[c].Contains('ε'))
                    {
                        canEpsilon = false;
                        break;
                    }
                }
                else
                {
                    canEpsilon = false;
                    temp.UnionWith(first[c]);
                    break;
                }
            }
            if (canEpsilon)
            {
                temp.Add('ε');
            }
            if (!temp.SetEquals(first[node.Left]))
            {
                first[node.Left].UnionWith(temp);
                flag = true;
            }
        }
    }
}

ComputeFollow() 函数的错误:

1. 非终结符的 Follow 集初始化: 对于每个非终结符，其 Follow 集应该初始化为一个包含空集 ('ε') 的 HashSet。
2. 最后一个符号的 Follow 集: 当一个产生式右部的最后一个符号为非终结符时，应该将该非终结符的 Follow 集加入该产生式右部最后一个符号的 Follow 集中。

改正后的 ComputeFollow() 函数代码如下:

public void ComputeFollow()
{
    // 初始化 Follow 集
    foreach (char c in Nchar)
    {
        follow.Add(c, new HashSet<char>() { 'ε' });
    }
    follow[SLRproNum[0].Left].Add('#');
    // 计算 Follow 集
    bool flag = true;
    while (flag)
    {
        flag = false;
        foreach (SLRNode node in SLRproNum)
        {
            for (int i = 0; i < node.Right.Length; i++)
            {
                if (Nchar.Contains(node.Right[i]))
                {
                    HashSet<char> temp = new HashSet<char>();
                    bool canEpsilon = true;
                    for (int j = i + 1; j < node.Right.Length; j++)
                    {
                        if (Echar.Contains(node.Right[j]))
                        {
                            temp.UnionWith(first[node.Right[j]]);
                            if (!first[node.Right[j]].Contains('ε'))
                            {
                                canEpsilon = false;
                                break;
                            }
                        }
                        else
                        {
                            canEpsilon = false;
                            temp.UnionWith(first[node.Right[j]]);
                            break;
                        }
                    }
                    if (canEpsilon)
                    {
                        temp.UnionWith(follow[node.Left]);
                    }
                    if (!temp.SetEquals(follow[node.Right[i]]))
                    {
                        follow[node.Right[i]].UnionWith(temp);
                        flag = true;
                    }
                }
            }
            if (node.Right.EndsWith(Nchar.ToString()))
            {
                if (!follow[node.Left].SetEquals(follow[node.Right[node.Right.Length - 1]]))
                {
                    follow[node.Right[node.Right.Length - 1]].UnionWith(follow[node.Left]);
                    flag = true;
                }
            }
        }
    }
}

总结

通过以上分析，我们修正了 ComputeFirst() 和 ComputeFollow() 函数中的错误，确保了 SLR1 分析器能够正确计算 First 集和 Follow 集，进而构建正确的 SLR1 分析表。

希望本文能帮助读者更好地理解 SLR1 分析器的核心算法，以及如何进行错误调试。