Request for a feedback: Grammar-Kit parser memorization

Thinking about optimization of my generated Perl parser, found an article about memorizartion. And i think it's pretty easy to implement it into the grammar kit.


The main idea: in every rule, after first parsing we should store:

  • entering offset
  • rule id
  • parsing result
  • markers added in this and subsequent rules
  • exit offset

On the next entrance we are checking if we've been in this rule on this offset and if we did, just advance lexer, restore markers and return result. Without all nested logic. So basically, every rule will work only once on every offset. This approach should significally improve parsing performance. 

Of course, there are few nuances:

  • rules must not depend on outer rules or markers (errorState if i remember right)
  • no direct lexing data modifications, only markers

I think it's a really cool idea, but i have them too often and they are too often not so cool as I thought, so I'm looking for a feedback and criticism.


Please sign in to leave a comment.