2
$\begingroup$

I'm preparing a presentation on prefix computation (aka scan, the generalization of prefix summation to any associative operator) for a class I'm taking on parallel algorithms.

Several lists of applications of prefix computation include lexical analysis (tokenizing), but do not cite a source for that. I have failed to find any other reference to it being used that way.

Where has any description of the use of a prefix computation for the purpose or lexical analysis been published? (Or, what was the origin of this misinformation?)

$\endgroup$
1
  • $\begingroup$ A classic APL one-liner for detecting unbalanced parens is to translate {'(',')'} to a vector of {1, -1} respectively and +\ (scan with addition). Negative numbers, or the end not being zero, indicate unbalance. I can imagine tokenization might be similar, although I don't know of a specific example. $\endgroup$
    – KWillets
    Sep 26, 2016 at 18:13

1 Answer 1

1
$\begingroup$

The important fact in this case is that the list append operation is associative.

Hadoop has "tokenize" as one of its built-in parallel operators. The meaning of "tokenize" in this case is much less general than "lexical analysis". They mean "splitting a string at a specific well-defined set of `delimeter' characters." I doubt there is much you could do with a more general lexical analyzer (one where you are running an arbitrary finite-automata over a string.)

So suppose you need to split a string at all the space characters. You are essentially creating a list of indices into the string. The list append operation is associative. So each processor generates the appropriate list of indices for the substring assigned to it, and then you append all the lists together.

$\endgroup$
1
  • $\begingroup$ That documentation doesn't mention prefix, so this doesn't technically answer the question. I can see how to use a prefix sum to find a list of indices, which is helpful, but I still need a more citable reference than an answer on Stack Exchange. $\endgroup$ Feb 1, 2015 at 19:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.