SLR1 分析器构建：函数代码及调用
public class SLRNode
{
public string Left;
public string Right;
public SLRNode(string Left, string Right)
{
this.Left = Left;
this.Right = Right;
}
}
//项目集类
public class SLRitemsets
{
public List
//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;
}
}
//分析表 结点
public class Table
{
public bool error;//是否为ERROR
public char type;//结点类型
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 Analyze
{
public List<string> stack_state = new List<string>(100);//记录状态栈
public List<string> stack_symbol = new List<string>(100);//记录符号栈
public List<string> Input_str = new List<string>(100);//记录输入串
public List<string> Tran_pro = new List<string>(100);//记录所用产生式
}
public DFA[] dfa = new DFA[100];
public int Pindex = 0; //dfa数组指针
public Table[][] SLRAna;//分析表
public Analyze Jz;
public bool Success = false;
public List<SLRNode> SLRproNum = new List<SLRNode>(50);//产生式 列表
public List<SLRNode> SLRobjNum = new List<SLRNode>(50);//项目 列表
public List<SLRitemsets> proitemset = new List<SLRitemsets>(100);//项目集合
public List<int> Gy_obj = new List<int>(50);//归约项目序号集合
public List<int> Gy_itemset = new List<int>(50);//含有归约项目的集合的序号 的集合
public List<char> Nchar = new List<char>(50);//非终结符集合
public List<char> Echar = new List<char>(50);//终结符集合
Dictionary<char, HashSet<char>> follow = new Dictionary<char, HashSet<char>>();//非终结符的Follow集
public string RStr = '';
public string RStr_obitemset = '';//输出返回
public string RStr_DFA = '';
public string RStr_ANA = '';
public void Buildprod(string str) { SLRNode Lr; int i = 0; string left = ''; string right = ''; left += 'S'; right += str[0]; Lr = new SLRNode(left, right);//拓广文法开始 SLRproNum.Add(Lr); while (i < str.Length) { left = right = '';//还原 int j = i; while (i < str.Length && str[i] != '\r' && str[i] != '\n')//换行符‘\r\n’ { if (str[i] == ' ') { i++; continue; } if (str[i] == '|') // 遇到'|'可构造一条产生式 { Lr = new SLRNode(left, right); SLRproNum.Add(Lr); right = ''; //产生式左边相同 右边重新积累 i++; //跳过'|' continue; } if ((i - j) == 0) { if (!exist(Nchar, str[i]))//如果非终结符集合中不存在str[i],加入Nchar 产生式左边 只有非终结符 不必判断终结符 Nchar.Add(str[i]); left += str[i++]; } else if (i - j <= 2) i++; else { if (isFinalsymbol(str[i]) && !exist(Nchar, str[i]))//如果非终结符集合中不存在str[i],加入Nchar isfinalsymbol 非终结符返回T 终结符返回F Nchar.Add(str[i]); else if (!isFinalsymbol(str[i]) && !exist(Echar, str[i]))//产生式右边 需要判断终结符 Echar.Add(str[i]); right += str[i++]; } }//while
i++;//跳过换行符
if (left != '' && right != '')
{
Lr = new SLRNode(left, right);//构造每一行最后一个产生式，不存在'|'时就是该行产生式本身
SLRproNum.Add(Lr);
}
}//while
Echar.Add('#');
//构造项目 对产生式集合SLRproNum中的所有产生式都循环插'.'
SLRNode Lobj;
for (i = 0; i < SLRproNum.Count; i++)
{
left = '';
right = '';
for (int j = 0; j <= SLRproNum[i].Right.Length; j++)//j可以等于length 项目共length+1个
{
left = SLRproNum[i].Left;
right = CreObj(SLRproNum[i].Right, j);//在第j个位置插入'.'
if (j == SLRproNum[i].Right.Length && SLRobjNum.Count != 1)
{
//在产生式最后的位置插入. 即为归约项目 项目集中1号位置为接受项目
Gy_obj.Add(SLRobjNum.Count);//归约项目在项目集中的序号 不用+1 本身就是从0开始的
}
Lobj = new SLRNode(left, right);
SLRobjNum.Add(Lobj);
left = '';//还原
right = '';
}
}
Creteitemsets();//项目集
RStr_obitemset += '\r\n项目集构建：\r\n';
for (int j = 0; j < proitemset.Count; j++)
{
RStr_obitemset += 'I' + j.ToString() + ':' + '\r\n';
for (i = 0; i < proitemset[j].Container.Count; i++)
{
RStr_obitemset += SLRobjNum[proitemset[j].Container[i]].Left.ToString() + '->' + SLRobjNum[proitemset[j].Container[i]].Right.ToString() + '\r\n';
}
}
//return RStr_obitemset;
}
public void Creteitemsets() { //初始化项目集 SLRitemsets itemset_0 = new SLRitemsets(); itemset_0.Container.Add(0); proitemset.Add(itemset_0);
//循环遍历项目集
for (int i = 0; i < proitemset.Count; i++)
{
//获取该项目集中所有项目的闭包
HashSet<int> closure = Closure(proitemset[i]);
//遍历所有终结符和非终结符，获取它们的Go函数
foreach (char c in Nchar.Concat(Echar))
{
HashSet<int> go = Go(closure, c);
if (go.Count == 0) continue;
//判断该Go函数是否已经在项目集中出现过，如果出现过，则直接使用该项目集的序号
int index = -1;
for (int j = 0; j < proitemset.Count; j++)
{
if (proitemset[j].Container.SetEquals(go))
{
index = j;
break;
}
}
if (index == -1)
{
//如果该Go函数没有在项目集中出现过，则新建一个项目集
index = proitemset.Count;
SLRitemsets itemset = new SLRitemsets();
itemset.Container = go.ToList();
proitemset.Add(itemset);
}
//添加DFA边
dfa[Pindex++] = new DFA(i, c, index);
}
}
}
public HashSet
bool flag = true;
while (flag)
{
flag = false;
foreach (int i in closure)
{
SLRNode node = SLRobjNum[i];
int dotIndex = node.Right.IndexOf('.');
if (dotIndex == node.Right.Length - 1) continue;
char nextChar = node.Right[dotIndex + 1];
if (!Nchar.Contains(nextChar)) continue;
foreach (SLRNode prod in SLRproNum)
{
if (prod.Left == nextChar.ToString())
{
SLRNode newNode = new SLRNode(nextChar.ToString(), '.' + prod.Right);
int index = SLRobjNum.IndexOf(newNode);
if (index == -1)
{
index = SLRobjNum.Count;
SLRobjNum.Add(newNode);
}
if (closure.Add(index)) flag = true;
}
}
}
}
return closure;
}
public HashSet
char nextChar = node.Right[dotIndex + 1];
if (nextChar == c) go.Add(i + 1);
}
return Closure(new SLRitemsets() { Container = go.ToList() });
}
//以下代码是对上面代码的补充，主要实现SLR1分析表的构建和分析过程 public void BuildSLRTable() { //初始化分析表 SLRAna = new Table[proitemset.Count][]; for (int i = 0; i < proitemset.Count; i++) { SLRAna[i] = new Table[Echar.Count + Nchar.Count]; for (int j = 0; j < Echar.Count + Nchar.Count; j++) { SLRAna[i][j] = new Table(); } }
//填充移进和规约表格
for (int i = 0; i < Pindex; i++)
{
char symbol = dfa[i].symbol;
int from = dfa[i].from;
int to = dfa[i].to;
if (isFinalsymbol(symbol))
{
int index = Echar.IndexOf(symbol);
SLRAna[from][index] = new Table('s', to);
}
else
{
int index = Nchar.IndexOf(symbol);
SLRAna[from][Echar.Count + index] = new Table('g', to);
}
}
for (int i = 0; i < proitemset.Count; i++)
{
foreach (int j in proitemset[i].Container)
{
SLRNode node = SLRobjNum[j];
int dotIndex = node.Right.IndexOf('.');
if (dotIndex == node.Right.Length - 1)
{
if (node.Left == 'S'') SLRAna[i][Echar.Count - 1] = new Table('a', 0);
else
{
foreach (char c in follow[node.Left[0]])
{
int index = Echar.IndexOf(c);
SLRAna[i][index] = new Table('r', j);
}
}
}
}
}
}
public void BuildFollow()
{
//初始化Follow集
foreach (char c in Nchar)
{
follow[c] = new HashSet
//循环遍历所有产生式，求解Follow集
bool flag = true;
while (flag)
{
flag = false;
foreach (SLRNode prod in SLRproNum)
{
string left = prod.Left;
string right = prod.Right;
for (int i = 0; i < right.Length; i++)
{
if (Nchar.Contains(right[i]))
{
//如果当前字符是非终结符
HashSet<char> tmp = First(right.Substring(i + 1));
if (tmp.Remove('#'))
{
//如果右侧剩余部分可以推出空串，则将左侧非终结符的Follow集加入其中
foreach (char c in follow[left[0]])
{
if (tmp.Add(c)) flag = true;
}
}
foreach (char c in tmp)
{
if (follow[right[i]].Add(c)) flag = true;
}
}
}
}
}
}
public HashSet
public bool isFinalsymbol(char c) { if (Nchar.Contains(c) || c == '|' || c == '\r' || c == '\n' || c == ' ') return false; return true; }
public bool exist(List
public string CreObj(string str, int dotIndex) { string result = ''; for (int i = 0; i < str.Length; i++) { if (i == dotIndex) result += '.'; result += str[i]; } if (dotIndex == str.Length) result += '.'; return result; }
public void SLRAnalyze(string input) { //初始化分析栈和输入串 Jz = new Analyze(); Jz.stack_state.Add('0'); Jz.Input_str.AddRange(input.Select(c => c.ToString())); Jz.Input_str.Add('#');
//循环分析输入串
while (Jz.Input_str.Count > 0)
{
string top_state = Jz.stack_state.Last();
string top_symbol = Jz.stack_symbol.Last();
string input_symbol = Jz.Input_str.First();
//根据分析表进行移进或规约
if (SLRAna[int.Parse(top_state)][Echar.IndexOf(input_symbol)].type == 's')
{
int nextState = SLRAna[int.Parse(top_state)][Echar.IndexOf(input_symbol)].id;
Jz.stack_state.Add(nextState.ToString());
Jz.stack_symbol.Add(input_symbol);
Jz.Input_str.RemoveAt(0);
}
else if (SLRAna[int.Parse(top_state)][Echar.IndexOf(input_symbol)].type == 'r')
{
int prodIndex = SLRAna[int.Parse(top_state)][Echar.IndexOf(input_symbol)].id;
SLRNode prod = SLRobjNum[prodIndex];
int length = prod.Right.Length;
Jz.stack_state.RemoveAt(Jz.stack_state.Count - length);
Jz.stack_symbol.RemoveAt(Jz.stack_symbol.Count - length);
top_state = Jz.stack_state.Last();
top_symbol = Jz.stack_symbol.Last();
int nextState = SLRAna[int.Parse(top_state)][Nchar.IndexOf(prod.Left[0]) + Echar.Count].id;
Jz.stack_state.Add(nextState.ToString());
Jz.stack_symbol.Add(prod.Left);
Jz.Tran_pro.Add(prod.Left + '->' + prod.Right);
}
else if (SLRAna[int.Parse(top_state)][Echar.IndexOf(input_symbol)].type == 'a')
{
Success = true;
break;
}
else
{
Success = false;
break;
}
}
}
原文地址: https://www.cveoy.top/t/topic/f0Nw 著作权归作者所有。请勿转载和采集!