
Algorithm HI Top-down recognizer using indices
Invoke (Derives >S [0,n])
Define (Derives A [i,j]) =
case j-i = 1 (member [A —> (input i j)] (UP A))
case j-i > 1 (For Some [[A --> BC],
[[i,k],
[k,j]]]
in (BP A) cross (split [i,j])
(and (Derives B [i,k])
(Derives C [k,j])))
with (Split [i,j]) =
(For k in (i+1 to j-1) collect [[i,k],[k,j]])
Notice that "Split" has been converted into an iterative algorithm and string oper-
ations have been replaced with index manipulation. The form (input i j) refers to the
substring of the input string. We now introduce caching of results for "Derives". Since
the algorithm has concurrency, caching should be don ...