LR分析表构建方法:buildtable() 函数解析
该方法用于根据LR(0)分析表的状态集合、转移函数和产生式,构建LR分析表。具体实现如下:
-
首先获取isLL_1_对象,用于判断是否是LL(1)语法。
-
初始化一个空的字典table,用于存储每个状态在不同终结符/非终结符下的操作。
-
对于每个状态i:
-
针对每个终结符symbol,在transitions中查找是否有状态i到达symbol的转移项:
-
如果有,则在转移项中找到第一个终结符为symbol的项,将该项加入strings列表,并将flag置为1。
-
如果没有,则跳过此步骤。
-
针对每个归约项item:
-
如果该项的dotIndex等于RHS的长度,且LHS不是起始符号的扩展符号,则判断该项的LHS的FOLLOW集中是否包含symbol:
-
如果包含,则将该项的产生式编号加入strings列表,并将flag置为1。
-
如果不包含,则跳过此步骤。
-
如果flag为0,则说明在该状态下没有针对当前终结符symbol的操作,将空串加入strings列表。
- 如果transitions中不存在状态i到达其他状态的转移项:
-
针对起始符号的扩展符号,判断该符号的FOLLOW集中是否包含symbol:
-
如果包含,则将该项的产生式编号加入strings列表,并将flag置为1。
-
如果symbol为#, 则将'acc'加入strings列表。
-
如果flag为0,则说明在该状态下没有针对当前终结符symbol的操作,将空串加入strings列表。
- 针对每个非终结符t,在transitions中查找是否有状态i到达t的转移项:
- 如果有,则将该项的目标状态编号加入strings列表,并将flag置为1。
- 如果没有,则将空串加入strings列表。
-
将strings列表加入table字典中,以状态i为键。
-
返回table字典作为LR分析表。
public void buildtable()
{
isLL_1_ isLL_1_ = isLR_0.isLL_1_;
int flag = 0;
table = new Dictionary<int, List<string>>();
for (int i = 0; i < states.Count; i++)
{
//对每个状态经过终结符的情况进行判断
List<string> strings = new List<string>();
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;
}
}
foreach (var item in states[i].items)
{
if (item.dotIndex == item.RHS.Count && !item.LHS.Equals(production.Keys.First() + '''))
{
if (isLL_1_.follow.getfollows()[item.LHS].Contains(symbol))
{
flag = 1;
int index = getproconut(item);
strings.Add('r' + index);
break;
}
}
}
if (flag == 0)
{
if (states[i].items.First().LHS.Equals(production.Keys.First() + ''') && i != 0)
{
if (symbol.Equals('#')) strings.Add('acc');
else strings.Add('');
}
else strings.Add('');
}
}
//只有归约项的
else
{
if (states[i].items.First().LHS.Equals(production.Keys.First() + '''))
{
if (symbol.Equals('#')) strings.Add('acc');
else strings.Add('');
}
else
{
flag = 0;
foreach (var item in states[i].items)
{
//如果该终结集在FOLLOW集中则加入分析表
if (isLL_1_.follow.getfollows()[item.LHS].Contains(symbol) || symbol.Equals('#'))
{
flag = 1;
int index = getproconut(item);
strings.Add('r' + index);
break;
}
}
if (flag == 0) strings.Add('');
}
}
}
//对每个状态经过非终结符的情况进行判断
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);
}
}
原文地址: https://www.cveoy.top/t/topic/oIkj 著作权归作者所有。请勿转载和采集!