SLR(1)分析表的构建与冲突解决

本文介绍如何将LR(0)分析表的构造代码修改为SLR(1)文法的分析表，并解决移进-归约冲突和归约-归约冲突。

SLR(1)分析表与LR(0)分析表的区别

LR(0)分析表只是简单地根据项目集和DFA进行构建，没有考虑文法的Follow集，因此可能会出现移进-归约冲突和归约-归约冲突。而SLR(1)分析表则利用Follow集来解决这些冲突。

SLRAnaly()函数的修改csharppublic 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];

// 初始化，赋予ERROR属性    for (int i = 0; i < proitemset.Count; i++)        for (int j = 0; j < Echar.Count + Nchar.Count; j++)            SLRAna[i][j] = tnode;

tnode = new Table('A', 0);    SLRAna[1][FindID(Echar, '#')] = tnode; // 项目集1必定是接受项目，构建[1][#]:acc的情况

// 处理归约项目    for (int i = 0; i < Gy_itemset.Count; i++)    {        foreach (int objnum in Gy_obj)        {            if (proitemset[Gy_itemset[i]].Container.Contains(objnum))            {                tnode = new Table('r', Find_pro(objnum)); // 归约项目，找到原产生式序号，添加状态r                // 使用Follow集判断                foreach (char symbol in Follow(SLRproNum[Find_pro(objnum)].Left))                {                    int CID = FindID(Echar, symbol);                    if (SLRAna[Gy_itemset[i]][CID].error)                    {                        SLRAna[Gy_itemset[i]][CID] = tnode;                    }                    else                    {                        // 出现归约-归约冲突，报错                        throw new Exception("出现归约-归约冲突");                    }                }                break;            }        }    }

// 处理移进项目和接受项目    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 + Echar.Count] = tnode;        }        else // 不是归约项目，添加状态S        {            int CID = FindID(Echar, dfa[i].symbol);            tnode = new Table('S', dfa[i].to);            if (!SLRAna[dfa[i].from][CID].error) // 出现移进-归约冲突，报错            {                throw new Exception("出现移进-归约冲突");            }            SLRAna[dfa[i].from][CID] = tnode;        }    }}

Follow集构造函数csharppublic List<List> Follows;

public void FollowAnaly(){ Follows = new List<List>(Nchar.Count); for (int i = 0; i < Nchar.Count; i++) { Follows.Add(new List()); } Follows[0].Add('#'); // 开始符号的Follow集中加入#

bool changed = true;    while (changed) // 循环直到不再有新元素加入Follow集    {        changed = false;        for (int i = 0; i < SLRproNum.Count; i++)        {            string right = SLRproNum[i].Right;            for (int j = 0; j < right.Length; j++)            {                if (isFinalsymbol(right[j])) // 如果是终结符，跳过                {                    continue;                }                int k = j + 1;                while (k < right.Length && isFinalsymbol(right[k]))                {                    k++;                }                if (k == right.Length) // 如果是最后一个符号，加入左部符号的Follow集                {                    int leftindex = FindID(Nchar, SLRproNum[i].Left);                    List<char> leftfollow = Follows[leftindex];                    List<char> follow = Follows[FindID(Nchar, right[j])];                    int count = follow.Count;                    for (int l = 0; l < count; l++)                    {                        if (!leftfollow.Contains(follow[l]))                        {                            leftfollow.Add(follow[l]);                            changed = true;                        }                    }                }                else // 否则加入后继符号的First集                {                    List<char> follow = Follows[FindID(Nchar, right[j])];                    List<char> first = First(right.Substring(k));                    int count = first.Count;                    for (int l = 0; l < count; l++)                    {                        if (!follow.Contains(first[l]))                        {                            follow.Add(first[l]);                            changed = true;                        }                    }                }            }        }    }}

First集构造函数csharppublic List First(string symbol){ List firstSet = new List(); if (isFinalsymbol(symbol[0])) // 如果是非终结符，直接加入First集 { firstSet.Add(symbol[0]); } else { for (int i = 0; i < SLRproNum.Count; i++) { if (SLRproNum[i].Left == symbol[0].ToString()) { List temp = First(SLRproNum[i].Right); foreach (char c in temp) { if (!firstSet.Contains(c)) { firstSet.Add(c); } } } } } return firstSet;}

调用相关函数代码csharpFollowAnaly(); // 构造Follow集SLRAnaly(); // 构造分析表

总结

通过上述代码修改，可以将LR(0)分析表的构造代码修改为SLR(1)文法的分析表，并解决了移进-归约冲突和归约-归约冲突。需要注意的是，SLR(1)文法仍然可能存在冲突，需要使用更强大的LR(1)文法进行解决。