CKYParser

CKYParser.swift

class CKYParser {
	func parse(words words: [String], language: Language) -> [[[ParseTreeNode]]] {
		let wordCount = words.count
		var table = [[[ParseTreeNode]]]()
		for _ in 0...words.count - 1 {
			let array = [[ParseTreeNode]](count: wordCount, repeatedValue: [ParseTreeNode]())
			table.append(array)
		}
		// populate lexicon. assuming all the words are in our lexicon
		for index in 0...words.count - 1 {
			let word = words[index]
			let nonTerminals = language.recognize([word])!
			for nonTerminal in nonTerminals {
				table[index][index].append(ParseTreeNode(nonTerminal: nonTerminal, leftNode: nil, rightNode: nil))
			}
		}
		for col in 0...wordCount - 1 {
			for row in (0...wordCount - 1).reverse() {
				var t = row
				while t + 1 <= col {
					let arr1 = table[row][t]
					let arr2 = table[t + 1][col]
					if arr1.count == 0 || arr2.count == 0 {
						t += 1
						continue
					}
					if let nonTerminals = language.recognize(arr1: arr1, arr2: arr2) {
						for nonTerminal in nonTerminals {
							table[row][col].append(nonTerminal)
						}
					}
					t += 1
				}
			}
		}
		return table
	}
}