SLR(1)分析器的Follow集计算与分析表构建

//获取非终结符的Follow集 public Dictionary<char, HashSet> GetFollow(List Nchar, List Echar, List SLRproNum, List SLRobjNum) { Dictionary<char, HashSet> follow = new Dictionary<char, HashSet>(); HashSet Vt = new HashSet(); Vt.Add('#'); for (int i = 0; i < Echar.Count; i++) { Vt.Add(Echar[i]); }

//初始化
foreach (char ch in Nchar)
{
    follow.Add(ch, new HashSet<char>());
}
follow['S\''] = new HashSet<char>{'#'};

bool change = true;
while (change)
{
    change = false;
    for (int i = 0; i < SLRproNum.Count; i++)
    {
        string right = SLRproNum[i].Right;
        char left = SLRproNum[i].Left[0];
        for (int j = 0; j < right.Length; j++)
        {
            if (!Nchar.Contains(right[j]))
                continue;
            if (j == right.Length - 1)
            {//A->αB, Follow(B) = Follow(B) U Follow(A)
                foreach (char ch in follow[left])
                {
                    if (!follow[right[j]].Contains(ch))
                    {
                        follow[right[j]].Add(ch);
                        change = true;
                    }
                }
            }
            else
            {//A->αBβ, Follow(B) = Follow(B) U First(β) - ε
                HashSet<char> first = GetFirst(right.Substring(j + 1), Vt, follow);
                foreach (char ch in first)
                {
                    if (!follow[right[j]].Contains(ch))
                    {
                        follow[right[j]].Add(ch);
                        change = true;
                    }
                }
                if (first.Contains('#'))
                {
                    foreach (char ch in follow[left])
                    {
                        if (!follow[right[j]].Contains(ch))
                        {
                            follow[right[j]].Add(ch);
                            change = true;
                        }
                    }
                }
            }
        }
    }
}

return follow;

}

//获取字符串的First集 public HashSet GetFirst(string str, HashSet Vt, Dictionary<char, HashSet> follow) { HashSet first = new HashSet(); if (str.Length == 0) return first; if (!Nchar.Contains(str[0])) { first.Add(str[0]); return first; }

for (int i = 0; i < str.Length; i++)
{
    if (!Nchar.Contains(str[i]))
    {
        first.Add(str[i]);
        return first;
    }
    else
    {
        HashSet<char> temp = new HashSet<char>(GetFirst(CreObj(str, i + 1), Vt, follow));
        first.UnionWith(temp);
        if (!temp.Contains('#'))
            return first;
    }
}
first.Add('#');
return first;

}