<commit_before># 
#   GrammarChecker usage:
#   Finds the LL(1) First, Follow, Parse Table of a grammar.
# 
#   use the solve function:
#   solve(grammar, startsymbol, [verbose])
#   
#       grammar = {
#           'S': ['F', '(S + F)'],
#           'F': ['a']
#       }
# 
#       startsymbol is the starting nonterminal of grammar
# 
#       verbose is an optional boolean (default is False) which if True
#       the solve function will pretty print its outputs
# 
#   solve return value:
#   (firstSets, followSets, parsingTable, status)
#       status is 0 if LL(1), 1 if not LL(1), and -1 if left recursion was found
# 

epsilon = 'ε'

class GrammarChecker:
    epsilon = 'ε'
    
    def solve(self, grammar, startsymbol, verbose=False):
        self.firstSets = {}
        self.followSets = {}
        self.parsingTable = {}
        self.firstOfStack = []
        self.isLL1 = True
        self.leftRecursionFound = False
        
        self.grammar = grammar
        self.startsymbol = startsymbol
        self.verbose = verbose
        self.nonterminals = [x for x,_ in self.grammar.items()]
        self.terminals = set()
        for _,prods in self.grammar.items():
            for prod in prods:
                for symbol in prod.replace(" ",""):
                    if symbol not in self.nonterminals and symbol != self.epsilon:
                        self.terminals.add(symbol)
        
        GrammarChecker.buildFirstSets(self)
        GrammarChecker.buildFollowSets(self)
        GrammarChecker.buildParsingTable(self)
        
        returnFirstSets = {}
        for nt in self.nonterminals:
            returnFirstSets[nt] = self.firstSets[nt]
        
        status = -1 if self.leftRecursionFound else (0 if self.isLL1 else 1)
        if self.verbose:
            if self.leftRecursionFound: 
                print("Left recursion found - don't trust any results here")
            else: 
                if self.isLL1: 
                    print("grammar is LL(1)") 
                else:
                    print("grammar is NOT LL(1)")
        return((returnFirstSets,self.followSets,self.parsingTable,status))
    
    def buildFirstSets(self):
        self.firstSets = {}<commit_msg>If applied implements reachability checking<commit_after># 
#   GrammarChecker usage:
#   Finds the LL(1) First, Follow, Parse Table of a grammar.
# 


#   
#   solve(grammar, startsymbol, [verbose])
#   PARAMS:
#       REQUIRED:
#       grammar = {
#           'S': ['F', '(S + F)'],
#           'F': ['a']
#       }
# 
#       REQUIRED: startsymbol is the starting nonterminal of grammar
# 
#       OPTIONAL: verbose is an optional boolean (default is False) which if True
#       the solve function will pretty print its outputs
# 
#   RETURNS:
#       (firstSets, followSets, parsingTable, status, reachable)
#           status:     0 if LL(1), 1 if not LL(1), and -1 if left recursion was found
#           reachable:  True if every nonterminal is reachable, else False
# 


# 
#   getSymbols(grammar)
#   PARAMS:
#       REQUIRED: grammar is in same format as above
# 
#   RETURNS:
#       (nonterminals, terminals)
#           both are lists, neither are ordered
# 
# 

epsilon = 'ε'

class GrammarChecker:
    epsilon = 'ε'
    
    def solve(self, grammar, startsymbol, verbose=False):
        self.firstSets = {}
        self.followSets = {}
        self.parsingTable = {}
        self.firstOfStack = []
        self.isLL1 = True
        self.leftRecursionFound = False
        
        self.grammar = grammar
        self.startsymbol = startsymbol
        self.verbose = verbose
        
        GrammarChecker.getSymbols(self,grammar)
        
        GrammarChecker.buildFirstSets(self)
        GrammarChecker.buildFollowSets(self)
        GrammarChecker.buildParsingTable(self)
        
        returnFirstSets = {}
        for nt in self.nonterminals:
            returnFirstSets[nt] = self.firstSets[nt]
        
        status = -1 if self.leftRecursionFound else (0 if self.isLL1 else 1)
        if self.verbose:
            if self.leftRecursionFound: 
                print("Left recursion found - don't trust any results here")
            else: 
                if self.isLL1: 
                    print("grammar is LL(1)") 
                else:
                    print("grammar is NOT LL(1)")
        return((returnFirstSets,self.followSets,self.parsingTable,status,GrammarChecker.reachability(self)))
    
    def getSymbols(self, grammar):
        self.grammar = grammar
        self.nonterminals = [x for x,_ in self.grammar.items()]
        self.terminals = set()
        for _,prods in self.grammar.items():
            for prod in prods:
                for symbol in prod.replace(" ",""):
                    if symbol not in self.nonterminals and symbol != self.epsilon:
                        self.terminals.add(symbol)
        return (self.nonterminals,list(self.terminals))

    def reachability(self):
        canreach = {}
        for LHS,RHS in self.grammar.items():
            reachability = set()
            for prod in RHS:
                for letter in prod:
                    if letter in self.nonterminals:
                        reachability.add(letter)
            canreach[LHS] = reachability
        for nt in self.nonterminals:
            if nt != self.startsymbol:
                if not GrammarChecker.path_exists(self, canreach, self.startsymbol, nt):
                    return False
        return True

    def path_exists(self, graph, start, end, path=[]):
        path = path + [start]
        if start == end:
            return True
        if start not in graph:
            return False
        for node in graph[start]:
            if node not in path:
                return GrammarChecker.path_exists(self, graph, node, end, path)
        return False

    def buildFirstSets(self):
        self.firstSets = {}
{'fraction_non_alphanumeric': 0.09505252456794307, 'fraction_numerical': 0.004744154523890207, 'mean_word_length': 1.8516908212560386, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4518743', 'n_tokens_mistral': 1745, 'n_tokens_neox': 1689, 'n_words': 471}