Verity ​

is anyone aware of research on generating LR or LL parse tables that exploits sharing in the grammar?

like, the conventional approach is to expand the grammar so that it is a sum of products: each nonterminal has multiple flat rules that it can match, with no choice in those rules

(the most classic of BNFs, if you will)

but grammars may be constructed in a tree shape, especially with applicative combinators, where sequencing and choice are interleaved:

(p <|> q) <*> (x <|> y)
-- expands to
(p <*> x) <|> (p <*> y) <|>
(q <*> x) <|> (q <*> y)

expanding this produces lots of rules and surely some duplicate work in the table generation, but I haven't seen anyone talk about this before

(one way to tame the duplication is by introducing nonterminals just to group items, but this runs the risk of introducing ambiguity in an LR(1) grammar, and, uh, I don't think it actually saves the generator much if any work)

remember to maintain adequate ecosystem diversity in your last used signal stickers!

thinking again about how natural transformations can really be thought of as natTrans :: (forall x y. (x -> y) -> f x -> g y)

subject to a simple coherence condition: fmap f . natTrans g . fmap h = natTrans (f . g . h)

or alternatively that fmap f . natTrans id = natTrans f = natTrans id . fmap f

basically meaning that the mapping (x -> y) is not sequenced with the natural transformation f ~> g in either direction, but integral to it

and it's just the tendency towards simpler primitives that is the reason we have natural transformations explained as (forall x. f x -> g x)

wonder how feasible it would be to do a whole-program kind of taint analysis to see which values of known types could possibly come from FFI

still thinking about my idea of compiling PureScript directly to some intermediate representation of JavaScript JIT, making direct/unsafe use of typing information where safe