SLR(1)语法分析器：从LR(0)到SLR(1)的演进

从LR(0)到SLR(1)语法分析器的演进：代码实现与原理详解

本文将重点介绍如何将已有的LR(0)语法分析器代码修改为SLR(1)语法分析器。SLR(1)分析器在LR(0)的基础上引入了Follow集，能够处理更多上下文无关文法，提高了分析器的识别能力。

SLR(1)项目集的构造

SLR(1)项目集与LR(0)项目集最大的区别在于，SLR(1)项目集中的每个项目都带有一个展望符集合（LookAhead）。展望符集合用于在分析过程中进行决策，判断应该采取哪种动作（移进或规约）。

以下是SLR(1)项目集的Closure函数代码：C#public SLRitemsets Closure(SLRitemsets I){ bool changed = true; while (changed) { changed = false; List currentItems = new List(I.Container); foreach (int itemIndex in currentItems) { // 获取当前项目的点后面的符号 string right = SLRobjNum[itemIndex].Right; int dotIndex = right.IndexOf('.'); if (dotIndex < right.Length - 1 && !isFinalsymbol(right[dotIndex + 1])) { char nextSymbol = right[dotIndex + 1];

            // 计算展望符集合                HashSet<char> lookAhead = new HashSet<char>();                if (dotIndex < right.Length - 2)                {                    string beta = right.Substring(dotIndex + 2);                    lookAhead = CalculateFirst(beta + string.Join('', I.LookAhead));                }                else                {                    lookAhead = new HashSet<char>(I.LookAhead);                }

            // 扩展项目集                foreach (int j in Enumerable.Range(0, SLRobjNum.Count))                {                    if (SLRobjNum[j].Left[0] == nextSymbol && SLRobjNum[j].Right[0] == '.')                    {                        SLRitemsets newItem = new SLRitemsets                        {                            Container = new List<int> { j },                            LookAhead = lookAhead                        };

                    if (!ContainsItemset(I, newItem))                        {                            I.Container.Add(j);                            I.LookAhead.UnionWith(lookAhead);                            changed = true;                        }                    }                }            }        }    }    return I;}

SLR(1) DFA的构建

SLR(1) DFA的构建过程与LR(0) DFA类似，但是需要考虑展望符集合。C#public void CreateItemsets(){ // 初始化第一个项目集 SLRitemsets itemset0 = new SLRitemsets(); itemset0.Container.Add(0); itemset0.LookAhead.Add('#'); itemset0 = Closure(itemset0); proitemset.Add(itemset0);

// 构造所有项目集    int i = 0;    while (i < proitemset.Count)    {        foreach (char symbol in Echar.Union(Nchar))        {            SLRitemsets newItemset = Go(proitemset[i], symbol);

        if (newItemset.Container.Count > 0 && !proitemset.Contains(newItemset))            {                proitemset.Add(newItemset);                dfa[Pindex++] = new DFA(i, symbol, proitemset.Count - 1, newItemset.LookAhead);            }            else if (newItemset.Container.Count > 0)            {                dfa[Pindex++] = new DFA(i, symbol, proitemset.IndexOf(newItemset), newItemset.LookAhead);            }        }        i++;    }}

public SLRitemsets Go(SLRitemsets I, char symbol){ SLRitemsets J = new SLRitemsets(); foreach (int itemIndex in I.Container) { string right = SLRobjNum[itemIndex].Right; int dotIndex = right.IndexOf('.'); if (dotIndex < right.Length - 1 && right[dotIndex + 1] == symbol) { string newRight = right.Substring(0, dotIndex) + symbol + '.' + right.Substring(dotIndex + 2); int newItemIndex = SLRobjNum.FindIndex(item => item.Left == SLRobjNum[itemIndex].Left && item.Right == newRight); if (newItemIndex != -1) { J.Container.Add(newItemIndex); J.LookAhead = I.LookAhead; } } } J = Closure(J); return J;}

SLR(1)分析表的构造

SLR(1)分析表的构造需要根据SLR(1) DFA和Follow集来进行。C#public void CreateSLRTable(){ CreateItemsets(); CreateDFA(); SLRAna = new Table[proitemset.Count][];

for (int i = 0; i < proitemset.Count; i++)    {        SLRAna[i] = new Table[Echar.Count + Nchar.Count];        for (int j = 0; j < Echar.Count; j++)        {            char a = Echar[j];            SLRitemsets next = Go(proitemset[i], a);            if (proitemset.Contains(next))            {                SLRAna[i][j] = new Table('S', proitemset.IndexOf(next));            }        }

    for (int j = 0; j < Nchar.Count; j++)        {            char A = Nchar[j];            SLRitemsets next = Go(proitemset[i], A);            if (proitemset.Contains(next))            {                SLRAna[i][j + Echar.Count] = new Table('N', proitemset.IndexOf(next));            }        }

    if (proitemset[i].Container.Any(itemIndex => SLRobjNum[itemIndex].Right.EndsWith('.')))        {            int productionIndex = SLRproNum.FindIndex(prod => prod.Left == SLRobjNum[proitemset[i].Container.First(itemIndex => SLRobjNum[itemIndex].Right.EndsWith('.'))].Left &&                                                            prod.Right == SLRobjNum[proitemset[i].Container.First(itemIndex => SLRobjNum[itemIndex].Right.EndsWith('.'))].Right.TrimEnd('.'));

        foreach (char b in proitemset[i].LookAhead)            {                int index = Echar.IndexOf(b);                if (index != -1)                {                    SLRAna[i][index] = new Table('R', productionIndex + 1);                }                else                {                    index = Nchar.IndexOf(b);                    if (index != -1)                    {                        SLRAna[i][index + Echar.Count] = new Table('R', productionIndex + 1);                    }                }            }        }    }    Success = true