private void GetFirst(string symbol, Dictionary<string, List<string>> production1, Dictionary<string, List<string>> firsts1)
        {
            // 如果该非终结符的 FIRST 集已经被计算出,则直接返回
            if (firsts1.ContainsKey(symbol))
            {
                return;
            }
            firsts1.Add(symbol, new List<string>());
            // 遍历产生式,计算 FIRST 集
            foreach (var prod in production1[symbol])
            {
                // 如果产生式首字符为终结符,则直接将其加入 FIRST 集中
                if (prod.Length > 0 && IsTerminal(prod[0]))
                {
                    if (!firsts1[symbol].Contains(prod[0].ToString()))
                        firsts1[symbol].Add(prod[0].ToString());
                    continue;
                }
                // 如果产生式首字符为非终结符,则计算该非终结符的 FIRST 集,并将结果加入首字符的 FIRST 集中
                else if (prod.Length > 0 && !IsTerminal(prod[0]))
                {
                    GetFirst(prod[0].ToString(), production1, firsts1);
                    foreach (var f in firsts1[prod[0].ToString()])
                    {
                        if (!firsts1[symbol].Contains(f) && !f.Equals('#'))
                            firsts1[symbol].Add(f);
                    }
                }
                //如果第一个非终结符能推出#
                if (IsReachEmpty(prod[0].ToString(), production1))
                {
                    // 递归计算第二个和后面的字符的 FIRST 集,并将结果加入该非终结符的 FIRST 集中
                    for (int j = 1; j < prod.Length; j++)
                    {
                        if (IsTerminal(prod[j]))
                        {
                            if (!firsts1[symbol].Contains(prod[j].ToString()))
                                firsts1[symbol].Add(prod[j].ToString());
                            break;
                        }
                        GetFirst(prod[j].ToString(), production1, firsts1);
                        foreach (var f in firsts1[prod[j].ToString()])
                        {
                            if (!firsts1[symbol].Contains(f) && !f.Equals('#'))
                                firsts1[symbol].Add(f);
                        }
                        // 如果该非终结符的 FIRST 集没有包含空串,则可以结束循环
                        if (!IsReachEmpty(prod[j].ToString(), production1))
                        {
                            break;
                        }
                        // 如果是最后一个字符且所有非终结符的 FIRST 集都含有空串,则将空串加入该非终结符的 FIRST 集中
                        if (j == prod.Length - 1 && IsReachEmpty(prod[j].ToString(), production1))
                        {
                            if (!firsts1[symbol].Contains('#'))
                                firsts1[symbol].Add('#');
                        }
                    }
                }
            }
        }

        // 判断一个字符是否为终结符
        private bool IsTerminal(char c)
        {
            if (char.IsUpper(c))
                return false;
            if (c.Equals('#'))
                return false;
            return true;
        }

        // 判断一个非终结符是否能推出空串
        private bool IsReachEmpty(string symbol, Dictionary<string, List<string>> production1)
        {
            if (!production1.ContainsKey(symbol))
                return false;
            foreach (var prod in production1[symbol])
            {
                if (prod.Equals('#'))
                    return true;
                bool flag = true;
                for (int i = 0; i < prod.Length; i++)
                {
                    if (!IsReachEmpty(prod[i].ToString(), production1))
                    {
                        flag = false;
                        break;
                    }
                }
                if (flag)
                    return true;
            }
            return false;
        }

        // 计算 FOLLOW 集
        private void GetFollow(string symbol, Dictionary<string, List<string>> production1, Dictionary<string, List<string>> firsts1, Dictionary<string, List<string>> follows1)
        {
            // 如果该非终结符的 FOLLOW 集已经被计算出,则直接返回
            if (follows1.ContainsKey(symbol))
            {
                return;
            }
            follows1.Add(symbol, new List<string>());
            // 如果是起始符号,则将 $ 加入 FOLLOW 集中
            if (symbol.Equals(production1.Keys.First()))
            {
                if (!follows1[symbol].Contains('$'))
                    follows1[symbol].Add('$');
            }
            // 遍历产生式,计算 FOLLOW 集
            foreach (var item in production1)
            {
                foreach (var prod in item.Value)
                {
                    int index = prod.IndexOf(symbol);
                    if (index == -1)
                        continue;
                    // 如果该非终结符位于产生式末尾,则将产生式左部的 FOLLOW 集加入该非终结符的 FOLLOW 集中
                    if (index == prod.Length - 1)
                    {
                        GetFollow(item.Key, production1, firsts1, follows1);
                        foreach (var f in follows1[item.Key])
                        {
                            if (!follows1[symbol].Contains(f))
                                follows1[symbol].Add(f);
                        }
                    }
                    else
                    {
                        // 如果该非终结符后面是终结符,则将该终结符加入该非终结符的 FOLLOW 集中
                        if (IsTerminal(prod[index + 1]))
                        {
                            if (!follows1[symbol].Contains(prod[index + 1].ToString()))
                                follows1[symbol].Add(prod[index + 1].ToString());
                        }
                        // 如果该非终结符后面是非终结符,则将该非终结符的 FIRST 集加入该非终结符的 FOLLOW 集中
                        else
                        {
                            GetFirst(prod[index + 1].ToString(), production1, firsts1);
                            foreach (var f in firsts1[prod[index + 1].ToString()])
                            {
                                if (!f.Equals('#') && !follows1[symbol].Contains(f))
                                    follows1[symbol].Add(f);
                            }
                            // 如果该非终结符后面的所有符号都能推出空串,则将产生式左部的 FOLLOW 集加入该非终结符的 FOLLOW 集中
                            if (IsReachEmpty(prod[index + 1].ToString(), production1))
                            {
                                GetFollow(item.Key, production1, firsts1, follows1);
                                foreach (var f in follows1[item.Key])
                                {
                                    if (!follows1[symbol].Contains(f))
                                        follows1[symbol].Add(f);
                                }
                            }
                        }
                    }
                }
            }
        }

        // 判断一个文法是否是 LL(1) 文法
        private bool JudgeLL1(Dictionary<string, List<string>> production1, Dictionary<string, List<string>> firsts1, Dictionary<string, List<string>> follows1)
        {
            foreach (var item in production1)
            {
                Dictionary<string, List<string>> map = new Dictionary<string, List<string>>();
                foreach (var prod in item.Value)
                {
                    List<string> list = new List<string>();
                    foreach (var c in prod)
                    {
                        if (IsTerminal(c))
                        {
                            list.Add(c.ToString());
                            break;
                        }
                        else
                        {
                            GetFirst(c.ToString(), production1, firsts1);
                            foreach (var f in firsts1[c.ToString()])
                            {
                                if (!f.Equals('#') && !list.Contains(f))
                                    list.Add(f);
                            }
                            if (!IsReachEmpty(c.ToString(), production1))
                                break;
                        }
                    }
                    if (list.Contains('#'))
                    {
                        GetFollow(item.Key, production1, firsts1, follows1);
                        foreach (var f in follows1[item.Key])
                        {
                            if (!list.Contains(f))
                                list.Add(f);
                        }
                    }
                    string key = string.Join("", list.ToArray());
                    if (map.ContainsKey(key))
                        return false;
                    map.Add(key, list);
                }
            }
            return true;
        }

该代码实现了以下功能:

  1. 计算 FIRST 集:GetFirst 函数用于计算每个非终结符的 FIRST 集,并处理可能出现的空串情况。
  2. 计算 FOLLOW 集:GetFollow 函数用于计算每个非终结符的 FOLLOW 集,并处理产生式末尾以及非终结符后面可能出现空串的情况。
  3. 判断 LL(1) 文法:JudgeLL1 函数通过判断每个非终结符的 FIRST 集和 FOLLOW 集是否相互交集为空来判断文法是否为 LL(1) 文法。

该代码示例展示了如何利用 FIRST 集和 FOLLOW 集来判断一个文法是否为 LL(1) 文法,可以作为学习编译原理和文法分析的参考。

LL(1) 文法判断算法:FIRST 集、FOLLOW 集计算与判别

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

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