LR(1) 分析表构建函数详解 - buildtable() 函数解析

LR(1) 分析表构建函数详解 - buildtable() 函数解析

代码示例：

private void buildtable()
{
    int flag = 0;
    table = new Dictionary<int, List<string>>();
    for(int i=0;i<states.Count; i++)
    {
        //对每个状态经过终结符的情况进行判断
        List<string> strings = new List<string>();
        foreach(var symbol in terminals)
        {
            flag = 0;
            if (transitions.ContainsKey(i))
            {
                foreach (var item in transitions[i])
                {
                    if (item[0].ToString().Equals(symbol))
                    {
                        strings.Add('S'+item.Substring(1));
                        flag = 1;
                        break;
                    }
                }
                if (flag==0)strings.Add('');
            }
            else
            {
                if (states[i].items.First().LHS.Equals(production.Keys.First() + ''))
                {
                    if(symbol.Equals('#')) strings.Add('acc');
                    else strings.Add('');
                }
                else
                {
                    int index = getproconut(states[i]);
                    strings.Add('r' + index);
                }
            }
        }
        //对每个状态经过非终结符的情况进行判断
        foreach(var t in nonterminal)
        {
            flag = 0;
            if (transitions.ContainsKey(i))
            {
                foreach (var item in transitions[i])
                {
                    if (item[0].ToString().Equals(t))
                    {
                        strings.Add(item.Substring(1));
                        flag = 1;
                        break;
                    }
                }
                if (flag == 0) strings.Add('');
            }
            else strings.Add('');
        }
        table.Add(i,strings);
    }
}

函数功能： 该函数 buildtable() 用于构建 LR(1) 分析表，该表用于指导语法分析器进行语法分析。函数分别对每个状态经过终结符和非终结符的情况进行判断，最终将结果存入一个字典 table 中。

代码解析：

1. 初始化分析表：

   • table = new Dictionary<int, List<string>>(); 创建一个空的字典，用于存储分析表。字典的键是状态编号，值是对应状态下各种符号的处理动作。

2. 遍历每个状态：

   • for(int i=0;i<states.Count; i++) 循环遍历所有状态，对每个状态进行分析。

3. 处理终结符：

   • foreach(var symbol in terminals) 循环遍历所有终结符。
   • if (transitions.ContainsKey(i)) 判断当前状态 i 是否存在对应该终结符的转移。
     • 如果存在转移，则遍历该状态的转移集合，查找与当前终结符匹配的转移。
     • 找到匹配转移后，将转移的后继状态信息添加到字符串列表 strings 中。
     • 如果未找到匹配转移，则将空字符串 '' 添加到字符串列表 strings 中。
   • else 如果当前状态没有与当前终结符的转移，则进行以下判断：
     • if (states[i].items.First().LHS.Equals(production.Keys.First() + '')) 判断当前状态是否是接受状态（即起始状态的扩展状态）。
       • 如果是接受状态，且当前终结符是 #，则将 'acc' 添加到字符串列表 strings 中，表示接受。
       • 否则，将空字符串 '' 添加到字符串列表 strings 中。
     • else 如果当前状态不是接受状态，则将该状态对应的规约动作添加到字符串列表 strings 中。

4. 处理非终结符：

   • foreach(var t in nonterminal) 循环遍历所有非终结符。
   • if (transitions.ContainsKey(i)) 判断当前状态 i 是否存在对应该非终结符的转移。
     • 如果存在转移，则遍历该状态的转移集合，查找与当前非终结符匹配的转移。
     • 找到匹配转移后，将转移的后继状态信息添加到字符串列表 strings 中。
     • 如果未找到匹配转移，则将空字符串 '' 添加到字符串列表 strings 中。
   • else 如果当前状态没有与当前非终结符的转移，则将空字符串 '' 添加到字符串列表 strings 中。

5. 存储状态信息：

   • table.Add(i,strings); 将当前状态 i 及其对应的所有处理动作列表 strings 添加到分析表字典 table 中。

总结： buildtable() 函数通过遍历所有状态，分别对每个状态经过终结符和非终结符的情况进行判断，最终构建一个字典，该字典包含了所有状态的处理动作信息，即 LR(1) 分析表。

参考：

• LR(1) 分析方法
• 编译原理
• 语法分析
• 终结符和非终结符
• 状态转移
• 接受状态
• 规约动作

希望以上解析能帮助您更好地理解 buildtable() 函数的功能和实现逻辑！