Python 接受预定义语法的代码

Question

我正在尝试编写一个代码来识别遵循语法规则的字符链：

S->abK
K->x|xK|H
H->c|d

所以像 abx、abxxx、abc、 这样的词abxd, abxc, 等等...都被接受并且像 ab, abb[=36 这样的词=], xxx, 等...不被接受。

我写了一个代码来做到这一点，在我的分析中它应该可以解决问题，但它有一些错误，即它 returns False for abxx，一个应该被接受的句子语法，我认为它与函数中的嵌套 return 值有关，我不太了解。

代码贴在下面，如果大家能指出或指出我做错了什么，将不胜感激。

def S(word): if word[0] == 'a': atual = 1 else: return False if word[1] == 'b': atual = 2 else: return False accepted = K(atual, word) if accepted == True: return True else: return False def K(atual, word): if word[atual] == 'x': atual += 1 if len(word) <= atual: # checks to see if the word ended and accept by the first rule of the set K. return True else: K(atual, word) # keeps increasing the value of atual, satisfying the rule xK else: value = H(atual, word) # if no more 'x' are found, try the rule H return value def H(atual, word): if word[atual] == 'c' or word[atual] == 'd': return True else: return False print(S(['a','b','x','x']))

Answer 1

您的实现不必要地冗长和重复：没有必要传递索引，例如，当您可以将单词的相关部分传递给下一个函数时。这是我放在一起的一个快速实现，应该可以解决它：

def S(chars):
  word = ''.join(chars)
  try:
    return word[:2] == 'ab' and K(word[2:])
  except IndexError:
    return False

def K(word):
  return word == 'x' or (word[0] == 'x' and K(word[1:])) or H(word)

def H(word):
  return word in ['c', 'd']

使用这个函数，我得到：

>>> list(map(S, ['abx', 'abxxx', 'abc', 'abxd', 'abxc']))
[True, True, True, True, True]

Python 接受预定义语法的代码

Python code to accept pre-defined grammar

python

grammar