上下文无关文法是一种强大的描述语言的方法。 编写一段程序，用于测试字符串在上下文无关文法中的成员性，即由此文法是否可以生成这个字符串。

<自动机理论、语言与计算理论>一书中有这样一节： http://layout.malic.xyz/%E6%B5%8B%E8%AF%95CFL%E7%9A%84%E6%88%90%E5%91%98%E6%80%A7.pdf，介绍了CYK算法。

python实现：

import sys
sys.stdin=open("_in","r")
grammarTable={}
while True:
    msg=input()
    if msg=='#':
        break
    wd,pt=msg.split("->")
    grammarTable[wd]=pt.split("|")
def judge(msg):
    CYK_Table = [ ["" for _ in range(len(msg)+1)] for __ in range(len(msg)+1)]
    for i in range(len(msg)):
        s=""
        for wd in grammarTable:
            if msg[i] in grammarTable[wd]:
                s+=wd
        CYK_Table[i+1][i+1]=s
    for gap in range(1,len(msg)):
        i=1
        while i+gap<=len(msg):
            s=""
            for k in range(i,i+gap+1):
                for w1 in CYK_Table[i][k]:
                    for w2 in CYK_Table[k+1][i+gap]:
                        for wd in grammarTable:
                            if w1+w2 in grammarTable[wd] and wd not in s:
                                s+=wd
            CYK_Table[i][i+gap]=s
            i+=1
    if 'S' in CYK_Table[1][len(msg)]:
        return True
    else:
        return False
while True:
    try:
        msg=input()
    except:
        break
    print(judge(msg))