SLR(1)分析器GetFollow()函数代码实现

// 获取非终结符的Follow集
public void GetFollow()
{
    // 初始化Follow集
    foreach (char c in Nchar)
    {
        follow[c] = new HashSet<char>();
    }
    // 将#加入开始符号S'的Follow集
    follow['S\''].Add('#');
    // 迭代计算Follow集
    bool changed = true;
    while (changed)
    {
        changed = false;
        foreach (SLRNode node in SLRproNum)
        {
            string right = node.Right;
            for (int i = 0; i < right.Length; i++)
            {
                char c = right[i];
                if (isFinalsymbol(c))
                {
                    continue;
                }
                // 如果当前符号是非终结符
                HashSet<char> set = follow[c];
                // 如果当前符号是最后一个符号或者下一个符号是终结符
                if (i == right.Length - 1 || isFinalsymbol(right[i + 1]))
                {
                    // 将该产生式左侧符号的Follow集加入当前符号的Follow集
                    HashSet<char> followLeft = follow[node.Left[0]];
                    int oldCount = set.Count;
                    set.UnionWith(followLeft);
                    if (set.Count != oldCount)
                    {
                        changed = true;
                    }
                }
                else
                {
                    // 如果下一个符号是非终结符
                    HashSet<char> first = First(right.Substring(i + 1));
                    if (first.Contains('#'))
                    {
                        // 如果下一个符号的First集包含空串，则将该产生式左侧符号的Follow集加入当前符号的Follow集
                        HashSet<char> followLeft = follow[node.Left[0]];
                        int oldCount = set.Count;
                        set.UnionWith(followLeft);
                        if (set.Count != oldCount)
                        {
                            changed = true;
                        }
                        // 移除空串
                        first.Remove('#');
                    }
                    // 将下一个符号的First集加入当前符号的Follow集
                    oldCount = set.Count;
                    set.UnionWith(first);
                    if (set.Count != oldCount)
                    {
                        changed = true;
                    }
                }
            }
        }
    }
}

// 获取字符串的First集
public HashSet<char> First(string str)
{
    HashSet<char> set = new HashSet<char>();
    if (str.Length == 0)
    {
        set.Add('#');
        return set;
    }
    char c = str[0];
    if (isFinalsymbol(c))
    {
        set.Add(c);
    }
    else
    {
        HashSet<char> first = First(getRight(str));
        set.UnionWith(first);
        if (first.Contains('#'))
        {
            set.Remove('#');
            set.UnionWith(First(str.Substring(1)));
        }
    }
    return set;
}

// 获取字符串的右侧部分
public string getRight(string str)
{
    int i = 0;
    while (i < str.Length && !isFinalsymbol(str[i]))
    {
        i++;
    }
    return str.Substring(i);
}