monoidmusician
@monoidmusician

uhh once again my bodymind refuses to let me actually code, so let me dump some thoughts about the next stage of parser implementation

the fun stuff (limited context sensitivity)


monoidmusician
@monoidmusician

^ time to try to implement this

I have a … not great chance of seeing it through before Friday afternoon, but much better now that I have my thoughts above as a guide


monoidmusician
@monoidmusician

okay, I think I actually implemented it??

now I need example grammars to parse that are:

  • lightly context sensitive
  • ambiguous without resolving the context sensitivity

as a non-example, the classic context-sensitive language of a^nb^nc^n does not satisfy my second criterion, because it can be parsed by a context-free grammar and then accepted/rejected afterwards

I guess I could start with Polish notation, and then work towards user-defined operators with arbitrary arity ...


monoidmusician
@monoidmusician

^ okay I fixed a few things, and I tried to make it a bit more powerful (by chaining a bunch of reductions together), but it still doesn't resolve the ambiguity of Polish notation

I'll probably have to go to a GLR(1) approach, which augments LR(1) by keeping track of multiple states at once, to nondeterministically evaluate any ambiguity along the way

(there's a compression scheme for these states, to make them into a DAG, but I don't know if that is compatible with the extra data I am keeping around ...... hmm)


You must log in to comment.

in reply to @monoidmusician's post: