I'll describe an algorithm that works. It's running time shouldn't be too bad. You can precompute quite a bit of this as well.

I'll assume that $a$ does not contain nonterminals (though it's probably easy to adapt to that case) and that you don't know $x$, $y$ or the derivation of $a$. I'll also assume your grammar doesn't contain productions that are never used in any derivation ($A \rightarrow A$ for example).

The main issue really is to parse $a$, as you want to know what kind of states you end up in, so you know what can follow $a$. This is not so easy as you don't know $x$.

We use an adaptation of [Earley's algorithm][1]. You'll want to understand that algorithm first. Our algorithm works in almost the same way, except our initialization and completion steps are different.

For the initialization, we seed our first set with an Earley item for every occurrence of $a_1$ (the first character in $a$) in any production of your grammar. We set the back pointer of this item to -1, an invalid value. This is important in our modified completion. Essentially, the -1 means 'I have no idea where this production was started'.

Now, we perform the Earley algorithm separately for every possible such initial Earley item. We can't simply do all of them at the same time, as the parses may interfere with each other. I can't easily see a faster method than backtracking here.

For the completion step, we only have to make a modification to handle -1 back pointers. As we've completed a production whose origin we don't know, we are in trouble. However, [the method used to compute $LALR(1)$ lookahead sets][2] by [Pennello and DeRemer][3] saves us: what we need here is exactly the $LALR(1)$ lookahead sets. Every item in these lookahead sets has a corresponding position in the grammar, which in turn corresponds to a possible continuation of the completed production.

Unfortunately, I don't really see any other choice than to backtrack once again here. For every position in the lookahead set, you perform the completion step with this position, and continue the parse from there. You do this separately for every parse. Note that if your grammar is $LALR(1)$, your lookahead will uniquely determine which position you have to go to, so you don't have to backtrack.

You continue the above algorithm one character beyond $a$, where you consider this extra, virtual character to be the 'any character', which immediately gives you the 'follow' set you are looking for - any time the scanner phase finds something for this final set, you can add this character to your answer set.


  [1]: http://en.wikipedia.org/wiki/Earley_parser
  [2]: http://3e8.org/pub/scheme/doc/parsing/Efficient%20Computation%20of%20LALR%281%29%20Look-Ahead%20Sets.pdf
  [3]: http://dl.acm.org/citation.cfm?id=989396