LR(1) 分析器构建代码详解 - 项目集构建与状态机生成
LR(1) 分析器构建代码详解 - 项目集构建与状态机生成
本文将深入解析 LR(1) 分析器构建过程中的关键代码，并逐行分析解释其逻辑，帮助读者深入理解 LR(1) 分析器的核心算法。
代码 1：按钮点击事件处理
private void button4_Click(object sender, EventArgs e)
{
step = 0;//单步计数置零
lr = new LR();
listView1.Columns.Clear();
listView1.Items.Clear();
listView1.View = View.Details;
// 添加第一列
listView1.Columns.Add('状态', 150);
listView1.Columns.Add('项目族信息', 350);
lr.Buildprod(richTextBox1.Text);//调用
for (int i = 0; i < lr.proitemset.Count; i++)//输出
{
ListViewItem li = new ListViewItem();
li.SubItems.Clear();
li.SubItems[0].Text = i.ToString();
string tempstr = '';
for (int j = 0; j < lr.proitemset[i].Container.Count; j++)
{
tempstr += lr.LRobjNum[lr.proitemset[i].Container[j]].Left + '->' + lr.LRobjNum[lr.proitemset[i].Container[j]].Right + ' ';
}
li.SubItems.Add(tempstr);
listView1.Items.Add(li);
}
listView1.GridLines = true;
}
代码分析：
-
初始化：
step = 0;：初始化单步计数器，用于跟踪分析过程。lr = new LR();：创建一个 LR 分析器对象。listView1.Columns.Clear();：清空 ListView 的列。listView1.Items.Clear();：清空 ListView 的项目。listView1.View = View.Details;：设置 ListView 的视图模式为 Details。listView1.Columns.Add('状态', 150);：添加一个名为 '状态' 的列，宽度为 150 像素。listView1.Columns.Add('项目族信息', 350);：添加一个名为 '项目族信息' 的列，宽度为 350 像素。
-
调用 Buildprod() 方法：
lr.Buildprod(richTextBox1.Text);：调用 LR 分析器对象的Buildprod()方法，传入从 richTextBox1 获取的文法字符串。该方法用于构建项目集和状态机。
-
输出结果：
for (int i = 0; i < lr.proitemset.Count; i++) { ... }：遍历 LR 分析器中的所有项目集。ListViewItem li = new ListViewItem();：创建一个新的 ListViewItem 对象，用于显示项目集信息。li.SubItems.Clear();：清空 ListViewItem 的子项目。li.SubItems[0].Text = i.ToString();：设置 ListViewItem 的第一个子项目为项目集的索引号。string tempstr = '';：定义一个字符串变量，用于存储项目的详细信息。for (int j = 0; j < lr.proitemset[i].Container.Count; j++) { ... }：遍历项目集中的每个项目。tempstr += lr.LRobjNum[lr.proitemset[i].Container[j]].Left + '->' + lr.LRobjNum[lr.proitemset[i].Container[j]].Right + ' ';：将项目的信息追加到 tempstr 字符串中，包括产生式的左部、右部和箭头。li.SubItems.Add(tempstr);：将项目信息添加到 ListViewItem 的子项目中。listView1.Items.Add(li);：将 ListViewItem 添加到 ListView 中。
-
设置网格线：
listView1.GridLines = true;：设置 ListView 显示网格线。
代码 2：构建项目集和状态机
public void Buildprod(string str)
{
LRNode Lr;
int i = 0;
string left = '';
string right = '';
left += 'S';
right += str[0];
Lr = new LRNode(left, right);//拓广文法开始
LRproNum.Add(Lr);
while (i < str.Length)
{
left = right = '';//还原
int j = i;
while (i < str.Length && str[i] != '\r' && str[i] != '\n')//换行符‘\r\n’
{
if (str[i] == ' ')
{
i++;
continue;
}
if (str[i] == '|') // 遇到“|”可构造一条产生式
{
Lr = new LRNode(left, right);
LRproNum.Add(Lr);
right = ''; //产生式左边相同 右边重新积累
i++; //跳过“|”
continue;
}
if ((i - j) == 0)
{
if (!exist(Nchar, str[i]))//如果非终结符集合中不存在str[i],加入Nchar 产生式左边 只有非终结符 不必判断终结符
Nchar.Add(str[i]);
left += str[i++];
}
else if (i - j <= 2)
i++;
else
{
if (isFinalsymbol(str[i]) && !exist(Nchar, str[i]))//如果非终结符集合中不存在str[i],加入Nchar isfinalsymbol 非
Nchar.Add(str[i]);
else if (!isFinalsymbol(str[i]) && !exist(Echar, str[i]))//产生式右边 需要判断终结符
Echar.Add(str[i]);
right += str[i++];
}
}//while
i++;//跳过换行符
if (left != '' && right != '')
{
Lr = new LRNode(left, right);//构造每一行最后一个产生式，不存在'|'时就是该行产生式本身
LRproNum.Add(Lr);
}
}//while
Echar.Add('#');
//构造项目 对产生式集合LRproNum中的所有产生式都循环插'.'
LRNode Lobj;
for (i = 0; i < LRproNum.Count; i++)
{
left = '';
right = '';
for (int j = 0; j <= LRproNum[i].Right.Length; j++)//j可以等于length 项目共length+1个
{
left = LRproNum[i].Left;
right = CreObj(LRproNum[i].Right, j);//在第j个位置插入'.'
if (j == LRproNum[i].Right.Length && LRobjNum.Count != 1)
{//在产生式最后的位置插入. 即为归约项目 项目集中1号位置为接受项目
Gy_obj.Add(LRobjNum.Count);//归约项目在项目集中的序号 不用+1 本身就是从0开始的
}
Lobj = new LRNode(left, right);
LRobjNum.Add(Lobj);
left = '';//还原
right = '';
}
}
Creteitemsets();//项目集
RStr_obitemset += '\r\n项目集构建：\r\n';
for (int j = 0; j < proitemset.Count; j++)
{
RStr_obitemset += 'I' + j.ToString() + ':' + '\r\n';
for (i = 0; i < proitemset[j].Container.Count; i++)
{
RStr_obitemset += LRobjNum[proitemset[j].Container[i]].Left.ToString() + '->' + LRobjNum[proitemset[j].Container[i]].Right.ToString() + '\r\n';
}
}
//return RStr_obitemset;
}
public void Creteitemsets()
{
List<int> lr_item = new List<int>(100);//记录项目的序号
lr_item.Add(0);
lr_item = Closure(lr_item);//构造初始项目集 求闭包
LRitemsets LR_C = new LRitemsets();
LR_C.Container = lr_item;//集合----项目集序号的集合
proitemset.Add(LR_C);//集合的集合----存放项目集序号集合 的集合
for (int i = 0; i < proitemset.Count; i++)//整体集合中 第i个项目集
{
proitemset[i].Container.Sort();//排序由小到大 后面用于判断是否存在的比较
int[] flag = new int[proitemset[i].Container.Count];
for (int fi = 0; fi < proitemset[i].Container.Count; fi++)//标志位，用来判断该序号是否已经构造
{
flag[fi] = 0;
}
for (int j = 0; j < proitemset[i].Container.Count; j++)//第i个项目集的第j个项目
{
if (flag[j] == 1)//如果已经访问过 就不再构造 找下一个项目
continue;
int index = proitemset[i].Container[j];
for (int pi = 0; pi < LRobjNum[index].Right.Length - 1; pi++)//length-1是避免匹配到.在最后的规约项目
{
if (LRobjNum[index].Right[pi] == '.')
{
List<int> lr2_club = new List<int>(100);//记录项目的序号
char symbol = LRobjNum[index].Right[pi + 1];//记录.a转移状态a.的符号a
lr2_club.Add((index + 1));//如果遇到.a形式的项目序号为index 那么项目a.的序号为index+1
for (int m1 = j + 1; m1 < proitemset[i].Container.Count; m1++)
{//在第i个项目集中找到了可以移动的.：.a 重新遍历第i个项目集j项目之后的 找到同样可以移动a的项目集
int index2 = proitemset[i].Container[m1];
for (int m2 = 0; m2 < LRobjNum[index2].Right.Length - 1; m2++)
{
if (LRobjNum[index2].Right[m2] == '.' && LRobjNum[index2].Right[m2 + 1] == symbol)
{
flag[m1] = 1;//标记位置为1 已经访问 之后不再访问
lr2_club.Add(index2 + 1);
}
}
}
lr2_club = Closure(lr2_club);//求闭包
int value = isexist(lr2_club);
if (value == -1)//-1表示不存在相同的
{
for (int m3 = 0; m3 < Gy_obj.Count; m3++)
{
if (isnexist(lr2_club, Gy_obj[m3]))
{
Gy_itemset.Add(proitemset.Count);
}
}
LRitemsets LR_C2 = new LRitemsets();
dfa[Pindex++] = new DFA(i, symbol, proitemset.Count);//count不用加1 本身从0开始
LR_C2.Container = lr2_club;
proitemset.Add(LR_C2);
}
else
{
dfa[Pindex++] = new DFA(i, symbol, value);
}
break;
}
}
}//end-forj
}//end-fori
}
代码分析：
-
拓广文法：
left += 'S';：添加起始符号 'S'。right += str[0];：添加文法字符串的第一个字符。Lr = new LRNode(left, right);：创建一个新的 LRNode 对象，表示拓广后的产生式。LRproNum.Add(Lr);：将拓广后的产生式添加到 LRproNum 集合中。
-
提取产生式：
while (i < str.Length) { ... }：循环遍历文法字符串。left = right = '';：重置 left 和 right 字符串。int j = i;：保存当前位置。while (i < str.Length && str[i] != '\r' && str[i] != '\n') { ... }：循环读取一行产生式。if (str[i] == ' ') { ... }：跳过空格。if (str[i] == '|') { ... }：遇到 '|' 符号，表示新的产生式开始，将当前的 left 和 right 字符串添加到 LRproNum 集合中。if ((i - j) == 0) { ... }：判断是否为产生式左部，将非终结符添加到 Nchar 集合中。else if (i - j <= 2) { ... }：跳过产生式左部的特殊字符。else { ... }：判断是否为产生式右部，将终结符和非终结符分别添加到 Echar 和 Nchar 集合中。
-
构建项目：
for (i = 0; i < LRproNum.Count; i++) { ... }：循环遍历 LRproNum 集合中的所有产生式。for (int j = 0; j <= LRproNum[i].Right.Length; j++) { ... }：在每个产生式中插入 '.'，生成项目。right = CreObj(LRproNum[i].Right, j);：调用 CreObj 方法在第 j 个位置插入 '.'。if (j == LRproNum[i].Right.Length && LRobjNum.Count != 1) { ... }：如果 '.' 插入到产生式末尾，则将该项目的序号添加到 Gy_obj 集合中，表示该项目为归约项目。Lobj = new LRNode(left, right);：创建一个新的 LRNode 对象，表示项目。LRobjNum.Add(Lobj);：将项目添加到 LRobjNum 集合中。
-
构建项目集：
Creteitemsets();：调用 Creteitemsets 方法，构建项目集。for (int j = 0; j < proitemset.Count; j++) { ... }：循环遍历 proitemset 集合中的每个项目集。for (i = 0; i < proitemset[j].Container.Count; i++) { ... }：循环遍历项目集中的每个项目。RStr_obitemset += LRobjNum[proitemset[j].Container[i]].Left.ToString() + '->' + LRobjNum[proitemset[j].Container[i]].Right.ToString() + '\r\n';：将项目集信息追加到 RStr_obitemset 字符串中。
-
求项目集的闭包：
lr_item = Closure(lr_item);：调用 Closure 方法求初始项目集的闭包。
-
生成状态机：
for (int i = 0; i < proitemset.Count; i++) { ... }：循环遍历所有项目集。for (int j = 0; j < proitemset[i].Container.Count; j++) { ... }：循环遍历每个项目集中的每个项目。for (int pi = 0; pi < LRobjNum[index].Right.Length - 1; pi++) { ... }：在每个项目中寻找 '.' 的位置。if (LRobjNum[index].Right[pi] == '.') { ... }：如果找到 '.'，则进行状态转移。List<int> lr2_club = new List<int>(100);：创建新的列表，用于存储新的项目集。lr2_club.Add((index + 1));：将当前项目的下一个项目添加到新列表中。for (int m1 = j + 1; m1 < proitemset[i].Container.Count; m1++) { ... }：遍历当前项目集中的其他项目，查找相同转移的项目。lr2_club = Closure(lr2_club);：对新列表求闭包。int value = isexist(lr2_club);：判断新的项目集是否已经存在。if (value == -1) { ... }：如果新的项目集不存在，则创建一个新的项目集，并将状态转移信息添加到 dfa 数组中。else { ... }：如果新的项目集存在，则将状态转移信息添加到 dfa 数组中，指向已存在的项目集。
总结
通过以上代码分析，我们可以清晰地理解 LR(1) 分析器构建过程中的核心步骤：
- 拓广文法：添加起始符号 'S'，将文法字符串转换为产生式集合 LRproNum。
- 构建项目：在每个产生式中插入 '.'，生成项目集合 LRobjNum。
- 求项目集的闭包：通过 Closure 方法，根据项目中的 '.' 位置进行扩展，构造项目集集合 proitemset。
- 生成状态机：根据项目集之间的状态转移关系，生成状态机 dfa。
通过这些步骤，我们就成功构建了一个 LR(1) 分析器，并可以根据其状态机进行语法分析。
注： 代码中的 LRNode、LRitemsets、DFA 等数据结构以及 Closure、isexist 等方法，需要根据具体实现进行定义。
原文地址: http://www.cveoy.top/t/topic/fZVN 著作权归作者所有。请勿转载和采集!