8 ms·
Reading the fourth entry on parenthesis matching made me wonder whether one could store, in the monoid, partials views into the table that is generated by CYK p
by cscheid 9y ago
Reading the fourth entry on parenthesis matching made me wonder whether one could store, in the monoid, partials views into the table that is generated by CYK parsing: https://en.wikipedia.org/wiki/CYK_algorithm https://en.wikipedia.org/wiki/CYK_algorithm
I love the idea of using monoids like they're described in the blog series, but the examples suggest that there's a certain amount of non-generalizable cleverness that goes into defining each monoid. Could you do CYK subtables inside the monoid, so that people can define arbitrary CF grammars, as long as they're in Chomsky normal form?
- asrp 9y agoWell, you can already have half of a split unicode character at the beginning and end of a substring in the rope. If that doesn't happen (like in the "parens" or "other" description), to use CYK, I think you could maybe have piece of the table for each substring (so for all entries with both indices inside the substring) in each node but then I don't think the operation at the parent is commutative. And you have to decide to copy the info from the children or not (if not, you'll spend an extra log n time looking down the tree).
- modeless 9y agoI've been wondering lately if it would be possible to make an entire compiler stack incremental, so that the binary changes on disk as I type. I am positively sick of waiting tens of seconds or even minutes for the compiler to redo all the work it's already done thousands of times just to make a one-byte change to my binary.
- cscheid 9y agoPresumably, moving to an infrastructure like this (everything is incremental) is the biggest difference between Old compilers and New compilers, because of the ubiquitous IDE. I think I remember watching a talk by Anders Hejlsberg about this.