4 ms·

AFAIK nowadays it is more common to write a recursive descent parser to build whatever structure you want to work with (if not use the parsing directly) than re

AFAIK nowadays it is more common to write a recursive descent parser to build whatever structure you want to work with (if not use the parsing directly) than rely on Flex/Bison. Personally i've written so many parsers over the years that the code for writing one "flows" naturally and i feel like Flex/Bison would introduce complexity and dependencies for no gain.

jakobson14 3y ago
Those Dodekalogue people are laughing.
kragen 3y ago
it introduces knowing where the ambiguities are in your grammar and eliminates large classes of parsing bugs it's also dramatically easier for other people to understand
- lifthrasiir 3y ago
  Unfortunately `%expect` is so easy to reach even in yacc.
CalChris 3y ago
There is also the ANTLR parser generator which generates a top-down parser. It's nice to write in a grammar. Still, almost all production lexers and parsers are hand written. https://www.antlr.org https://www.antlr.org
- mdaniel 3y ago
  > Still, almost all production lexers and parsers are hand written. As a counterpoint, I consider the JetBrains parsing system to be world class and they hand-write very few (instead building on this system: https://github.com/JetBrains/Grammar-Kit#readme https://github.com/JetBrains/Grammar-Kit#readme ) - https://github.com/JetBrains/intellij-community/blob/idea/233.11555.11/java/java-frontback-psi-impl/src/com/intellij/lang/java/lexer/_JavaLexer.flex https://github.com/JetBrains/intellij-community/blob/idea/23... (the parser I'll concede, as they do seem to be hand-rolling that part) - https://github.com/JetBrains/intellij-community/blob/idea/233.11555.11/python/python-parser/src/com/jetbrains/python/lexer/Python.flex https://github.com/JetBrains/intellij-community/blob/idea/23... (same for its parser) - https://github.com/JetBrains/intellij-community/blob/idea/233.11555.11/plugins/sh/core/src/com/intellij/sh/lexer/Sh.flex https://github.com/JetBrains/intellij-community/blob/idea/23... and https://github.com/JetBrains/intellij-community/blob/idea/233.11555.11/plugins/sh/core/grammar/sh.bnf https://github.com/JetBrains/intellij-community/blob/idea/23... - https://github.com/JetBrains/intellij-plugins/blob/idea/233.11555.11/makefile/grammars/MakefileLexer.flex https://github.com/JetBrains/intellij-plugins/blob/idea/233.... and https://github.com/JetBrains/intellij-plugins/blob/idea/233.11555.11/makefile/grammars/Makefile.bnf https://github.com/JetBrains/intellij-plugins/blob/idea/233....
vidarh 3y ago
I keep writing parser generators because I hate writing parsers manually, but keep returning to writing parsers manually because making a parser generator survive the first few meetings with reality without the pretty grammar turning into a hairy beast (when e.g. adding error recovery or trying to wrangle it into producing the trees you'd prefer rather than what fits the structure of the grammar) remains elusive. Ironically I think the sheer number of parser generators reflects our collective failure to make a good one more so than their amazing utility (sure, some projects so actually use some). I'm knee deep in her another parser generator these days, and I'm mildly hopeful (then that's always the case at the outset) of taking an augmented BNF variant and producing something DFA like that retains links from each state to higher level rules to retain enough information to backtrack to a reasonable place to both report errors from and/or resume parsing after an error. I doubt the overall approach is novel in any way, and I suspect I'll be back to hand rolling parsers soon enough, but who knows, I might end up with some worthwhile reusable components from it...
- kragen 3y ago
  there are boatloads of projects that use flex and bison, or antlr, for their parsers. handy here right now i have gcc 0.9, gforth, yosys's ilang and verilog frontends, linux kconfig, perf, and pcc, all using yacc or bison. also wget uses lex for css (maybe flex) but not yacc. but i only have the source code of a few dozen free software projects handy here to grep many of them do eventually switch to shotgun parsers, but in a sense that's sort of like rewriting a c subroutine in assembly; it gives you, usually, modestly more benefit, for enormously more effort — but it's a benefit you can't get any other way i recently worked on a project that parsed pdf files with a peg parser generator, a parser generator we had to extend in significant ways during the project in order to get what we needed

jakobson14 3y ago

Those Dodekalogue people are laughing.

kragen 3y ago

it introduces knowing where the ambiguities are in your grammar and eliminates large classes of parsing bugs it's also dramatically easier for other people to understand

lifthrasiir 3y ago
Unfortunately `%expect` is so easy to reach even in yacc.

CalChris 3y ago

There is also the ANTLR parser generator which generates a top-down parser. It's nice to write in a grammar. Still, almost all production lexers and parsers are hand written. https://www.antlr.org https://www.antlr.org

mdaniel 3y ago
> Still, almost all production lexers and parsers are hand written. As a counterpoint, I consider the JetBrains parsing system to be world class and they hand-write very few (instead building on this system: https://github.com/JetBrains/Grammar-Kit#readme https://github.com/JetBrains/Grammar-Kit#readme ) - https://github.com/JetBrains/intellij-community/blob/idea/233.11555.11/java/java-frontback-psi-impl/src/com/intellij/lang/java/lexer/_JavaLexer.flex https://github.com/JetBrains/intellij-community/blob/idea/23... (the parser I'll concede, as they do seem to be hand-rolling that part) - https://github.com/JetBrains/intellij-community/blob/idea/233.11555.11/python/python-parser/src/com/jetbrains/python/lexer/Python.flex https://github.com/JetBrains/intellij-community/blob/idea/23... (same for its parser) - https://github.com/JetBrains/intellij-community/blob/idea/233.11555.11/plugins/sh/core/src/com/intellij/sh/lexer/Sh.flex https://github.com/JetBrains/intellij-community/blob/idea/23... and https://github.com/JetBrains/intellij-community/blob/idea/233.11555.11/plugins/sh/core/grammar/sh.bnf https://github.com/JetBrains/intellij-community/blob/idea/23... - https://github.com/JetBrains/intellij-plugins/blob/idea/233.11555.11/makefile/grammars/MakefileLexer.flex https://github.com/JetBrains/intellij-plugins/blob/idea/233.... and https://github.com/JetBrains/intellij-plugins/blob/idea/233.11555.11/makefile/grammars/Makefile.bnf https://github.com/JetBrains/intellij-plugins/blob/idea/233....

vidarh 3y ago

I keep writing parser generators because I hate writing parsers manually, but keep returning to writing parsers manually because making a parser generator survive the first few meetings with reality without the pretty grammar turning into a hairy beast (when e.g. adding error recovery or trying to wrangle it into producing the trees you'd prefer rather than what fits the structure of the grammar) remains elusive. Ironically I think the sheer number of parser generators reflects our collective failure to make a good one more so than their amazing utility (sure, some projects so actually use some). I'm knee deep in her another parser generator these days, and I'm mildly hopeful (then that's always the case at the outset) of taking an augmented BNF variant and producing something DFA like that retains links from each state to higher level rules to retain enough information to backtrack to a reasonable place to both report errors from and/or resume parsing after an error. I doubt the overall approach is novel in any way, and I suspect I'll be back to hand rolling parsers soon enough, but who knows, I might end up with some worthwhile reusable components from it...

kragen 3y ago
there are boatloads of projects that use flex and bison, or antlr, for their parsers. handy here right now i have gcc 0.9, gforth, yosys's ilang and verilog frontends, linux kconfig, perf, and pcc, all using yacc or bison. also wget uses lex for css (maybe flex) but not yacc. but i only have the source code of a few dozen free software projects handy here to grep many of them do eventually switch to shotgun parsers, but in a sense that's sort of like rewriting a c subroutine in assembly; it gives you, usually, modestly more benefit, for enormously more effort — but it's a benefit you can't get any other way i recently worked on a project that parsed pdf files with a peg parser generator, a parser generator we had to extend in significant ways during the project in order to get what we needed