LR(0)分析表构造算法到SLR(1)分析表构造算法的改进

本文介绍如何将用于构造LR(0)分析器的LR(0)分析表构造算法改进为用于构造SLR(1)分析器的SLR(1)分析表构造算法。

SLR(1)分析表构造算法

SLR(1)分析表构造算法是在LR(0)分析表构造算法的基础上，增加了对Follow集的计算，并使用Follow集来解决LR(0)分析表中存在的移进-归约冲突。

代码实现

以下是修改后的C#代码，用于构造SLR(1)分析表：csharppublic class SLRNode{ public string Left; public string Right; public HashSet LookAhead; // 新增LookAhead集合 public SLRNode(string Left, string Right) { this.Left = Left; this.Right = Right; this.LookAhead = new HashSet(); }}

public class SLRitemsets{ public List Container = new List(100); public HashSet LookAhead = new HashSet(); // 新增LookAhead集合}

// ...其他代码...

public Table[][] GET_ANA(){ SLRAnaly(); // 调用SLRAnaly函数构造分析表 RStr_ANA += '\r\nSLR(1)分析表:\r\n '; // 修改输出字符串 // ...其他代码...}

public void SLRAnaly(){ // 新增：计算所有非终结符的Follow集合 foreach (char c in Nchar) { follow[c] = new HashSet(); } follow[SLRproNum[0].Left].Add('$'); for (int i = 0; i < SLRproNum.Count; i++) { for (int j = 0; j < SLRproNum[i].Right.Length; j++) { if (isNonFinalsymbol(SLRproNum[i].Right[j])) { if (j == SLRproNum[i].Right.Length - 1) { foreach (char c in follow[SLRproNum[i].Left]) { follow[SLRproNum[i].Right[j]].Add(c); } } else { HashSet firstSet = first(SLRproNum[i].Right.Substring(j + 1)); foreach (char c in firstSet) { if (c != 'ε') { follow[SLRproNum[i].Right[j]].Add(c); } } if (firstSet.Contains('ε')) { foreach (char c in follow[SLRproNum[i].Left]) { follow[SLRproNum[i].Right[j]].Add(c); } } } } } }

// ...其他代码...

// 构造DFA和LR分析表    // ...其他代码...}

// 计算First集的函数private HashSet first(string symbol){ // ...}

// 计算Follow集的函数// ...

// 判断是否为非终结符的函数private bool isNonFinalsymbol(char c){ // ..