7 ms·

Use context-free grammars instead of parser combinators and PEG

100 points by mmastrac 2y ago

HelloNurse 2y ago
Parsing is an application domain where I'd expect more hard logic and less soft feelings than in this article. "I feel that CFGs more naturally represent how we think" but "All this doesn't apply to situations where you trying to parse some language, whose specification explicitly says that the language is based on PEG formalism" A terrible context free grammar (with left and right recursion, not a small feat) is presented. "I blindly converted grammar above to Haskell code" "I accidentally discovered my grammar was ambiguous!" "All this gave me psychological trauma (figuratively speaking). I will never use Parsec (and PEG parsers) anymore." Denial that an ambiguous grammar is a defect, denial that the ambiguity has to be resolved, refusal to use parser combinators to resolve the ambiguity in the correct way. It's also strange to see someone react to a modest, non-shameful failure (guess what, parsing is difficult is language design is even more difficult) that should be a nice learning opportunity (elegant context free grammars are usually insufficient in practical usage) with anger and radicalization far beyond an acceptable level of blaming the tools. The other post in the blog, however, follows a similar general pattern: never use a popular technique (de Bruijn indices rather than parser combinators), because they advocate another technique (expressing lambda calculus terms with randomly generated globally unique identifiers for all bound variables rather than pure context free grammars) because that's what they like.
- just_mc 2y ago
  Well said.
- eslaught 2y ago
  So, I agree with your take as a reaction to this article specifically. However, I also think that there is a legitimate point here. Which is that parser combinators, even in languages like Haskell, are shockingly tricky to use correctly. In particular, they violate the usual Haskell principle that "if it compiles, then it will probably run correctly". Having written multiple parsers in multiple languages with multiple parsing frameworks (including direct recursive descent), using Parsec in Haskell was the only time I had to write a test suite for the parser specifically. And that's because there were so many footguns that I was repeatedly making mistakes despite the fact that this was a port of a parser I'd already written (and therefore, ought to know backward and forward). (For the record, this was not my first Haskell project either, which is why I was so shocked it went so poorly.) I'm sure it's possible to make mistakes in CFGs too, but practically speaking I can't remember running into that situation myself. Whereas with Parsec I ran into it repeatedly.
  - HelloNurse 2y ago
    PEG parsing is likely to squash some grammar ambiguities in unexpected ways, making a test suite a very good idea; but we shouldn't forget that this kind of failure can only happen starting from an ambiguous grammar specification, so the work of taming PEG precedence or combinator behaviour is not an additional burden of the technology but an additional tool to correct the grammar to become less ambiguous, an alternative to rewriting it in unnatural, verbose and complex ways.
    - yatac42 2y ago
      > but we shouldn't forget that this kind of failure can only happen starting from an ambiguous grammar specification I don't think that's true. The following CFG is unambiguous: S ::= A S | A A ::= 'a' | 'a' 'b' Yet if we translate this 1-to-1 to a PEG (without changing the order of the alternatives), it's not going to match any input with 'b's in it, so it doesn't match the same language.
      - HelloNurse 2y ago
        This grammar is difficult to adapt to ordered choice, having 4 possible variants that mostly define different languages from each other and from the "same" grammar with traditional parsing. It's a formally very different problem from spontaneously and arbitrarily disambiguating an ambiguous grammar, but in practice it causes the same kind of suffering and it's likely to be a more common issue.
  - rowanG077 2y ago
    I have written a simple compiler in Haskell using parser combinators for parsing. And I couldn't disagree more with you. It was super straightforward writing the parser and it worked immediately. Why do say they are tricky?
    - HelloNurse 2y ago
      What language did you compile? Some languages can be much more manageable than others. Did you adapt an existing CFG, or another parser combinator implementation, or did you start from scratch? The first case is more treacherous.
- paulddraper 2y ago
  > Parsing is an application domain where I'd expect more hard logic and less soft feelings than in this article. Ah, an S-expr enjoyer I see
- kragen 2y ago
  it's important to read your comment in the context that we have established in https://news.ycombinator.com/item?id=40582885 https://news.ycombinator.com/item?id=40582885 that you wrote it before finding out what pegs were i'm curious if you change your mind once you understand peg's limited backtracking semantics
- aranchelk 2y ago
  > I feel that CFGs more naturally represent how we think Author could have replaced the “we” with “I” and made it into a mildly interesting diary entry.
behnamoh 2y ago
This also applies to LLM constrained generation. Instead of outputting something that promised to be a JSON (but maybe it's not, or maybe it's an incomplete JSON, or maybe it's a JSON but doesn't conform to your JSON schema), just use CFGs (e.g., GBNF) to guide the model to generate the exact JSON you want. It's guaranteed, and you don't have to send lengthy JSON schemas to the LLM.
- hansvm 2y ago
  With the caveat that you significantly change the distribution of the output. Picking on JSON with current-gen LLMs, consider (1) Retry till the output passes the grammar (2) Only generate tokens passing the grammar Assuming (2) actually runs (not guaranteed for all grammars and distributions theoretically, basically never a problem in practice), one of many common failure modes is forcing the generation of grammar-valid tokens after an error has been made. E.g., one sort of "truncation" error happens when the LLM is producing an object with metadata around a transcription (e.g., an author, timestamp, and blob of text). A common incorrect result looks like {"author": "John Doe", "timestamp": "20:23:58", "transcript": "My name is John Doe, and ... Those ellipses weren't just cutting off my description of the invalid data. The model will produce ellipses after the string carries on for too long. If you greedily produce tokens adhering to a grammar, your only options at that point are continuing the string and ending it, and both options are very wrong. Contrast that with option (1). Empirically, if the model is willing to actually produce those tokens rather than cut off its answer, it's much more likely to be correct (i.e., the presence of that ellipses bug will tend to cut off the entire response, not just truncating the string and still generating a valid object). If you just retry till the model succeeds then you have a substantially higher accuracy in that task. That particular example may or may not apply to your favorite problem and favorite model, but it highlights the problem that constraining to a grammar forces a large skew in your result distribution. A large part of the power of an LLM is its autoregressiveness, and other sampling algorithms only tend to perform well when there's some outside knowledge relevant to the real-world problem being solved (e.g., if the LLM has >50% accuracy on a task with a small, finite number of outputs, then you might want to drop the temperature to 0 and just sample repeatedly, selecting the most likely option), but messing with the result distribution without a rationale for why you're still likely to get good results is risky.
deleted 2y ago
[deleted]
hansvm 2y ago
> Parser and lexer for reversible parsing with guaranteed reversibility. Seems to be totally unique across all programming languages. Of course, CFG-based. There's also the parser combinator approach of parser-printers ;)
lifthrasiir 2y ago
The reality however is that many applications find a recursive descent parser easier to handle once the grammar has been fixed (and in spite of its many caveats!), so PEG is a natural formalism for them. For example I once tried to write a full parser for Lua in LALRPOP and gave up after a week because it was too slow to compile and too hard to avoid conflicts; I ended up writing a recursive descent parser in a single day. I already knew that LALRPOP doesn't resolve shift-reduce conflicts and also how to transform the grammar to avoid them, but that wasn't enough for me. I think there is a niche for CFG-like formalisms with bounded PEG-like constructs so that it can be quickly adjusted without giving up all the benefits of CFG. I have been already in situations where I really want to have such formalisms for multiple times, including the aforementioned one.
yawpitch 2y ago
> Python spec says Python is PEG, so you should use PEG parser for parsing Python. Python switched to PEG in IIRC 3.9, the language standard, parser and the grammer were previously CFG, specifically LL(1). That switch implies that maybe the author is only correct until your language is widely (if not wildly) successful? https://peps.python.org/pep-0617/ https://peps.python.org/pep-0617/
- VagabundoP 2y ago
  Core.py episode on the transition to the parser mentioned limitations of the LL(1) parser wrt to new syntax.[1][2] There were some positive side effects to the move and it enabled better exceptions, with more detailed information. [1] https://podcasts.apple.com/us/podcast/episode-8-the-new-parser/id1712665877?i=1000647675451 https://podcasts.apple.com/us/podcast/episode-8-the-new-pars... [2]https://podcasts.apple.com/us/podcast/episode-7-the-old-parser/id1712665877?i=1000643716095 https://podcasts.apple.com/us/podcast/episode-7-the-old-pars...
- dathinab 2y ago
  I think the main issue here is that you in general just don't "get a CFG" parser which magically works correct with nice ergonomics and grate performance. You get a LL(1), LR(1), LALR(1), etc. parser and the more of CFG they can parse the more drawbacks there often are. And making a programming language fit into more limited parsers like LL(1) is a total pain. So you need something which is more powerful, but still not to complicated to have a fast efficient implementation for python and python tooling. At which point it can be simpler to just go with PEG especially if you have the amount of people and brain power to make sure you don't slip up with resolving ambiguity in a arbitrary "accidental" way.
vidarh 2y ago
His problem isn't primarily the choice of formalism, but that his grammar is wildly overcomplicated and makes it really hard to see what language it specifies irrespective of formalism. This is a common problem. In this case the amount of recursion makes it hard to even guess at what it is trying to express. If my grammar looked like that, I'd throw it away and start over, because the problem to me appears to be not quite having a clear idea of what the grammar is expressing. EDIT: Trying to clean up his grammar into something readable t0 = t1 | a t1 = t3 ("==>" t1)? t3 = (id | d)+ c? | b a = "!!" id c "." t0 b = "%" id c "." t3 c = "::" t0 d = "(" t0 ")" t999 in the original was left-recursive, but in this case that's a matter that can be left to the parse tree construction if he insists on keeping it that way. For your own sanity don't mix left and right-recursion in a parser, and decide how you structure the parse-tree in terms of left/right binding separately, and only express that in the grammar if your tool doesn't let you express it when building the tree, or if it actually changes the language recognised. One thing to note, is that my first instinct when writing parsers is to look for opportunities to factor out rules that start with a terminal, because it's usually a good way of avoiding or reducing the need for lookahead. Hence the extra rules, that to me at least makes it a lot clearer. The part of the grammar to look for places where your formalism causes ambiguities is now much smaller. This grammar still gives me hives, but without knowing his constraints and intent, it's tricky to see if it can be cleaned up further.
- chipdart 2y ago
  > If my grammar looked like that, I'd throw it away and start over, because the problem to me appears to be not quite having a clear idea of what the grammar is expressing. That's fine if you are working in a purely academic domain, or you're just having fun writing something on your free time. In production settings, you need to keep extending whatever language you have. The alternative is having to start to maintain two separate parsers and a migration tool, and be stuck with that for years. The point is that being able to throw away code is a luxury that virtually no one is able to afford.
  - bruce343434 2y ago
    What do you mean? Stuff gets refactored all the time.
aidenn0 2y ago
> And if you agree with me that grammar above in intuitive sense is ambiguous, i. e. if you agree that A :: B ==> C allows two parse trees, then your brain thinks in terms of CFG, too! CFGs are simply more natural. Count me as my brain being on team PEG then, so also a data point against CFGs being more natural. In fact, I think this example proves that author of TFA does not think in CFG, otherwise they wouldn't have accidentally written an ambiguous grammar! In my experience, it's an extraordinarily tiny fraction of people who actually want parse forests instead of parse trees in the languages they are constructing (TFA specifically excludes pre-existing languages). A PEG will be unambiguous. People want unambiguous. There's a chance it disambiguates against the intent of the author, but a CFG won't disambiguate at all, which will nearly always be against the intent of the author.
- orlp 2y ago
  Great! Someone who's brain is on team PEG. You are just the person I need. Can you explain in plain English what strings match the following PEG grammar? Str = "a" Str "a" / "a"
  - HelloNurse 2y ago
    Any odd number 2n+1 of "a" repetitions, longest match. The inflating first rule is preferred about 2n times until it fails at input end, then the parser backtracks until the middle "a" is matched by the second rule and the others by n expansions of the first rule.
    - orlp 2y ago
      I'm sorry that is not correct at all. It does not match the string "aaaaa" for example.
      - HelloNurse 2y ago
        Why not? Preferring the first rule, after seeing a you expect Str a; after seeing another a you expect Str a a; after seeing the third a you expect Str a a a (and you can already realize it cannot match) so after some backtracking you match the third a with the second rule instead, expecting a a, which are the fourth and fifth a in the input. Do you have a different parsing algorithm in mind?
Eliah_Lakhin 2y ago
I think it all depends on the language, but I found it (usually) easier to implement the recursive-descending parsers just manually. This may include combination approach too, but using my own combinatorial and domain-specific functions. In a nutshell such a parser is PEG in a sense that the choice is ordered, but with little to no test expressions. In other words, I try to stick to lookahead-1 most of the time. Left recursion quite often could be resolved by lifting the branches to their siblings rather than re-parsing the same things many times using the cache (packrat). In fact both approaches, the packrat and the nodes lifting, are the same in a nutshell, but nodes lifting is usually easier to maintain (again, it all depends). Writing the parser manually, or in other words a set of relatively simple mutually recursive functions, in my opinion, is not the hardest problem in practical engineering. At least it's not so hard when you have a mental model of the language's syntax upfront. If the language fits specific class of formal grammars very well, perhaps it would be not so hard to implement it using the parsers generator tool. But it is likely there will be edge cases that are hard to express properly using the formal grammar, and fighting with the tool specifics will waste a lot of your time rather than benefit you.
- eru 2y ago
  > I think it all depends on the language, but I found it (usually) easier to implement the recursive-descending parsers just manually. This may include combination approach too, but using my own combinatorial and domain-specific functions. Working in what languages did you make this observation? In something like C I would probably agree with you. But in eg Haskell or OCaml, I would probably prefer parser combinators.
  - Eliah_Lakhin 2y ago
    I work with Rust most of the time. As of the pure functional languages, yes, perhaps using parser combinators is better.
  - deredede 2y ago
    In other functional languages I tend to reach for combinators, but in OCaml I either use Menhir or regret not using it.
zelphirkalt 2y ago
PEGs are more expressive than CFGs, iirc. So use the right tool for the job. I have come to quite like PEGs and they become quite natural, once one understands things like no left recursion. I also often prefer them over complex regexes.
- sparkie 2y ago
  It's difficult to conclude meaningfully that any one is more expressive than the other. They parse different languages, though there is a large subset of PEGs which are also CFGs, they're not a proper superset - there are things you can parse with a CFG which cannot be parsed with PEG, and vice-versa. OTOH, when comparing LL and LR, we can conclusively say that LR are more expressive than LL because they're a proper superset - any language that can be parsed by an LL(k) grammar can be parsed by an LR(k) grammar (for same k).
  - orlp 2y ago
    > there are things you can parse with a CFG which cannot be parsed with PEG This is not known. It is conjectured to be true because if all context-free languages could be parsed with a PEG grammar it would imply you'd have a linear-time boolean matrix multiplication algorithm, but no one has ever constructed a concrete example of a language which is context-free but not parsable with a PEG.
    - kragen 2y ago
      the other one is known, though, isn't it? there's an example of a peg parsing a non-context-free language aⁿbⁿcⁿ in ford's dissertation?
      - orlp 2y ago
        Yes.
mrkeen 2y ago
> when I wrote that grammar, I meant it is CFG. Simply because my brain thinks in terms of CFG. > I blindly converted grammar above to Haskell code. > But then I accidentally discovered my grammar was ambiguous! You wrote an ambiguous CFG, implemented its parser, and then discovered that it was ambiguous. Would the CFG have become non-ambiguous if you took your advice and avoided parser combinators? This makes me really want to avoid the CFG step altogether.
- sparkie 2y ago
  The advice to "use CFGs" is incomplete. What you really want is to use one of the deterministic subsets of CFGs, like LR(k), and importantly, with a parser-generator which will reject any non-LR productions in the grammar before even generating the parser. This way, you can get a guarantee that there are no ambiguities in the language you've defined ahead-of-time. You might consider this to be analogous to the difference between static and dynamic typing. A statically typed language will reject an erroneously typed program before attempting to run it, but the dynamically typed language may accept it and attempt to run it, only to fail at runtime if there's a type mismatch. Parser combinators are more like the dynamic language. You find out at runtime (when parsing), whether the text you have parsed has ambiguities because more than one parse result is returned if that is the case. Normal operation is that the combinator returns a single result, in which case there are no ambiguities in the input, but the parser combinator doesn't provide any guarantees about absence of ambiguity in the language itself - it only proves that there's no ambiguity for the given input. And there's no practical way of testing for all inputs that the defined language is unambiguous, because there are infinite possible inputs. LL/LR parser generators are like a type system for grammar. They'll take your input grammar, and check that all rules adhere to the constraints of LL/LR, and iff that's the case, then they'll produce a valid parser for a provably unambiguous language. PEG are also provably unambiguous, but for a given input, the "correct parse" is not necessarily the "desired parse". Essentially, when you're using a PEG, the language is defined by its grammar. When you use an LL/LR parser-generator, you're attempting to use some constraints to formalize a grammar for your language, which you define yourself, and the tool will correct you if you've made a mistake and introduced some ambiguity by accident, whereas a PEG will silently mask that issue by just picking the first option. Rather than prompting you to fix the language to match the intuition you had about its syntax, the "accidental ambiguity" becomes a non-ambiguity and part of the language definition. Also, when extending an existing language with new syntax, PEGs can have unexpected results which may break existing code written in the language, or interpret it differently to what was intended by whoever wrote it. However, when you're parsing a language that somebody else has already defined, it doesn't really matter which method you use to write the parser, as an incorrect parse is a bug in your code, and not the language itself. For greenfield languages, I'm largely with the article's author that LL/LR are the correct constructions to use - they assist you in designing a language that is free of ambiguity from the start because incorrect assumptions about your syntax are flagged by the parser-generator. A greenfield language designed with a PEG becomes a language that is defined by the PEG, and any potential mistakes in your intuition become a set-in-stone part of the language. As for the choice between LL and LR, it's pretty much a non-brainer to use LR (or LALR) to give yourself greater flexibility. LL had their place on resource constrained systems of the past, but on today's systems, LR parsing uses a trivial amount of resources and is only going to be a fraction the compiler or interpreter's memory and CPU time. If you can fit your language into an LL grammar, you certainly should, as it will be blazingly fast to parse, but I don't think you should constrain yourself just because of this. Recommendation: Use Menhir. It supports writing production rules which are parametrized by other production rules. This can "feel" a bit like parser combinators to write, but it's all ultimately lowered to LR. The parsers it produces are fast, and you can use the tool for incremental parsing.
dathinab 2y ago
I both agree and disagree. I would avoid PEGs they are a huge food gun. But a lot of things you need to parse are file formats designed to be reasonable straight forward parseable and in many such situations using a parsing combinatorics is all of: the fastest write, the easiest to write, the easiest to debug, the easiest to maintain, the smallest code size (potentially by a lot), the fastest build times and often even the fastest to execute . So a very clear straightforward win for parsing combinatorics. Through the moment you parse (programming) languages and similar instead of data formats things often change leading a massive increase of complexity and ways you can subtle get it wrong (e.g. not explicitly handling operator precedence). And here proper grammar parsing frameworks can shine, sometimes. But even there they don't shine always as they are huge complicates pieces of code which often require running some complicated code gen to have any chance to get acceptable perf/code size which is often hardly debugable in case you might have run into a bug. Furthermore parsing arbitrary CFG is complicated and potentially slow so most frameworks prefer you to use a specific subset like LR(1) grammars. And understanding what exactly that means for your grammar and if that works for you use case is neither obvious nor intuitive and can make you wast a lot of time. Sure you probably should have learned all about it (if you have a CS Bachelor or similar degree) but I mean when was the last time you used that knowledge? So in the end even for such cases using a PEG or parser generator, while being _very_ _very_ careful about grammar design is sometimes still the better choice (even through it shouldn't, it's a better choice born due to limitations of existing tooling). As a side note a good hint to weather using a CFG or parser combinator is the better choice is often to ask yourself if a tokenization pass would make parsing much more simple. For thinks where using a CFG is a terrible idea (e.g. parsing msgpack) the answer is often that it doesn't make sense at all. For things where tokenization makes sense, but is literally most of the parsing (e.g. JSON) it's often just easier/better to not use a CFG. But the moment it seems to make a lot of sense (e.g. a programming language) it also tends to be the best choice to use a CFG (or similar) grammar parser.
thefaux 2y ago
IMO, people get way too caught up in the formal specification of grammars. Writing an unambiguous parser by hand is not that difficult. It can be done without a lexer using recursive descent and a switch statement at each byte in the input stream where a decision needs to be made.
deterministic 2y ago
To the author: How "you" think is not how "we" think. The tendency to assume that your preferences or tastes are globally shared is really puzzling to me. That has never been true and (most likely) never will be true.

100 points by mmastrac 2y ago

Parsing is an application domain where I'd expect more hard logic and less soft feelings than in this article. "I feel that CFGs more naturally represent how we think" but "All this doesn't apply to situations where you trying to parse some language, whose specification explicitly says that the language is based on PEG formalism" A terrible context free grammar (with left and right recursion, not a small feat) is presented. "I blindly converted grammar above to Haskell code" "I accidentally discovered my grammar was ambiguous!" "All this gave me psychological trauma (figuratively speaking). I will never use Parsec (and PEG parsers) anymore." Denial that an ambiguous grammar is a defect, denial that the ambiguity has to be resolved, refusal to use parser combinators to resolve the ambiguity in the correct way. It's also strange to see someone react to a modest, non-shameful failure (guess what, parsing is difficult is language design is even more difficult) that should be a nice learning opportunity (elegant context free grammars are usually insufficient in practical usage) with anger and radicalization far beyond an acceptable level of blaming the tools. The other post in the blog, however, follows a similar general pattern: never use a popular technique (de Bruijn indices rather than parser combinators), because they advocate another technique (expressing lambda calculus terms with randomly generated globally unique identifiers for all bound variables rather than pure context free grammars) because that's what they like.

just_mc 2y ago
Well said.
eslaught 2y ago
So, I agree with your take as a reaction to this article specifically. However, I also think that there is a legitimate point here. Which is that parser combinators, even in languages like Haskell, are shockingly tricky to use correctly. In particular, they violate the usual Haskell principle that "if it compiles, then it will probably run correctly". Having written multiple parsers in multiple languages with multiple parsing frameworks (including direct recursive descent), using Parsec in Haskell was the only time I had to write a test suite for the parser specifically. And that's because there were so many footguns that I was repeatedly making mistakes despite the fact that this was a port of a parser I'd already written (and therefore, ought to know backward and forward). (For the record, this was not my first Haskell project either, which is why I was so shocked it went so poorly.) I'm sure it's possible to make mistakes in CFGs too, but practically speaking I can't remember running into that situation myself. Whereas with Parsec I ran into it repeatedly.
- HelloNurse 2y ago
  PEG parsing is likely to squash some grammar ambiguities in unexpected ways, making a test suite a very good idea; but we shouldn't forget that this kind of failure can only happen starting from an ambiguous grammar specification, so the work of taming PEG precedence or combinator behaviour is not an additional burden of the technology but an additional tool to correct the grammar to become less ambiguous, an alternative to rewriting it in unnatural, verbose and complex ways.
  - yatac42 2y ago
    > but we shouldn't forget that this kind of failure can only happen starting from an ambiguous grammar specification I don't think that's true. The following CFG is unambiguous: S ::= A S | A A ::= 'a' | 'a' 'b' Yet if we translate this 1-to-1 to a PEG (without changing the order of the alternatives), it's not going to match any input with 'b's in it, so it doesn't match the same language.
    - HelloNurse 2y ago
      This grammar is difficult to adapt to ordered choice, having 4 possible variants that mostly define different languages from each other and from the "same" grammar with traditional parsing. It's a formally very different problem from spontaneously and arbitrarily disambiguating an ambiguous grammar, but in practice it causes the same kind of suffering and it's likely to be a more common issue.
- rowanG077 2y ago
  I have written a simple compiler in Haskell using parser combinators for parsing. And I couldn't disagree more with you. It was super straightforward writing the parser and it worked immediately. Why do say they are tricky?
  - HelloNurse 2y ago
    What language did you compile? Some languages can be much more manageable than others. Did you adapt an existing CFG, or another parser combinator implementation, or did you start from scratch? The first case is more treacherous.
paulddraper 2y ago
> Parsing is an application domain where I'd expect more hard logic and less soft feelings than in this article. Ah, an S-expr enjoyer I see
kragen 2y ago
it's important to read your comment in the context that we have established in https://news.ycombinator.com/item?id=40582885 https://news.ycombinator.com/item?id=40582885 that you wrote it before finding out what pegs were i'm curious if you change your mind once you understand peg's limited backtracking semantics
aranchelk 2y ago
> I feel that CFGs more naturally represent how we think Author could have replaced the “we” with “I” and made it into a mildly interesting diary entry.

behnamoh 2y ago

This also applies to LLM constrained generation. Instead of outputting something that promised to be a JSON (but maybe it's not, or maybe it's an incomplete JSON, or maybe it's a JSON but doesn't conform to your JSON schema), just use CFGs (e.g., GBNF) to guide the model to generate the exact JSON you want. It's guaranteed, and you don't have to send lengthy JSON schemas to the LLM.

hansvm 2y ago
With the caveat that you significantly change the distribution of the output. Picking on JSON with current-gen LLMs, consider (1) Retry till the output passes the grammar (2) Only generate tokens passing the grammar Assuming (2) actually runs (not guaranteed for all grammars and distributions theoretically, basically never a problem in practice), one of many common failure modes is forcing the generation of grammar-valid tokens after an error has been made. E.g., one sort of "truncation" error happens when the LLM is producing an object with metadata around a transcription (e.g., an author, timestamp, and blob of text). A common incorrect result looks like {"author": "John Doe", "timestamp": "20:23:58", "transcript": "My name is John Doe, and ... Those ellipses weren't just cutting off my description of the invalid data. The model will produce ellipses after the string carries on for too long. If you greedily produce tokens adhering to a grammar, your only options at that point are continuing the string and ending it, and both options are very wrong. Contrast that with option (1). Empirically, if the model is willing to actually produce those tokens rather than cut off its answer, it's much more likely to be correct (i.e., the presence of that ellipses bug will tend to cut off the entire response, not just truncating the string and still generating a valid object). If you just retry till the model succeeds then you have a substantially higher accuracy in that task. That particular example may or may not apply to your favorite problem and favorite model, but it highlights the problem that constraining to a grammar forces a large skew in your result distribution. A large part of the power of an LLM is its autoregressiveness, and other sampling algorithms only tend to perform well when there's some outside knowledge relevant to the real-world problem being solved (e.g., if the LLM has >50% accuracy on a task with a small, finite number of outputs, then you might want to drop the temperature to 0 and just sample repeatedly, selecting the most likely option), but messing with the result distribution without a rationale for why you're still likely to get good results is risky.

deleted 2y ago

[deleted]

hansvm 2y ago

> Parser and lexer for reversible parsing with guaranteed reversibility. Seems to be totally unique across all programming languages. Of course, CFG-based. There's also the parser combinator approach of parser-printers ;)

lifthrasiir 2y ago

The reality however is that many applications find a recursive descent parser easier to handle once the grammar has been fixed (and in spite of its many caveats!), so PEG is a natural formalism for them. For example I once tried to write a full parser for Lua in LALRPOP and gave up after a week because it was too slow to compile and too hard to avoid conflicts; I ended up writing a recursive descent parser in a single day. I already knew that LALRPOP doesn't resolve shift-reduce conflicts and also how to transform the grammar to avoid them, but that wasn't enough for me. I think there is a niche for CFG-like formalisms with bounded PEG-like constructs so that it can be quickly adjusted without giving up all the benefits of CFG. I have been already in situations where I really want to have such formalisms for multiple times, including the aforementioned one.

yawpitch 2y ago

> Python spec says Python is PEG, so you should use PEG parser for parsing Python. Python switched to PEG in IIRC 3.9, the language standard, parser and the grammer were previously CFG, specifically LL(1). That switch implies that maybe the author is only correct until your language is widely (if not wildly) successful? https://peps.python.org/pep-0617/ https://peps.python.org/pep-0617/

VagabundoP 2y ago
Core.py episode on the transition to the parser mentioned limitations of the LL(1) parser wrt to new syntax.[1][2] There were some positive side effects to the move and it enabled better exceptions, with more detailed information. [1] https://podcasts.apple.com/us/podcast/episode-8-the-new-parser/id1712665877?i=1000647675451 https://podcasts.apple.com/us/podcast/episode-8-the-new-pars... [2]https://podcasts.apple.com/us/podcast/episode-7-the-old-parser/id1712665877?i=1000643716095 https://podcasts.apple.com/us/podcast/episode-7-the-old-pars...
dathinab 2y ago
I think the main issue here is that you in general just don't "get a CFG" parser which magically works correct with nice ergonomics and grate performance. You get a LL(1), LR(1), LALR(1), etc. parser and the more of CFG they can parse the more drawbacks there often are. And making a programming language fit into more limited parsers like LL(1) is a total pain. So you need something which is more powerful, but still not to complicated to have a fast efficient implementation for python and python tooling. At which point it can be simpler to just go with PEG especially if you have the amount of people and brain power to make sure you don't slip up with resolving ambiguity in a arbitrary "accidental" way.

vidarh 2y ago

His problem isn't primarily the choice of formalism, but that his grammar is wildly overcomplicated and makes it really hard to see what language it specifies irrespective of formalism. This is a common problem. In this case the amount of recursion makes it hard to even guess at what it is trying to express. If my grammar looked like that, I'd throw it away and start over, because the problem to me appears to be not quite having a clear idea of what the grammar is expressing. EDIT: Trying to clean up his grammar into something readable t0 = t1 | a t1 = t3 ("==>" t1)? t3 = (id | d)+ c? | b a = "!!" id c "." t0 b = "%" id c "." t3 c = "::" t0 d = "(" t0 ")" t999 in the original was left-recursive, but in this case that's a matter that can be left to the parse tree construction if he insists on keeping it that way. For your own sanity don't mix left and right-recursion in a parser, and decide how you structure the parse-tree in terms of left/right binding separately, and only express that in the grammar if your tool doesn't let you express it when building the tree, or if it actually changes the language recognised. One thing to note, is that my first instinct when writing parsers is to look for opportunities to factor out rules that start with a terminal, because it's usually a good way of avoiding or reducing the need for lookahead. Hence the extra rules, that to me at least makes it a lot clearer. The part of the grammar to look for places where your formalism causes ambiguities is now much smaller. This grammar still gives me hives, but without knowing his constraints and intent, it's tricky to see if it can be cleaned up further.

chipdart 2y ago
> If my grammar looked like that, I'd throw it away and start over, because the problem to me appears to be not quite having a clear idea of what the grammar is expressing. That's fine if you are working in a purely academic domain, or you're just having fun writing something on your free time. In production settings, you need to keep extending whatever language you have. The alternative is having to start to maintain two separate parsers and a migration tool, and be stuck with that for years. The point is that being able to throw away code is a luxury that virtually no one is able to afford.
- bruce343434 2y ago
  What do you mean? Stuff gets refactored all the time.

aidenn0 2y ago

> And if you agree with me that grammar above in intuitive sense is ambiguous, i. e. if you agree that A :: B ==> C allows two parse trees, then your brain thinks in terms of CFG, too! CFGs are simply more natural. Count me as my brain being on team PEG then, so also a data point against CFGs being more natural. In fact, I think this example proves that author of TFA does not think in CFG, otherwise they wouldn't have accidentally written an ambiguous grammar! In my experience, it's an extraordinarily tiny fraction of people who actually want parse forests instead of parse trees in the languages they are constructing (TFA specifically excludes pre-existing languages). A PEG will be unambiguous. People want unambiguous. There's a chance it disambiguates against the intent of the author, but a CFG won't disambiguate at all, which will nearly always be against the intent of the author.

orlp 2y ago
Great! Someone who's brain is on team PEG. You are just the person I need. Can you explain in plain English what strings match the following PEG grammar? Str = "a" Str "a" / "a"
- HelloNurse 2y ago
  Any odd number 2n+1 of "a" repetitions, longest match. The inflating first rule is preferred about 2n times until it fails at input end, then the parser backtracks until the middle "a" is matched by the second rule and the others by n expansions of the first rule.
  - orlp 2y ago
    I'm sorry that is not correct at all. It does not match the string "aaaaa" for example.
    - HelloNurse 2y ago
      Why not? Preferring the first rule, after seeing a you expect Str a; after seeing another a you expect Str a a; after seeing the third a you expect Str a a a (and you can already realize it cannot match) so after some backtracking you match the third a with the second rule instead, expecting a a, which are the fourth and fifth a in the input. Do you have a different parsing algorithm in mind?

Eliah_Lakhin 2y ago

I think it all depends on the language, but I found it (usually) easier to implement the recursive-descending parsers just manually. This may include combination approach too, but using my own combinatorial and domain-specific functions. In a nutshell such a parser is PEG in a sense that the choice is ordered, but with little to no test expressions. In other words, I try to stick to lookahead-1 most of the time. Left recursion quite often could be resolved by lifting the branches to their siblings rather than re-parsing the same things many times using the cache (packrat). In fact both approaches, the packrat and the nodes lifting, are the same in a nutshell, but nodes lifting is usually easier to maintain (again, it all depends). Writing the parser manually, or in other words a set of relatively simple mutually recursive functions, in my opinion, is not the hardest problem in practical engineering. At least it's not so hard when you have a mental model of the language's syntax upfront. If the language fits specific class of formal grammars very well, perhaps it would be not so hard to implement it using the parsers generator tool. But it is likely there will be edge cases that are hard to express properly using the formal grammar, and fighting with the tool specifics will waste a lot of your time rather than benefit you.

eru 2y ago
> I think it all depends on the language, but I found it (usually) easier to implement the recursive-descending parsers just manually. This may include combination approach too, but using my own combinatorial and domain-specific functions. Working in what languages did you make this observation? In something like C I would probably agree with you. But in eg Haskell or OCaml, I would probably prefer parser combinators.
- Eliah_Lakhin 2y ago
  I work with Rust most of the time. As of the pure functional languages, yes, perhaps using parser combinators is better.
- deredede 2y ago
  In other functional languages I tend to reach for combinators, but in OCaml I either use Menhir or regret not using it.

zelphirkalt 2y ago

PEGs are more expressive than CFGs, iirc. So use the right tool for the job. I have come to quite like PEGs and they become quite natural, once one understands things like no left recursion. I also often prefer them over complex regexes.

sparkie 2y ago
It's difficult to conclude meaningfully that any one is more expressive than the other. They parse different languages, though there is a large subset of PEGs which are also CFGs, they're not a proper superset - there are things you can parse with a CFG which cannot be parsed with PEG, and vice-versa. OTOH, when comparing LL and LR, we can conclusively say that LR are more expressive than LL because they're a proper superset - any language that can be parsed by an LL(k) grammar can be parsed by an LR(k) grammar (for same k).
- orlp 2y ago
  > there are things you can parse with a CFG which cannot be parsed with PEG This is not known. It is conjectured to be true because if all context-free languages could be parsed with a PEG grammar it would imply you'd have a linear-time boolean matrix multiplication algorithm, but no one has ever constructed a concrete example of a language which is context-free but not parsable with a PEG.
  - kragen 2y ago
    the other one is known, though, isn't it? there's an example of a peg parsing a non-context-free language aⁿbⁿcⁿ in ford's dissertation?
    - orlp 2y ago
      Yes.

mrkeen 2y ago

> when I wrote that grammar, I meant it is CFG. Simply because my brain thinks in terms of CFG. > I blindly converted grammar above to Haskell code. > But then I accidentally discovered my grammar was ambiguous! You wrote an ambiguous CFG, implemented its parser, and then discovered that it was ambiguous. Would the CFG have become non-ambiguous if you took your advice and avoided parser combinators? This makes me really want to avoid the CFG step altogether.

sparkie 2y ago
The advice to "use CFGs" is incomplete. What you really want is to use one of the deterministic subsets of CFGs, like LR(k), and importantly, with a parser-generator which will reject any non-LR productions in the grammar before even generating the parser. This way, you can get a guarantee that there are no ambiguities in the language you've defined ahead-of-time. You might consider this to be analogous to the difference between static and dynamic typing. A statically typed language will reject an erroneously typed program before attempting to run it, but the dynamically typed language may accept it and attempt to run it, only to fail at runtime if there's a type mismatch. Parser combinators are more like the dynamic language. You find out at runtime (when parsing), whether the text you have parsed has ambiguities because more than one parse result is returned if that is the case. Normal operation is that the combinator returns a single result, in which case there are no ambiguities in the input, but the parser combinator doesn't provide any guarantees about absence of ambiguity in the language itself - it only proves that there's no ambiguity for the given input. And there's no practical way of testing for all inputs that the defined language is unambiguous, because there are infinite possible inputs. LL/LR parser generators are like a type system for grammar. They'll take your input grammar, and check that all rules adhere to the constraints of LL/LR, and iff that's the case, then they'll produce a valid parser for a provably unambiguous language. PEG are also provably unambiguous, but for a given input, the "correct parse" is not necessarily the "desired parse". Essentially, when you're using a PEG, the language is defined by its grammar. When you use an LL/LR parser-generator, you're attempting to use some constraints to formalize a grammar for your language, which you define yourself, and the tool will correct you if you've made a mistake and introduced some ambiguity by accident, whereas a PEG will silently mask that issue by just picking the first option. Rather than prompting you to fix the language to match the intuition you had about its syntax, the "accidental ambiguity" becomes a non-ambiguity and part of the language definition. Also, when extending an existing language with new syntax, PEGs can have unexpected results which may break existing code written in the language, or interpret it differently to what was intended by whoever wrote it. However, when you're parsing a language that somebody else has already defined, it doesn't really matter which method you use to write the parser, as an incorrect parse is a bug in your code, and not the language itself. For greenfield languages, I'm largely with the article's author that LL/LR are the correct constructions to use - they assist you in designing a language that is free of ambiguity from the start because incorrect assumptions about your syntax are flagged by the parser-generator. A greenfield language designed with a PEG becomes a language that is defined by the PEG, and any potential mistakes in your intuition become a set-in-stone part of the language. As for the choice between LL and LR, it's pretty much a non-brainer to use LR (or LALR) to give yourself greater flexibility. LL had their place on resource constrained systems of the past, but on today's systems, LR parsing uses a trivial amount of resources and is only going to be a fraction the compiler or interpreter's memory and CPU time. If you can fit your language into an LL grammar, you certainly should, as it will be blazingly fast to parse, but I don't think you should constrain yourself just because of this. Recommendation: Use Menhir. It supports writing production rules which are parametrized by other production rules. This can "feel" a bit like parser combinators to write, but it's all ultimately lowered to LR. The parsers it produces are fast, and you can use the tool for incremental parsing.

dathinab 2y ago

I both agree and disagree. I would avoid PEGs they are a huge food gun. But a lot of things you need to parse are file formats designed to be reasonable straight forward parseable and in many such situations using a parsing combinatorics is all of: the fastest write, the easiest to write, the easiest to debug, the easiest to maintain, the smallest code size (potentially by a lot), the fastest build times and often even the fastest to execute . So a very clear straightforward win for parsing combinatorics. Through the moment you parse (programming) languages and similar instead of data formats things often change leading a massive increase of complexity and ways you can subtle get it wrong (e.g. not explicitly handling operator precedence). And here proper grammar parsing frameworks can shine, sometimes. But even there they don't shine always as they are huge complicates pieces of code which often require running some complicated code gen to have any chance to get acceptable perf/code size which is often hardly debugable in case you might have run into a bug. Furthermore parsing arbitrary CFG is complicated and potentially slow so most frameworks prefer you to use a specific subset like LR(1) grammars. And understanding what exactly that means for your grammar and if that works for you use case is neither obvious nor intuitive and can make you wast a lot of time. Sure you probably should have learned all about it (if you have a CS Bachelor or similar degree) but I mean when was the last time you used that knowledge? So in the end even for such cases using a PEG or parser generator, while being _very_ _very_ careful about grammar design is sometimes still the better choice (even through it shouldn't, it's a better choice born due to limitations of existing tooling). As a side note a good hint to weather using a CFG or parser combinator is the better choice is often to ask yourself if a tokenization pass would make parsing much more simple. For thinks where using a CFG is a terrible idea (e.g. parsing msgpack) the answer is often that it doesn't make sense at all. For things where tokenization makes sense, but is literally most of the parsing (e.g. JSON) it's often just easier/better to not use a CFG. But the moment it seems to make a lot of sense (e.g. a programming language) it also tends to be the best choice to use a CFG (or similar) grammar parser.

thefaux 2y ago

IMO, people get way too caught up in the formal specification of grammars. Writing an unambiguous parser by hand is not that difficult. It can be done without a lexer using recursive descent and a switch statement at each byte in the input stream where a decision needs to be made.

deterministic 2y ago

To the author: How "you" think is not how "we" think. The tendency to assume that your preferences or tastes are globally shared is really puzzling to me. That has never been true and (most likely) never will be true.