Investigation on dynamic follow sets

[pablogsal]

I am doing some toy implementation of the dynamic follow sets described in the paper (to better understand them) and what I am experiencing is that keeping the tree to query the parse records using the proposed dynfollow and follow_at demands a considerable amount of extra memory. In my naive implementation for a small toy grammar of a calculator (done by hand) it consumes 120% more space when parsing some nested expressions.

I am doing some other experiments to see if I can reduce this by making it smarter (or maybe I did some error in my toy implementation. which is possible) but these results may suggest that, even if Guido's initial implementation does not use them at all already, we may not even want to consider using them in the future (even in a second pass) because with our grammar the memory consumption can go crazy very soon.

This is just some initial notes on this approach on the paper, though. I wanted to open this issue to collect future discussions about this in one place.

[gvanrossum]

Are you sure you need to compute those sets? My own algorithm doesn't use them. (It does use the trick of pruning the memo cache of items that could be influenced by the presence of the error token; for this I need one extra integer per memo cache item.)

[pablogsal]

Are you sure you need to compute those sets?

We probably don't need them to have good error reporting as your algorithm seems to work nicely, but I wanted to better understand what they propose.

Just to clarify: this is no pre-computing them (they cannot be pre-computed as the cardinality may be infinite). This creates them when needed (by using parsing records, the first sets and the definition they give for dynfollow and follow_at). What right now takes all this memory is me keeping the "parsing records" (described in 4.1.1) , which is a tree of data representing the state of every parser invocation during the parsing. As we are emitting AST directly, we cannot reuse any CST-like structure for this (I am also doing some initial investigation so I may be perfectly missing something).

[gvanrossum]

I saw that their algorithm looked like that, and decided not to bother. :-)

[pablogsal]

I saw that their algorithm looked like that, and decided not to bother. :-)

For what I am experiencing, it seems that that was a wise decision indeed 😉