8 ms·

At this point, I think that it’s a bad idea to use things like yacc or lex for parsing and tokenization. Parser combinators are available in many languages and

by mruts 8y ago

At this point, I think that it’s a bad idea to use things like yacc or lex for parsing and tokenization. Parser combinators are available in many languages and are much easier to use and much more expressive. Of course if you need insane performance, a hand written recursive descent parser is probably the best option. The only reason people used parser generators in the past is because the languages they were using (mostly C I suppose) weren’t expressive enough to support higher order functions and higher kinded types.

mhh__ 8y ago
Error messages are a much more important reason to use a hand written parser/lexer: Unless you basically write your own parser generator, it'll never be as direct or fluent as a hand written parser
- zzzcpan 8y ago
  I'm not sure what you are confusing higher order parsers with, but there is absolute no problem with providing a couple of higher order abstractions for error messages. In fact, error messages are much easier to produce that way, than manually.
  - mhh__ 8y ago
    Are they? I'll be upfront in saying I've never done any actual work with parser combinators (I played with Parsec for about 15 minutes on the train), but I don't see how having direct control is worse. Easier, it may be, but I can only imagine real world situations harder when you get to the nasty stuff in your implementation (e.g. C++ templates basically need to be "run" while being parsed, or lexed even)
YorkshireSeason 8y ago
My rule of thumb: - If you don't need reasonable performance and reasonable error messages, (and your language is expressive enough) use parser combinators. - If you need at least one of reasonable performance and reasonable error messages, (or your language isn't expressive enough for parser combinators) use a parser generator. - If the code at hand is the interpreter / compiler for a widely used programming language (like Java or C++), get an expert to produce a hand-written parser.
- smaddox 8y ago
  Last I checked, Elm uses parser combinators and is hailed as having among the best error messages...
  - BoiledCabbage 8y ago
    How does Elm do it? Because Elms error messages were actually mind blowing. They fundamentally changed my view of what a language and compiler is capable of. It honestly makes every other language laughable. I seriously want anyone who ever designs a language to spend even one weekend playing with Elm just to see what's possible, because prior to that I would have never even considered a compiler could be so helpful. At times it was so clear and accurate it seems like it could've just fixed my code for me.
- zzzcpan 8y ago
  Hand written parsers are actually pretty slow. And higher order parsers are still hand written parsers and usually perform almost exactly the same (except for languages where higher order programming is slow on itself).
  - ascar 8y ago
    My personal experience is very contradictionary to that statement. Handoptimizing a slow PEG parser, but still using PEG gave me 10% performance increase. Handwriting it on low level libraries, but in the same high level language, gave me a 50,000% performance increase on the average file it had to parse. Task at hand wasn't a programming language though, but more like YAML with only one level of nesting and a lot of quoted strings (which were the bottleneck for PEG in my case).
Darmani 8y ago
I'm a Ph. D. student in programming languages. I've written at least 7 language frontends over the years, read many more, and have given a talk on parsing algorithms. My primary programming language is Haskell. I really don't like parser combinators. I've found that, with parser generators, bugs in the parser are very rare. When they exist, you can find them just by carefully inspecting your grammar. With parser combinators, a misplaced "try" can give you a parser that looks correct and usually works, but some odd placement of tokens makes it fail to parse something it should. I agree that yacc is not very good, but it's hardly state of the art. It's a LALR generator, and hence very restricted. Instead, you can use: (1) ANTLR, which has a huge ecosystem, produces very fast generators, and can take in an almost-arbitrary context-free grammar. The ALL(*) algorithm makes it far superior to Yacc. (2) A GLR parser-generator, which can take in an actually arbitrary grammar, and is usually very fast. The one I have experience with is Semantic Designs DMS. Michael Mehlich of Semantic Designs has produced a C++ parser that can accurately parse all the major C++ dialects (MS, GCC, Borland, etc), all using general machinery. The only other group that's come close is the Edison Group, which has a huge hand-written C++ parser, and has 5 people full-time on it.
- deleted 8y ago
  [deleted]
- anaphor 8y ago
  What about PEGs? You can get the benefits of writing down a grammar that you can analyze yourself, and you can call methods on the production results, etc.
  - ufo 8y ago
    PEGs have the same downsides the parser combinators have. If you put things in the wrong order you can have programs that work most of the time but do the wrong thing on a corner case or in a parsing ambiguity.
- mekaj 8y ago
  By default I’m skeptical of hand-written parsers, especially if they’re implemented in a language lacking memory safety features. I have seen too many parsers fall victim to (domain specific) fuzzing, and the consequences are serious security vulnerabilities. Parser combinators are great, but they’re still hand-written in excessively powerful languages. That’s error-prone if the goal is to end up with a trustworthy, portable parser. The most frequently used parser combinator tools I know of are embedded DSLs, which means porting such a parser to another language requires manually converting to another parser combinator’s syntax and semantics and potentially implementing a new DSL which hasn’t yet been battle tested. Parser generators which are in a position to get battle tested by supporting many parser implementations and integrations seem like the safest and most scalable way to go. I’m not familiar with Semantic Designs’ GLR implementation; thanks for mentioning it. Another worth knowing is tree-sitter (https://tree-sitter.github.io/tree-sitter/ https://tree-sitter.github.io/tree-sitter/). As a GLR-based parser generator it supports ambiguous context-free grammars. At first ambiguity may sound like a downside, but without a computer-verified proof that your grammar doesn’t admit multiple valid parses for any inputs it’s safest to assume ambiguity and proceed accordingly. For example, if at parse-time multiple parses are found you have the option to warn the user or even reject their input with a diff of the ASTs so they can try to patch the input so it’s no longer ambiguous. Tree-sitter is young, but it has reach. Atom editor packages for languages are encouraged to implement tree-sitter parsers. It’s particularly well-suited for editors because it supports incremental parsing. Parsing the same file from scratch after every edit isn’t necessary. Recently I implemented a tree-sitter grammar for ABNF (https://github.com/jmitchell/tree-sitter-abnf https://github.com/jmitchell/tree-sitter-abnf) and an Atom package (https://atom.io/packages/language-abnf https://atom.io/packages/language-abnf) for it. Now I’m exploring how to generate tree-sitter parsers for grammars specified using ABNF, such as Dhall’s (https://github.com/dhall-lang/dhall-lang/blob/master/standard/dhall.abnf https://github.com/dhall-lang/dhall-lang/blob/master/standar...). My plan is to automatically generate and fuzz C-friendly parser libraries for many languages to make them more accessible. I also want to help address any tree-sitter bugs discovered along the way that could translate into security vulnerabilities in generated parsers. For now this is a labor of love, and I am not affiliated with the tree-sitter project.
pjmlp 8y ago
I never liked them, even in the late 90's, in spite of having written a tutorial how to use bison with C++, back when the integration wasn't the best. Category grammars, PCCTS and ANTRL always seemed better approaches to prototype languages. I was quite happy that our compiler design professor decided to switch to the barely introduced Java, adopting JavaCC and JJTree in the process.
CJefferson 8y ago
Parser combinators are fine for languages not designed to be written by people, but the error messages tend to be awful. What's increasingly clear to me, having designed a few languages, is that a well designed languages is easy to parse. I work on a couple of languages which require one token lookahead. This means when something goes wrong, we know exactly where the problem is, and what token we didn't expect.
QuinnWilton 8y ago
I like parser combinators, but I think they obscure the formal definition of the language being parsed. There's something to be said for having a declarative specification of what you're parsing. This is less important if you're just implementing a parser for an existing language or standard, but if your implementation is going to be the reference implementation, then I think it's important to generate your parser from the formal language you're working with, to give other implementers confidence that your implementation is correct.
- jarcane 8y ago
  I like parser combinators, but I think they obscure the formal definition of the language being parsed. There's something to be said for having a declarative specification of what you're parsing. I used to feel similarly, but that was because I'd been introduced to parser combinators in languages that lacked the features to replicate what made them great in Haskell. Properly implemented, they can take on a very readable, declarative-like style. Over the weekend for instance, I threw together a JSON parser in Haskell using Graham Hutton's monadic parser library, and I found the result refreshingly clear and readable: https://gist.github.com/jarcane/025f5475418858bba8276f1dfcf215be https://gist.github.com/jarcane/025f5475418858bba8276f1dfcf2... With do notation and ADTs, the code comes out looking more or less pretty close to what it describes, and that reflectivity applies both to the reading and the coding. I simply describe the patterns in looking to match and which parts to pass on, and voila: a parser.
- naasking 8y ago
  To clarify: Combinators are declarative specifications, and for parsing, they are specifications of the grammar.
WalterBright 8y ago
Lexing and parsing are the easiest (by far) parts of writing a compiler. Writing them by hand is very easy, and the code often looks like the grammar. They also tend to be the least buggy parts, I would handwave that maybe 1 in a thousand bugs were in the lexer/parser. Lexer/parser generators are simply not needed and not particularly helpful. Two areas where they are particularly inferior: 1. Error messages. Since the generator doesn't know what you're doing, error messages tend to be generic and very unhelpful to the user. With a hand-built one, context can be supplied to the user in the language of the language(!). Suggestions for corrections for the most common mistakes can be given. 2. Error recovery. Doing this well relies on guessing at what the most likely AST was intended by the user. But a generator can't know that. By the time you've expended effort trying to overcome (1) and (2), you'd have been better off just writing a custom one. Here are D's lexer and parser: https://github.com/dlang/dmd/blob/master/src/dmd/lexer.d https://github.com/dlang/dmd/blob/master/src/dmd/lexer.d https://github.com/dlang/dmd/blob/master/src/dmd/parse.d https://github.com/dlang/dmd/blob/master/src/dmd/parse.d For a complex language like D, they are pretty simple. (The lexer even comes with some builtin unittests!) Probably the most complex part is the arbitrary lookahead scheme. Of course, this wouldn't be necessary if the grammar didn't need lookahead. P.S. The initial versions of these were written 20 years ago in C, so the coding style is a bit archaic and could use improvement.
- WalterBright 8y ago
  For comparison, here's the C++ lexer for Digital Mars C++: https://github.com/DigitalMars/Compiler/blob/master/dm/src/dmc/xtoken.d https://github.com/DigitalMars/Compiler/blob/master/dm/src/d... The parser isn't in its own file, it's intermingled with the semantic processing, a mistake I didn't want to repeat with D :-)
- targon 8y ago
  > They also tend to be the least buggy parts, I would handwave that maybe 1 in a thousand bugs were in the lexer/parser. Ehh, I don't know... https://johanengelen.github.io/ldc/2018/01/14/Fuzzing-with-LDC.html https://johanengelen.github.io/ldc/2018/01/14/Fuzzing-with-L... From the article: > My expectation was that there would be a bug deep down with some rare cornercase of a cornercase, and that the fuzzer would have to run for hours and hours covering more and more of the lexer to, perhaps, finally find a bug. So I was preparing for a long fuzzing session, wanted to go to bed and kick this one off but… The fuzzer found a first failure within a second. > Running the fuzzer several times, sometimes it still hadn’t found a bug after 15 seconds, but usually it found the bug within a second; the process is (semi-)random so that’s expected.

by mruts 8y ago

mhh__ 8y ago

Error messages are a much more important reason to use a hand written parser/lexer: Unless you basically write your own parser generator, it'll never be as direct or fluent as a hand written parser

zzzcpan 8y ago
I'm not sure what you are confusing higher order parsers with, but there is absolute no problem with providing a couple of higher order abstractions for error messages. In fact, error messages are much easier to produce that way, than manually.
- mhh__ 8y ago
  Are they? I'll be upfront in saying I've never done any actual work with parser combinators (I played with Parsec for about 15 minutes on the train), but I don't see how having direct control is worse. Easier, it may be, but I can only imagine real world situations harder when you get to the nasty stuff in your implementation (e.g. C++ templates basically need to be "run" while being parsed, or lexed even)

YorkshireSeason 8y ago

My rule of thumb: - If you don't need reasonable performance and reasonable error messages, (and your language is expressive enough) use parser combinators. - If you need at least one of reasonable performance and reasonable error messages, (or your language isn't expressive enough for parser combinators) use a parser generator. - If the code at hand is the interpreter / compiler for a widely used programming language (like Java or C++), get an expert to produce a hand-written parser.

smaddox 8y ago
Last I checked, Elm uses parser combinators and is hailed as having among the best error messages...
- BoiledCabbage 8y ago
  How does Elm do it? Because Elms error messages were actually mind blowing. They fundamentally changed my view of what a language and compiler is capable of. It honestly makes every other language laughable. I seriously want anyone who ever designs a language to spend even one weekend playing with Elm just to see what's possible, because prior to that I would have never even considered a compiler could be so helpful. At times it was so clear and accurate it seems like it could've just fixed my code for me.
zzzcpan 8y ago
Hand written parsers are actually pretty slow. And higher order parsers are still hand written parsers and usually perform almost exactly the same (except for languages where higher order programming is slow on itself).
- ascar 8y ago
  My personal experience is very contradictionary to that statement. Handoptimizing a slow PEG parser, but still using PEG gave me 10% performance increase. Handwriting it on low level libraries, but in the same high level language, gave me a 50,000% performance increase on the average file it had to parse. Task at hand wasn't a programming language though, but more like YAML with only one level of nesting and a lot of quoted strings (which were the bottleneck for PEG in my case).

Darmani 8y ago

I'm a Ph. D. student in programming languages. I've written at least 7 language frontends over the years, read many more, and have given a talk on parsing algorithms. My primary programming language is Haskell. I really don't like parser combinators. I've found that, with parser generators, bugs in the parser are very rare. When they exist, you can find them just by carefully inspecting your grammar. With parser combinators, a misplaced "try" can give you a parser that looks correct and usually works, but some odd placement of tokens makes it fail to parse something it should. I agree that yacc is not very good, but it's hardly state of the art. It's a LALR generator, and hence very restricted. Instead, you can use: (1) ANTLR, which has a huge ecosystem, produces very fast generators, and can take in an almost-arbitrary context-free grammar. The ALL(*) algorithm makes it far superior to Yacc. (2) A GLR parser-generator, which can take in an actually arbitrary grammar, and is usually very fast. The one I have experience with is Semantic Designs DMS. Michael Mehlich of Semantic Designs has produced a C++ parser that can accurately parse all the major C++ dialects (MS, GCC, Borland, etc), all using general machinery. The only other group that's come close is the Edison Group, which has a huge hand-written C++ parser, and has 5 people full-time on it.

deleted 8y ago
[deleted]
anaphor 8y ago
What about PEGs? You can get the benefits of writing down a grammar that you can analyze yourself, and you can call methods on the production results, etc.
- ufo 8y ago
  PEGs have the same downsides the parser combinators have. If you put things in the wrong order you can have programs that work most of the time but do the wrong thing on a corner case or in a parsing ambiguity.
mekaj 8y ago
By default I’m skeptical of hand-written parsers, especially if they’re implemented in a language lacking memory safety features. I have seen too many parsers fall victim to (domain specific) fuzzing, and the consequences are serious security vulnerabilities. Parser combinators are great, but they’re still hand-written in excessively powerful languages. That’s error-prone if the goal is to end up with a trustworthy, portable parser. The most frequently used parser combinator tools I know of are embedded DSLs, which means porting such a parser to another language requires manually converting to another parser combinator’s syntax and semantics and potentially implementing a new DSL which hasn’t yet been battle tested. Parser generators which are in a position to get battle tested by supporting many parser implementations and integrations seem like the safest and most scalable way to go. I’m not familiar with Semantic Designs’ GLR implementation; thanks for mentioning it. Another worth knowing is tree-sitter (https://tree-sitter.github.io/tree-sitter/ https://tree-sitter.github.io/tree-sitter/). As a GLR-based parser generator it supports ambiguous context-free grammars. At first ambiguity may sound like a downside, but without a computer-verified proof that your grammar doesn’t admit multiple valid parses for any inputs it’s safest to assume ambiguity and proceed accordingly. For example, if at parse-time multiple parses are found you have the option to warn the user or even reject their input with a diff of the ASTs so they can try to patch the input so it’s no longer ambiguous. Tree-sitter is young, but it has reach. Atom editor packages for languages are encouraged to implement tree-sitter parsers. It’s particularly well-suited for editors because it supports incremental parsing. Parsing the same file from scratch after every edit isn’t necessary. Recently I implemented a tree-sitter grammar for ABNF (https://github.com/jmitchell/tree-sitter-abnf https://github.com/jmitchell/tree-sitter-abnf) and an Atom package (https://atom.io/packages/language-abnf https://atom.io/packages/language-abnf) for it. Now I’m exploring how to generate tree-sitter parsers for grammars specified using ABNF, such as Dhall’s (https://github.com/dhall-lang/dhall-lang/blob/master/standard/dhall.abnf https://github.com/dhall-lang/dhall-lang/blob/master/standar...). My plan is to automatically generate and fuzz C-friendly parser libraries for many languages to make them more accessible. I also want to help address any tree-sitter bugs discovered along the way that could translate into security vulnerabilities in generated parsers. For now this is a labor of love, and I am not affiliated with the tree-sitter project.

pjmlp 8y ago

I never liked them, even in the late 90's, in spite of having written a tutorial how to use bison with C++, back when the integration wasn't the best. Category grammars, PCCTS and ANTRL always seemed better approaches to prototype languages. I was quite happy that our compiler design professor decided to switch to the barely introduced Java, adopting JavaCC and JJTree in the process.

CJefferson 8y ago

Parser combinators are fine for languages not designed to be written by people, but the error messages tend to be awful. What's increasingly clear to me, having designed a few languages, is that a well designed languages is easy to parse. I work on a couple of languages which require one token lookahead. This means when something goes wrong, we know exactly where the problem is, and what token we didn't expect.

QuinnWilton 8y ago

I like parser combinators, but I think they obscure the formal definition of the language being parsed. There's something to be said for having a declarative specification of what you're parsing. This is less important if you're just implementing a parser for an existing language or standard, but if your implementation is going to be the reference implementation, then I think it's important to generate your parser from the formal language you're working with, to give other implementers confidence that your implementation is correct.

jarcane 8y ago
I like parser combinators, but I think they obscure the formal definition of the language being parsed. There's something to be said for having a declarative specification of what you're parsing. I used to feel similarly, but that was because I'd been introduced to parser combinators in languages that lacked the features to replicate what made them great in Haskell. Properly implemented, they can take on a very readable, declarative-like style. Over the weekend for instance, I threw together a JSON parser in Haskell using Graham Hutton's monadic parser library, and I found the result refreshingly clear and readable: https://gist.github.com/jarcane/025f5475418858bba8276f1dfcf215be https://gist.github.com/jarcane/025f5475418858bba8276f1dfcf2... With do notation and ADTs, the code comes out looking more or less pretty close to what it describes, and that reflectivity applies both to the reading and the coding. I simply describe the patterns in looking to match and which parts to pass on, and voila: a parser.
naasking 8y ago
To clarify: Combinators are declarative specifications, and for parsing, they are specifications of the grammar.

WalterBright 8y ago

Lexing and parsing are the easiest (by far) parts of writing a compiler. Writing them by hand is very easy, and the code often looks like the grammar. They also tend to be the least buggy parts, I would handwave that maybe 1 in a thousand bugs were in the lexer/parser. Lexer/parser generators are simply not needed and not particularly helpful. Two areas where they are particularly inferior: 1. Error messages. Since the generator doesn't know what you're doing, error messages tend to be generic and very unhelpful to the user. With a hand-built one, context can be supplied to the user in the language of the language(!). Suggestions for corrections for the most common mistakes can be given. 2. Error recovery. Doing this well relies on guessing at what the most likely AST was intended by the user. But a generator can't know that. By the time you've expended effort trying to overcome (1) and (2), you'd have been better off just writing a custom one. Here are D's lexer and parser: https://github.com/dlang/dmd/blob/master/src/dmd/lexer.d https://github.com/dlang/dmd/blob/master/src/dmd/lexer.d https://github.com/dlang/dmd/blob/master/src/dmd/parse.d https://github.com/dlang/dmd/blob/master/src/dmd/parse.d For a complex language like D, they are pretty simple. (The lexer even comes with some builtin unittests!) Probably the most complex part is the arbitrary lookahead scheme. Of course, this wouldn't be necessary if the grammar didn't need lookahead. P.S. The initial versions of these were written 20 years ago in C, so the coding style is a bit archaic and could use improvement.

WalterBright 8y ago
For comparison, here's the C++ lexer for Digital Mars C++: https://github.com/DigitalMars/Compiler/blob/master/dm/src/dmc/xtoken.d https://github.com/DigitalMars/Compiler/blob/master/dm/src/d... The parser isn't in its own file, it's intermingled with the semantic processing, a mistake I didn't want to repeat with D :-)
targon 8y ago
> They also tend to be the least buggy parts, I would handwave that maybe 1 in a thousand bugs were in the lexer/parser. Ehh, I don't know... https://johanengelen.github.io/ldc/2018/01/14/Fuzzing-with-LDC.html https://johanengelen.github.io/ldc/2018/01/14/Fuzzing-with-L... From the article: > My expectation was that there would be a bug deep down with some rare cornercase of a cornercase, and that the fuzzer would have to run for hours and hours covering more and more of the lexer to, perhaps, finally find a bug. So I was preparing for a long fuzzing session, wanted to go to bed and kick this one off but… The fuzzer found a first failure within a second. > Running the fuzzer several times, sometimes it still hadn’t found a bug after 15 seconds, but usually it found the bug within a second; the process is (semi-)random so that’s expected.