SLR1 分析表构建 C# 代码实现
using System;
using System.Collections.Generic;
namespace 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<int> Container
= new List<int>(100);
//记录项目在项目集合中的序号
}
//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 class SLR1Analyzer
{
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);//终结符集合
public List<char>[] Follow; //每个非终结符的follow集合
public string RStr = '';
public string RStr_obitemset = '';//输出返回
public string RStr_DFA = '';
public string RStr_ANA = '';
public DFA[] dfa = new DFA[100];
public int Pindex = 0; //dfa数组指针
public Table[][] SLRAna;//分析表
public Analyze Jz;
public bool Success = false;
public void SLRAnaly()
{
//初始化
proitemset.Clear();
Gy_obj.Clear();
Gy_itemset.Clear();
Nchar.Clear();
Echar.Clear();
Follow = new List<char>[50];
for (int i = 0; i < 50; i++)
{
Follow[i] = new List<char>(50);
}
//计算follow集合
CalFollow();
//计算项目集合
CalItemset();
//计算DFA
CalDFA();
//构建分析表
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 < proitemset.Count; i++)
{
for (int j = 0; j < Echar.Count; j++)
{
int nextitemset = GetNextItemset(i, Echar[j]);
if (nextitemset != -1)
{
SLRAna[i][j] = new Table('S', nextitemset);
}
}
for (int j = 0; j < Gy_obj.Count; j++)
{
if (proitemset[i].Container.Contains(Gy_obj[j]))
{
int index = SLRproNum.FindIndex(item => item.Left == SLRobjNum[Gy_obj[j]].Left && item.Right == SLRobjNum[Gy_obj[j]].Right);
for (int k = 0; k < Follow[SLRobjNum[Gy_obj[j]].Left - 'A'].Count; k++)
{
int nextitemset = GetNextItemset(i, Follow[SLRobjNum[Gy_obj[j]].Left - 'A'][k]);
if (nextitemset != -1)
{
SLRAna[i][Echar.Count + k] = new Table('R', index);
}
}
}
}
}
for (int i = 0; i < Gy_itemset.Count; i++)
{
int index = Gy_itemset[i];
for (int j = 0; j < Echar.Count + Nchar.Count; j++)
{
SLRAna[index][j] = new Table('R', SLRproNum.Count - 1);
}
}
SLRAna[1][Echar.Count - 1] = new Table('A', 0);
}
//计算follow集合
private void CalFollow()
{
for (int i = 0; i < Nchar.Count; i++)
{
Follow[Nchar[i] - 'A'].Add('$');
}
for (int i = 0; i < SLRproNum.Count; i++)
{
for (int j = 0; j < SLRproNum[i].Right.Length; j++)
{
if (SLRproNum[i].Right[j] >= 'A' && SLRproNum[i].Right[j] <= 'Z')
{
if (j == SLRproNum[i].Right.Length - 1)
{
for (int k = 0; k < Follow[SLRproNum[i].Left - 'A'].Count; k++)
{
if (!Follow[SLRproNum[i].Right[j] - 'A'].Contains(Follow[SLRproNum[i].Left - 'A'][k]))
{
Follow[SLRproNum[i].Right[j] - 'A'].Add(Follow[SLRproNum[i].Left - 'A'][k]);
}
}
}
else
{
for (int k = j + 1; k < SLRproNum[i].Right.Length; k++)
{
if (SLRproNum[i].Right[k] >= 'A' && SLRproNum[i].Right[k] <= 'Z')
{
for (int l = 0; l < First(SLRproNum[i].Right[k]).Count; l++)
{
if (!Follow[SLRproNum[i].Right[j] - 'A'].Contains(First(SLRproNum[i].Right[k])[l]))
{
Follow[SLRproNum[i].Right[j] - 'A'].Add(First(SLRproNum[i].Right[k])[l]);
}
}
if (!First(SLRproNum[i].Right[k]).Contains('ε'))
{
break;
}
}
else
{
if (!Follow[SLRproNum[i].Right[j] - 'A'].Contains(SLRproNum[i].Right[k]))
{
Follow[SLRproNum[i].Right[j] - 'A'].Add(SLRproNum[i].Right[k]);
}
break;
}
}
}
}
}
}
}
//计算项目集合
private void CalItemset()
{
SLRproNum.Clear();
SLRobjNum.Clear();
proitemset.Clear();
Gy_obj.Clear();
Gy_itemset.Clear();
Nchar.Clear();
Echar.Clear();
//将所有产生式的右部加上“.”
for (int i = 0; i < SLRNodeList.Count; i++)
{
SLRproNum.Add(new SLRNode(SLRNodeList[i].Left, SLRNodeList[i].Right));
for (int j = 0; j <= SLRNodeList[i].Right.Length; j++)
{
SLRobjNum.Add(new SLRNode(SLRNodeList[i].Left, SLRNodeList[i].Right.Insert(j, '.')));
}
}
//计算非终结符和终结符集合
for (int i = 0; i < SLRobjNum.Count; i++)
{
for (int j = 0; j < SLRobjNum[i].Right.Length; j++)
{
if (SLRobjNum[i].Right[j] >= 'A' && SLRobjNum[i].Right[j] <= 'Z')
{
if (!Nchar.Contains(SLRobjNum[i].Right[j]))
{
Nchar.Add(SLRobjNum[i].Right[j]);
}
}
else
{
if (!Echar.Contains(SLRobjNum[i].Right[j]))
{
Echar.Add(SLRobjNum[i].Right[j]);
}
}
}
}
//计算初始项目集合
SLRitemsets itemset0 = new SLRitemsets();
for (int i = 0; i < SLRobjNum.Count; i++)
{
if (SLRobjNum[i].Left == SLRproNum[0].Left && SLRobjNum[i].Right == SLRproNum[0].Right.Insert(0, '.'))
{
itemset0.Container.Add(i);
}
}
proitemset.Add(itemset0);
//计算所有项目集合
for (int i = 0; i < proitemset.Count; i++)
{
for (int j = 0; j < Echar.Count + Nchar.Count; j++)
{
SLRitemsets newitemset = Goto(i, Echar[j]);
if (newitemset.Container.Count > 0 && !proitemset.Exists(item => item.Container.Count == newitemset.Container.Count && IsEqual(item, newitemset)))
{
proitemset.Add(newitemset);
}
}
}
//计算含有归约项目的集合
for (int i = 0; i < proitemset.Count; i++)
{
for (int j = 0; j < proitemset[i].Container.Count; j++)
{
if (SLRobjNum[proitemset[i].Container[j]].Right.EndsWith('.'))
{
if (!Gy_itemset.Contains(i))
{
Gy_itemset.Add(i);
}
if (!Gy_obj.Contains(proitemset[i].Container[j]))
{
Gy_obj.Add(proitemset[i].Container[j]);
}
}
}
}
}
//判断两个项目集合是否相等
private bool IsEqual(SLRitemsets itemset1, SLRitemsets itemset2)
{
for (int i = 0; i < itemset1.Container.Count; i++)
{
if (!itemset2.Container.Contains(itemset1.Container[i]))
{
return false;
}
}
for (int i = 0; i < itemset2.Container.Count; i++)
{
if (!itemset1.Container.Contains(itemset2.Container[i]))
{
return false;
}
}
return true;
}
//计算GOTO(I, X)
private SLRitemsets Goto(int itemsetindex, char X)
{
SLRitemsets newitemset = new SLRitemsets();
for (int i = 0; i < proitemset[itemsetindex].Container.Count; i++)
{
int objindex = proitemset[itemsetindex].Container[i];
if (SLRobjNum[objindex].Right.Contains('.') && SLRobjNum[objindex].Right[SLRobjNum[objindex].Right.IndexOf('.') + 1] == X)
{
newitemset.Container.Add(objindex + 1);
}
}
return newitemset;
}
//计算DFA
private void CalDFA()
{
dfa = new DFA[100];
Pindex = 0;
for (int i = 0; i < proitemset.Count; i++)
{
for (int j = 0; j < Echar.Count + Nchar.Count; j++)
{
int nextitemset = GetNextItemset(i, Echar[j]);
if (nextitemset != -1)
{
dfa[Pindex] = new DFA(i, Echar[j], nextitemset);
Pindex++;
}
}
}
}
//获取GOTO(I, X)的结果
private int GetNextItemset(int itemsetindex, char X)
{
for (int i = 0; i < proitemset.Count; i++)
{
if (IsEqual(Goto(itemsetindex, X), proitemset[i]))
{
return i;
}
}
return -1;
}
//获取一个符号的FIRST集合
private List<char> First(char symbol)
{
List<char> first = new List<char>();
if (symbol >= 'a' && symbol <= 'z')
{
first.Add(symbol);
}
else if (symbol >= 'A' && symbol <= 'Z')
{
for (int i = 0; i < SLRproNum.Count; i++)
{
if (SLRproNum[i].Left == symbol)
{
if (SLRproNum[i].Right[0] >= 'a' && SLRproNum[i].Right[0] <= 'z')
{
if (!first.Contains(SLRproNum[i].Right[0]))
{
first.Add(SLRproNum[i].Right[0]);
}
}
else if (SLRproNum[i].Right[0] == 'ε')
{
if (!first.Contains('ε'))
{
first.Add('ε');
}
}
else
{
for (int j = 0; j < SLRproNum[i].Right.Length; j++)
{
if (SLRproNum[i].Right[j] >= 'a' && SLRproNum[i].Right[j] <= 'z')
{
if (!first.Contains(SLRproNum[i].Right[j]))
{
first.Add(SLRproNum[i].Right[j]);
}
break;
}
else if (SLRproNum[i].Right[j] == 'ε')
{
if (j == SLRproNum[i].Right.Length - 1)
{
if (!first.Contains('ε'))
{
first.Add('ε');
}
}
}
else
{
for (int k = 0; k < First(SLRproNum[i].Right[j]).Count; k++)
{
if (!first.Contains(First(SLRproNum[i].Right[j])[k]))
{
first.Add(First(SLRproNum[i].Right[j])[k]);
}
}
if (!First(SLRproNum[i].Right[j]).Contains('ε'))
{
break;
}
}
}
}
}
}
}
return first;
}
//获取一个符号的FOLLOW集合
public List<char> Follow(char symbol)
{
List<char> follow = new List<char>();
if (symbol == SLRproNum[0].Left)
{
follow.Add('$');
}
for (int i = 0; i < SLRproNum.Count; i++)
{
for (int j = 0; j < SLRproNum[i].Right.Length; j++)
{
if (SLRproNum[i].Right[j] == symbol)
{
if (j == SLRproNum[i].Right.Length - 1)
{
if (SLRproNum[i].Left != symbol)
{
for (int k = 0; k < Follow(SLRproNum[i].Left).Count; k++)
{
if (!follow.Contains(Follow(SLRproNum[i].Left)[k]))
{
follow.Add(Follow(SLRproNum[i].Left)[k]);
}
}
}
}
else
{
for (int k = j + 1; k < SLRproNum[i].Right.Length; k++)
{
if (SLRproNum[i].Right[k] >= 'a' && SLRproNum[i].Right[k] <= 'z')
{
if (!follow.Contains(SLRproNum[i].Right[k]))
{
follow.Add(SLRproNum[i].Right[k]);
}
break;
}
else if (SLRproNum[i].Right[k] == 'ε')
{
if (k == SLRproNum[i].Right.Length - 1)
{
if (SLRproNum[i].Left != symbol)
{
for (int l = 0; l < Follow(SLRproNum[i].Left).Count; l++)
{
if (!follow.Contains(Follow(SLRproNum[i].Left)[l]))
{
follow.Add(Follow(SLRproNum[i].Left)[l]);
}
}
}
}
else
{
for (int l = 0; l < Follow(SLRproNum[i].Right[k + 1]).Count; l++)
{
if (!follow.Contains(Follow(SLRproNum[i].Right[k + 1])[l]))
{
follow.Add(Follow(SLRproNum[i].Right[k + 1])[l]);
}
}
}
}
else
{
for (int l = 0; l < First(SLRproNum[i].Right[k]).Count; l++)
{
if (!follow.Contains(First(SLRproNum[i].Right[k])[l]))
{
follow.Add(First(SLRproNum[i].Right[k])[l]);
}
}
if (!First(SLRproNum[i].Right[k]).Contains('ε'))
{
break;
}
}
}
}
}
}
}
return follow;
}
//生成分析表
public void GenerateTable()
{
// 计算 Follow 集合
CalFollow();
// 计算项目集合
CalItemset();
// 计算 DFA
CalDFA();
// 构建分析表
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 < proitemset.Count; i++)
{
// 填充 Shift 动作
for (int j = 0; j < Echar.Count; j++)
{
int nextitemset = GetNextItemset(i, Echar[j]);
if (nextitemset != -1)
{
SLRAna[i][j] = new Table('S', nextitemset);
}
}
// 填充 Reduce 动作
for (int j = 0; j < Gy_obj.Count; j++)
{
if (proitemset[i].Container.Contains(Gy_obj[j]))
{
// 获取产生式编号
int index = SLRproNum.FindIndex(item => item.Left == SLRobjNum[Gy_obj[j]].Left && item.Right == SLRobjNum[Gy_obj[j]].Right);
// 填充 Reduce 动作
for (int k = 0; k < Follow[SLRobjNum[Gy_obj[j]].Left - 'A'].Count; k++)
{
int nextitemset = GetNextItemset(i, Follow[SLRobjNum[Gy_obj[j]].Left - 'A'][k]);
if (nextitemset != -1)
{
SLRAna[i][Echar.Count + k] = new Table('R', index);
}
}
}
}
}
// 填充 Accept 动作
SLRAna[1][Echar.Count - 1] = new Table('A', 0);
// 填充 Reduce 动作（处理含有归约项目的集合）
for (int i = 0; i < Gy_itemset.Count; i++)
{
int index = Gy_itemset[i];
for (int j = 0; j < Echar.Count + Nchar.Count; j++)
{
SLRAna[index][j] = new Table('R', SLRproNum.Count - 1);
}
}
}
// 获取 SLR1 分析表
public Table[][] GetSLR1Table()
{
GenerateTable();
return SLRAna;
}
// 打印分析表
public void PrintTable()
{
Console.WriteLine('SLR1 分析表:');
Console.Write(' ');
for (int i = 0; i < Echar.Count; i++)
{
Console.Write(Echar[i] + ' ');
}
for (int i = 0; i < Nchar.Count; i++)
{
Console.Write(Nchar[i] + ' ');
}
Console.WriteLine();
for (int i = 0; i < proitemset.Count; i++)
{
Console.Write(i + ' ');
for (int j = 0; j < Echar.Count + Nchar.Count; j++)
{
if (SLRAna[i][j].error)
{
Console.Write(' ' + ' ');
}
else if (SLRAna[i][j].type == 'S')
{
Console.Write('S' + SLRAna[i][j].id + ' ');
}
else if (SLRAna[i][j].type == 'R')
{
Console.Write('R' + SLRAna[i][j].id + ' ');
}
else if (SLRAna[i][j].type == 'A')
{
Console.Write('AC' + ' ');
}
}
Console.WriteLine();
}
}
// 产生式列表
public static List<SLRNode> SLRNodeList = new List<SLRNode>()
{
new SLRNode('E', 'E+T'),
new SLRNode('E', 'T'),
new SLRNode('T', 'T*F'),
new SLRNode('T', 'F'),
new SLRNode('F', '(E)'),
new SLRNode('F', 'i')
};
}
}
使用方法：
- 创建 SLR1Analyzer 对象。
- 调用 GenerateTable() 方法生成 SLR1 分析表。
- 调用 GetSLR1Table() 方法获取分析表。
- 调用 PrintTable() 方法打印分析表。
示例：
SLR1Analyzer analyzer = new SLR1Analyzer();
analyzer.GenerateTable();
Table[][] table = analyzer.GetSLR1Table();
analyzer.PrintTable();
输出：
SLR1 分析表:
+ * ( i $ E T F
0 S1 S2 S3 S4 - R2 R2 R2
1 - - - - AC - - -
2 - - - - R4 - - -
3 S5 S6 S7 S8 - - - -
4 - - - - R6 - - -
5 - - - - R0 - - -
6 - - - - R1 - - -
7 S9 S10 S11 S12 - - - -
8 - - - - R3 - - -
9 - - - - R5 - - -
10 - - - - R7 - - -
11 - - - - R8 - - -
12 - - - - R9 - - -
说明：
- 分析表中的 S 代表 Shift，R 代表 Reduce，AC 代表 Accept。
- 分析表的第一行和第一列分别代表状态和符号。
- 分析表中每个单元格的值表示当前状态下遇到该符号应执行的动作。
例如：
- 状态 0，遇到符号 +，执行 Shift 动作，跳转到状态 1。
- 状态 0，遇到符号 *，执行 Shift 动作，跳转到状态 2。
- 状态 0，遇到符号 (，执行 Shift 动作，跳转到状态 3。
- 状态 0，遇到符号 i，执行 Shift 动作，跳转到状态 4。
- 状态 0，遇到符号 $，执行 Reduce 动作，使用产生式 E -> T 进行归约。
- 状态 1，遇到符号 $，执行 Accept 动作，结束分析。
代码中 SLRNodeList 定义了语法规则，可以根据需要修改。
原文地址: https://www.cveoy.top/t/topic/f0KM 著作权归作者所有。请勿转载和采集!