python - 弄清楚如何扩展语法 (Python)

Question

我正在尝试编写将返回扩展语法的代码。所以在这个例子中，我将指定长度为 3，N = N D 会将其自身扩展为 N = N D D，然后它将再次扩展为 N = N D D D，然后退出程序，有什么建议可以实现这一点？我目前尝试在 printGrammar 中执行 replace 方法，但正如您在出于某种原因运行它时看到的那样 NT(被替换的非终结符，在本例中为 N)和 item(字典中的值，在本例中为 N D 和D) 不会替换，我只剩下一个带有“N”的列表，而不是我想要的 N D D，有人可以帮我吗？

Binary.txt 是:

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

代码是

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 1

假设你的语法是这样的

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

算法看起来很简单:

• 遍历当前字符串(最初只是一个符号)
• 如果符号是非终结符，将其替换为产生式
• 如果结果包含非终结符，则将其放入队列中以供进一步处理
• 否则，返回结果(一串终端)
• 从队列顶部选择下一个“当前”字符串并继续

:

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(grammar, 'N'):
    print x
    if len(x) > 4:
        break