LR(0)和SLR(1)分析表构造算法及代码实现

LR(0)和SLR(1)分析表构造算法及代码实现

本文介绍了LR(0)和SLR(1)分析表的构造算法，并提供了C#代码实现。

LR(0)分析表构造算法回顾C#public Table[][] GET_ANA(){ LRAnaly(); RStr_ANA += '\r\nLR0分析表:\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 (LRAna[i][j].error)            {                RStr_ANA += '  ' + '    ';            }            else if (i == 1 && j == Echar.Count - 1)            {                RStr_ANA += 'AC' + '    ';            }            else if (LRAna[i][j].type != 'N')            {                RStr_ANA += LRAna[i][j].type.ToString() + LRAna[i][j].id.ToString() + '    ';            }            else                RStr_ANA += LRAna[i][j].id.ToString() + '    ';        }        RStr_ANA += '\r\n';    }

return LRAna;

}

public void LRAnaly(){ Table tnode = new Table();

LRAna = new Table[proitemset.Count][];    for (int i = 0; i < proitemset.Count; i++)        LRAna[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状态             LRAna[i][j] = tnode;

tnode = new Table('A', 0);    LRAna[1][FindID(Echar, '#')] = tnode;//项目集1必定是接受项目   构建[1][#]:acc的情况 先直接赋值好 dfa里没有

for (int i = 0; i < Gy_itemset.Count; i++)    {        tnode = new Table('r', Find_pro(LRobjNum[proitemset[Gy_itemset[i]].Container[0]]));//归约项目 找到原产生式序号 添加状态r        for (int j = 0; j < Echar.Count; j++)        {            LRAna[Gy_itemset[i]][j] = tnode;        }    }    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);            LRAna[dfa[i].from][CID + Echar.Count] = tnode;        }        else //不是归约项目 添加状态S        {            int CID = FindID(Echar, dfa[i].symbol);            tnode = new Table('S', dfa[i].to);            LRAna[dfa[i].from][CID] = tnode;        }

}}

SLR(1)分析表构造算法

SLR(1)分析表构造算法是在LR(0)分析表的基础上，利用Follow集解决移进-归约冲突和归约-归约冲突。

SLR(1)分析表构造函数SLRAnaly()C#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++)        for (int j = 0; j < Echar.Count + Nchar.Count; j++)            SLRAna[i][j] = tnode;

tnode = new Table('A', 0);    SLRAna[1][FindID(Echar, '#')] = tnode;

for (int i = 0; i < Gy_itemset.Count; i++)    {        SLRNode node = SLRobjNum[proitemset[Gy_itemset[i]].Container[0]];        char left = node.Left;        List<char> follow = FOLLOW(left);        foreach (char c in follow)        {            int CID = FindID(Echar, c);            Table temp = new Table('r', Find_pro(node));            SLRAna[Gy_itemset[i]][CID] = temp;        }    }

for (int i = 0; i < Pindex; i++)    {        if (isFinalsymbol(dfa[i].symbol))        {            int CID = FindID(Nchar, dfa[i].symbol);            SLRNode node = SLRobjNum[proitemset[dfa[i].from].Container[0]];            List<char> follow = FOLLOW(node.Left);            foreach (char c in follow)            {                int index = FindID(Echar, c);                Table temp = new Table('N', dfa[i].to);                SLRAna[dfa[i].from][index + Echar.Count] = temp;            }        }        else         {            int CID = FindID(Echar, dfa[i].symbol);            Table temp = new Table('S', dfa[i].to);            SLRAna[dfa[i].from][CID] = temp;        }    }}

Follow集构造函数FOLLOW()C#public List FOLLOW(char c){ List follow = new List(); if (c == SLRproNum[0].Left) { follow.Add('#'); } for (int i = 0; i < SLRproNum.Count; i++) { SLRNode node = SLRproNum[i]; for (int j = 0; j < node.Right.Length; j++) { if (node.Right[j] == c) { if (j == node.Right.Length - 1) { if (node.Left != c) { List temp = FOLLOW(node.Left); follow.AddRange(temp); } } else { List temp = FIRST1(node.Right.Substring(j + 1)); if (temp.Contains('#')) { temp.Remove('#'); List temp2 = FOLLOW(node.Left); temp.AddRange(temp2); } follow.AddRange(temp); } } } } follow = follow.Distinct().ToList(); return follow;}

First1集构造函数FIRST1()C#public List FIRST1(string str){ List first = new List(); if (str.Length == 0) { first.Add('#'); return first; } else if (str.Length == 1) { if (isFinalsymbol(str[0])) { first.Add(str[0]); return first; } else { first = FIRST1_pro(str[0]); return first; } } else { if (isFinalsymbol(str[0])) { first.Add(str[0]); return first; } else { first = FIRST1_pro(str[0]); if (first.Contains('#')) { first.Remove('#'); List temp = FIRST1(str.Substring(1)); first.AddRange(temp); } return first; } }}

FIRST1_pro()函数C#public List FIRST1_pro(char c){ List first = new List(); for (int i = 0; i < SLRproNum.Count; i++) { if (SLRproNum[i].Left == c) { if (SLRproNum[i].Right == '#') { first.Add('#'); } else if (isFinalsymbol(SLRproNum[i].Right[0])) { first.Add(SLRproNum[i].Right[0]); } else { List temp = FIRST1(SLRproNum[i].Right); first.AddRange(temp); } } } return first;}

总结

本文介绍了LR(0)和SLR(1)分析表的构造算法，并提供了C#代码实现。SLR(1)分析表构造算法利用Follow集解决了LR(0)分析表中存在的移进-归约冲突和归约-归约冲突问题，可以应用于更广泛的文法。