Re: Myrddin Retrospective for 2016

[Ori Bernstein <ori@xxxxxxxxxxxxxx>]

On Sun, 1 Jan 2017 10:52:23 -0500, "S. Gilles" <sgilles@xxxxxxxxxxxx> wrote:

> On 2017-01-01T02:39:49-0800, Ori Bernstein wrote:
> > For those on the list but not on IRC, here's a summary of what happened this
> > year. More than I wanted to get done in some areas. Less than I wanted to get
> > done in many others. All written up here for your intense viewing pleasure.
> > 
> > 	http://myrlang.org/retrospective
> 
> Nice!
> 
> Personally, I'm quite interested in the parser generator.  A month or
> so back I had to pull out flex, and my memories of it as a simple and
> integrable tool were rather incorrect: I had to put in special CFLAGS
> for the file it generated, etc. etc. I'd very much like an excuse to
> revisit that project in Myrddin.

Awesome.

To be honest, this has been a lower priorty for me than I'd like, so
you may be waiting for a while. There are 5 major things left to do
to get this into a state I'd be happy with for a release:

	1) Finish off core functionality. This means actually implementing
	   the basic LALR(1) algorithm, instead of what we have now. The
	   dragon book documents this part pretty well.

	2) DFA minimization. This is just a performance thing, but our
	   switch statement is gigantic. Again, the dragon book is the
	   go-to reference for this.

	3) Implementing better error checking. Russ Cox has a great
	   post on this[1], and I want it built in. But even basic error
	   messages like what Bison does with `#define YYERROR_VERBOSE 1`
	   would be a giant win, especially if we teach this to pretty
	   print the names instead of just using the token name.
	
	4) Implementing better error messages. 'shift/reduce error'
	   is a crappy message. The way to go about called 'countexample
	   generation'[2]

	5) Adding additional output languages. C is definitely in, and I
	   think C++ is common enough that an idiomatic output for that
	   is also something I'd want. I'm open to basically any other
	   language that people care about, but those are the ones I'd
	   be willing to do the work for.

There are a few other bells and whistles that may also be nice to add, like
lexer states -- those make things like /* */ comments quite a bit easier to
parse. And eventually I think upgrading from LALR to IELR[3] is a good way
forward.

If there's any chance you have the time/knowlege to help, I'd be extremely
grateful.

The code that currently exists is here:

	http://git.eigenstate.org/ori/hairless.git

And you can see what its inputs look like in the example/ directory.

[1] https://research.swtch.com/yyerror
[2] https://www.cs.cornell.edu/andru/papers/cupex/cupex.pdf
[3] https://people.cs.clemson.edu/~malloy/publications/papers/sac08/paper.pdf
-- 
    Ori Bernstein