• 日期: 2024-11-28
  • 标签: 常规

SLR 文法分析表构造 - 详解及代码实现

本篇文章将深入探讨 SLR 文法分析表的构造过程，并提供详细的代码实现，帮助读者理解如何利用 SLR 算法构建分析表，以及如何处理移进-归约冲突和归约-归约冲突。

关键步骤

  1. 构建项目集族：通过对产生式进行扩展，生成项目集族，每个项目集代表分析过程中的一个状态。
  2. 构造 DFA：利用项目集族，构建 DFA（确定有限自动机），每个状态对应一个项目集，每个转移对应一个终结符或非终结符。
  3. 构建 Follow 集：计算每个非终结符的 Follow 集，用于判断归约时应采取的动作。
  4. 构建 SLR 分析表：根据项目集族、DFA 和 Follow 集，构建 SLR 分析表，表中每个元素对应一个状态和一个输入符号，决定应执行的操作（移进、归约或接受）。

代码实现

// SLRNode 类表示一个产生式，包含左部和右部
public class SLRNode
{
    public string Left;
    public string Right;
    public SLRNode(string Left, string Right)
    {
        this.Left = Left;
        this.Right = Right;
    }
}

// SLRitemsets 类表示一个项目集，包含一个项目列表
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;
    }
}

// ... 其他代码 ...

// SLR 分析函数
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) // 遍历项目集中的项目
        {
            SLRNode node = SLRobjNum[item];
            if (node.Right != "#") // 不是空产生式
            {
                char last = node.Right[node.Right.Length - 1]; // 取出最后一个符号
                if (isFinalsymbol(last)) // 最后一个符号是终结符
                {
                    int CID = FindID(Echar, last);
                    if (SLRAna[Gy_itemset[i]][CID].error) // 没有冲突
                    {
                        tnode = new Table('r', Find_pro(node)); // 添加状态 r
                        SLRAna[Gy_itemset[i]][CID] = tnode;
                    }
                    else // 冲突
                    {
                        RStr_ANA += "移进-归约冲突：" + Gy_itemset[i].ToString() + "," + last.ToString() + "\r\n";
                    }
                }
                else // 最后一个符号是非终结符
                {
                    int CID = FindID(Nchar, last);
                    if (SLRAna[Gy_itemset[i]][CID + Echar.Count].error) // 没有冲突
                    {
                        tnode = new Table('r', Find_pro(node)); // 添加状态 r
                        SLRAna[Gy_itemset[i]][CID + Echar.Count] = tnode;
                    }
                    else // 冲突
                    {
                        RStr_ANA += "移进-归约冲突：" + Gy_itemset[i].ToString() + "," + last.ToString() + "\r\n";
                    }
                }
            }
            else // 是空产生式
            {
                foreach (char c in Follow(node.Left)) // 遍历左部符号的 Follow 集
                {
                    int CID;
                    if (isFinalsymbol(c)) // 是终结符
                    {
                        CID = FindID(Echar, c);
                        if (SLRAna[Gy_itemset[i]][CID].error) // 没有冲突
                        {
                            tnode = new Table('r', Find_pro(node)); // 添加状态 r
                            SLRAna[Gy_itemset[i]][CID] = tnode;
                        }
                        else // 冲突
                        {
                            RStr_ANA += "移进-归约冲突：" + Gy_itemset[i].ToString() + "," + c.ToString() + "\r\n";
                        }
                    }
                    else // 是非终结符
                    {
                        CID = FindID(Nchar, c);
                        if (SLRAna[Gy_itemset[i]][CID + Echar.Count].error) // 没有冲突
                        {
                            tnode = new Table('r', Find_pro(node)); // 添加状态 r
                            SLRAna[Gy_itemset[i]][CID + Echar.Count] = tnode;
                        }
                        else // 冲突
                        {
                            RStr_ANA += "移进-归约冲突：" + Gy_itemset[i].ToString() + "," + c.ToString() + "\r\n";
                        }
                    }
                }
            }
        }
    }

    for (int i = 0; i < Pindex; i++) // 移进项目
    {
        if (isFinalsymbol(dfa[i].symbol)) // symbol 为非终结符
        {
            int CID = FindID(Nchar, dfa[i].symbol);
            if (SLRAna[dfa[i].from][CID + Echar.Count].error) // 没有冲突
            {
                tnode = new Table('N', dfa[i].to);
                SLRAna[dfa[i].from][CID + Echar.Count] = tnode;
            }
            else // 冲突
            {
                RStr_ANA += "归约-归约冲突：" + dfa[i].from.ToString() + "," + dfa[i].symbol.ToString() + "\r\n";
            }
        }
        else // 不是归约项目
        {
            int CID = FindID(Echar, dfa[i].symbol);
            if (SLRAna[dfa[i].from][CID].error) // 没有冲突
            {
                tnode = new Table('S', dfa[i].to);
                SLRAna[dfa[i].from][CID] = tnode;
            }
            else // 冲突
            {
                RStr_ANA += "移进-移进冲突：" + dfa[i].from.ToString() + "," + dfa[i].symbol.ToString() + "\r\n";
            }
        }
    }
}

// Follow 集构造函数
public void FollowConstruct()
{
    FollowSet = new List<char>[Nchar.Count];
    for (int i = 0; i < Nchar.Count; i++)
        FollowSet[i] = new List<char>();

    FollowSet[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++) // 遍历产生式的右部
            {
                char c = right[j];
                if (isFinalsymbol(c)) // 是终结符，跳过
                    continue;
                int index = FindID(Nchar, c);
                string tmp = right.Substring(j + 1);
                if (tmp.Length == 0) // A->αB
                {
                    foreach (char ch in FollowSet[i]) // 将 Follow(A) 加入 Follow(B)
                    {
                        if (!FollowSet[index].Contains(ch))
                        {
                            FollowSet[index].Add(ch);
                            changed = true;
                        }
                    }
                }
                else // A->αBβ
                {
                    List<char> first = First(tmp + FollowSet[i]); // 求出 First(βFollow(A))
                    foreach (char ch in first) // 将 First(βFollow(A)) 加入 Follow(B)
                    {
                        if (!FollowSet[index].Contains(ch))
                        {
                            FollowSet[index].Add(ch);
                            changed = true;
                        }
                    }
                }
            }
        }
    }
}

// ... 其他相关函数 ...

应对冲突

SLR 算法可能会遇到移进-归约冲突和归约-归约冲突。

  • 移进-归约冲突：在某些情况下，对于同一个状态和同一个输入符号，分析表中既包含移进动作，也包含归约动作。这种情况通常是因为存在歧义的语法规则。解决方法是使用更强大的分析方法，例如 LALR 或 LR(1)。
  • 归约-归约冲突：在某些情况下，对于同一个状态和同一个输入符号，分析表中包含多个归约动作。这种情况通常是因为语法规则存在重复。解决方法是修改语法规则，消除重复。

小结

本文详细介绍了 SLR 文法分析表的构造过程，并提供了关键代码实现。读者可以通过学习本文内容，掌握 SLR 算法的原理，并了解如何构建分析表以及如何处理冲突。SLR 算法是编译器构造中常用的分析方法，对理解编译原理具有重要意义。

SLR 文法分析表构造 - 详解及代码实现

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

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