LL(1) First & Follow C# edition

FF.cs

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace MyLL1
{
    public interface IRule
    {
        string Name { get; }
    }

    public class Token : IRule
    {
        public string Name { get; }

        public Token(string name)
        {
            Name = name;
        }

        public override string ToString()
        {
            return Name;
        }

        public static Token Eof = new Token("$");
        public static Token Empty = new Token("?");
    }

    public class Rule : IRule
    {
        public string Name { get; }

        public IEnumerable<IEnumerable<IRule>> Definitions { get; }

        public Rule(string name, IEnumerable<IEnumerable<IRule>> definitions)
        {
            Name = name;
            Definitions = definitions;
        }

        public override string ToString()
        {
            return $"{Name}->" + string.Join("/", Definitions.Select(definition =>
                string.Join("", definition.Select(rule => rule.Name))
                ));
        }
    }

    public class RuleManager
    {
        public List<Rule> Rules { get; } = new List<Rule>();

        private Dictionary<string, Token> TokenMap = new Dictionary<string, Token>();

        private Token GetOrCreateToken(string tokenName)
        {
            if (tokenName == "$")
                return Token.Eof;
            if (tokenName == "?")
                return Token.Empty;
            if (!TokenMap.ContainsKey(tokenName))
                TokenMap.Add(tokenName, new Token(tokenName));
            return TokenMap[tokenName];
        }

        public Rule CreateTextRule(string text)
        {
            var segments = text.Split(new[] { "->" }, StringSplitOptions.None);
            var name = segments[0];
            var ruleText = segments[1];

            var ruleDefinitions = ruleText
                .Split('/')
                .Select(ruleSequenceText =>
                {
                    return ruleSequenceText.Select(token =>
                    {
                        return char.IsUpper(token) ?
                            Rules.First(x => x.Name == token.ToString()) :
                            (IRule)GetOrCreateToken(token.ToString());
                    });
                });
            return new Rule(name, ruleDefinitions);
        }

        public IEnumerable<Token> First(IEnumerable<IEnumerable<IRule>> definitions)
        {
            return definitions.SelectMany(ruleSequence =>
            {
                var tokens = new List<Token>();
                var hasEmpty = true;
                foreach (var item in ruleSequence)
                {
                    if (item is Token token)
                    {
                        if (token != Token.Empty)
                        {
                            hasEmpty = false;
                            tokens.Add(token);
                            break;
                        }
                    }
                    else if (item is Rule rule)
                    {
                        var ruleFirsts = First(rule.Definitions);
                        if (!ruleFirsts.Contains(Token.Empty))
                        {
                            hasEmpty = false;
                            tokens.AddRange(ruleFirsts);
                            break;
                        }
                        else
                        {
                            tokens.AddRange(ruleFirsts.Where(x => x != Token.Empty));
                        }
                    }
                }
                if (hasEmpty) tokens.Add(Token.Empty);
                return tokens;
            })
            .Distinct();
        }

        public IEnumerable<Token> Follow(Rule theRule)
        {
            return Rules
                .SelectMany(knownRule =>
                {
                    return knownRule.Definitions
                        .Where(ruleSequence => ruleSequence.Contains(theRule))
                        .SelectMany(relatedSequence =>
                        {   
                            var tokens = new List<Token>();
                            do
                            {
                                relatedSequence = relatedSequence
                                    .SkipWhile(x => x != theRule)
                                    .Skip(1);

                                if (relatedSequence.Any())
                                {
                                    var firsts = First(new[] { relatedSequence });
                                    tokens.AddRange(firsts.Where(x => x != Token.Empty));
                                    if (firsts.Contains(Token.Empty))
                                    {
                                        tokens.AddRange(Follow(knownRule));
                                    }
                                }
                                else if (knownRule != theRule)
                                {
                                    tokens.AddRange(Follow(knownRule));
                                }
                            } while (relatedSequence.Contains(theRule));
                            return tokens;
                        });
                })
                .DefaultIfEmpty(Token.Eof)
                .Distinct();
        }

        public void DumpFF()
        {
            foreach (Rule rule in Rules)
            {
                Console.Write($"{rule, -15}");
                Console.Write("{0, -15}", string.Join(",", First(rule.Definitions)));
                Console.Write("{0, -15}", string.Join(",", Follow(rule)));
                Console.WriteLine();
            }
        }
    }


    class Program
    {
        static void Main(string[] args)
        {
            var rm = new RuleManager();

            //rm.Rules.Add(rm.CreateTextRule("S->ACB/CbB/Ba"));
            //rm.Rules.Add(rm.CreateTextRule("A->da/BC"));
            //rm.Rules.Add(rm.CreateTextRule("B->g/?"));
            //rm.Rules.Add(rm.CreateTextRule("C->h/?"));

            rm.Rules.Add(rm.CreateTextRule("S->(S)/?"));

            rm.DumpFF();
        }
    }
}

UnitTest.cs

using System;
using System.Collections.Generic;
using System.Linq;
using Xunit;

namespace MyLL1.test
{
    public class UnitTest1
    {
        [Fact]
        public void Test1()
        {
            var ffList = new List<FirstFollow>
            {
                new FirstFollow("S->ABCDE", "a,b,c", "$"),
                new FirstFollow("A->a/?", "a,?", "b,c"),
                new FirstFollow("B->b/?", "b,?", "c"),
                new FirstFollow("C->c", "c", "d,e,$"),
                new FirstFollow("D->d/?", "d,?", "e,$"),
                new FirstFollow("E->e/?", "e,?", "$"),
            };
            Check(ffList);
        }

        [Fact]
        public void Test2()
        {
            var ffList = new List<FirstFollow>
            {
                new FirstFollow("S->Bb/Cd", "a,b,c,d", "$"),
                new FirstFollow("B->aB/?", "a,?", "b"),
                new FirstFollow("C->cC/?", "c,?", "d"),
            };
            Check(ffList);
        }

        [Fact]
        public void Test3()
        {
            var ffList = new List<FirstFollow>
            {
                new FirstFollow("S->ACB/CbB/Ba", "d,g,h,?,b,a", "$"),
                new FirstFollow("A->da/BC", "d,g,h,?", "h,g,$"),
                new FirstFollow("B->g/?", "g,?", "$,a,h,g"),
                new FirstFollow("C->h/?", "h,?", "g,$,b,h"),
            };
            Check(ffList);
        }

        [Fact]
        public void Test4()
        {
            var ffList = new List<FirstFollow>
            {
                new FirstFollow("S->aABb", "a", "$"),
                new FirstFollow("A->c/?", "c,?", "d,b"),
                new FirstFollow("B->d/?", "d,?", "b"),
            };
            Check(ffList);
        }

        [Fact]
        public void Test5()
        {
            var ffList = new List<FirstFollow>
            {
                new FirstFollow("S->aBDh", "a", "$"),
                new FirstFollow("B->cC", "c", "g,f,h"),
                new FirstFollow("C->bC/?", "b,?", "g,f,h"),
                new FirstFollow("D->EF", "g,f,?", "h"),
                new FirstFollow("E->g/?", "g,?", "f,h"),
                new FirstFollow("F->f/?", "f,?", "h"),
            };
            Check(ffList);
        }

        [Fact]
        public void Test6()
        {
            var ffList = new List<FirstFollow>
            {
                new FirstFollow("A->BaBb", "c", "$"),
                new FirstFollow("B->c", "c", "a,b")
            };
            Check(ffList);
        }

        public void Check(List<FirstFollow> rulesAndResults)
        {
            var rm = new RuleManager();
            foreach (var rule in rulesAndResults)
            {
                rm.Rules.Add(rm.CreateTextRule(rule.RuleName));
            }

            var results = DumpFirstFollows(rm).ToList();
            for (var i = 0; i < results.Count; ++i)
            {
                Assert.Equal(rulesAndResults[i].First, results[i].First);
                Assert.Equal(rulesAndResults[i].Follow, results[i].Follow);
            }
        }

        public IEnumerable<FirstFollow> DumpFirstFollows(RuleManager rm)
        {
            return rm.Rules
                .Select(x => new FirstFollow(
                    x.Name,
                    string.Join(",", rm.First(x.Definitions)),
                    string.Join(",", rm.Follow(x))
                    ));
        }
    }

    public class FirstFollow
    {
        public string RuleName { get; set; }

        public string First { get; set; }

        public string Follow { get; set; }

        public FirstFollow(string ruleName, string first, string follow)
        {
            RuleName = ruleName;
            First = first;
            Follow = follow;
        }

        public bool Match(FirstFollow other)
        {
            return RuleName == other.RuleName &&
                First == other.First &&
                Follow == other.Follow;
        }
    }
}