LR(1) 自动机构建算法代码详解

此代码实现了构建 LR(1) 自动机的过程。具体分析如下：

函数 CLOSURE(ItemSet I) 计算一个项目集的闭包。首先将原项目集中的所有项目添加到新的项目集 J 中，然后对于每个项目中 dot 后面是非终结符的情况，将该非终结符对应的每个产生式的第一个符号作为 dot 所指向的位置，新建一个项目加入到 J 中。最后返回闭包项目集 J。

函数 GOTO(ItemSet I, string X) 计算一个项目集 I 关于符号 X 的 goto 操作后得到的新项目集。遍历 I 中的每个项目，对于 dot 后面是 X 的项目，新建一个项目，dot 位置后移一位，加入到新项目集 J 中。最后返回闭包项目集 J。

函数 buildDFA() 构建 LR(1) 自动机。首先构造初始项目集，即将 S'->S 作为第一个项目加入到一个项目集中，然后对该项目集求闭包，得到初始项目集。使用队列保存待处理的项目集，初始化状态编号和状态集合。依次对队列中的每个项目集 I 进行处理，计算 I 中每个符号的移进操作后得到的新项目集 J，并将 J 加入到状态集合中。如果 J 不为空且还没有被加入到状态集合中，则将其加入到队列中。同时，记录每个状态到达其他状态的转移操作，并保存到 transitions 字典中。最后得到构建好的 LR(1) 自动机。

private ItemSet CLOSURE(ItemSet I)
{
    ItemSet J = new ItemSet();
    foreach (var item in I.items)
        J.items.Add(item);
    Stack<Item> stack = new Stack<Item>();
    foreach (Item i in I.items)
    {
        stack.Push(i);
    }
    while (stack.Count > 0)
    {
        Item i = stack.Pop();
        if (i.dotIndex < i.RHS.Count && nonterminal.Contains(i.RHS[i.dotIndex])) // dot 后的符号为非终结符
        {
            string X = i.RHS[i.dotIndex];
            foreach (List<string> prod in productions[X]) // 考虑 X -> Y1 Y2 ... Yk 的每个产生式
            {
                Item newI = new Item(X, prod, 0);
                if (!J.items.Contains(newI))
                {
                    J.items.Add(newI);
                    stack.Push(newI);
                }
            }
        }
    }
    return J;
}

private ItemSet GOTO(ItemSet I, string X)
{
    ItemSet J = new ItemSet();
    foreach (Item i in I.items)
    {
        if (i.dotIndex < i.RHS.Count && i.RHS[i.dotIndex] == X)
        {
            Item newI = new Item(i.LHS, i.RHS, i.dotIndex + 1);
            J.items.Add(newI);
        }
    }
    return CLOSURE(J);
}

private void buildDFA()
{
    //构造初始项目集
    string s = productions.Keys.First() + ''';
    Item startItem = new Item(s, new List<string>() { productions.Keys.First() }, 0);
    ItemSet startSet = new ItemSet();
    startSet.items.Add(startItem);
    startSet = CLOSURE(startSet);
    // 初始化状态编号
    stateNumbers = new Dictionary<ItemSet, int>();
    states = new Dictionary<int, ItemSet>();
    // 使用队列保存待处理的项集
    Queue<ItemSet> queue = new Queue<ItemSet>();
    stateNumbers[startSet] = 0;
    states.Add(0, startSet);
    queue.Enqueue(startSet);
    while (queue.Count > 0)
    {
        ItemSet I = queue.Dequeue();
        int stateNumber = stateNumbers[I];
        // 计算 I 中每个符号的移进操作后得到的新项集，并添加到 DFA 中
        foreach (string symbol in nonterminal.Union(terminals))
        {
            ItemSet J = GOTO(I, symbol);
            int index;
            if (J.items.Count > 0) 
            {
                index = iscommon(stateNumbers, J);
                if(index == -1)// 如果该项集不为空且还没有被加入到状态集合中
                {
                    stateNumbers[J] = states.Count;
                    states.Add(states.Count, J);
                    queue.Enqueue(J);
                }
                if (!transitions.ContainsKey(stateNumber))// 如果该项集不为空
                {
                    transitions[stateNumber] = new HashSet<string>();
                }
                transitions[stateNumber].Add(symbol + (index!=-1? index:stateNumbers[J]));
            }
        }
    }
}