SLR1 分析器构造 - 修改后的代码 - 常规

public class SLRNode
{
    public string Left;
    public string Right;
    public HashSet<char> First;
    public HashSet<char> Follow;
    public SLRNode(string Left, string Right)
    {
        this.Left = Left;
        this.Right = Right;
        First = new HashSet<char>();
        Follow = new HashSet<char>();
    }
}
//项目集类
public class SLRitemsets
{
    public List<int> Container
        = new List<int>(100);
    //记录项目在项目集合中的序号
    public HashSet<char> LookAhead
        = new HashSet<char>();
    //记录展望符
}

//DFA结点
public struct DFA
{
    public int from;
    public char symbol;
    public int to;
    public HashSet<char> LookAhead;
    public DFA(int from, char symbol, int to, HashSet<char> LookAhead)
    {
        this.from = from;
        this.symbol = symbol;
        this.to = to;
        this.LookAhead = LookAhead;
    }
}

//分析表 结点
public class Table
{
    public bool error;//是否为ERROR
    public char type;//结点类型
    public int id;//数值
    public Table()
    {
        this.error = true;
    }
    public Table(char type, int id)
    {
        this.type = type;
        this.id = id;
        this.error = false;
    }
}

public DFA[] dfa = new DFA[100];
public int Pindex = 0; //dfa数组指针
public Table[][] SLRAna;//分析表
public Analyze Jz;
public bool Success = false;
public List<SLRNode> SLRproNum = new List<SLRNode>(50);//产生式 列表
public List<SLRNode> SLRobjNum = new List<SLRNode>(50);//项目 列表
public List<SLRitemsets> proitemset = new List<SLRitemsets>(100);//项目集合
public List<int> Gy_obj = new List<int>(50);//归约项目序号集合
public List<int> Gy_itemset = new List<int>(50);//含有归约项目的集合的序号 的集合
public List<char> Nchar = new List<char>(50);//非终结符集合
public List<char> Echar = new List<char>(50);//终结符集合

Dictionary<char, HashSet<char>> first = new Dictionary<char, HashSet<char>>();//非终结符的First集
Dictionary<char, HashSet<char>> follow = new Dictionary<char, HashSet<char>>();//非终结符的Follow集

public string RStr = '';
public string RStr_obitemset = '';//输出返回
public string RStr_DFA = '';
public string RStr_ANA = '';
public void CreateItemsets()
{
    //初始化第一个项目集
    SLRitemsets itemset0 = new SLRitemsets();
    itemset0.Container.Add(0);
    itemset0.LookAhead.Add('#');
    itemset0 = Closure(itemset0);
    proitemset.Add(itemset0);
    //构造所有项目集
    bool flag = true;
    while (flag)
    {
        flag = false;
        for (int i = 0; i < proitemset.Count; i++)
        {
            for (int j = 0; j < Echar.Count + Nchar.Count; j++)
            {
                char symbol = j < Echar.Count ? Echar[j] : Nchar[j - Echar.Count];
                HashSet<char> lookAhead = new HashSet<char>();
                foreach (int index in proitemset[i].Container)
                {
                    if (SLRobjNum[index].Right.Contains('.') && SLRobjNum[index].Right.IndexOf('.') < SLRobjNum[index].Right.Length - 1 && SLRobjNum[index].Right[SLRobjNum[index].Right.IndexOf('.') + 1] == symbol)
                    {
                        if (SLRobjNum[index].Right.Length - 1 == SLRobjNum[index].Right.IndexOf('.') + 1)
                        {
                            lookAhead.UnionWith(proitemset[i].LookAhead);
                        }
                        else
                        {
                            bool canEpsilon = true;
                            for (int k = SLRobjNum[index].Right.IndexOf('.') + 2; k < SLRobjNum[index].Right.Length; k++)
                            {
                                if (Echar.Contains(SLRobjNum[index].Right[k]))
                                {
                                    lookAhead.UnionWith(first[SLRobjNum[index].Right[k]]);
                                    if (!first[SLRobjNum[index].Right[k]].Contains('ε'))
                                    {
                                        canEpsilon = false;
                                        break;
                                    }
                                }
                                else
                                {
                                    canEpsilon = false;
                                    lookAhead.UnionWith(first[SLRobjNum[index].Right[k]]);
                                    break;
                                }
                            }
                            if (canEpsilon)
                            {
                                lookAhead.UnionWith(proitemset[i].LookAhead);
                            }
                        }
                    }
                }
                if (lookAhead.Count > 0)
                {
                    SLRitemsets newItemset = new SLRitemsets();
                    foreach (int index in proitemset[i].Container)
                    {
                        if (SLRobjNum[index].Right.Contains('.') && SLRobjNum[index].Right.IndexOf('.') < SLRobjNum[index].Right.Length - 1 && SLRobjNum[index].Right[SLRobjNum[index].Right.IndexOf('.') + 1] == symbol)
                        {
                            SLRNode newNode = new SLRNode(SLRobjNum[index].Left, SLRobjNum[index].Right.Insert(SLRobjNum[index].Right.IndexOf('.') + 2, '$'));
                            if (!SLRobjNum.Contains(newNode))
                            {
                                SLRobjNum.Add(newNode);
                                newItemset.Container.Add(SLRobjNum.Count - 1);
                                newItemset.LookAhead.Add(symbol);
                            }
                            else
                            {
                                int index2 = SLRobjNum.IndexOf(newNode);
                                newItemset.Container.Add(index2);
                                newItemset.LookAhead.Add(symbol);
                            }
                        }
                    }
                    newItemset = Closure(newItemset);
                    if (!proitemset.Contains(newItemset))
                    {
                        proitemset.Add(newItemset);
                        flag = true;
                    }
                    dfa[Pindex++] = new DFA(i, symbol, proitemset.IndexOf(newItemset), lookAhead);
                }
            }
        }
    }
}

public void CreateSLRTable()
{
    CreateItemsets();
    CreateDFA();
    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++)
        {
            char symbol = j < Echar.Count ? Echar[j] : Nchar[j - Echar.Count];
            int nextState = -1;
            HashSet<char> lookAhead = new HashSet<char>();
            foreach (DFA d in dfa)
            {
                if (d.from == i && d.symbol == symbol)
                {
                    nextState = d.to;
                    lookAhead.UnionWith(d.LookAhead);
                    break;
                }
            }
            if (nextState == -1)
            {
                SLRAna[i][j] = new Table();
            }
            else if (Gy_obj.Contains(nextState))
            {
                SLRAna[i][j] = new Table('R', Gy_obj.IndexOf(nextState) + 1);
            }
            else if (proitemset[nextState].LookAhead.Contains('#'))
            {
                SLRAna[i][j] = new Table('A', 0);
            }
            else
            {
                SLRAna[i][j] = new Table('S', nextState);
            }
        }
        foreach (int index in Gy_itemset)
        {
            if (proitemset[index].Container.Contains(i))
            {
                foreach (char c in proitemset[index].LookAhead)
                {
                    if (Echar.IndexOf(c) >= 0)
                    {
                        SLRAna[i][Echar.IndexOf(c)] = new Table('R', Gy_obj.IndexOf(index) + 1);
                    }
                    else if (c == '#')
                    {
                        SLRAna[i][Nchar.Count - 1] = new Table('R', Gy_obj.IndexOf(index) + 1);
                    }
                }
            }
        }
    }
    Success = true;
}

// Closure 函数实现
public SLRitemsets Closure(SLRitemsets I)
{
    // 1. 添加所有 I 中的项目到 Closure 中
    SLRitemsets Closure = new SLRitemsets();
    foreach (int index in I.Container)
    {
        Closure.Container.Add(index);
    }
    // 2. 遍历 Closure 中的所有项目
    bool flag = true;
    while (flag)
    {
        flag = false;
        for (int i = 0; i < Closure.Container.Count; i++)
        {
            int index = Closure.Container[i];
            if (SLRobjNum[index].Right.Contains('.') && SLRobjNum[index].Right.IndexOf('.') < SLRobjNum[index].Right.Length - 1)
            {
                // 如果项目右侧有 .A 结构
                char A = SLRobjNum[index].Right[SLRobjNum[index].Right.IndexOf('.') + 1];
                for (int j = 0; j < SLRobjNum.Count; j++)
                {
                    // 遍历所有项目，找到以 A 开头的 .a 项目
                    if (SLRobjNum[j].Left == A.ToString() && SLRobjNum[j].Right[0] == '.')
                    {
                        // 判断该项目是否已经存在 Closure 中
                        if (!Closure.Container.Contains(j))
                        {
                            // 如果不存在，则添加该项目到 Closure 中
                            Closure.Container.Add(j);
                            // 更新 Closure 的展望符
                            Closure.LookAhead.UnionWith(GetLookAhead(index, I.LookAhead));
                            flag = true;
                        }
                    }
                }
            }
        }
    }
    return Closure;
}

// 计算项目展望符
private HashSet<char> GetLookAhead(int index, HashSet<char> lookAhead)
{
    HashSet<char> result = new HashSet<char>();
    // 如果项目右侧是 .A，则展望符是 I 的展望符
    if (SLRobjNum[index].Right.IndexOf('.') == SLRobjNum[index].Right.Length - 1)
    {
        result.UnionWith(lookAhead);
    }
    // 如果项目右侧是 .a，则展望符是 a 的 First 集
    else
    {
        string right = SLRobjNum[index].Right.Substring(SLRobjNum[index].Right.IndexOf('.') + 1);
        for (int i = 0; i < right.Length; i++)
        {
            if (Echar.Contains(right[i]))
            {
                result.Add(right[i]);
                break;
            }
            else
            {
                result.UnionWith(first[right[i]]);
                if (!first[right[i]].Contains('ε'))
                {
                    break;
                }
            }
        }
        if (result.Contains('ε'))
        {
            result.UnionWith(lookAhead);
        }
    }
    return result;
}
代码说明
SLRNode: 项目类，增加了 First 和 Follow 属性来存储非终结符的 First 集和 Follow 集。
SLRitemsets: 项目集类，增加了 LookAhead 属性来存储展望符集合。
Closure 函数: 该函数用于计算一个项目的闭包。
GetLookAhead 函数: 该函数用于计算一个项目的展望符。
其他变化
将 LR0 分析器中相关的数据结构和函数改名为 SLR1 对应的数据结构和函数。
在构造分析表时，增加了对展望符的判断。
在 CreateItemsets 函数中，对 DFA 的构造进行了修改，以适应 SLR1 分析器。