Figuring out how to expand a grammar (Python)
Question: Im trying to write code that will return an expanding grammar. so in this
example I will specify a length of 3, N = N D will expand it self to N = N D D
and then it will expand again to N = N D D D but then exit the program, any
advice for making this happen? I currently tried to do the replace method in
printGrammar but as you can see when you run it for some reason NT (the non
terminal being replaced, in this example N), and item (the value from the
dictionary, in this case N D and D) wont replace and I am left with a list
with 'N' instead of what I want which is N D D, can someone please help me?

Binary.txt is:

    
    
    N = N D
    N = D
    D = 0
    D = 1
    

Code is

    
    
    import sys
    import string
    from collections import defaultdict
    
    #default length of 3
    stringLength = 3
    
    #get last argument of command line(file)
    if len(sys.argv) == 1:
        #get a length from user
        try:
            stringLength = int(input('Length? '))
            filename = input('Filename: ')
        except ValueError:
            print("Not a number")
    
    elif len(sys.argv) == 2:
        #get a length from user
        try:
            stringLength = int(input('Length? '))
            filename = sys.argv[1]
        except ValueError:
            print("Not a number")
    
    elif len(sys.argv) == 3:
        filename = sys.argv[2]
        stringLength  = sys.argv[1].split('l')[1]
    else:
        print("Invalid input!")
    
    
    #get start symbol
    with open(filename, "r") as grammar:
        #read file 
        lines = grammar.readlines()
        start = lines[0].split('=')[0]
        start = start.replace(" ", "")
    
    
    #checks
    
    #print(stringLength)
    #print(filename)
    #print(start)
    def str2dict(filename):
        result = defaultdict(list)
        with open(filename, "r") as grammar:
            #read file 
            lines = grammar.readlines()
            count = 0
    
            #loop through
            for line in lines:
                #append info 
                line = line.rstrip()
    
                result[line[0]].append(line.split('=')[1])
    
        return result
    
    
    workingDict = str2dict("Binary.txt")
    print(workingDict)
    
    
    def strings(grammar, start):
        queue = [start]
        while len(queue):
            current = queue.pop(0)
            # for each symbol in the current string
            for n, sym in enumerate(current):
                # if this symbol is a non-terminal
                if sym in grammar:
                    # for each rule for this symbol...
                    for rhs in grammar[sym]:
                        # replace it with the right part
                        new = current[:n] + rhs + current[n+1:]
                        # does the result contain non-terminals
                        if any(s in grammar for s in new):
                            # yes, place it into the queue
                            queue.append(new)
                        else:
                            # no, return it
                            yield new
    
    for x in strings(workingDict, stringLength):
        print (x)
        if len(x) > 4:
            break
    


Answer: Assuming your grammar is in the form

    
    
    grammar = {
        'N': ['ND', 'D'],
        'D': ['0', '1']
    }
    

the algorithm looks straightforward:

  * iterate over the current string (which is initially just one symbol)
  * if the symbol is a non-terminal, replace it with its production
  * if the result contains non-terminals, place it in a queue for further processing
  * otherwise, return the result (which is a string of terminals)
  * pick the next "current" string from the top of the queue and continue

:

    
    
    def strings(grammar, start):
        queue = [start]
        while len(queue):
            current = queue.pop(0)
            # for each symbol in the current string
            for n, sym in enumerate(current):
                # if this symbol is a non-terminal
                if sym in grammar:
                    # for each rule for this symbol...
                    for rhs in grammar[sym]:
                        # replace it with the right part
                        new = current[:n] + rhs + current[n+1:]
                        # does the result contain non-terminals
                        if any(s in grammar for s in new):
                            # yes, place it into the queue
                            queue.append(new)
                        else:
                            # no, return it
                            yield new
    

Usage:

    
    
    for x in strings(grammar, 'N'):
        print x
        if len(x) > 4:
            break
    

