gpt4 book ai didi

python - 如何构建trie树来解决这个解析算法

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:14:56 29 4
gpt4 key购买 nike

我正在尝试使用 trie 树来解决这个问题:

Symbol string generator consists of two parts, a set of the start symbol and a set of rules of generation.
For example:
Start symbol: ['S'], Rules of generation: ["S → abc", "S → aA", "A → b", "A → c"]
Then, symbolic string abc can be generated because S → abc.
Symbolic string ab can be generated because S → aA → ab.
Symbolic string abc can be generated because S → aA → ac.
Now, give you a symbolic string generator and a symbolic string, and you need to return True if the symbolic string can be generated, False otherwise

Example
Given generator = ["S -> abcd", "S -> Ad", "A -> ab", "A -> c"], startSymbol = S, symbolString = “abd”, return True.

explanation:
S → Ad → abd

Given generator = ["S → abc", "S → aA", "A → b", "A → c"], startSymbol = S, symbolString = “a”, return False

我发现这个问题的关键点是构建一个 trie 树。我试着写:

def build_trie(values): #value is like ['abc', 'Ad'...]
root = {}
for word in values:
current = root
is_end = False
for c in word:
if 'A' <= c <= 'Z':
vals = m[c] #m is a mapping of {'S': ['abc', 'Ad'], ...}
rs = build_trie(vals)
for k in rs:
if k not in current:
current[k] = rs[k]
else:
# stuck here...
pass

# temp = collections.defaultdict(dict)
# for d in (current[k], rs[k]):
# for k, v in d.items():
# if k in temp and k != '__end__':
# temp[k].update(v)
# else:
# temp[k] = v
# # current[k].update(rs[k])
# current[k] = temp[k]
is_end = True
else:
current = current.setdefault(c, {})
is_end = False
if not is_end:
current['__end__'] = '__end__'
return root

但卡在了 else 部分......还没有弄清楚如何编写这棵特里树。有什么线索吗?

最佳答案

您可能想使用 Python 中的多个解析器库。我用过LARK parser .他们对各种 python 解析器进行了比较。

在大学期间,我用 C 语言实现了一个 LALR(1) 解析器。我想它用处不大。我在 python here 中找到了一个有用的实现,如果你想再次编写整个解析器。我还没有测试该代码的工作情况。

对于给定的语法,我使用 LARK 编写了一个验证器,如下所示。

from lark import Lark
import sys

grammar = """
start: "abcd"
| A "d"
A: "ab"
| "c"
"""

parser = Lark(grammar)

def check_grammer(word):
try:
parser.parse(word)
return True
except Exception as exception:
print exception
return False



word = sys.argv[1]
print check_grammer(word)

希望对您有所帮助!

关于python - 如何构建trie树来解决这个解析算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48627247/

29 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com