如何根據語法規則生成所有可能的字符串？

Question

我想給JSGF語法生成所有映射到的終端字符串。例如，給定A (B | C) D [E]，我所需的輸出是：

A B D E 
A C D E 
A B D 
A C D 

我決定先從最簡單的項目，可選的支架，但很快就遇到了磚牆。它適用於1件物品，但不適用於替代物品。任何意見，將不勝感激。

我現在擁有的一切：

import re 
rule = raw_input('Enter the rule you want to test: ') 
items = re.findall(r"\w[\w ]*\w|\w|\[|\]|\(|\)", rule) 
for anitem in range(len(items)): 
    bracketc = items[:anitem].count('[') - items[:anitem].count(']') 
    if items[anitem] != '[' and items[anitem] != ']': 
     if bracketc > 0: 
      optional = True 
     else: 
      optional = False 
     while optional == True: 
      print ' '.join(items) 
      it2 = items[:] 
      it2.remove(it2[anitem]) 
      print ' '.join(it2) 
      break 

它適用於1個項目，並給予一個字符串AB [C] d，返回：

A B [ C ] D 
A B [ ] D 

，但在日益複雜壞了，所以我我猜我需要完全不同的東西。

Answer 1

從你的榜樣，我已經寫了下面的一段代碼：

rule="A(B|C)D[E]FG" 

def generate_strings(rule): 
    if not rule: 
     return [""] 
    begin,end=rule[0],rule[1:] 
    if begin=='[': 
     i=end.find(']') 
     if i==-1: 
      raise Exception("Unmatched '['") 
     alt,end=end[0:i],end[i+1:] 
     return [a+e for e in generate_strings(end) for a in [alt,""]] 
    if begin=='(': 
     i=end.find(')') 
     if i==-1: 
      raise Exception("Unmatched '('") 
     alt,end=end[0:i].split('|'),end[i+1:] 
     return [a+e for e in generate_strings(end) for a in alt] 
    if begin in [']',')','|']: 
     raise Exception("Unexpected " + begin) 
    return [begin + e for e in generate_strings(end)] 

print generate_strings(rule) 

編輯： 這是企圖把事情嵌套式工作。它並不總是一直工作，因爲解析現在更加微妙：當我們找到一個右括號時，它可能不是我們想要的，而是一個嵌套表達式。管道和括號也一樣。

def flatten(l): 
    return [item for sublist in l for item in sublist] 

def generate_strings(rule): 
    if not rule: 
     return [""] 
    begin,end=rule[0],rule[1:] 
    if begin=='[': 
     i=end.find(']') 
     if i==-1: 
      raise Exception("Unmatched '['") 
     alt=flatten([generate_strings(a) for a in [end[0:i],""]]) 
     end=end[i+1:] 
     return [a+e for e in generate_strings(end) for a in alt] 
    if begin=='(': 
     i=end.find(')') 
     if i==-1: 
      raise Exception("Unmatched '('") 
     alt=flatten([generate_strings(a) for a in end[0:i].split('|')]) 
     end=end[i+1:] 
     return [a+e for e in generate_strings(end) for a in alt] 
    if begin in [']',')','|']: 
     raise Exception("Unexpected " + begin) 
    return [begin + e for e in generate_strings(end)] 

print generate_strings(rule) 

Answer 2

Josay的回答發電機形式：

def generate_strings(rule): 
    if not rule: 
     yield "" 
    else: 
     begin, end = rule[0], rule[1:] 
     if begin == '[': 
      i = end.find(']') 
      if i == -1: 
       raise ValueError("Unmatched '['") 
      optional, end = end[:i], end[i+1:] 
      for e in generate_strings(end): 
       yield e 
       yield optional + e 
     elif begin == '(': 
      i = end.find(')') 
      if i == -1: 
       raise ValueError("Unmatched '('") 
      parts, end = end[:i].split('|'), end[i+1:] 

      for e in generate_strings(end): 
       for p in parts: 
        yield p + e 
     elif begin in '])|': 
      raise ValueError("Unexpected " + begin) 
     else: 
      for e in generate_strings(end): 
       yield begin + e 

>>> list(generate_strings("A(B|C)D[E]FG")) 
['ABDFG', 'ACDFG', 'ABDEFG', 'ACDEFG']