SLR 分析表构建算法实现
{ "title": "SLR 分析表构建算法实现", "description": "本文介绍了如何使用 C# 代码实现 SLR 分析表构建算法，并提供了完整的代码示例。SLR 分析表是用于语法分析的工具，可以帮助编译器识别输入字符串是否符合语法规则。", "keywords": "SLR分析表, 语法分析, 编译器, C# 代码", "content": "class SLR
{
//产生式结点类
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 DFA[] dfa = new DFA[100];
public Table[][] SLRAna;//分析表
public List<string> terminals; // 终结符集合
public List<string> nonterminal;// 非终结符集合
public Dictionary<string, List<string>> production;//继承LL1中的原始产生式
public Dictionary<string, List<List<string>>> productions; // 产生式规则（包含全部规则）
public Dictionary<int, HashSet<string>> transitions; // 状态转移函数
public Dictionary<ItemSet, int> stateNumbers; // 状态编号
public Dictionary<int, ItemSet> states; // 状态集合
public Dictionary<int, List<string>> table;
public isLL_1_ isLL_1_;
public SLR(isLR_0_ isLR_0_) //判断是否为LR(0)文法
{
isLR_0 = isLR_0_;
terminals = isLR_0.getLR0().terminals;
nonterminal = isLR_0.getLR0().nonterminal;
productions = isLR_0.getLR0().productions;
production = isLR_0.getLR0().production;
transitions = isLR_0.getLR0().transitions;
stateNumbers = isLR_0.getLR0().stateNumbers;
states = isLR_0.getLR0().states;
isLL_1_ = isLR_0.isLL_1_;
SLRAna = new Table[stateNumbers.Count][];
for (int i = 0; i < stateNumbers.Count; i++)
{
SLRAna[i] = new Table[terminals.Count + nonterminal.Count];
for (int j = 0; j < terminals.Count + nonterminal.Count; j++)
{
SLRAna[i][j] = new Table();
}
}
}
public void SLRAnaly()
{
for (int i = 0; i < stateNumbers.Count; i++)
{
for (int j = 0; j < terminals.Count + nonterminal.Count; j++)
{
if (j < terminals.Count)
{
//移进项
foreach (var item in transitions[i])
{
if (item[0] == terminals[j][0])
{
int to = int.Parse(item.Substring(1));
SLRAna[i][j] = new Table('S', to);
}
}
//归约项
foreach (var item in states[i].items)
{
if (item.dotIndex == item.RHS.Count && !item.LHS.Equals(production.Keys.First() + '''))
{
if (isLL_1_.follow.getfollows()[item.LHS].Contains(terminals[j]))
{
int index = getproconut(item);
SLRAna[i][j] = new Table('r', index);
}
}
}
//错误项
if (SLRAna[i][j].error)
{
SLRAna[i][j] = new Table();
}
}
else
{
//非终结符
foreach (var item in transitions[i])
{
if (item[0] == nonterminal[j - terminals.Count][0])
{
int to = int.Parse(item.Substring(1));
SLRAna[i][j] = new Table('G', to);
}
}
//错误项
if (SLRAna[i][j].error)
{
SLRAna[i][j] = new Table();
}
}
}
}
}
private int getproconut(Item item)
{
//获取对应的产生式编号
int index = 1;
if (item.dotIndex == item.RHS.Count)
{
foreach (var key in productions.Keys)
{
if (key.Equals(item.LHS))
{
//查找当前左部中符合item的产生式
foreach (var item2 in productions[key])
{
if (item.RHS.Equals(item2)) return index;
else index++;
}
}
index += productions[key].Count;
}
return index;
}
return -1;
}
public bool judgeSLR()
{
isLL_1_ isLL_1_ = isLR_0.isLL_1_;
List<List<string>> back;
List<string> put;
foreach (var item in stateNumbers.Keys)
{
back = new List<List<string>>();
put = new List<string>();
foreach (var pro in item.items)
{
if (pro.dotIndex == pro.RHS.Count)
{
if(!pro.LHS.Equals(productions.Keys.First() + '''))
back.Add(isLL_1_.follow.getfollows()[pro.LHS]);
}
else if (terminals.Contains(pro.RHS[pro.dotIndex])) put.Add(pro.RHS[pro.dotIndex]);
}
//看移进归约冲突能否解决
if (back.Count > 0 && put.Count > 0)
{
//遍历每个归约项FOLLOW集
foreach(var item1 in back)
{
//遍历每个移进项FIRST集
foreach(var item2 in put)
{
if(item1.Contains(item2))return false;
}
}
}
//看归约归约冲突能否解决
if (back.Count >= 2)
{
for (int i=0;i<back.Count-1;i++)
{
//对之后的FOLLOW集进行查询
for(int j = i+1; j < back.Count; j++)
{
//看当前FOLLOW与之后FOLLW集是否有交集
foreach(var item3 in back[i])
if (back[j].Contains(item3)) return false;
}
}
}
}
return true;
}
public void buildtable()//构造分析表
{
isLL_1_ isLL_1_ = isLR_0.isLL_1_;
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;
}
}
foreach (var item in states[i].items)
{
if (item.dotIndex == item.RHS.Count&& !item.LHS.Equals(production.Keys.First() + '''))
{
if (isLL_1_.follow.getfollows()[item.LHS].Contains(symbol))
{
flag = 1;
int index = getproconut(item);
strings.Add("r" + index);
break;
}
}
}
if (flag == 0)
{
if (states[i].items.First().LHS.Equals(production.Keys.First() + '''))&&i!=0
{
if (symbol.Equals("#")) strings.Add("acc");
else strings.Add("");
}
else strings.Add("");
}
}
//只有归约项的
else
{
if (states[i].items.First().LHS.Equals(production.Keys.First() + '''))
{
if (symbol.Equals("#")) strings.Add("acc");
else strings.Add("");
}
else
{
flag = 0;
foreach (var item in states[i].items)
{
//如果该终结集在FOLLOW集中则加入分析表
if (isLL_1_.follow.getfollows()[item.LHS].Contains(symbol) || symbol.Equals('#'))
{
flag = 1;
int index = getproconut(item);
strings.Add("r" + index);
break;
}
}
if (flag==0) strings.Add("");
}
}
}
//对每个状态经过非终结符的情况进行判断
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);
}
}
}
原文地址: https://www.cveoy.top/t/topic/f1Pr 著作权归作者所有。请勿转载和采集!