Saturday, January 13, 2007

Memoising a complete parser

Not sure if "complete" is the correct term but I mean a parser that finds all possible parses of the stirng by the grammar. Usually very expensive but by memoising the application of rule A at char N in the string it becomes cheaper. The key is the value that you store. For memoised recursive descent, you just store the parsed value or FAIL. For this you have to store an object that can generate parsed values in the correct order and which caches any previously generated ones. Not so bad really. There are some questions though about quantifiers. It might be worth trying to share data between X{4} and X{5} applied at the same char. But maybe not.

Post a Comment