如何使用NLTK判断字符串是否由给定上下文无关文法生成？

问题根因 #

你碰到的问题是目标字符串a b b b c明明属于给定CFG的语言，但开源方案判定错误，核心问题基本是文法格式不符合NLTK的解析规范，尤其是空产生式的写法、终结符的定义不标准。

正确的验证步骤 #

1. 规范CFG的产生式格式 #

NLTK要求空产生式用""表示，终结符必须加单引号区分于非终结符。把你提供的产生式转换成NLTK可识别的正确格式：

import nltk
from nltk import CFG
from nltk.parse import ChartParser

# 转换后的合法CFG
cfg = CFG.fromstring("""
S -> ""
S -> B A10 | B0
A1 -> T A2
A10 -> T A20 | T0
A2 -> 'c'
A20 -> 'c' | ""
T -> 'b'
T0 -> 'b' | ""
T -> C T
T0 -> C T0 | C0
B -> 'a'
B0 -> 'a' | ""
S0 -> B A1
C -> 'b'
C0 -> 'b' | ""
""")

2. 验证目标字符串 #

将目标字符串拆分为词列表，用NLTK的ChartParser（稳定的CFG解析器）进行验证：

# 目标字符串转为tokens列表
target_tokens = ['a', 'b', 'b', 'b', 'c']
# 创建解析器
parser = ChartParser(cfg)
# 检查是否存在有效推导树
can_generate = any(parser.parse(target_tokens))

print(f"该字符串能否被生成: {can_generate}")

运行后会输出True，证明目标字符串确实能被该CFG生成。

3. 开源方案出错的常见原因 #

• 空产生式处理错误：直接留空而未用""，导致NLTK无法识别空推导规则。
• 终结符未加引号：NLTK会把未加引号的小写字母当作非终结符，导致a/b/c无法匹配目标字符串的tokens。
• 解析器选型问题：部分开源方案用了有bug或效率受限的解析器，ChartParser是NLTK中更可靠的选择。

内容的提问来源于stack exchange，提问作者rideau