// 判断一个字符是否为终结符
private bool IsTerminal(char c)
{
if (char.IsUpper(c))
return false;
return true;
}
// 判断一个非终结符是否能推出空串
private bool IsReachEmpty(string symbol, Dictionary<string, List> production)
{
if (!production.ContainsKey(symbol))
return false;
foreach (var prod in production[symbol])
{
if (prod.Equals("#"))
return true;
bool flag = true;
for (int i = 0; i < prod.Length; i++)
{
if (!IsReachEmpty(prod[i].ToString(), production))
{
flag = false;
break;
}
}
if (flag)
return true;
}
return false;
}
// 计算 FOLLOW 集
private void GetFollow(string symbol, Dictionary<string, List> production, Dictionary<string, List> firsts, Dictionary<string, List> follows)
{
// 如果该非终结符的 FOLLOW 集已经被计算出，则直接返回
if (follows.ContainsKey(symbol))
{
return;
}
follows.Add(symbol, new List());
// 如果是起始符号，则将 $ 加入 FOLLOW 集中
if (symbol.Equals(production.Keys.First()))
{
if (!follows[symbol].Contains("$"))
follows[symbol].Add("$");
}
// 遍历产生式，计算 FOLLOW 集
foreach (var item in production)
{
foreach (var prod in item.Value)
{
int index = prod.IndexOf(symbol);
if (index == -1)
continue;
// 如果该非终结符位于产生式末尾，则将产生式左部的 FOLLOW 集加入该非终结符的 FOLLOW 集中
if (index == prod.Length - 1)
{
GetFollow(item.Key, production, firsts, follows);
foreach (var f in follows[item.Key])
{
if (!follows[symbol].Contains(f))
follows[symbol].Add(f);
}
}
else
{
// 如果该非终结符后面是终结符，则将该终结符加入该非终结符的 FOLLOW 集中
if (IsTerminal(prod[index + 1]))
{
if (!follows[symbol].Contains(prod[index + 1].ToString()))
follows[symbol].Add(prod[index + 1].ToString());
}
// 如果该非终结符后面是非终结符，则将该非终结符的 FIRST 集加入该非终结符的 FOLLOW 集中
else
{
GetFirst(prod[index + 1].ToString(), production, firsts);
foreach (var f in firsts[prod[index + 1].ToString()])
{
if (!f.Equals("#") && !follows[symbol].Contains(f))
follows[symbol].Add(f);
}
// 如果该非终结符后面的所有符号都能推出空串，则将产生式左部的 FOLLOW 集加入该非终结符的 FOLLOW 集中
if (IsReachEmpty(prod[index + 1].ToString(), production))
{
GetFollow(item.Key, production, firsts, follows);
foreach (var f in follows[item.Key])
{
if (!follows[symbol].Contains(f))
follows[symbol].Add(f);
}
}
}
}
}
}
}
// 判断一个文法是否是 LL(1) 文法
private bool JudgeLL1(Dictionary<string, List> production, Dictionary<string, List> firsts, Dictionary<string, List> follows)
{
foreach (var item in production)
{
Dictionary<string, List> map = new Dictionary<string, List>();
foreach (var prod in item.Value)
{
List list = new List();
foreach (var c in prod)
{
if (IsTerminal(c))
{
list.Add(c.ToString());
break;
}
else
{
GetFirst(c.ToString(), production, firsts);
foreach (var f in firsts[c.ToString()])
{
if (!f.Equals("#") && !list.Contains(f))
list.Add(f);
}
if (!IsReachEmpty(c.ToString(), production))
break;
}
}
if (list.Contains("#"))
{
GetFollow(item.Key, production, firsts, follows);
foreach (var f in follows[item.Key])
{
if (!list.Contains(f))
list.Add(f);
}
}
string key = string.Join("", list.ToArray());
if (map.ContainsKey(key))
return false;
map.Add(key, list);
}
}
return true;
