private void button4_Click(object sender, EventArgs e)
{
Dictionary<string, List> first = new Dictionary<string, List>();
Dictionary<string, List> follow = new Dictionary<string, List>();
Dictionary<string, Dictionary<string, List>> table = new Dictionary<string, Dictionary<string, List>>();
// 计算FIRST集
foreach (var item in production)
{
string left = item.Key;
List rightList = item.Value;
if (!first.ContainsKey(left))
first.Add(left, new List());
foreach (string right in rightList)
{
if (right.Length == 1 && !char.IsUpper(right[0])) // 形如A->a
{
if (!first[left].Contains(right))
first[left].Add(right);
}
else if (right.Length > 1) // 形如A->BCD
{
for (int i = 0; i < right.Length; i++)
{
string beta = right.Substring(i);
if (!char.IsUpper(right[i])) // 形如A->aBCD
{
if (!first[left].Contains(right[i].ToString()))
first[left].Add(right[i].ToString());
break;
}
else if (char.IsUpper(right[i])) // 形如A->BCD
{
if (!first.ContainsKey(right[i].ToString())) // B的FIRST集尚未计算
break;
else
{
if (!first[left].Contains(right[i].ToString()))
first[left].AddRange(first[right[i].ToString()]);
if (!first[right[i].ToString()].Contains("ε")) // 如果B的FIRST集中不包含ε，则不再计算后面的符号
break;
else if (i == right.Length - 1) // 如果B的FIRST集中包含ε且B是最后一个符号，则将ε加入FIRST(A)
{
if (!first[left].Contains("ε"))
first[left].Add("ε");
}
}
}
}
}
}
}
// 计算FOLLOW集
foreach (var item in production)
{
string left = item.Key;
if (!follow.ContainsKey(left))
follow.Add(left, new List());
}
follow[production.First().Key].Add("$");
bool isChanged = true;
while (isChanged)
{
isChanged = false;
foreach (var item in production)
{
string left = item.Key;
List rightList = item.Value;
foreach (string right in rightList)
{
for (int i = 0; i < right.Length; i++)
{
string beta = right.Substring(i + 1);
if (char.IsUpper(right[i])) // 形如A->BCD
{
if (!follow.ContainsKey(right[i].ToString())) // B的FOLLOW集尚未计算
break;
else
{
if (beta.Length == 0) // 形如A->BC
{
if (!follow[left].ContainsRange(follow[right[i].ToString()]))
{
follow[left].AddRange(follow[right[i].ToString()]);
isChanged = true;
}
}
else // 形如A->BCD
{
if (!char.IsUpper(beta[0])) // 形如A->BCa
{
if (!follow[left].Contains(beta[0].ToString()))
{
follow[left].Add(beta[0].ToString());
isChanged = true;
}
}
else // 形如A->BCD
{
if (!first.ContainsKey(beta[0].ToString())) // C的FIRST集尚未计算
break;
else
{
if (!first[beta[0].ToString()].Contains("ε")) // 如果C的FIRST集中不包含ε，则将FIRST(C)加入FOLLOW(B)
{
if (!follow[left].ContainsRange(first[beta[0].ToString()]))
{
follow[left].AddRange(first[beta[0].ToString()]);
isChanged = true;
}
}
else // 如果C的FIRST集中包含ε，则将FIRST(C)-ε加入FOLLOW(B)，并将FOLLOW(A)加入FOLLOW(B)
{
if (!follow[left].ContainsRange(first[beta[0].ToString()].Except(new List() { "ε" })))
{
follow[left].AddRange(first[beta[0].ToString()].Except(new List() { "ε" }));
isChanged = true;
}
if (!follow[left].ContainsRange(follow[right[i].ToString()]))
{
follow[left].AddRange(follow[right[i].ToString()]);
isChanged = true;
}
}
}
}
}
}
}
}
}
}
}
// 构造分析表
foreach (var item in production)
{
string left = item.Key;
List rightList = item.Value;
foreach (string right in rightList)
{
List temp = new List();
if (right == "ε")
{
foreach (string s in follow[left])
{
if (!temp.Contains(s))
temp.Add(s);
}
}
else
{
for (int i = 0; i < right.Length; i++)
{
string beta = right.Substring(i + 1);
if (char.IsUpper(right[i])) // 形如A->BCD
{
if (!first.ContainsKey(right[i].ToString())) // B的FIRST集尚未计算
break;
else
{
if (!first[right[i].ToString()].Contains("ε")) // 如果B的FIRST集中不包含ε，则直接将FIRST(B)加入分析表
{
foreach (string s in first[right[i].ToString()])
{
if (!temp.Contains(s))
temp.Add(s);
}
break;
}
else // 如果B的FIRST集中包含ε，则将FIRST(B)-ε加入分析表，并将FOLLOW(A)加入分析表
{
foreach (string s in first[right[i].ToString()].Except(new List() { "ε" }))
{
if (!temp.Contains(s))
temp.Add(s);
}
if (i == right.Length - 1) // 如果B是最后一个符号，则将FOLLOW(A)加入分析表
{
foreach (string s in follow[left])
{
if (!temp.Contains(s))
temp.Add(s);
}
}
}
}
}
else // 形如A->aB或A->a
{
if (!temp.Contains(right[i].ToString()))
temp.Add(right[i].ToString());
break;
}
}
}
if (!table.ContainsKey(left))
table.Add(left, new Dictionary<string, List>());
foreach (string s in temp)
{
if (!table[left].ContainsKey(s))
table[left].Add(s, new List());
table[left][s].Add(right);
}
}
}
// 输出分析表
listView3.Items.Clear();
foreach (var item in table)
{
string left = item.Key;
Dictionary<string, List> rightDict = item.Value;
foreach (var subItem in rightDict)
{
string right = string.Join("|", subItem.Value);
string action = "";
if (right == "ε")
action = "acc";
else
action = "shift";
string content = "(" + left + "," + subItem.Key + "," + action + right + ")";
listView3.Items.Add(content);
}
}