SLR 分析表构建算法详解

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])].Container[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);
}