SLR1文法分析器构造代码详解
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';
}
}
部分示例如下：
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 CreateSLRDFA()
{
//初始化第一个项目集
List
//遍历所有项目集
for (int i = 0; i < proitemset.Count; i++)
{
//遍历所有终结符和非终结符
foreach (char X in Echar.Union(Nchar))
{
List<int> GotoIX = Goto(proitemset[i].Container, X);
if (GotoIX.Count > 0)
{
int j;
for (j = 0; j < proitemset.Count; j++)
{
if (proitemset[j].Container.SequenceEqual(GotoIX))
{
break;
}
}
if (j == proitemset.Count)
{
proitemset.Add(new SLRitemsets { Container = GotoIX });
}
dfa[Pindex] = new DFA(i, X, j, new HashSet<char>());
Pindex++;
}
}
}
//添加归约项目的展望符
foreach (int i in Gy_obj)
{
foreach (int j in Gy_itemset)
{
if (proitemset[j].Container.Contains(i))
{
proitemset[j].LookAhead.UnionWith(follow[SLRobjNum[i].Left[0]]);
}
}
}
//为每个DFA结点添加展望符
for (int i = 0; i < proitemset.Count; i++)
{
foreach (int j in proitemset[i].Container)
{
SLRNode node = SLRobjNum[j];
if (node.Right.IndexOf('.') < node.Right.Length - 1)//不是规约项目
{
char X = node.Right[node.Right.IndexOf('.') + 1];//X为.后面的符号
if (isNonFinalsymbol(X))//X为非终结符
{
HashSet<char> LA = new HashSet<char>();
if (node.Right.IndexOf('.') == node.Right.Length - 2)//.在倒数第二个位置
{
LA.UnionWith(proitemset[i].LookAhead);
}
else//.不在倒数第二个位置
{
for (int k = node.Right.IndexOf('.') + 2; k < node.Right.Length; k++)
{
LA.UnionWith(first[node.Right[k]]);
if (!first[node.Right[k]].Contains('e'))
{
break;
}
}
LA.UnionWith(proitemset[i].LookAhead);
}
foreach (DFA d in dfa)
{
if (d.from == i && d.symbol == X)
{
d.LookAhead.UnionWith(LA);
}
}
}
}
}
}
}
public void CreateSLRTable() { 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++)
{
if (Echar.Contains(dfa[i].symbol))
{
SLRAna[dfa[i].from][Echar.IndexOf(dfa[i].symbol)] = new Table('S', dfa[i].to);
}
else if (dfa[i].symbol == '#')
{
SLRAna[dfa[i].from][Echar.Count + Nchar.IndexOf(dfa[i].symbol)] = new Table('A', 0);
}
else
{
foreach (char c in dfa[i].LookAhead)
{
int k = Gy_obj.IndexOf(dfa[i].to);
if (SLRAna[dfa[i].from][Echar.Count + Nchar.IndexOf(c)].error)
{
SLRAna[dfa[i].from][Echar.Count + Nchar.IndexOf(c)] = new Table('R', k);
}
else
{
RStr_ANA += '冲突：状态' + dfa[i].from + '的' + c + '存在移进/归约冲突';
Success = false;
return;
}
}
}
}
//填充规约表
foreach (int i in Gy_itemset)
{
foreach (char c in proitemset[i].LookAhead)
{
foreach (int j in proitemset[i].Container)
{
int k = Gy_obj.IndexOf(j);
if (SLRAna[i][Echar.Count + Nchar.IndexOf(c)].error)
{
SLRAna[i][Echar.Count + Nchar.IndexOf(c)] = new Table('R', k);
}
else
{
RStr_ANA += '冲突：状态' + i + '的' + c + '存在规约/归约冲突';
Success = false;
return;
}
}
}
}
}
原文地址: https://www.cveoy.top/t/topic/f0N9 著作权归作者所有。请勿转载和采集!