SLR(1) 语法分析表构建算法实现与优化

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 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 Table[][] GET_ANA()
{
    SLRAnaly();
    RStr_ANA += '\r\nSLR0分析表:\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 (SLRAna[i][j].error)
            {
                RStr_ANA += '  ' + '    ';
            }
            else if (i == 1 && j == Echar.Count - 1)
            {
                RStr_ANA += 'AC' + '    ';
            }
            else if (SLRAna[i][j].type != 'N')
            {
                RStr_ANA += SLRAna[i][j].type.ToString() + SLRAna[i][j].id.ToString() + '    ';
            }
            else
                RStr_ANA += SLRAna[i][j].id.ToString() + '    ';
        }
        RStr_ANA += '\r\n';
    }

    return SLRAna;

}

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];

    // 初始化分析表为ERROR
    for (int i = 0; i < proitemset.Count; i++)
        for (int j = 0; j < Echar.Count + Nchar.Count; j++)
            SLRAna[i][j] = tnode;

    // 项目集1必定是接受项目
    tnode = new Table('A', 0);
    SLRAna[1][FindID(Echar, '#')] = tnode; 

    // 处理归约项目
    for (int i = 0; i < Gy_itemset.Count; i++)
    {
        SLRNode item = SLRobjNum[proitemset[Gy_itemset[i]].Container[0]];
        char left = item.Left[0];
        List<char> follow = GetFollow(left);
        foreach (char c in follow)
        {
            int CID = FindID(Echar, c);
            // 修正：归约项应该放在非终结符对应的位置
            SLRAna[Gy_itemset[i]][CID + Echar.Count] = new Table('r', Find_pro(item)); 
        }
    }

    // 处理DFA
    for (int i = 0; i < Pindex; i++)
    {
        if (isFinalsymbol(dfa[i].symbol)) // symbol为非终结符
        {
            int CID = FindID(Nchar, dfa[i].symbol);
            SLRAna[dfa[i].from][CID + Echar.Count] = new Table('N', dfa[i].to);
        }
        else // symbol为终结符
        {
            int CID = FindID(Echar, dfa[i].symbol);
            SLRAna[dfa[i].from][CID] = new Table('S', dfa[i].to);
        }
    }
}

public List<char> GetFollow(char c)
{
    // ... (代码逻辑不变)
}

public List<char> GetFirst(char c)
{
    // ... (代码逻辑不变)
}

问题分析:

在原始代码中，构建SLR分析表时，归约项（'r'）的位置计算有误。分析表中，终结符和非终结符拥有各自的列范围。归约项应该出现在非终结符对应的列，而原始代码错误地将其放置在了终结符的列范围内，导致显示错误。

代码修改:

在 SLRAnaly() 函数中，处理归约项的部分，将 SLRAna[Gy_itemset[i]][CID] = new Table('r', Find_pro(item)); 修改为 SLRAna[Gy_itemset[i]][CID + Echar.Count] = new Table('r', Find_pro(item));。

解释:

• Echar.Count 表示终结符的数量，因此 CID + Echar.Count 正确定位到非终结符的列范围。
• 通过将归约项放置在正确的列位置，解决了分析表显示错误的问题。

通过上述修改，SLR(1) 语法分析表构建的代码逻辑更加严谨，确保了分析表的正确性，为后续的语法分析过程提供了可靠的基础。