SLR文法分析表构造代码详解 - C#实现 - 常规

//产生式结点类
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<int> Container
        = new List<int>(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;
    }
}

//分析句子
public class Analyze
{
    public List<string> stack_state = new List<string>(100);//记录状态栈
    public List<string> stack_symbol = new List<string>(100);//记录符号栈
    public List<string> Input_str = new List<string>(100);//记录输入串
    public List<string> Tran_pro = new List<string>(100);//记录所用产生式
}

public DFA[] dfa = new DFA[100];
public int Pindex = 0; //dfa数组指针
public Table[][] SLRAna;//分析表
public Analyze Jz;
public bool Success = false;
public List<SLRNode> SLRproNum = new List<SLRNode>(50);//产生式 列表
public List<SLRNode> SLRobjNum = new List<SLRNode>(50);//项目 列表
public List<SLRitemsets> proitemset = new List<SLRitemsets>(100);//项目集合
public List<int> Gy_obj = new List<int>(50);//归约项目序号集合
public List<int> Gy_itemset = new List<int>(50);//含有归约项目的集合的序号 的集合
public List<char> Nchar = new List<char>(50);//非终结符集合
public List<char> Echar = new List<char>(50);//终结符集合

public List<char>[] Follow; //每个非终结符的follow集合

public string RStr = '';
public string RStr_obitemset = '';//输出返回
public string RStr_DFA = '';
public string RStr_ANA = '';
public SLRAnaly()
{
}
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 + Nchar.Count];

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

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

    for (int i = 0; i < Gy_itemset.Count; i++)
    {
        foreach (int item in proitemset[Gy_itemset[i]].Container)
        {
            if (SLRobjNum[item].Right == '')//如果是S'->S则直接跳过
                continue;
            char left = SLRobjNum[item].Left[0];
            foreach (char follow in Follow[FindID(Nchar, left)])//对于follow集里的每个终结符
            {
                int j = FindID(Echar, follow);
                if (SLRAna[Gy_itemset[i]][j].error)//如果此处原来是error，则直接填写r状态
                {
                    tnode = new Table('r', item);
                    SLRAna[Gy_itemset[i]][j] = tnode;
                }
                else//否则就是移进-归约冲突，需要报错
                {
                    Console.WriteLine('移进-归约冲突！');
                    return;
                }
            }
        }
    }

    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);
            foreach (char follow in Follow[CID])//对于follow集里的每个终结符
            {
                int j = FindID(Echar, follow);
                if (SLRAna[dfa[i].from][j].error)//如果此处原来是error，则直接填写N状态
                {
                    SLRAna[dfa[i].from][j] = tnode;
                }
                else//否则就是移进-移进冲突，需要报错
                {
                    Console.WriteLine('移进-移进冲突！');
                    return;
                }
            }
        }
        else //不是归约项目 添加状态S
        {
            int CID = FindID(Echar, dfa[i].symbol);
            tnode = new Table('S', dfa[i].to);
            if (SLRAna[dfa[i].from][CID].error)//如果此处原来是error，则直接填写S状态
            {
                SLRAna[dfa[i].from][CID] = tnode;
            }
            else//否则就是移进-移进冲突，需要报错
            {
                Console.WriteLine('移进-移进冲突！');
                return;
            }
        }
    }
}

上述代码是对LR分析表构造代码的修改，主要变化在于以下几个方面：

使用了follow集来判断是否可以归约。在遍历项目集合时，对于每个归约项目，会遍历其左部非终结符的follow集，并将所有follow集中的终结符作为该项目的归约状态，添加到分析表中。
处理移进-归约冲突。如果在分析表中发现某个状态下，同一个终结符既可以移进又可以归约，则发生了移进-归约冲突，程序会输出错误信息并终止。
处理归约-归约冲突。如果在分析表中发现某个状态下，同一个终结符对应多个归约状态，则发生了归约-归约冲突，程序会输出错误信息并终止。
添加了对S'->S的特殊处理。如果项目是S'->S，则不会添加任何归约状态，因为其follow集为空。

代码示例说明:

// 遍历项目集合，对于每个归约项目
for (int i = 0; i < Gy_itemset.Count; i++)
{
    foreach (int item in proitemset[Gy_itemset[i]].Container)
    {
        if (SLRobjNum[item].Right == '')//如果是S'->S则直接跳过
            continue;
        char left = SLRobjNum[item].Left[0];
        foreach (char follow in Follow[FindID(Nchar, left)])//对于follow集里的每个终结符
        {
            int j = FindID(Echar, follow);
            if (SLRAna[Gy_itemset[i]][j].error)//如果此处原来是error，则直接填写r状态
            {
                tnode = new Table('r', item);
                SLRAna[Gy_itemset[i]][j] = tnode;
            }
            else//否则就是移进-归约冲突，需要报错
            {
                Console.WriteLine('移进-归约冲突！');
                return;
            }
        }
    }
}

关键点:

使用follow集进行判断：follow集用于确定一个非终结符的后面可能出现的终结符，根据follow集可以判断是否可以归约。
处理冲突：对于移进-归约冲突和归约-归约冲突，程序会输出错误信息并终止，因为这些冲突意味着文法不是SLR(1)文法。
S'->S的特殊处理：S'->S的follow集为空，所以不会添加任何归约状态。

总结:

通过对follow集的应用以及对冲突的处理，可以将LR分析表构造代码修改成SLR分析表构造代码，从而构建SLR文法分析器。需要注意的是，只有当文法是SLR(1)文法时，才能使用这种方法构建分析表，否则会产生冲突，无法构建正确的分析表。