5 ms·

Are Lex and Yacc still the state of the art 20 years later?

Terr_ 11y ago
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.
- jacquesm 11y ago
  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.
  - bm1362 11y ago
    Or maybe the job of the tool has become more complex in it's nature.
  - Terr_ 11y ago
    > 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.
jhallenworld 11y ago
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.
- eru 11y ago
  In terms of ease of use, Parser Combinators beat most Parser Generators. (For absolute speed, Generators might still beat Combinators.)
  - jhallenworld 11y ago
    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 https://news.ycombinator.com/item?id=10103460
    - eru 11y ago
      I learned Parser Combinators on Haskell. But a basic version is easy to write yourself in any language that supports first class functions.
- Athas 11y ago
  > 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/ 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.
kazinator 11y ago
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.html#Push-Decl http://www.gnu.org/software/bison/manual/html_node/Push-Decl...
- hvis 11y ago
  > freeware Did you mean "free software"?
Cacti 11y ago
They still work perfectly fine, though, ANTLR is pretty great. Having learned both, I would hesitate to switch back from ANTLR.
yarou 11y ago
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/ http://www.colm.net/open-source/ragel/
- nly 11y ago
  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.
knome 11y ago
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.
lmm 11y ago
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.
amelius 11y ago
Parsing JavaScript efficiently is not the problem. Much more difficult is writing the garbage collector. Especially a concurrent one.
- munificent 11y ago
  > 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.
garethrees 11y ago
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.
srathbun 11y ago
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#Generalized-LR-Parsing 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/ 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 https://github.com/srathbun/pyMarpa)
- srathbun 11y ago
  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/json-libmarpa.py https://github.com/rns/libmarpa-bindings/blob/master/python/...) available.

Terr_ 11y ago

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.

jacquesm 11y ago
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.
- bm1362 11y ago
  Or maybe the job of the tool has become more complex in it's nature.
- Terr_ 11y ago
  > 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.

jhallenworld 11y ago

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.

eru 11y ago
In terms of ease of use, Parser Combinators beat most Parser Generators. (For absolute speed, Generators might still beat Combinators.)
- jhallenworld 11y ago
  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 https://news.ycombinator.com/item?id=10103460
  - eru 11y ago
    I learned Parser Combinators on Haskell. But a basic version is easy to write yourself in any language that supports first class functions.
Athas 11y ago
> 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/ 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.

kazinator 11y ago

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.html#Push-Decl http://www.gnu.org/software/bison/manual/html_node/Push-Decl...

hvis 11y ago
> freeware Did you mean "free software"?

Cacti 11y ago

They still work perfectly fine, though, ANTLR is pretty great. Having learned both, I would hesitate to switch back from ANTLR.

yarou 11y ago

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/ http://www.colm.net/open-source/ragel/

nly 11y ago
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.

knome 11y ago

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.

lmm 11y ago

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.

amelius 11y ago

Parsing JavaScript efficiently is not the problem. Much more difficult is writing the garbage collector. Especially a concurrent one.

munificent 11y ago
> 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.

garethrees 11y ago

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.

srathbun 11y ago

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#Generalized-LR-Parsing 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/ 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 https://github.com/srathbun/pyMarpa)

srathbun 11y ago
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/json-libmarpa.py https://github.com/rns/libmarpa-bindings/blob/master/python/...) available.