Use context-free grammars instead of parser combinators and PEG

https://safinaskar.writeas.com/

by mmastrac • 2 years ago

100 82 2 years ago

safinaskar.writeas.com

HelloNurse10• 2 years 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• 2 years ago

Well said.

eslaught2• 2 years 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.

HelloNurse10• 2 years 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.

rowanG0772• 2 years 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?

paulddraper• 2 years 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

kragen8• 2 years ago

it's important to read your comment in the context that we have established in 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• 2 years 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.

behnamoh2• 2 years 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.

hansvm3• 2 years 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.

behnamoh2• 2 years ago

Let's say the grammar forces a JSON like this:

    {"transaction_number": <number>}

Is this also problematic? My understanding is that the model is first forced to generate "transaction_number", which then hints to the model that it must generate the number of the transaction, not something else. I understand that maybe the model didn't want to start writing "transaction_number" without enforcing the grammar, but after being forced to, it has to only continue the generation.

hansvm3• 2 years 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• 2 years 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• 2 years 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/

VagabundoP• 2 years 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-pars...

[2]https://podcasts.apple.com/us/podcast/episode-7-the-old-pars...

dathinab2• 2 years 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.

vidarh6• 2 years 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.

chipdart2• 2 years 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• 2 years ago

What do you mean? Stuff gets refactored all the time.

vidarh6• 2 years ago

No, I'm not talking about an academic setting.

This is not about the language but about his expression of it in this specific instance of the grammar.

As the article makes clear, he didn't understand the language, and my claim is that is to a large extent down to how it is expressed.

Not throwing away this specific grammar instance is something you can't afford.

HelloNurse10• 2 years ago

In production settings, you need to keep extending whatever language you have.

Then the hard work of leaving behind simplistic, ambiguous, imprecise, inefficient grammar specifications has already been done (mostly) and you are ready to add small new features without serious rewrites.

pxc• 2 years ago

Can't you prove that your new grammar describes the same language as your old one, or mechanically concert both to some normal form and check that they're identical or something like that?

aidenn03• 2 years 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.

orlp10• 2 years 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"

HelloNurse10• 2 years 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.

dxdm• 2 years ago

Interesting. I've last had to deal with formal grammars in the previous century, and your post had me go scratch the surface of what PEGs are.

If I understand correctly, your example is not a well-formed grammar, because of the left recursion.

So what you're saying is that PEGs align badly with our expectations, tempting us to create non-well-formed grammars, and making it hard to recognize them as such, because our brains want to parse them differently. Right?

nhatcher• 2 years ago

Beautiful example! `2^n -1` times a?

I love PEG parsers though

thequux• 2 years ago

The question here is whether it is better to silently guess at the author's intent or to loudly say "your intent isn't clear; try again".

I strongly believe that the second is the better approach for nearly all use cases. When I'm writing a grammar, I'm focused on the happy case and not on how the rules interact with each other. My intent was to write a grammar with only a single result, indeed, but if that's not what I've done, I'd want to know!

nbadg• 2 years ago

I disagree on both counts.

I think the fundamental question here is "how easily can you construct (write or generate) a parser that matches your intent?". And to answer that question, I think you have to look at the entire process.

What good does it do you to hear "your intent isn't clear; try again" if you don't understand where the ambiguity is? Presumably, if you knew where the ambiguity was, you wouldn't have written it -- since you know it can't create a grammar. So really what that message is telling you is, "you don't understand your own grammar" or "you don't understand how to write rules for your PG". And in my experience with several different PGs, the failure messages returned in those cases are... less than helpful. So you end up spending hours banging your head against your desk trying to figure out where the ambiguity is, even with a grammar you know back-to-front.

Furthermore, even if you use a CFG, you still haven't gathered evidence that the resulting parse matches your intent. For that you need test cases. And as soon as you write a test case, you get immediate feedback that your intent isn't clear, regardless of PEG, CFG, or anything else: you see that your resulting parse doesn't match with the expected one.

Given both of those things, it seems to me that issue at hand really does boil down to "which feels more natural, PEG, CFG, etc", which is always going to be a personal preference.

Eliah_Lakhin2• 2 years 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• 2 years 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_Lakhin2• 2 years ago

I work with Rust most of the time. As of the pure functional languages, yes, perhaps using parser combinators is better.

deredede• 2 years ago

In other functional languages I tend to reach for combinators, but in OCaml I either use Menhir or regret not using it.

chipdart2• 2 years ago

I think it all depends on the language, but I found it (usually) easier to implement the recursive-descending parsers just manually.

I think that packrat parsers are even easier to implement by hand, and even troubleshoot.

It's all procedural code, and you just call the next routine to figure out if you have a token match or not.

More importantly, PEGs promise to be easier to maintain in smaller custom parsers. To support an enum, all you need to do is add a function call, and that's it. One line of code. Can't beat that.

zelphirkalt• 2 years 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.

sparkie4• 2 years 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).

orlp10• 2 years 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.

mrkeen• 2 years 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.

sparkie4• 2 years 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.

vidarh6• 2 years ago

There's no requirement for parser combinators to allow ambiguity. It's perfectly fine, and possible to write parser combinators that will only parse an unambiguous language, and only ever return a single unambiguous parse or throw an error.

You're right it's often easy to use them in ways that introduce ambiguity, and some explicitly support ambiguity, though.

WorldMaker• 2 years 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.

Which is also why there is no "just use CFG". CFG is an abstraction from language generation. BNF as a "language" was invented for language generation. It's suitability to parsing was mostly an accident, and we've been dealing with the pragmatic repercussions in the field of parsing ever sense. To make parsing work we have bounded subsets of the abstraction. To make the illusion of the abstraction work we've bent BNF to nearly its breaking point, but the illusion fails as soon as you realize the BNF for LL and LR (and LALR and so on and so forth) is subtly incompatible. There's no universal BNF, there never was, it's a broken illusion.

PEG is just as useful as a bounded subset of the abstraction as LL/LR. The break was PEG decided to stop pretending BNF was a useful lingua franca between these subsets and then parser combinators contributed further to the demise of "universal BNF", which was never universal.

dathinab2• 2 years 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• 2 years 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• 2 years 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.

Use context-free grammars instead of parser combinators and PEG

Related Stories