Parser pickers

The Backtracking Parse Engine must repeatedly find Parsers that can successfully parse a token list. In the early days of LastCalc it would naively try every single parser, but obviously this is very inefficient.

These days we use a Keyword Parser Picker. It relies on the templates defined by each parser (and returned by the parser's getTemplate() method), and identifies specific keywords that must be present in the token list for this parser to apply.

For example, if the token list contains the string "+", then the Keyword Parser Picker will try Parsers with the string "+" in their templates.

It does need to be smart enough to deal with more complicated templates which contain multiple keyword possibilities, and it handles these as you might hope it would.

This approach to finding parsers means that LastCalc should be able to scale to tens or hundreds of thousands of parsers quite efficiently (RAM permitting). Its main weakness is that a Parser who'se template consists only of Classes, without any keywords, must be tried every time (although they are attempted last).

Not trying the same parser twice on the same token list

Another thing to bear in mind is that we don't want to try the same parser twice on the same TokenList. This is prevented in the getNext() method of ParserPickerFactory.java by maintaining a map of previously attempted parsers and the token lists they were attempted on. It actually goes further than this, remembering what position in the token list the previous parser was attempted on (since a parser could be applied more than once to different parts of a token list).