SLR 语法分析表构造算法及代码实现

本文介绍 SLR 语法分析表的构造算法，并提供 C# 代码实现。

1. SLRAnaly() 函数

SLRAnaly() 函数用于构造 SLR 分析表，其核心思想是根据 Follow 集解决移进-归约冲突和归约-归约冲突。c#public void SLRAnaly(){ Table tnode = new Table();

SLRAna = new Table[proitemset.Count][];    for (int i = 0; i < proitemset.Count; i++)        SLRAna[i] = new Table[Echar.Count + Nchar.Count];

// 初始化，赋予 ERROR 属性    for (int i = 0; i < proitemset.Count; i++)        for (int j = 0; j < Echar.Count + Nchar.Count; j++)            SLRAna[i][j] = tnode;

// 项目集 1 必定是接受项目，构建 [1][#]:acc 的情况    tnode = new Table('A', 0);    SLRAna[1][FindID(Echar, '#')] = tnode;

// 处理归约项目    for (int i = 0; i < Gy_itemset.Count; i++)    {        SLRNode proNode = SLRproNum[SLRobjNum[proitemset[Gy_itemset[i]].Container[0]].Left[0]];        foreach (char c in Follow(proNode.Left[0])) // 对于每个 follow 集中的终结符        {            int CID = FindID(Echar, c);            if (SLRAna[Gy_itemset[i]][CID].error) // 如果存在冲突            {                Console.WriteLine('SLR 分析表存在冲突');                Success = false;                return;            }            else            {                tnode = new Table('r', Find_pro(SLRobjNum[proitemset[Gy_itemset[i]].Container[0]])); // 归约项目，找到原产生式序号，添加状态 r                SLRAna[Gy_itemset[i]][CID] = tnode;            }        }    }

// 处理移进项目和 goto 项目    for (int i = 0; i < Pindex; i++)    {        if (isFinalsymbol(dfa[i].symbol)) // symbol 为非终结符，添加状态 N        {            int CID = FindID(Nchar, dfa[i].symbol);            foreach (char c in Follow(dfa[i].symbol)) // 对于每个 follow 集中的终结符            {                int CID2 = FindID(Echar, c);                if (SLRAna[dfa[i].from][CID2 + Echar.Count].error) // 如果存在冲突                {                    Console.WriteLine('SLR 分析表存在冲突');                    Success = false;                    return;                }                else                {                    tnode = new Table('N', dfa[i].to);                    SLRAna[dfa[i].from][CID2 + Echar.Count] = tnode;                }            }        }        else // 不是归约项目，添加状态 S        {            int CID = FindID(Echar, dfa[i].symbol);            if (SLRAna[dfa[i].from][CID].error) // 如果存在冲突            {                Console.WriteLine('SLR 分析表存在冲突');                Success = false;                return;            }            else            {                tnode = new Table('S', dfa[i].to);                SLRAna[dfa[i].from][CID] = tnode;            }        }    }}

2. Follow 集构造函数

Follow 集构造函数用于计算非终结符的 Follow 集。c#public HashSet Follow(char Vn){ HashSet follow = new HashSet(); if (Vn == 'S') { follow.Add('#'); } foreach (SLRNode node in SLRproNum) { int index = node.Right.IndexOf(Vn); if (index == -1) { continue; } if (index == node.Right.Length - 1) // Vn 在产生式右侧最后一个字符 { if (node.Left[0] != Vn) // 如果不是本身 { follow.UnionWith(Follow(node.Left[0])); } } else { char nextChar = node.Right[index + 1]; if (isFinalsymbol(nextChar)) // nextChar 是终结符 { follow.Add(nextChar); } else // nextChar 是非终结符 { HashSet first = First(nextChar); if (first.Contains('#')) // 如果 nextChar 可以推出空串 { first.Remove('#'); follow.UnionWith(first); follow.UnionWith(Follow(node.Left[0])); } else { follow.UnionWith(first); } } } } return follow