LL(1) 文法语法分析 - analyze 函数代码修改
由于 LL(1) 文法的语法分析需要借助于 FIRST 集、FOLLOW 集和预测分析表，因此需要在原有代码的基础上添加相应的计算函数和数据结构。以下是修改后的代码：
private Dictionary<string, Dictionary<string, string>> table; // 预测分析表
private Dictionary<string, List<string>> firsts; // FIRST 集
private Dictionary<string, List<string>> follows; // FOLLOW 集
private void GetFirst(string symbol, Dictionary<string, List<string>> production, Dictionary<string, List<string>> firsts)
{
// 如果该非终结符的 FIRST 集已经被计算出，则直接返回
if (firsts.ContainsKey(symbol))
{
return;
}
firsts.Add(symbol, new List<string>());
// 遍历产生式，计算 FIRST 集
foreach (var prod in production[symbol])
{
// 如果产生式首字符为终结符，则直接将其加入 FIRST 集中
if (prod.Length > 0 && IsTerminal(prod[0]))
{
if (!firsts[symbol].Contains(prod[0].ToString()))
firsts[symbol].Add(prod[0].ToString());
continue;
}
// 如果产生式首字符为非终结符，则计算该非终结符的 FIRST 集，并将结果加入首字符的 FIRST 集中
else if (prod.Length > 0 && !IsTerminal(prod[0]))
{
GetFirst(prod[0].ToString(), production, firsts);
foreach (var f in firsts[prod[0].ToString()])
{
if (!firsts[symbol].Contains(f) && !f.Equals('#'))
firsts[symbol].Add(f);
}
}
//如果第一个非终结符能推出#
if (IsReachEmpty(prod[0].ToString(), production))
{
// 递归计算第二个和后面的字符的 FIRST 集，并将结果加入该非终结符的 FIRST 集中
for (int j = 1; j < prod.Length; j++)
{
if (IsTerminal(prod[j]))
{
if (!firsts[symbol].Contains(prod[j].ToString()))
firsts[symbol].Add(prod[j].ToString());
break;
}
GetFirst(prod[j].ToString(), production, firsts);
foreach (var f in firsts[prod[j].ToString()])
{
if (!firsts[symbol].Contains(f) && !f.Equals('#'))
firsts[symbol].Add(f);
}
// 如果该非终结符的 FIRST 集没有包含空串，则可以结束循环
if (!IsReachEmpty(prod[j].ToString(), production))
{
break;
}
// 如果是最后一个字符且所有非终结符的 FIRST 集都含有空串，则将空串加入该非终结符的 FIRST 集中
if (j == prod.Length - 1)
{
if (!firsts[symbol].Contains('#'))
firsts[symbol].Add('#');
}
}
}
}
}
// 计算 FOLLOW 集
private void GetFollow(string symbol, Dictionary<string, List<string>> production, Dictionary<string, List<string>> firsts, Dictionary<string, List<string>> follows)
{
// 如果该非终结符的 FOLLOW 集已经被计算出，则直接返回
if (follows.ContainsKey(symbol))
{
return;
}
follows.Add(symbol, new List<string>());
// 如果是起始符号，则将 # 加入 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);
}
}
}
}
}
}
}
private void GetSelect(Dictionary<string, List<string>> production, Dictionary<string, List<string>> firsts, Dictionary<string, List<string>> follows)
{
//对非终结符的每个产生式获取select值
//如果该产生式第一个字符为终结符
//如果该产生式第一个字符为非终结符
// 对每个非终结符进行操作
// 对每个非终结符进行遍历
foreach (var nonterm in nonterminals)
{
// 获取该非终结符的所有产生式
var productions = production[nonterm];
// 遍历该非终结符的所有产生式
foreach (var prod in productions)
{
// 初始化该产生式的 select 值
List<string> select = new List<string>();
// 如果该产生式的第一个字符为终结符，直接将该字符加入 select
if (IsTerminal(prod[0]))
{
if (prod[0].Equals('#'))
{
// 如果该产生式的第一个字符为 #，将 follow(nonterm) 加入 select
select.AddRange(follows[nonterm]);
}
else
{
// 如果该产生式的第一个字符为其他终结符，将该终结符加入 select
select.Add(prod[0].ToString());
}
}
else
{
// 如果该产生式的第一个字符为非终结符，将该非终结符的 first 集加入 select
select.AddRange(firsts[prod[0].ToString()]);
// 如果该非终结符的 first 集中包含空串，将 follow(nonterm) 加入 select
if (select.Contains('#'))
{
select.Remove('#');
select.AddRange(follows[nonterm]);
}
}
// 将该产生式的 select 值加入预测分析表中
foreach (var term in select)
{
table[nonterm][term] = prod;
}
}
}
}
private void analyze()
{
while (true)
{
// 如果分析栈为空或者输入栈为空，则分析结束
if (analyseStack.Count == 0 || inputStack.Count == 0)
{
break;
}
// 获取分析栈的栈顶元素和输入栈的栈顶元素
char topAnalyse = analyseStack.Peek();
char topInput = inputStack.Peek();
// 如果分析栈的栈顶元素和输入栈的栈顶元素相同，则进行匹配
if (topAnalyse == topInput)
{
// 将匹配的元素从分析栈和输入栈中弹出
analyseStack.Pop();
inputStack.Pop();
// 在分析结果列表中添加匹配信息
resultAnalyse.Add(analyseStack.ToString());
resultInput.Add(inputStack.ToString());
resultParse.Add(''' + topAnalyse + ''' + " 匹配");
}
else
{
// 如果分析栈的栈顶元素为终结符，则出错
if (IsTerminal(topAnalyse))
{
resultParse.Add("出错");
break;
}
else
{
if (!table.ContainsKey(topAnalyse.ToString()) || !table[topAnalyse.ToString()].ContainsKey(topInput.ToString()))
{
resultParse.Add("出错");
break;
}
else
{
// 获取分析表中的产生式
string production = table[topAnalyse.ToString()][topInput.ToString()];
// 如果分析表中没有产生式，则出错
if (production == null)
{
resultParse.Add("出错");
break;
}
else
{
// 将产生式从分析栈中弹出
analyseStack.Pop();
// 如果产生式不是空串，则将产生式中的符号逆序压入分析栈中
if (production != "#" )
{
for (int i = production.Length - 1; i >= 0; i--)
{
analyseStack.Push(production[i]);
}
}
// 在分析结果列表中添加产生式信息
resultAnalyse.Add(analyseStack.ToString());
resultInput.Add(inputStack.ToString());
resultParse.Add(topAnalyse + " -> " + production);
}
}
}
}
}
// 如果分析栈和输入栈都为空，则分析成功
if (analyseStack.Count == 0 && inputStack.Count == 0)
{
resultParse.Add("成功");
}
}
代码说明：
- 预测分析表：
table存储了每个非终结符在不同输入符号下的对应产生式。 - FIRST 集：
firsts存储了每个非终结符能够推出的第一个终结符集合。 - FOLLOW 集：
follows存储了每个非终结符能够出现在其后面的终结符集合。 - GetFirst 函数：用于计算非终结符的 FIRST 集。
- GetFollow 函数：用于计算非终结符的 FOLLOW 集。
- GetSelect 函数：用于根据 FIRST 集和 FOLLOW 集构建预测分析表。
- analyze 函数：用于执行语法分析。
代码原理
-
FIRST 集的计算：
- 首先判断产生式的第一个字符是否是终结符，如果是则直接加入 FIRST 集；
- 如果是第一个字符是非终结符，则递归计算该非终结符的 FIRST 集，并将结果加入当前非终结符的 FIRST 集；
- 如果第一个字符是非终结符，并且能推导出空串，则递归计算第二个字符的 FIRST 集，以此类推，直到遇到非空串推导或者产生式结束；
-
FOLLOW 集的计算：
- 如果是起始符号，则将 # 加入 FOLLOW 集；
- 遍历所有产生式，找到包含当前非终结符的产生式；
- 如果当前非终结符位于产生式末尾，则将该产生式左部的 FOLLOW 集加入当前非终结符的 FOLLOW 集；
- 如果当前非终结符后面是终结符，则将该终结符加入当前非终结符的 FOLLOW 集；
- 如果当前非终结符后面是非终结符，则将该非终结符的 FIRST 集加入当前非终结符的 FOLLOW 集；
- 如果当前非终结符后面是非终结符，并且该非终结符能够推导出空串，则将产生式左部的 FOLLOW 集加入当前非终结符的 FOLLOW 集；
-
预测分析表的构建：
- 遍历所有非终结符；
- 遍历每个非终结符的所有产生式；
- 如果产生式第一个字符为终结符，则将该字符加入该产生式的 select 集合；
- 如果产生式第一个字符为非终结符，则将该非终结符的 FIRST 集加入该产生式的 select 集合；
- 如果该非终结符的 FIRST 集包含空串，则将该非终结符的 FOLLOW 集加入该产生式的 select 集合；
- 将该产生式的 select 集合中的每个元素作为键，产生式作为值，存入预测分析表中；
-
语法分析：
- 循环遍历分析栈和输入栈；
- 如果分析栈栈顶元素和输入栈栈顶元素相同，则进行匹配，弹出两个栈的栈顶元素；
- 如果分析栈栈顶元素为非终结符，则从预测分析表中获取该非终结符在当前输入符号下的对应产生式；
- 如果预测分析表中没有对应的产生式，则报错；
- 如果预测分析表中有对应的产生式，则将该产生式从分析栈中弹出，并将产生式中的符号逆序压入分析栈；
- 如果分析栈和输入栈都为空，则分析成功；
通过以上步骤，就能够使用 LL(1) 文法进行语法分析，并将分析结果存储在相应栈中。
原文地址: https://www.cveoy.top/t/topic/fYDH 著作权归作者所有。请勿转载和采集!