LR(0)和SLR(1)分析表构造算法及C#代码实现
LR(0)和SLR(1)分析表构造算法及C#代码实现
本文介绍LR(0)和SLR(1)分析表的构造算法，并提供使用C#语言实现的代码示例。
1. LR(0)分析表构造算法
LR(0)分析表是一种自底向上的语法分析方法，它使用一个栈来存储语法分析过程中的状态和符号。LR(0)分析表的构造过程如下：
- 构造增广文法：在原始文法的开始符号前添加一个新的非终结符，并在其后添加一个点'.'，表示分析的进度。2. 构造项目集规范族：从增广文法的开始项目出发，通过闭包运算和转移运算，构造出所有可能的项目集，并建立它们之间的转移关系，形成一个有向图，称为项目集规范族（Canonical Collection of LR(0) Items）。3. 构造LR(0)分析表：根据项目集规范族，为每个状态和每个终结符/非终结符定义动作（Action）和状态转换（Goto）。
**代码示例：**C#// SLRNode类表示语法分析树的节点public class SLRNode{ public string Left; // 节点的左孩子 public string Right; // 节点的右孩子 public SLRNode(string Left, string Right) { this.Left = Left; this.Right = Right; }}
// SLRitemsets类表示项目集public class SLRitemsets{ public List
// DFA结构体表示DFA的状态转换public struct DFA{ public int from; // 起始状态 public char symbol; // 输入符号 public int to; // 目标状态 public DFA(int from, char symbol, int to) { this.from = from; this.symbol = symbol; this.to = to; }}
// Table类表示LR(0)分析表public class Table{ public bool error; // 是否为错误状态 public char type; // 动作类型：'S'表示移进，'r'表示归约，'A'表示接受 public int id; // 状态编号或产生式编号 public Table() { this.error = true; } public Table(char type, int id) { this.type = type; this.id = id; this.error = false; }}
public class LR0Analyzer{ // ... 其他成员变量和函数 ...
public DFA[] dfa = new DFA[100]; // DFA状态转换表 public int Pindex = 0; // DFA状态转换表指针 public Table[][] LRAna; // LR(0)分析表 // ... 其他成员变量和函数 ...
// 构造LR(0)分析表 public void LRAnaly() { Table tnode = new Table();
LRAna = new Table[proitemset.Count][]; for (int i = 0; i < proitemset.Count; i++) LRAna[i] = new Table[Echar.Count + Nchar.Count];
for (int i = 0; i < proitemset.Count; i++) // 初始化，赋予ERROR属性 for (int j = 0; j < Echar.Count + Nchar.Count; j++) LRAna[i][j] = tnode;
tnode = new Table('A', 0); LRAna[1][FindID(Echar, '#')] = tnode; // 项目集1必定是接受项目，构建[1][#]:acc的情况，先直接赋值好，dfa里没有
for (int i = 0; i < Gy_itemset.Count; i++) { tnode = new Table('r', Find_pro(LRobjNum[proitemset[Gy_itemset[i]].Container[0]])); // 归约项目，找到原产生式序号，添加状态r for (int j = 0; j < Echar.Count; j++) { LRAna[Gy_itemset[i]][j] = tnode; } } for (int i = 0; i < Pindex; i++) { if (isFinalsymbol(dfa[i].symbol)) // symbol为非终结符，添加状态N { int CID = FindID(Nchar, dfa[i].symbol); tnode = new Table('N', dfa[i].to); LRAna[dfa[i].from][CID + Echar.Count] = tnode; } else // 不是归约项目，添加状态S { int CID = FindID(Echar, dfa[i].symbol); tnode = new Table('S', dfa[i].to); LRAna[dfa[i].from][CID] = tnode; } } } // ... 其他成员变量和函数 ...}
2. SLR(1)分析表构造算法
SLR(1)分析表是对LR(0)分析表的一种改进，它考虑了FOLLOW集的信息，可以解决一些LR(0)分析表无法解决的移进-归约冲突。SLR(1)分析表的构造过程与LR(0)分析表类似，只是在添加归约项目的动作时，需要判断当前输入符号是否在归约项目的FOLLOW集中。
**代码示例：**C#// ... 其他代码 ...
public class SLR1Analyzer : LR0Analyzer{ // ... 其他成员变量和函数 ...
// 构造SLR(1)分析表 public void SLRAnaly() { // ... 初始化SLRAna ...
// ... 处理接受项目 ...
for (int i = 0; i < Gy_itemset.Count; i++) { tnode = new Table('r', Find_pro(SLRobjNum[proitemset[Gy_itemset[i]].Container[0]])); // 获取归约项目的左部非终结符 string left = SLRobjNum[proitemset[Gy_itemset[i]].Container[0]].Left; // 获取左部非终结符的FOLLOW集 List<char> followSet = follow(left); for (int j = 0; j < Echar.Count; j++) { // 如果当前输入符号在FOLLOW集中，则添加归约动作 if (followSet.Contains(Echar[j])) { if (SLRAna[Gy_itemset[i]][j].error) SLRAna[Gy_itemset[i]][j] = tnode; else Console.WriteLine('SLR分析表存在归约-归约冲突！'); } } }
// ... 处理移进项目 ... }
// 计算非终结符X的FOLLOW集 public List<char> follow(string X) { List<char> f = new List<char>(); if (X == SLRproNum[0].Left) // X为文法开始符号 f.Add('#'); for (int i = 0; i < SLRproNum.Count; i++) { for (int j = 0; j < SLRproNum[i].Right.Length; j++) { if (SLRproNum[i].Right[j].ToString() == X) // 找到X { if (j == SLRproNum[i].Right.Length - 1) // X在产生式右部最后 { if (SLRproNum[i].Left != X) // 避免无限递归 f.AddRange(follow(SLRproNum[i].Left)); // 将左部的follow集加入 } else // X不在产生式右部最后 { List<char> first = first1(SLRproNum[i].Right.Substring(j + 1)); // 求X后面的符号串的first1集 if (first.Contains('ε')) // 如果first1集中包含ε，还需要加入左部的follow集 { first.Remove('ε'); if (SLRproNum[i].Left != X) // 避免无限递归 first.AddRange(follow(SLRproNum[i].Left)); } f.AddRange(first); // 将first1集加入 } } } } return f.Distinct().ToList(); // 去重 }
// 计算符号串X的FIRST(1)集 public List<char> first1(string X) { List<char> f = new List<char>(); if (isFinalsymbol(X[0])) // X为终结符 f.Add(X[0]); else // X为非终结符 { for (int i = 0; i < SLRproNum.Count; i++) { if (SLRproNum[i].Left == X[0].ToString()) // 找到X[0]所在的产生式 { if (X.Length == 1) // X只有一个符号 { if (SLRproNum[i].Right.Contains('ε')) // X[0]可以推出ε f.Add('ε'); f.AddRange(first1(SLRproNum[i].Right.Substring(0, 1))); // 将右部第一个符号的first1集加入 } else // X有多个符号 { List<char> first = first1(X.Substring(1)); // 求X[1:]的first1集 if (first.Contains('ε')) // 如果first1集中包含ε，还需要加入右部第一个符号的first1集 { first.Remove('ε'); f.AddRange(first); f.AddRange(first1(SLRproNum[i].Right.Substring(0, 1))); } else // 如果first1集中不包含ε，直接加入 f.AddRange(first); } } } } return f.Distinct().ToList(); // 去重 } // ... 其他成员变量和函数 ..
原文地址: https://www.cveoy.top/t/topic/f0uZ 著作权归作者所有。请勿转载和采集!