LR(0)和SLR(1)分析表构造算法及代码实现

本文介绍LR(0)和SLR(1)分析表的构造算法，并给出C#代码实现。

1. 数据结构定义c#// SLR语法分析树节点public class SLRNode{ public string Left; public string Right; public SLRNode(string Left, string Right) { this.Left = Left; this.Right = Right; }}

// 项目集类public class SLRitemsets{ public List Container = new List(100); //记录项目在项目集合中的序号}

// DFA节点public struct DFA{ public int from; public char symbol; public int to; public DFA(int from, char symbol, int to) { this.from = from; this.symbol = symbol; this.to = to; }}

// 分析表节点public class Table{ public bool error;//是否为ERROR public char type;//节点类型 public int id;//数值 public Table() { this.error = true; } public Table(char type, int id) { this.type = type; this.id = id; this.error = false; }}

2. LR(0)分析表构造函数c#public Table[][] GET_ANA(){ LRAnaly(); RStr_ANA += '\r\nLR(0)分析表:\r\n '; int i; for (i = 0; i < Echar.Count; i++) { RStr_ANA += Echar[i].ToString() + ' '; } for (i = 0; i < Nchar.Count; i++) { RStr_ANA += Nchar[i].ToString() + ' '; } RStr_ANA += '\r\n'; for (i = 0; i < proitemset.Count; i++) { RStr_ANA += i.ToString() + ' '; for (int j = 0; j < Echar.Count + Nchar.Count; j++) {

        if (LRAna[i][j].error)            {                RStr_ANA += '  ' + '    ';            }            else if (i == 1 && j == Echar.Count - 1)            {                RStr_ANA += 'AC' + '    ';            }            else if (LRAna[i][j].type != 'N')            {                RStr_ANA += LRAna[i][j].type.ToString() + LRAna[i][j].id.ToString() + '    ';            }            else                RStr_ANA += LRAna[i][j].id.ToString() + '    ';        }        RStr_ANA += '\r\n';    }

return LRAna;

}

public void LRAnaly(){ Table tnode = new Table();

LRAna = new Table[proitemset.Count][];    for (int i = 0; i < proitemset.Count; i++)        LRAna[i] = new Table[Echar.Count + Nchar.Count];

for (int i = 0; i < proitemset.Count; i++)//初始化 赋予ERROR属性        for (int j = 0; j < Echar.Count + Nchar.Count; j++)//为终结符加r状态             LRAna[i][j] = tnode;

tnode = new Table('A', 0);    LRAna[1][FindID(Echar, '#')] = tnode;//项目集1必定是接受项目   构建[1][#]:acc的情况 先直接赋值好 dfa里没有

for (int i = 0; i < Gy_itemset.Count; i++)    {        tnode = new Table('r', Find_pro(LRobjNum[proitemset[Gy_itemset[i]].Container[0]]));//归约项目 找到原产生式序号 添加状态r        for (int j = 0; j < Echar.Count; j++)        {            LRAna[Gy_itemset[i]][j] = tnode;        }    }    for (int i = 0; i < Pindex; i++)    {

    if (isFinalsymbol(dfa[i].symbol))//symbol为非终结符  添加状态N        {            int CID = FindID(Nchar, dfa[i].symbol);            tnode = new Table('N', dfa[i].to);            LRAna[dfa[i].from][CID + Echar.Count] = tnode;        }        else //不是归约项目 添加状态S        {            int CID = FindID(Echar, dfa[i].symbol);            tnode = new Table('S', dfa[i].to);            LRAna[dfa[i].from][CID] = tnode;        }

}}

3. SLR(1)分析表构造函数c#public void SLRAnaly(){ Table tnode = new Table();

SLRAna = new Table[proitemset.Count][];    for (int i = 0; i < proitemset.Count; i++)        SLRAna[i] = new Table[Echar.Count + 1];//增加一个$符号列

for (int i = 0; i < proitemset.Count; i++)//初始化 赋予ERROR属性        for (int j = 0; j < Echar.Count + 1; j++)//为终结符加r状态             SLRAna[i][j] = tnode;

tnode = new Table('A', 0);    SLRAna[1][Echar.Count] = tnode;//项目集1必定是接受项目   构建[1][$]:acc的情况 先直接赋值好 dfa里没有

for (int i = 0; i < Gy_itemset.Count; i++)    {        SLRNode node = SLRobjNum[proitemset[Gy_itemset[i]].Container[0]];        string follow = Follow(node.Left);//获取归约项目的左部符号的follow集        foreach (char c in follow)//遍历follow集        {            int CID = FindID(Echar, c);            tnode = new Table('r', Find_pro(node));//归约项目 找到原产生式序号 添加状态r            SLRAna[Gy_itemset[i]][CID] = tnode;        }    }

for (int i = 0; i < Pindex; i++)    {        if (isFinalsymbol(dfa[i].symbol))//symbol为非终结符  添加状态N        {            int CID = FindID(Nchar, dfa[i].symbol);            tnode = new Table('N', dfa[i].to);            SLRAna[dfa[i].from][CID] = tnode;        }        else //不是归约项目 添加状态S        {            int CID = FindID(Echar, dfa[i].symbol);            tnode = new Table('S', dfa[i].to);            SLRAna[dfa[i].from][CID] = tnode;        }    }}

4. Follow集和First1集构造函数c#//获取符号的first1集public List First1(string s){ List result = new List(); if (isFinalsymbol(s[0]))//终结符 { result.Add(s[0]); } else//非终结符 { foreach (SLRNode node in SLRproNum)//遍历产生式 { if (node.Left.ToString() == s)//找到符号对应的产生式 { if (isFinalsymbol(node.Right[0]))//产生式右部第一个符号是终结符 { result.Add(node.Right[0]); } else//产生式右部第一个符号是非终结符 { List temp = First1(node.Right);//递归获取该符号的first1集 result.AddRange(temp); } } } } return result;}

//获取符号的follow集public string Follow(string s){ string result = ''; if (s == SLRproNum[0].Left)//开始符号的follow集为$ { result += '$'; } foreach (SLRNode node in SLRproNum)//遍历产生式 { string right = node.Right; int index = right.IndexOf(s); if (index != -1)//找到符号在产生式右部的位置 { if (index == right.Length - 1)//符号在产生式右部的末尾 { if (node.Left != s)//产生式左部不是该符号本身 { string temp = Follow(node.Left);//递归获取产生式左部符号的follow集 result += temp; } } else//符号在产生式右部的中间 { string str = right.Substring(index + 1);//获取符号后面的字符串 List temp = First1(str);//获取该字符串的first1集 if (temp.Contains('#'))//字符串的first1集包含空串 { temp.Remove('#');//去掉空串 string temp2 = Follow(node.Left);//递归获取产生式左部符号的follow集 result += temp2; } result += new string(temp.ToArray());//将first1集加入结果中 } } } return result