• 日期: 2025-09-17
  • 标签: 常规
class SLR
    {
        //产生式结点类
        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 class Analyze
        {
            public List<string> stack_state = new List<string>(100);//记录状态栈
            public List<string> stack_symbol = new List<string>(100);//记录符号栈
            public List<string> Input_str = new List<string>(100);//记录输入串
            public List<string> Tran_pro = new List<string>(100);//记录所用产生式
        }

        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>> follow = new Dictionary<char, HashSet<char>>();//非终结符的Follow集

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

        public void Buildprod(string str)//构造项目
        {
            
        }

        public void Creteitemsets()//项目集构建
        {
            
        }

public Table[][] GET_ANA(){}//获取LR0分析表

public void SLRAnaly(){}//构造分析表

public void sen_Analyze(string text){}//分析句子


      
        //构造项目 在right[index]位置插入'.'
        public string CreObj(string right, int index)
        {
            int i = 0;
            string Restr = '';
            while (i < right.Length)
            {
                if (i == index)
                    Restr += '.';

                Restr += right[i];
                i++;
            }
            if (i == index)
                Restr += '.';
            return Restr;
        }

        //判断ch是否为非终结符
        public bool isFinalsymbol(char ch1)
        {
            //char ch1=ch[0];
            if (ch1 >= 'A' && ch1 <= 'Z')
                return true;
            else
                return false;
        }


        //判断集合是I否存在于proitemset
        //如果存在就返回已存在的项目集序号 
        //如果不存在就返回-1
        public int isexist(List<int> I)
        {
            I.Sort();
            for (int i = 0; i < proitemset.Count; i++)
            {
                proitemset[i].Container.Sort();
                if (I.SequenceEqual(proitemset[i].Container))
                {
                    return i;
                }
            }
            return -1;

        }

        //判断num是否存在于I
        //存在返回true 不存在返回False
        public bool isnexist(List<int> I, int num)
        {
            for (int i = 0; i < I.Count; i++)
            {
                if (I[i] == num)
                    return true;
            }
            return false;
        }

        //判断ch是否存在于I
        //存在返回true 不存在返回False
        public bool exist(List<char> I, char ch)
        {
            for (int i = 0; i < I.Count; i++)
            {
                if (I[i] == ch)
                    return true;

            }
            return false;
        }
        //寻找ch在I中的序号
        public int FindID(List<char> I, char ch)
        {
            for (int i = 0; i < I.Count; i++)
            {
                if (I[i] == ch)
                    return i;

            }
            return -1;
        }

        //寻找项目最初的产生式序号  E->.ab  ====>  E->a
        public int Find_pro(SLRNode SLR)
        {
            string s = '';
            for (int i = 0; i < SLR.Right.Length; i++)
            {
                if (SLR.Right[i] != '.')
                    s += SLR.Right[i];
            }
            for (int i = 0; i < SLRproNum.Count; i++)
            {
                if (SLRproNum[i].Left == SLR.Left && SLRproNum[i].Right == s)
                    return i;
            }
            return -1;
        }

    }

}

//构造项目 在right[index]位置插入'.'
public string CreObj(string right, int index)
{
    int i = 0;
    string Restr = '';
    while (i < right.Length)
    {
        if (i == index)
            Restr += '.';

        Restr += right[i];
        i++;
    }
    if (i == index)
        Restr += '.';
    return Restr;
}

//判断ch是否为非终结符
public bool isFinalsymbol(char ch1)
{
    //char ch1=ch[0];
    if (ch1 >= 'A' && ch1 <= 'Z')
        return true;
    else
        return false;
}

//判断集合是I否存在于proitemset
//如果存在就返回已存在的项目集序号 
//如果不存在就返回-1
public int isexist(List<int> I)
{
    I.Sort();
    for (int i = 0; i < proitemset.Count; i++)
    {
        proitemset[i].Container.Sort();
        if (I.SequenceEqual(proitemset[i].Container))
        {
            return i;
        }
    }
    return -1;

}

//判断num是否存在于I
//存在返回true 不存在返回False
public bool isnexist(List<int> I, int num)
{
    for (int i = 0; i < I.Count; i++)
    {
        if (I[i] == num)
            return true;
    }
    return false;
}

//判断ch是否存在于I
//存在返回true 不存在返回False
public bool exist(List<char> I, char ch)
{
    for (int i = 0; i < I.Count; i++)
    {
        if (I[i] == ch)
            return true;

    }
    return false;
}
//寻找ch在I中的序号
public int FindID(List<char> I, char ch)
{
    for (int i = 0; i < I.Count; i++)
    {
        if (I[i] == ch)
            return i;

    }
    return -1;
}

//寻找项目最初的产生式序号  E->.ab  ====>  E->a
public int Find_pro(SLRNode SLR)
{
    string s = '';
    for (int i = 0; i < SLR.Right.Length; i++)
    {
        if (SLR.Right[i] != '.')
            s += SLR.Right[i];
    }
    for (int i = 0; i < SLRproNum.Count; i++)
    {
        if (SLRproNum[i].Left == SLR.Left && SLRproNum[i].Right == s)
            return i;
    }
    return -1;
}

//获取非终结符的Follow集
public HashSet<char> GetFollow(char ch)
{
    if (follow.ContainsKey(ch))
        return follow[ch];

    HashSet<char> set = new HashSet<char>();
    if (ch == 'S')
        set.Add('$');

    foreach (SLRNode node in SLRproNum)
    {
        string right = node.Right;
        int index = right.IndexOf(ch);
        if (index < 0)
            continue;

        if (index == right.Length - 1)
        {
            if (node.Left != ch)
            {
                HashSet<char> next = GetFollow(node.Left);
                set.UnionWith(next);
            }
        }
        else
        {
            char next = right[index + 1];
            if (isFinalsymbol(next))
                set.Add(next);
            else
            {
                HashSet<char> first = GetFirst(next);
                set.UnionWith(first);
                if (exist(first, '#'))
                {
                    if (node.Left != ch)
                    {
                        HashSet<char> next_follow = GetFollow(node.Left);
                        set.UnionWith(next_follow);
                    }
                }
            }
        }
    }
    follow[ch] = set;
    return set;
}

//获取非终结符的First集
public HashSet<char> GetFirst(char ch)
{
    HashSet<char> set = new HashSet<char>();
    if (isFinalsymbol(ch))
    {
        set.Add(ch);
        return set;
    }

    foreach (SLRNode node in SLRproNum)
    {
        if (node.Left != ch)
            continue;

        string right = node.Right;
        int i = 0;
        while (i < right.Length)
        {
            char c = right[i];
            HashSet<char> first = GetFirst(c);
            set.UnionWith(first);
            if (!exist(first, '#'))
                break;
            i++;
        }
        if (i == right.Length)
            set.Add('#');
    }
    return set;
}

//构造产生式
public void Buildprod(string str)
{
    string[] strs = str.Split(new char[] { '\r', '\n' }, StringSplitOptions.RemoveEmptyEntries);
    int index = 0;
    foreach (string s in strs)
    {
        string[] arr = s.Split(new char[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries);
        string left = arr[0];
        string right = '';
        for (int i = 2; i < arr.Length; i++)
            right += arr[i];
        SLRNode node = new SLRNode(left, right);
        SLRproNum.Add(node);
        string obj = CreObj(right, 0);
        SLRNode objnode = new SLRNode(left, obj);
        SLRobjNum.Add(objnode);
        index++;
    }
}

//构造项目集
public void Creteitemsets()
{
    SLRitemsets itemset = new SLRitemsets();
    itemset.Container.Add(0);
    proitemset.Add(itemset);
    int index = 0;
    while (index < proitemset.Count)
    {
        SLRitemsets I = proitemset[index];
        List<int> Container = I.Container;
        Dictionary<char, List<int>> dict = new Dictionary<char, List<int>>();
        foreach (int i in Container)
        {
            SLRNode node = SLRobjNum[i];
            string right = node.Right;
            int dot_index = right.IndexOf('.');
            if (dot_index == right.Length - 1)
                continue;
            char symbol = right[dot_index + 1];
            if (!dict.ContainsKey(symbol))
                dict[symbol] = new List<int>();
            dict[symbol].Add(i + 1);
        }

        foreach (KeyValuePair<char, List<int>> kvp in dict)
        {
            List<int> J = kvp.Value;
            int exist_index = isexist(J);
            if (exist_index < 0)
            {
                SLRitemsets newitemset = new SLRitemsets();
                newitemset.Container = J;
                proitemset.Add(newitemset);
                exist_index = proitemset.Count - 1;
            }
            dfa[Pindex] = new DFA(index, kvp.Key, exist_index);
            Pindex++;
        }
        index++;
    }
}

//获取LR0分析表
public Table[][] GET_ANA()
{
    int row = proitemset.Count;
    int col = Echar.Count + Nchar.Count;
    Table[][] table = new Table[row][];
    for (int i = 0; i < row; i++)
    {
        table[i] = new Table[col];
        for (int j = 0; j < col; j++)
        {
            table[i][j] = new Table();
        }
    }

    foreach (SLRNode node in SLRobjNum)
    {
        int i = isexist(proitemset[0].Container);
        string right = node.Right;
        if (right[right.Length - 1] == '.')
        {
            int j = Find_pro(node);
            foreach (char ch in Gy_obj)
            {
                int col_index = FindID(Echar, ch);
                table[i][col_index] = new Table('r', j);
            }
            if (node.Left == 'S')
                table[i][col - 1] = new Table('a', -1);
        }
    }

    for (int i = 0; i < proitemset.Count; i++)
    {
        List<int> I = proitemset[i].Container;
        foreach (char ch in Echar)
        {
            int col_index = FindID(Echar, ch);
            List<int> J = new List<int>();
            foreach (int num in I)
            {
                SLRNode node = SLRobjNum[num];
                string right = node.Right;
                int index = right.IndexOf('.');
                if (index + 1 >= right.Length)
                    continue;
                if (right[index + 1] == ch)
                {
                    J.Add(num + 1);
                }
            }

            if (J.Count == 0)
                continue;

            int exist_index = isexist(J);
            if (exist_index >= 0)
            {
                table[i][col_index] = new Table('s', exist_index);
            }
        }

        foreach (char ch in Nchar)
        {
            int col_index = FindID(Nchar, ch) + Echar.Count;
            List<int> J = new List<int>();
            foreach (int num in I)
            {
                SLRNode node = SLRobjNum[num];
                string right = node.Right;
                int index = right.IndexOf('.');
                if (index + 1 >= right.Length)
                    continue;
                if (right[index + 1] == ch)
                {
                    J.Add(num + 1);
                }
            }

            if (J.Count == 0)
                continue;

            int exist_index = isexist(J);
            if (exist_index >= 0)
            {
                table[i][col_index] = new Table('g', exist_index);
            }
        }
    }

    SLRAna = table;
    return table;
}

//构造SLR分析表
public void SLRAnaly()
{
    Buildprod(RStr);
    Echar.Add('#');
    foreach (SLRNode node in SLRproNum)
    {
        string left = node.Left;
        if (!exist(Nchar, left[0]))
            Nchar.Add(left[0]);
    }

    foreach (SLRNode node in SLRobjNum)
    {
        string right = node.Right;
        int index = right.IndexOf('.');
        if (index + 1 >= right.Length)
        {
            int j = Find_pro(node);
            Gy_obj.Add(j);
        }
    }

    Creteitemsets();
    GET_ANA();
}

//分析句子
public void sen_Analyze(string text)
{
    RStr_obitemset = '';
    RStr_DFA = '';
    RStr_ANA = '';
    Jz = new Analyze();
    Jz.stack_state.Add('0');
    Jz.Input_str = text.Split(' ').ToList();
    Jz.Input_str.Add('$');
    Jz.stack_symbol.Add('$');
    int index = 0;
    while (true)
    {
        string state = Jz.stack_state[Jz.stack_state.Count - 1];
        string symbol = Jz.Input_str[index];
        int row = int.Parse(state);
        int col = FindID(Echar, symbol[0]);
        if (col < 0)
            col = FindID(Nchar, symbol[0]) + Echar.Count;

        Table table = SLRAna[row][col];
        if (table.error)
        {
            Success = false;
            break;
        }
        if (table.type == 's')
        {
            Jz.stack_state.Add(table.id.ToString());
            Jz.stack_symbol.Add(symbol);
            index++;
        }
        else if (table.type == 'r')
        {
            SLRNode node = SLRproNum[table.id];
            int len = node.Right.Length;
            if (len > 1)
            {
                Jz.stack_state.RemoveRange(Jz.stack_state.Count - len, len);
                Jz.stack_symbol.RemoveRange(Jz.stack_symbol.Count - len, len);
            }

            string top_state = Jz.stack_state[Jz.stack_state.Count - 1];
            int top_row = int.Parse(top_state);
            string left = node.Left;
            int col_index = FindID(Nchar, left[0]) + Echar.Count;
            Table newtable = SLRAna[top_row][col_index];
            Jz.Tran_pro.Add(node.Left + '->' + node.Right);
            Jz.stack_symbol.Add(left);
            Jz.stack_state.Add(newtable.id.ToString());
        }
        else if (table.type == 'a')
        {
            Success = true;
           
        }
    }
}
SLR1 分析器构建代码及功能实现 - C# 示例

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

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