def parseCYK ( grammar : Grammar , input : IndexedSeq [ Token ]) : Option [ Tree ] = {
/** The memoization table: if the string of symbols ABC derives the substring of length `length`
* starting at position `from` of the `input`, then the entry for (Seq("A", "B", "C"), from, length)
* contains the three parse trees of A, B, and C. If a particular string of symbols * does not derive a given substring of the `input`, the corresponding table entry is `None`.
*/ val memo = mutable. Map [( Seq [ String ], Int , Int ), Option [ Seq [ Tree ]]]()
/** If the string of symbols `lhs` derives the substring of length `length`
* starting at position `from` of the `input`, returns a sequence of the parse trees for the
* symbols in `lhs`.
* * If `lhs` does not derive this substring of the input, returns `None`.
*/ def recur ( lhs : List [ String ], from : Int , length : Int ) : Option [ Seq [ Tree ]] = {
if (memo.contains((lhs, from, length))) {
memo((lhs, from, length))
} else {
memo((lhs, from,length)) = None
if (lhs.isEmpty) { // Case 1
// println("Case #1",(lhs, from, length))
if (length == 0 ) memo((lhs, from, length)) = Some ( Seq ())
else memo((lhs, from, length)) = None
return memo((lhs, from, length))
} else if (grammar.terminals.contains(lhs( 0 ))) { // Case 2
// println("Case #2",(lhs, from, length))
if (input(from).kind == lhs( 0 )) {
val temp = recur(lhs.tail, from + 1 , length - 1 )
if ( ! temp.isEmpty) {
memo((lhs, from, length)) = Some ( Seq ( new Tree (input(from))) ++ temp.get)
} else {
memo((lhs, from, length)) = None
}
} else {
memo((lhs, from, length)) = None
}
return memo((lhs, from, length))
} else if (grammar.nonTerminals.contains(lhs( 0 )) && lhs.length == 1 ) {
// println("Case #3",(lhs, from, length))
grammar.productionsExpanding(lhs( 0 )).foreach(gamma => {
val temp = recur(gamma.rhs.toList, from, length)
if ( ! temp.isEmpty) {
memo((lhs, from, length)) = Some ( Seq ( new Tree ( Token (lhs( 0 )), temp.get)))
return memo((lhs, from, length))
}
})
memo((lhs, from, length)) = None
return memo((lhs, from, length))
} else {
// println("Case #4",(lhs, from, length))
for (i <- 0 until length) {
val temp1 = recur( List (lhs( 0 )), from, i)
val temp2 = recur(lhs.tail, from + i, length - i)
if ( ! temp1.isEmpty && ! temp2.isEmpty) {
memo((lhs,from, length)) = Some (temp1.get ++ temp2.get)
return memo((lhs, from, length))
}
}
return memo((lhs, from, length))
}
}
}
recur( List (grammar.start), 0 , input.size).map(_.head)
}