News for hackers. Stuff that matters.
Re:Plan to throw one away by jaytaylor on Monday December 14, 2015 @09:16PM (#10735507)
Are Lex and Yacc still the state of the art 20 years later?
Re:Plan to throw one away by kazinator on Monday December 14, 2015 @10:14PM (#10735675)
The freeware versions have improved a bit.

For exmaple, Both Bison and Berkeley Yacc (the new one maintained by T. E. Dickey) support reentrant parsing, which works hand-in-glove with likewise support in GNU Flex.

A parser that whacks around global variables (like parser generated by classic Yacc) is going to be a nonstarter in any modern language which gives programs run-time and compile-time access to the parser (code can execute while parsing and call yyparse). Not to mention if there are threads.

Bison has support for "push parsers" which are state machines called for each token, rather than functions that retain control until they parse an entire unit:

http://www.gnu.org/software/bison/manual/html_node/Push-Decl...

Re:Plan to throw one away by hvis on Monday December 14, 2015 @11:28PM (#10735928)
> freeware

Did you mean "free software"?

Re:Plan to throw one away by Terr_ on Monday December 14, 2015 @09:32PM (#10735544)
I'm not sure how they've aged (I've only really used ANTLR) but I think this one of those situations where 95% of the importance is using the right kind of tool for the job, even if the tool itself is a little rusty.
Re:Plan to throw one away by jacquesm on Monday December 14, 2015 @10:03PM (#10735638)
The only thing that lets old tools get rusty is a lack of maintenance or improper storage. Software does not need to suffer from either and plenty of 'old' tools are still in maintenance. Kernels, compilers, file-systems and network stacks originally written decades ago are still in common use today. Flex and Bison are still being maintained and still have major releases. Whether they are still 'state of the art' is another question entirely but they're definitely being used and they are more than ok for quite a few jobs.
Re:Plan to throw one away by Terr_ on Monday December 14, 2015 @11:59PM (#10736032)
> The only thing that lets old tools get rusty is a lack of maintenance or improper storage. Software does not need to suffer from either

1. Yes, you can ruin every metaphor if you over-analyze it enough.

2. No, software has its own "rust" scenarios, like not staying compatible with other ecosystem elements, or simply being different than the current best-practice.

Re:Plan to throw one away by bm1362 on Monday December 14, 2015 @11:25PM (#10735924)
Or maybe the job of the tool has become more complex in it's nature.
Re:Plan to throw one away by garethrees on Tuesday December 15, 2015 @09:59AM (#10738048)
I don't think they were state of the art even back then, but they were widely available, well documented, and produced fast, robust lexers and parsers. They are still just the ticket if you need to quickly get a programming language implementation off the ground.

There are some things that they don't do so well. It takes hard work to get good error messages out of Yacc, and anything that you might prefer to solve using feedback between the parser and the lexer (such as JavaScript's use of newline to terminate a statement, but only if it makes syntactic sense) is awkward to do because of Lex's lookahead — the token you want to suppress has already been produced by the time you know whether you want to suppress it.

But its important not to get stuck worrying about minor issues like these when the critical task is to make something that works. You can always plan to throw away the Yacc-built parser and replace it with something better when you have time.

Re:Plan to throw one away by srathbun on Tuesday December 15, 2015 @10:11AM (#10738151)
Yes, yes they are. I've used them successfully for various parsing projects. And in fact Bison recently picked up GLR parsing to deal with multiple options (https://www.gnu.org/software/bison/manual/bison.html#General...).

But for something even more fun, I suggest you check out Marpa (https://jeffreykegler.github.io/Marpa-web-site/). It is, by far, the nicest parsing tool I have ever worked with. Being able to parse ANY BNF is huge. And the state tables for debugging! Knowing what possibilities you have makes things way easier. Especially for getting stuck in an ambiguous spot of your grammer. Finally, using ruby slippers to get out of a tight spot is hugely useful.

My one complaint is that the only implementation is in Perl. The core engine is written in C though, so someday I would like to convert the Perl into Python. I started several months ago, and haven't been able to get back to it. (https://github.com/srathbun/pyMarpa)

Re:Plan to throw one away by srathbun on Tuesday December 15, 2015 @12:34PM (#10739058)
Oh, and I found something new and fun for Marpa just now! It seems there's already the beginnings of a Python port (https://github.com/rns/libmarpa-bindings/blob/master/python/...) available.
Re:Plan to throw one away by jhallenworld on Monday December 14, 2015 @10:13PM (#10735673)
Be prepared to just use the generated tables and forget the generated code:

The generated code is not so great if you have an event driven environment: I mean I want to push 50 bytes into the compiler, instead of having it request the next input character. This means it's not so great for a repl, unless some other pre-parser gives complete translation units to lex/yacc.

I think Yacc has a pretty primitive conflict resolution strategy: (pick shift unless otherwise indicated by precedence declarations). If code could resolve the conflict then you could handle a lot of newer syntax: for example, in "a-b" vs. "a -b", you could use the whitespace to distinguish between prefix (reduce) or infix (shift).

It would be nice (I know someone who has done this..) if there was an option to degenerate into using backtracking to resolve conflicts. It means try all possibilities (split the stack at each conflict) and keep only those results which produce an error free full parse. If there is more than one full result, only then do you have a real conflict.

I'm not sure if other parser generators are any better, but there are improvements which could be made.

Re:Plan to throw one away by eru on Monday December 14, 2015 @10:34PM (#10735731)
In terms of ease of use, Parser Combinators beat most Parser Generators. (For absolute speed, Generators might still beat Combinators.)
Re:Plan to throw one away by jhallenworld on Monday December 14, 2015 @10:44PM (#10735778)
Yeah, I should try them. I remember a previous discussion about the old language SNOBOL having parser combinators as a built-in feature: https://news.ycombinator.com/item?id=10103460
Re:Plan to throw one away by eru on Tuesday December 15, 2015 @01:11AM (#10736243)
I learned Parser Combinators on Haskell. But a basic version is easy to write yourself in any language that supports first class functions.
Re:Plan to throw one away by Athas on Tuesday December 15, 2015 @03:38AM (#10736632)
> The generated code is not so great if you have an event driven environment: I mean I want to push 50 bytes into the compiler, instead of having it request the next input character. This means it's not so great for a repl, unless some other pre-parser gives complete translation units to lex/yacc.

This actually works quite well in [Happy](https://www.haskell.org/happy/), the Yacc-alike for Haskell, so it is not a fundamental limitation of Yacc-style tools. In Happy, it works by generating monadic code and using a monadic action for token reading, which you can then make event-driven.

Re:Plan to throw one away by Cacti on Monday December 14, 2015 @10:20PM (#10735691)
They still work perfectly fine, though, ANTLR is pretty great. Having learned both, I would hesitate to switch back from ANTLR.
Re:Plan to throw one away by knome on Tuesday December 15, 2015 @12:18AM (#10736087)
If you're in the market for a parser generator, you may want to look into the lemon parser distributed with sqlite3. I found it much nicer to play with.
Re:Plan to throw one away by lmm on Tuesday December 15, 2015 @06:13AM (#10737114)
Parser combinators are a better alternative. You end up writing a bit more of the data structure yourself, but the result is code that fundamentally makes sense.
Re:Plan to throw one away by amelius on Tuesday December 15, 2015 @06:43AM (#10737220)
Parsing JavaScript efficiently is not the problem. Much more difficult is writing the garbage collector. Especially a concurrent one.
Re:Plan to throw one away by munificent on Tuesday December 15, 2015 @12:33PM (#10739054)
> Much more difficult is writing the garbage collector. Especially a concurrent one.

Since JS is single-threaded, you can write a simple stop-the-world mark-sweep collector as a first iteration. (Simple reference counting probably isn't a good idea since cycles are common in JS.) Then you can move to incremental and/or generational if that's giving you annoying hitches. Only after that do you need to put concurrent on the table.

I believe even world class JS engines have only relatively recently started doing GC in another thread.

Re:Plan to throw one away by yarou on Monday December 14, 2015 @11:01PM (#10735842)
I don't know about "state of the art", but they are tried and true for lexing and parsing respectively.

If you are looking for something more exotic or a very specific use-case, I'd say use something like Ragel[0].

[0]http://www.colm.net/open-source/ragel/

Re:Plan to throw one away by nly on Tuesday December 15, 2015 @12:32AM (#10736124)
Ragel is great for replacing regex validation code ("Does this string look like a IP address, email address, or date?"), or for writing a lexer, but if you need to actually parse something (i.e. extract even a moderate amount of structured data) then you need something else.

It has a particularly sublime output mode for generating Graphviz dot files however.