This has to be a really common problem, but I can't for the life of me figure out what it's called in order to google it. Any pointers appreciated :)
In essence, I have an input string along the lines of "ABAAACBAABCBBA", and a set of rules for replacing substrings that look like "AA->B", "BCB->A"... (rules may be arbitrarily long substrings, but always result in a single token output).
Given an input string and a set of rules, I need to figure out (a) the unique order in which to apply the rules (potentially recursively) to arrive at a single token result, or (b) if no such ordering exists, or (c) if more than one such ordering exists.
The input strings may be of arbitrary length, but are generally somewhere between 5 and 30 tokens. Rules are generally short (2-8 tokens), but there may be many thousands of rules, and hundreds of distinct tokens in the grammar. It is however acceptable to pre-process the set of rules rules.
Bonus points for pointers to a solution that runs in reasonable time complexity...