SLR1分析器构造 - 代码详解及示例
上述代码为构造LR0分析器中的LR分析表的代码，若要改成对SLR1文法的分析器的构造，该怎么修改，请给出 //构造DFACreateDFA();//构造分析表CreateSLRTable();函数及其中调用的相关函数的完整代码，不需要给出变量定义了
public class SLRNode
{
public string Left;
public string Right;
public HashSet
//DFA结点
public struct DFA
{
public int from;
public char symbol;
public int to;
public HashSet<char> LookAhead;
public DFA(int from, char symbol, int to, HashSet<char> LookAhead)
{
this.from = from;
this.symbol = symbol;
this.to = to;
this.LookAhead = LookAhead;
}
}
//分析表 结点
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 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>> first = new Dictionary<char, HashSet<char>>();//非终结符的First集
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 CreateDFA()
{
RStr_DFA += '\r\nSLR1分析器DFA:\r\n';
RStr_DFA += '状态|';
foreach (char c in Echar)
{
RStr_DFA += c + '|';
}
foreach (char c in Nchar)
{
RStr_DFA += c + '|';
}
RStr_DFA += '\r\n';
for (int i = 0; i < Pindex; i++)
{
RStr_DFA += i + ' |';
for (int j = 0; j < Echar.Count + Nchar.Count; j++)
{
if (dfa[i].to == -1)
{
RStr_DFA += ' |';
}
else
{
if (dfa[i].symbol == (j < Echar.Count ? Echar[j] : Nchar[j - Echar.Count]))
{
RStr_DFA += dfa[i].to + ',' + string.Join('', dfa[i].LookAhead) + '|';
}
else
{
RStr_DFA += ' |';
}
}
}
RStr_DFA += '\r\n';
}
}
public void CreateItemsets()
{
//初始化第一个项目集
SLRitemsets itemset0 = new SLRitemsets();
itemset0.Container.Add(0);
itemset0.LookAhead.Add('#');
itemset0 = Closure(itemset0);
proitemset.Add(itemset0);
//构造所有项目集
bool flag = true;
while (flag)
{
flag = false;
for (int i = 0; i < proitemset.Count; i++)
{
for (int j = 0; j < Echar.Count + Nchar.Count; j++)
{
char symbol = j < Echar.Count ? Echar[j] : Nchar[j - Echar.Count];
HashSet
部分示例如下：
E->E+T|T
T->TF|F
F->(E)|d
对上述文法进行SLR1分析
正确答案是：
状态|+||(|)|d|#|E
4| | |S4| |S5| |8
5|r6|r6| |r6| |r6|
6| | |S4| |S5| |
7| | |S4| |S5| |
8|S6| | |S11| | |
9|r1|S7| |r1| |r1|
10|r3|r3| |r3| |r3|
11|r5|r5| |r5| |r5|内容：public void CreateSLRTable()
{
//构造DFA和项目集
CreateItemsets();
CreateDFA();
//构造分析表
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++)
{
char symbol = j < Echar.Count ? Echar[j] : Nchar[j - Echar.Count];
if (dfa[i].to == -1)
{
SLRAna[i][j] = new Table();
}
else if (Echar.Contains(symbol))
{
if (SLRobjNum[dfa[i].to].Right == symbol.ToString() + '.')
{
SLRAna[i][j] = new Table('R', Gy_obj.IndexOf(dfa[i].to) + 1);
}
else
{
int toIndex = dfa[i].to;
while (SLRobjNum[toIndex].Right.Contains('.') && SLRobjNum[toIndex].Right.IndexOf('.') < SLRobjNum[toIndex].Right.Length - 1 && Echar.Contains(SLRobjNum[toIndex].Right[SLRobjNum[toIndex].Right.IndexOf('.') + 1]))
{
toIndex = SLRitemsetTransition(toIndex, SLRobjNum[toIndex].Right[SLRobjNum[toIndex].Right.IndexOf('.') + 1]);
}
if (SLRobjNum[toIndex].Right == symbol.ToString() + '.')
{
SLRAna[i][j] = new Table('S', toIndex);
}
else
{
SLRAna[i][j] = new Table();
}
}
}
else if (Nchar.Contains(symbol))
{
int toIndex = dfa[i].to;
while (SLRobjNum[toIndex].Right.Contains('.') && SLRobjNum[toIndex].Right.IndexOf('.') < SLRobjNum[toIndex].Right.Length - 1 && Echar.Contains(SLRobjNum[toIndex].Right[SLRobjNum[toIndex].Right.IndexOf('.') + 1]))
{
toIndex = SLRitemsetTransition(toIndex, SLRobjNum[toIndex].Right[SLRobjNum[toIndex].Right.IndexOf('.') + 1]);
}
HashSet
原文地址: https://www.cveoy.top/t/topic/f0Oa 著作权归作者所有。请勿转载和采集!