LR(0) 文法分析器：判别、项目族和分析表生成

{ 'title': 'class isLR_0_\n {\n Dictionary<char, List> product;
public bool is_LR = false;
isLL_1_ isLL_1_;
LR0 LR0;

public isLR_0_(String text)
{
isLL_1_ = new isLL_1_(text);
if (isLL_1_.is_LL != 1) return;
else LR0 = new LR0(isLL_1_);
//当发生移进归约冲突或归约归约冲突时
is_LR = LR0.judgeLR0();
}

public LR0 getLR0()
{
return LR0;
}
}

// LR(0)项目类
class Item
{
public string LHS; // 产生式左部
public List RHS; // 产生式右部
public int dotIndex; // 点的位置

public Item(string lhs, List rhs, int dotIndex)
{
this.LHS = lhs;
this.RHS = rhs;
this.dotIndex = dotIndex;
}

// 判断两个项目是否相等
public bool Equals(Item other)
{
return LHS == other.LHS && dotIndex == other.dotIndex && RHS.Count == other.RHS.Count
&& new HashSet(RHS).SetEquals(other.RHS);
}

public override string ToString()
{
List tempRHS = new List(RHS);
tempRHS.Insert(dotIndex, '.');
return $'{LHS}->{string.Join('',tempRHS)}';
}

public string ToString2()
{
List tempRHS = new List(RHS);
return $'{LHS}->{string.Join('', tempRHS)}';
}
}

// 项集类
class ItemSet
{
public HashSet items;

public ItemSet()
{
items = new HashSet();
}

public override bool Equals(object other)
{
if (other == null || GetType() != other.GetType())
{
return false;
}

ItemSet otherSet = (ItemSet)other;
return items.SetEquals(otherSet.items);
}

//public override string ToString()
//{
// return string.Join('\n', items);
//}
}

// LR(0)分析器类
class LR0
{
public List terminals; // 终结符集合
public List nonterminal;// 非终结符集合
public Dictionary<string, List> production;//继承LL1中的原始产生式
public Dictionary<string, List<List>> productions; // 产生式规则（包含全部规则）

public Dictionary<int, HashSet> transitions; // 状态转移函数
public Dictionary<ItemSet, int> stateNumbers; // 状态编号
public Dictionary<int, ItemSet> states; // 状态集合
public Dictionary<int, List> table;

public LR0(isLL_1_ isLL_1_)
{
this.terminals = isLL_1_.LL1Item.final;
this.nonterminal = isLL_1_.LL1Item.nofinal;

this.production = isLL_1_.product;

productions = new Dictionary<string, List<List>>();
transformpro();

transitions = new Dictionary<int, HashSet>();
buildDFA(); // 构建 DFA
buildtable(); //构建分析表
}

private void transformpro()
{
foreach (var item in production)
{
productions.Add(item.Key, new List<List>());
foreach(var item2 in item.Value)
{
List proitem = new List();
for (int i = 0; i < item2.Length; i++)
proitem.Add(item2[i].ToString());
productions[item.Key].Add(proitem);
}
}
}

private ItemSet CLOSURE(ItemSet I)
{
ItemSet J = new ItemSet();
foreach (var item in I.items)
J.items.Add(item);
Stack stack = new Stack();

foreach (Item i in I.items)
{
stack.Push(i);
}

while (stack.Count > 0)
{
Item i = stack.Pop();
if (i.dotIndex < i.RHS.Count && nonterminal.Contains(i.RHS[i.dotIndex])) // dot 后的符号为非终结符
{
string X = i.RHS[i.dotIndex];
foreach (List prod in productions[X]) // 考虑 X -> Y1 Y2 ... Yk 的每个产生式
{
Item newI = new Item(X, prod, 0);
if (!J.items.Contains(newI))
{
J.items.Add(newI);
stack.Push(newI);
}
}
}
}
return J;
}

private ItemSet GOTO(ItemSet I, string X)
{
ItemSet J = new ItemSet();
foreach (Item i in I.items)
{
if (i.dotIndex < i.RHS.Count && i.RHS[i.dotIndex] == X)
{
Item newI = new Item(i.LHS, i.RHS, i.dotIndex + 1);
J.items.Add(newI);
}
}

return CLOSURE(J);
}

private int iscommon(Dictionary<ItemSet, int> states, ItemSet itemSet)
{
int flag;
int index=-1;
foreach(var item in states.Keys)
{
flag = 0;
if (item.items.Count == itemSet.items.Count)
{
foreach (var j in itemSet.items)
{
foreach (var i in item.items)
{
if (i.Equals(j))
{
flag++;
break;
}
}
}
if (flag == item.items.Count) index=states[item];
}
}
return index;
}

private void buildDFA()
{
//构造初始项目集
string s = productions.Keys.First() + ''';
Item startItem = new Item(s, new List() { productions.Keys.First() }, 0);
ItemSet startSet = new ItemSet();
startSet.items.Add(startItem);
startSet = CLOSURE(startSet);

// 初始化状态编号
stateNumbers = new Dictionary<ItemSet, int>();
states = new Dictionary<int, ItemSet>();

// 使用队列保存待处理的项集
Queue queue = new Queue();
stateNumbers[startSet] = 0;
states.Add(0, startSet);
queue.Enqueue(startSet);

while (queue.Count > 0)
{
ItemSet I = queue.Dequeue();
int stateNumber = stateNumbers[I];

// 计算 I 中每个符号的移进操作后得到的新项集，并添加到 DFA 中
foreach (string symbol in nonterminal.Union(terminals))
{
ItemSet J = GOTO(I, symbol);
int index;

if (J.items.Count > 0)
{
index = iscommon(stateNumbers, J);
if(index == -1)// 如果该项集不为空且还没有被加入到状态集合中
{
stateNumbers[J] = states.Count;
states.Add(states.Count, J);
queue.Enqueue(J);
}
if (!transitions.ContainsKey(stateNumber))// 如果该项集不为空
{
transitions[stateNumber] = new HashSet();
}
transitions[stateNumber].Add(symbol + (index!=-1? index:stateNumbers[J]));
}
}
}
}

public bool judgeLR0()
{
int back = 0;
int put = 0;

foreach(var item in stateNumbers.Keys)
{
back = 0;
put = 0;
foreach (var pro in item.items)
{
if (pro.dotIndex == pro.RHS.Count) back++;
else if (terminals.Contains(pro.RHS[pro.dotIndex])) put++;
}
if (back > 0 && put > 0) return false;
if (back >= 2) return false;
}
return true;
}

private int getproconut(ItemSet itemSet)
{
int index = 1;
if (itemSet.items.Count == 1)
{
foreach (var item in itemSet.items)
if(item.dotIndex == item.RHS.Count)
{
foreach(var key in productions.Keys)
{
if (key.Equals(item.LHS))
{
foreach( var item2 in productions[key])
{
if (item.RHS.Equals(item2)) return index;
else index++;
}
}
index += productions[key].Count;
}
return index;
}
}
return -1;
}
private void buildtable()
{
int flag = 0;
table = new Dictionary<int, List>();
for(int i=0;i<states.Count; i++)
{
//对每个状态经过终结符的情况进行判断
List strings = new List();
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;
}
}
if (flag==0)strings.Add('');
}
else
{
if (states[i].items.First().LHS.Equals(production.Keys.First() + '''))
{
if(symbol.Equals('#')) strings.Add('acc');
else strings.Add('');
}
else
{
int index = getproconut(states[i]);
strings.Add('r' + index);
}
}
}
//对每个状态经过非终结符的情况进行判断
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);
}
}

}
根据上述代码，补充函数button2_Click、button4_Click和button5_Click，分别实现判别LR0文法、生成项目族信息和构造LR分析表功能，其中输入的文法在richTextBox1中，得到的项目族信息以状态和项目族信息两列显示在dataGridView1中，构造的LR分析表字符集为列，状态序号为行显示在dataGridView2中。要求不不能使用上述代码中定义过的函数，重新在函数中定义调用。内容：private void button2_Click(object sender, EventArgs e) { isLR_0_ lr0 = new isLR_0_(richTextBox1.Text); if (lr0.is_LR) { MessageBox.Show('该文法是LR(0)文法'); } else { MessageBox.Show('该文法不是LR(0)文法'); } }

private void button4_Click(object sender, EventArgs e) { isLL_1_ isLL_1_ = new isLL_1_(richTextBox1.Text); if (isLL_1_.is_LL != 1) return; LR0 lr0 = new LR0(isLL_1_); dataGridView1.Rows.Clear(); foreach (var item in lr0.stateNumbers) { dataGridView1.Rows.Add(item.Value, string.Join('\n', item.Key.items)); } }

private void button5_Click(object sender, EventArgs e) { isLL_1_ isLL_1_ = new isLL_1_(richTextBox1.Text); if (isLL_1_.is_LL != 1) return; LR0 lr0 = new LR0(isLL_1_); dataGridView2.Rows.Clear(); dataGridView2.Columns.Clear(); dataGridView2.Columns.Add('state', 'state'); foreach (var symbol in lr0.terminals.Union(lr0.nonterminal)) { dataGridView2.Columns.Add(symbol, symbol); } foreach (var item in lr0.table) { List row = new List(); row.Add(item.Key.ToString()); row.AddRange(item.Value); dataGridView2.Rows.Add(row.ToArray()); } }