• 日期: 2027-06-22 09:23:43
  • 标签: 常规

上述代码为构造 LR0 分析器中的 LR 分析表的代码，若要改成对 SLR1 文法的分析表的构造，该怎么修改，请给出各个函数代码及其中调用的相关函数如 first、follow 等代码以及需要修改的部分修改过后的代码，不需要给出变量定义了

public class SLRNode
{
    public string Left;
    public string Right;
    public HashSet<char> First;
    public HashSet<char> Follow;
    public SLRNode(string Left, string Right)
    {
        this.Left = Left;
        this.Right = Right;
        First = new HashSet<char>();
        Follow = new HashSet<char>();
    }
}
//项目集类
public class SLRitemsets
{
    public List<int> Container
        = new List<int>(100);
    //记录项目在项目集合中的序号
    public HashSet<char> LookAhead
        = new HashSet<char>();
    //记录展望符
}

//DFA结点
public struct DFA
{
    public int from;
    public char symbol;
    public int to;
    public HashSet<char> LookAhead;
    public DFA(int from, char symbol, int to, HashSet<char> LookAhead)
    {
        this.from = from;
        this.symbol = symbol;
        this.to = to;
        this.LookAhead = LookAhead;
    }
}

//分析表 结点
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 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);//终结符集合

Dictionary<char, HashSet<char>> first = new Dictionary<char, HashSet<char>>();//非终结符的First集
Dictionary<char, HashSet<char>> follow = new Dictionary<char, HashSet<char>>();//非终结符的Follow集

public string RStr = '';
public string RStr_obitemset = '';//输出返回
public string RStr_DFA = '';
public string RStr_ANA = '';

// 以下为需要修改的代码部分：

public List<int> Closure(List<int> I)
{
    for (int index = 0; index < I.Count; index++)
    {
        for (int i = 0; i < SLRobjNum[I[index]].Right.Length - 1; i++)
        {
            if (SLRobjNum[I[index]].Right[i] == '.' && isFinalsymbol(SLRobjNum[I[index]].Right[i + 1]))
            {
                for (int j = 0; j < SLRobjNum.Count; j++)
                {
                    if (isnexist(I, j))
                        continue;
                    if (SLRobjNum[j].Left == SLRobjNum[I[index]].Right[i + 1].ToString() && SLRobjNum[j].Right[0] == '.')
                    {
                        I.Add(j);
                        foreach (char lookahead in proitemset[index].LookAhead)
                        {
                            if (!proitemset[j].LookAhead.Contains(lookahead))
                                proitemset[j].LookAhead.Add(lookahead);
                        }
                    }
                }
            }
        }
    }
    return I;
}

public void CalFollow()
{
    follow[SLRproNum[0].Left].Add('#');
    for (int i = 0; i < SLRproNum.Count; i++)
    {
        for (int j = 0; j < SLRproNum[i].Right.Length; j++)
        {
            char cur = SLRproNum[i].Right[j];
            if (isNonFinalsymbol(cur))
            {
                if (j == SLRproNum[i].Right.Length - 1)
                {
                    foreach (char c in follow[SLRproNum[i].Left])
                    {
                        if (!follow[cur].Contains(c))
                            follow[cur].Add(c);
                    }
                }
                else
                {
                    HashSet<char> temp = new HashSet<char>();
                    for (int k = j + 1; k < SLRproNum[i].Right.Length; k++)
                    {
                        if (isFinalsymbol(SLRproNum[i].Right[k]))
                        {
                            if (!temp.Contains(SLRproNum[i].Right[k]))
                                temp.Add(SLRproNum[i].Right[k]);
                            break;
                        }
                        else
                        {
                            foreach (char c in first[SLRproNum[i].Right[k]])
                            {
                                if (!temp.Contains(c))
                                    temp.Add(c);
                            }
                            if (!first[SLRproNum[i].Right[k]].Contains('@'))
                                break;
                        }
                    }
                    foreach (char c in temp)
                    {
                        if (!follow[cur].Contains(c))
                            follow[cur].Add(c);
                    }
                }
            }
        }
    }
}

public void SLRAnaly()
{
    //初始化
    for (int i = 0; i < proitemset.Count; i++)
    {
        for (int j = 0; j < Echar.Count + Nchar.Count; j++)
        {
            SLRAna[i][j] = new Table();
        }
    }
    //填充移进和归约状态
    for (int i = 0; i < proitemset.Count; i++)
    {
        foreach (int index in proitemset[i].Container)
        {
            SLRNode node = SLRobjNum[index];
            int dotpos = node.Right.IndexOf('.');
            if (dotpos == node.Right.Length - 1)//归约
            {
                if (node.Left == SLRproNum[0].Left)//接受状态
                {
                    SLRAna[i][Echar.Count - 1] = new Table('A', 0);
                }
                else
                {
                    foreach (char lookahead in proitemset[i].LookAhead)
                    {
                        int id = Gy_obj.IndexOf(index);
                        if (SLRAna[i][Echar.IndexOf(lookahead)].error)//如果该位置还没有被填充
                        {
                            SLRAna[i][Echar.IndexOf(lookahead)] = new Table('r', id);
                        }
                        else//如果该位置已经被填充了
                        {
                            if (SLRAna[i][Echar.IndexOf(lookahead)].type == 'r' && SLRAna[i][Echar.IndexOf(lookahead)].id != id)
                                SLRAna[i][Echar.IndexOf(lookahead)].error = true;
                            else if (SLRAna[i][Echar.IndexOf(lookahead)].type == 's')
                                SLRAna[i][Echar.IndexOf(lookahead)].error = true;
                        }
                    }
                }
            }
            else if (isFinalsymbol(node.Right[dotpos + 1]))//移进
            {
                int j = proitemset.IndexOf(new SLRitemsets() { Container = new List<int>() { index } });
                if (j == -1)//如果该项目还没有被加入项目集合中
                {
                    SLRitemsets temp = new SLRitemsets();
                    temp.Container.Add(index);
                    temp.LookAhead.Add(node.Right[dotpos + 1]);
                    proitemset.Add(temp);
                    j = proitemset.Count - 1;
                }
                else
                {
                    if (!proitemset[j].LookAhead.Contains(node.Right[dotpos + 1]))
                        proitemset[j].LookAhead.Add(node.Right[dotpos + 1]);
                }
                if (SLRAna[i][Echar.IndexOf(node.Right[dotpos + 1])].error)//如果该位置还没有被填充
                {
                    SLRAna[i][Echar.IndexOf(node.Right[dotpos + 1])] = new Table('s', j);
                }
                else//如果该位置已经被填充了
                {
                    if (SLRAna[i][Echar.IndexOf(node.Right[dotpos + 1])].type == 's' && SLRAna[i][Echar.IndexOf(node.Right[dotpos + 1])].id != j)
                        SLRAna[i][Echar.IndexOf(node.Right[dotpos + 1])].error = true;
                    else if (SLRAna[i][Echar.IndexOf(node.Right[dotpos + 1])].type == 'r')
                        SLRAna[i][Echar.IndexOf(node.Right[dotpos + 1])].error = true;
                }
            }
        }
    }
    //填充GOTO状态
    for (int i = 0; i < proitemset.Count; i++)
    {
        foreach (char c in Nchar)
        {
            List<int> temp = new List<int>();
            foreach (int index in proitemset[i].Container)
            {
                SLRNode node = SLRobjNum[index];
                int dotpos = node.Right.IndexOf('.');
                if (dotpos != node.Right.Length - 1 && node.Right[dotpos + 1] == c)
                {
                    SLRNode newnode = new SLRNode(node.Left, node.Right.Substring(0, dotpos + 1) + '.' + node.Right.Substring(dotpos + 1));
                    int j = SLRobjNum.IndexOf(newnode);
                    if (j == -1)//如果该项目还没有被加入项目列表中
                    {
                        SLRobjNum.Add(newnode);
                        j = SLRobjNum.Count - 1;
                    }
                    temp.Add(j);
                }
            }
            temp = Closure(temp

部分示例如下：

E->E+T|T T->T*F|F F->(E)|d

对上述文法进行 SLR1 分析

正确答案是：

状态|+|*|(|)|d|#|E 4| | |S4| |S5| |8 5|r6|r6| |r6| |r6| 6| | |S4| |S5| | 7| | |S4| |S5| | 8|S6| | |S11| | | 9|r1|S7| |r1| |r1| 10|r3|r3| |r3| |r3| 11|r5|r5| |r5| |r5|

内容：首先需要修改的是 SLRNode 类，需要加入 First 和 Follow 集合的记录：

public class SLRNode
{
    public string Left;
    public string Right;
    public HashSet<char> First;
    public HashSet<char> Follow;
    public SLRNode(string Left, string Right)
    {
        this.Left = Left;
        this.Right = Right;
        First = new HashSet<char>();
        Follow = new HashSet<char>();
    }
}

接下来是对于 SLR1 分析表的构造，需要对 Closure 函数进行修改，加入对于展望符的处理：

public List<int> Closure(List<int> I)
{
    for (int index = 0; index < I.Count; index++)
    {
        for (int i = 0; i < SLRobjNum[I[index]].Right.Length - 1; i++)
        {
            if (SLRobjNum[I[index]].Right[i] == '.' && isFinalsymbol(SLRobjNum[I[index]].Right[i + 1]))
            {
                for (int j = 0; j < SLRobjNum.Count; j++)
                {
                    if (isnexist(I, j))
                        continue;
                    if (SLRobjNum[j].Left == SLRobjNum[I[index]].Right[i + 1].ToString() && SLRobjNum[j].Right[0] == '.')
                    {
                        I.Add(j);
                        foreach (char lookahead in proitemset[index].LookAhead)
                        {
                            if (!proitemset[j].LookAhead.Contains(lookahead))
                                proitemset[j].LookAhead.Add(lookahead);
                        }
                    }
                }
            }
        }
    }
    return I;
}

然后需要添加一个函数，用于计算每个项目集的 Follow 集合：

public void CalFollow()
{
    follow[SLRproNum[0].Left].Add('#');
    for (int i = 0; i < SLRproNum.Count; i++)
    {
        for (int j = 0; j < SLRproNum[i].Right.Length; j++)
        {
            char cur = SLRproNum[i].Right[j];
            if (isNonFinalsymbol(cur))
            {
                if (j == SLRproNum[i].Right.Length - 1)
                {
                    foreach (char c in follow[SLRproNum[i].Left])
                    {
                        if (!follow[cur].Contains(c))
                            follow[cur].Add(c);
                    }
                }
                else
                {
                    HashSet<char> temp = new HashSet<char>();
                    for (int k = j + 1; k < SLRproNum[i].Right.Length; k++)
                    {
                        if (isFinalsymbol(SLRproNum[i].Right[k]))
                        {
                            if (!temp.Contains(SLRproNum[i].Right[k]))
                                temp.Add(SLRproNum[i].Right[k]);
                            break;
                        }
                        else
                        {
                            foreach (char c in first[SLRproNum[i].Right[k]])
                            {
                                if (!temp.Contains(c))
                                    temp.Add(c);
                            }
                            if (!first[SLRproNum[i].Right[k]].Contains('@'))
                                break;
                        }
                    }
                    foreach (char c in temp)
                    {
                        if (!follow[cur].Contains(c))
                            follow[cur].Add(c);
                    }
                }
            }
        }
    }
}

接下来是对于 SLR1 分析表的构造，需要加入对于 LookAhead 符号的处理：

public void SLRAnaly()
{
    //初始化
    for (int i = 0; i < proitemset.Count; i++)
    {
        for (int j = 0; j < Echar.Count + Nchar.Count; j++)
        {
            SLRAna[i][j] = new Table();
        }
    }
    //填充移进和归约状态
    for (int i = 0; i < proitemset.Count; i++)
    {
        foreach (int index in proitemset[i].Container)
        {
            SLRNode node = SLRobjNum[index];
            int dotpos = node.Right.IndexOf('.');
            if (dotpos == node.Right.Length - 1)//归约
            {
                if (node.Left == SLRproNum[0].Left)//接受状态
                {
                    SLRAna[i][Echar.Count - 1] = new Table('A', 0);
                }
                else
                {
                    foreach (char lookahead in proitemset[i].LookAhead)
                    {
                        int id = Gy_obj.IndexOf(index);
                        if (SLRAna[i][Echar.IndexOf(lookahead)].error)//如果该位置还没有被填充
                        {
                            SLRAna[i][Echar.IndexOf(lookahead)] = new Table('r', id);
                        }
                        else//如果该位置已经被填充了
                        {
                            if (SLRAna[i][Echar.IndexOf(lookahead)].type == 'r' && SLRAna[i][Echar.IndexOf(lookahead)].id != id)
                                SLRAna[i][Echar.IndexOf(lookahead)].error = true;
                            else if (SLRAna[i][Echar.IndexOf(lookahead)].type == 's')
                                SLRAna[i][Echar.IndexOf(lookahead)].error = true;
                        }
                    }
                }
            }
            else if (isFinalsymbol(node.Right[dotpos + 1]))//移进
            {
                int j = proitemset.IndexOf(new SLRitemsets() { Container = new List<int>() { index } });
                if (j == -1)//如果该项目还没有被加入项目集合中
                {
                    SLRitemsets temp = new SLRitemsets();
                    temp.Container.Add(index);
                    temp.LookAhead.Add(node.Right[dotpos + 1]);
                    proitemset.Add(temp);
                    j = proitemset.Count - 1;
                }
                else
                {
                    if (!proitemset[j].LookAhead.Contains(node.Right[dotpos + 1]))
                        proitemset[j].LookAhead.Add(node.Right[dotpos + 1]);
                }
                if (SLRAna[i][Echar.IndexOf(node.Right[dotpos + 1])].error)//如果该位置还没有被填充
                {
                    SLRAna[i][Echar.IndexOf(node.Right[dotpos + 1])] = new Table('s', j);
                }
                else//如果该位置已经被填充了
                {
                    if (SLRAna[i][Echar.IndexOf(node.Right[dotpos + 1])].type == 's' && SLRAna[i][Echar.IndexOf(node.Right[dotpos + 1])].id != j)
                        SLRAna[i][Echar.IndexOf(node.Right[dotpos + 1])].error = true;
                    else if (SLRAna[i][Echar.IndexOf(node.Right[dotpos + 1])].type == 'r')
                        SLRAna[i][Echar.IndexOf(node.Right[dotpos + 1])].error = true;
                }
            }
        }
    }
    //填充GOTO状态
    for (int i = 0; i < proitemset.Count; i++)
    {
        foreach (char c in Nchar)
        {
            List<int> temp = new List<int>();
            foreach (int index in proitemset[i].Container)
            {
                SLRNode node = SLRobjNum[index];
                int dotpos = node.Right.IndexOf('.');
                if (dotpos != node.Right.Length - 1 && node.Right[dotpos + 1] == c)
                {
                    SLRNode newnode = new SLRNode(node.Left, node.Right.Substring(0, dotpos + 1) + '.' + node.Right.Substring(dotpos + 1));
                    int j = SLRobjNum.IndexOf(newnode);
                    if (j == -1)//如果该项目还没有被加入项目列表中
                    {
                        SLRobjNum.Add(newnode);
                        j = SLRobjNum.Count - 1;
                    }
                    temp.Add(j);
                }
            }
            temp = Closure(temp

上述代码中，首先需要定义 SLRNode 类，该类需要包含 First 和 Follow 集合。

其次，需要修改 Closure 函数，在该函数中，需要根据当前项目集的 LookAhead 集合来更新新加入项目的 LookAhead 集合。

最后，需要添加一个 CalFollow 函数，用于计算每个非终结符的 Follow 集合。

在 SLRAnaly 函数中，需要根据当前项目集的 LookAhead 集合来填充分析表中的归约状态，并根据项目集的 LookAhead 集合来添加新的项目到项目集合中。

上述代码只是 SLR1 分析表构造代码的部分示例，具体的代码实现还需要根据具体的文法进行调整。

SLR1 分析表构造代码 - 详解及示例

原文地址: https://www.cveoy.top/t/topic/f0N4 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录