Overlapping functionality: IFTI, templates, is-expressions

[Russell Lewis]

BCS wrote:
> One thing I've bean thinking of is trying to build in a memoizer: "we 
> tried to parse a foo at location 294 before and got this, lets use it" 
> I'm not sure how or how well it will work but I've got some ideas.

I have an idea that didn't work with my design, but it probably would 
with yours: you should be able to do a hybrid parser with bottom-up 
parsings of unambiguous strings.  Basically, the concept is that you 
look for certain tokens (or strings of tokens) which are only used in a 
certain reduction.  Then, you build a low-level scanner which scans the 
lexer's output (utterly without any understanding of the larger 
contexts) and collapses any patterns that it recognizes.  You can 
perform multiple passes, and collapse even strings of things that 
include nonterminals, if you get lucky.  Then, once you run out of 
bottom-up parsings, you run the top-down parser.  Things that were 
bottom-up parsed are effectively memoized.

There are other tricks you can use, too, by mixing the bottom-up and 
top-down parsers.  For instance, in D the token ? is (as far as I 
remember) only used as part of a conditional expression.  Your parser 
library could detect that in the grammar, and say, "whenever I see ? in 
the bottom-up parser scan, I will run the top-down parser to parse an 
'expression' nonterminal as the next thing, then look for a ':' token 
and then do it again."  Likewise, '&' only comes before an expression, 
as do all of the assignment operators and most of the binary operators. 
  In most of these cases, you don't have any efficient way to bottom-up 
parse the stuff to the *left* of the key-token, but you can at least 
memoize the stuff on the right.

Of course, it only works on grammars that happen to have unambiguous 
opportunities, but in D, there are a lot of those.