wlist = "book the flight through Houston".split()
Lexicon = {
"that | this | the | a": "Det",
"book | flight | meal | money": "Noun",
"book | include | prefer": "Verb",
"I | she | me": "Pronoun",
"Houston | NWA": "Proper-Noun",
"does": "Aux",
"from | to | on | near | through": "Preposition"
}
# Grammar = {
# "NP VP": "S",
# "Aux NP VP": "S",
# "VP": "S",
# "Pronoun": "NP",
# "Proper-Noun": "NP",
# "Det Nominal": "NP",
# "Noun": "Nominal",
# "Nominal Noun": "Nominal",
# "Nominal PP": "Nominal",
# "Verb": "VP",
# "Verb NP": "VP",
# "Verb NP PP": "VP",
# "Verb PP": "VP",
# "VP PP": "VP",
# "Preposition NP": "PP",
# }
# Grammar = [
# "S NP VP",
# "S Aux NP VP",
# "S VP",
# "NP Pronoun",
# "NP Proper-Noun",
# "NPDet Nominal",
# "Nominal Noun",
# "Nominal Nominal Noun",
# "Nominal Nominal PP",
# "VP Verb",
# "VP Verb NP",
# "VP Verb NP PP",
# "VP Verb PP",
# "VP VP PP",
# "PP Preposition NP",
# ]
CNF = [
"S -> NP VP",
"S -> X1 VP",
"X1 -> Aux NP",
"S -> book | inclue | prefer",
"S -> Verb NP",
"S -> X2 PP",
"S -> Verb PP",
"S -> VP PP",
"NP -> I | she | me",
"NP -> TWA | Houston",
"NP -> Det Nominal",
"Nominal -> book | flight | meal | money",
"Nominal -> Nominal Noun",
"Nominal -> Nominal PP",
"VP -> book | include | prefer",
"VP -> Verb NP",
"VP -> X2 PP",
"X2 -> Verb NP",
"VP -> Verb PP",
"VP -> VP PP",
"PP -> Preposition NP",
]
def get_diag_eles(w):
res = []
for key,value in Lexicon.items():
if w in key:
res.append(value)
for item in CNF:
key, value = item.split(" -> ")
if w in value:
res.append(key)
return res
def get_inner_eles(table, i, j, k):
res = []
B = table[i][k].split(',')
C = table[k][j].split(',')
for b in B:
for c in C:
bc = " ".join((b, c))
for item in CNF:
key, value = item.split(" -> ")
if bc == value:
res.append(key)
return res
def cyk(wlist):
lenw = len(wlist)
table = [['' for i in range(lenw+1)] for i in range(lenw)]
for j in range(1, lenw+1):
diag_eles = get_diag_eles(wlist[j-1])
table[j-1][j] = ",".join(diag_eles)
# j = 1,2,3,4,5
for i in range(j-2, -1, -1):
# i = 3,2,1,0
inner_eles = []
for k in range(i+1, j):
# print('k',(i,j), (i,k), (k,j))
tmp = get_inner_eles(table, i, j, k)
inner_eles.extend(tmp)
table[i][j] = ",".join(inner_eles)
return table
cyk(wlist)
[['', 'Noun,Verb,S,Nominal,VP', '', 'S,VP,X2', '', 'S,VP,X2,S,VP,S,VP'], ['', '', 'Det', 'NP', '', 'NP'], ['', '', '', 'Noun,Nominal', '', 'Nominal'], ['', '', '', '', 'Preposition', 'PP'], ['', '', '', '', '', 'Proper-Noun,NP']]