The Packrat Parsing and Parsing Expression Grammars Page | Hacker News Reader

The Packrat Parsing and Parsing Expression Grammars Page

bford.info

47 pointsgjvc41 comments

If you think PEG parsers are a good idea and we should use them, comment below which strings this PEG grammar matches:

    Str = "a" Str "a" / "a"

If you get it right and you understand the logic, by all means use them. If you get it wrong or can't wrap your head around how it works despite knowing the answer, maybe reconsider.

EDIT: since my point was too subtle and I have been misunderstood and downvoted as a result of it, allow me to give a hint. If you believe the above grammar matches aaaaa you fall in the latter category. It does not. Yes, aaa matches, aaaaaaa matches, but aaaaa does not. Yes, this is mind-boggling.

Well, it seems simple. But from your tone I'm guessing it's not?

    a: (a)
    aaa: (a(a)a)
    aaaaa: (a(a(a)a)a)
    etc

That is incorrect. Feel free to try it here: https://pegjs.org/online, you will see that aaaaa is not a match. And no, that is not a bug in pegjs.

I can't wrap my head around it. Why doesn't it work?

It parses this: a a aaa a a But not this: a aaa a

I think it will parse "a", it will parse "a a a", and "aaa a aaa", and "aaaaaaa a aaaaaaa" and so on, but nothing else.

The problem for aaaaa is it gets to this parse

  (a(a(a(a)a)

and can't complete the (aXa) parse for the second a, so it backtracks to try the (a) parse

  (a(a)

The issue is since the parse of the third a as (a(a)a) succeeded, it will never try the (a) parse for the third a.

Why not just write it more simply as

    Str = "a" "aa"*

Most languages allow writing tortured and hard to understand logic where simpler alternatives can also be written. I'm not sure why that should make people consider not using them.

The parse tree from that would be different, though it would match the same strings.

Incorrect, it does not match the same strings.

Because that does not recognize the same set of strings. That matches aaaaa, but my example above does not. That is exactly the point I'm trying to make.

Well, if you wanted all odd-length strings, you'd write what GP wrote. If you wanted whatever it was your grammar accepted, you'd write what you wrote :)

> If you wanted whatever it was your grammar accepted

It is one-line, two-rule PEG grammar. What does it accept, and why? If we can't state this with confidence in such a tiny example, what makes us have any confidence in larger, more complex grammars? We should understand our tools. PEG pretends to be simple and understandable, but it's much less so than it might seem on the surface.

Simple rules can give surprising, complex behaviour.

That's a good point. Unfortunately, it's also true not only of PEGs and recursive-descent parsing, but also of essentially every parsing formalism out there. So it doesn't seem to disqualify PEGs in particular.

(It's also true of programming languages generally: For which inputs does Collatz halt, and why?)

I contest that. The parsers based on the formalism of CFG do not have that problem. The straightforward mental model of the user always matches their behaviour, no complexity, no surprises.

This is a good point in favour of context free grammar based parser generators. I think the trade-off is a bit more subtle though.

CFG semantics is nice and declarative when we specify which strings belong to the language, but a parser is a function from strings to parse results, and then the nice semantics stops working due to ambiguities. The PEG semantics on the other hand naturally expresses such a function, and the function you get with PEG semantics is almost always the function you want.

When we look at character level grammars, the CFG formalism doesn't work well either. They fundamentally rely on greedy lexical token matching.

Extensions such as indentation sensitive parsing and user defined operators quite naturally fit into PEG style semantics, and are more difficult to integrate into CFGs.

CFG based parser generators are way more complicated internally than PEG based parser generators, which are extremely simple.

> The grammar may not be exactly what you want to illustrate your point (I think you want to swap the two sides of the /)

No, I think you might be misunderstanding my point. For example, if you think the grammar I posted matches aaaaa, you'd be wrong.

Yes you're right, I had already edited that while you were posting your reply. I thought you wanted to point out the usual simple "a" / "aa" problem.

This is a good example of a theoretical problem with PEGs. It also applies (of course) to recursive descent parsers. I don't think this problem is a practical issue, though; I can't speak for others, but this kind of problem hasn't come up in practice for me. PEGs do cause other headaches from time to time, but are still head-and-shoulders easier to get right than other styles of working with grammars.

I work with PEGs every working day of my life. When I saw your example, it immediately gave me a chuckle, so thank you for that.

Does that mean I'd spot the same gotcha deep in some grammar I was working on? No of course not, that would never happen. It's going to be some other mistake that makes me feel like an idiot after staring at the screen for several hours.

Parsers are designed around data, not conundrums. For structured languages, PEGs are a sharp and simple tool for slicing them up. But they're not great at solving the Liar's Paradox.

This is a really nice example, but I feel that it comes to an unfair conclusion.

I'll concede that this appears counterintuitive, but I feel that cases like this most often just pop up because people have been "overexposed" to EBNF/CFGs before and write PEG grammars with wrong preconceptions (also often ending in "left recursion" confusion, but that at least gives early errors).

But I still think that it is much preferable to debug/rewrite a questionable PEG grammar than e.g. a cobbled-together mess of conditionals and regular expressions...

But now I'm really interested in what you're advocating for instead? CFG parser frameworks? Or learning how to write the parser by hand? Or learning about PEGs until your example is understood?

For general parsing of data I am currently advocating LR(1), and GLR or Earley for those that need ambiguity. The exception to this is programming languages, for which I think the #1 priority is error messages, thus recursive descent is quite logical. If whatever you are parsing is unambiguous isn't strictly LR(1) a small lexer can almost always fix that, but often scannerless works fine.

LR(1) gets a bad rap for impossible to understand conflicts while writing a grammar. I strongly believe this is due to most tools advertising LR(1) actually using LALR(1). LALR(1) is deservedly awful, and introduces mysterious conflicts. But modern parser generators can support minimal LR(1), which generates parse tables almost as small (or often exactly ad small) as LALR(1) without the mysterious conflicts.

Finally LR(1) gets a bad rap for screaming at you at all during parser writing, but I see this as a feature, like the type checker in a programming language, preventing you from writing ambiguous or expensive to parse constructs.

That grammar simply matches 2^(n-1) a's. Not mind-boggling from that point of view

I love PEGs, but their error messages are usually vague, because it will backtrack out of a deep tree (where it should have discovered the actual error), and then presents an error much higher up ("computer says no").

Is there a mechanism that works well for improving errors in PEGs (i.e. something like a non-returnable node), and how does one practically implement that?

> Is there a mechanism that works well for improving errors in PEGs (i.e. something like a non-returnable node)

Yes, it's called the "cut operator".

> how does one practically implement that?

Pick a parser generator that supports it natively. ;-) If you're talking about implementing the parser generator yourself then you probably already know more about it than I do.

Thanks! I see the <cut> operator is actually explained in an older HN post: https://news.ycombinator.com/item?id=20502032

It's fascinating how many times the Prolog cut operator has been borrowed into parsing. It shouldn't be surprising, probably, given how easily lookahead leads people down the path of some backtracking mechanism or other for ease of implementation, and how ingrained the idea of a cut to stop backtracking is if you've ever been exposed to Prolog...

In an implementation I made ages ago, I created a different operator, the “naughty or”, which defines “invalid” syntax paths (for example, if the entire parse fails, allow going into the branch that does match identifiers that start with a number). This adds a language-level facility for a strategy I see most hand-rolled parsers end up in, which is to start parsing common mistakes to be able to provide better errors. It’s basically “free” because those paths are only explored if the parse is known to fail, so performance of successful parses isn’t affected, and allows the same level of “craft” in error messages as a hand-rolled one. It also allows people to easily submit patches to improve confusing errors they’ve gotten.

https://github.com/tolmasky/language

I think PEG let people think they can get away from the complexities of grammars because there are no ambiguities when you express them using PEGs. This is not true: the ambiguities are still there, and you still have to think about them, otherwise PEGs will generate "garden path" parses that make no sense. I think the sweet spot for parsing medium and high complexity languages is autogenerated lexer + handwritten recursive descent.

PEGs are a compact notation for recursive descent and they compile to recursive descent parsers. What would be the advantage of writing the compiled code by hand?

Few parser generators do well on things like error reporting in a human friendly manner. In effect production parsers tends to end up being hand written or extensively hand-modified for that reason. I wish more work on parser generators would involve focusing on better diagnostics (for end users, not the parser developer) and reporting rather than making them easier to use for the parser writers, as "just" writing the parser is rarely the hard part.

EDIT: Even making it easier to annotate the parser specifications to improve error reporting would be an improvement for many parser generators. In the past I've experimented with parser generators that included a prolog-inspired "cut" like operator that stops further backtracking, and that'd take an error message to output if nothing further can be matched without backtracking. It'd prevent the parser from "escaping" out of a likely human error and end up reporting a failure to match productions much higher up. It worked fairly well, and mimics what human parser writers tends to do in recursive descent parsers - we'll often guess at the likely error based on context deep down and bail out.

> people think they can get away from the complexities of grammars because there are no ambiguities when you express them using PEGs. This is not true: the ambiguities are still there

It's literally impossible to write a PEG with an ambiguity. So I don't know what you mean?

Ambiguities in the intended language aren't literally "still there" in the PEG, but realistically they are "still there" as a source of problems: naive PEGs can remove ambiguities incorrectly in less than obvious ways, and figuring out what's wrong can be more difficult than hitting a brick wall with other parsing approaches.

Just because the PEG doesn't have ambiguities doesn't mean the grammar you meant to recognize doesn't have one. What I mean is: PEGs give you a false sense of confidence by making you feel like you solved all your grammar's issues. In reality, you need to think really carefully about what your PEG is doing, because it's not going to warn you. As you said, PEGs are never ambiguous.

Well yeah if the grammar you wrote doesn't match what you intended to write then it's not going to work.

Not sure how that's saying anything useful though? If you write the wrong grammar with any parsing system it's also not going to work.

Most other parser generator systems give you indication that what you're writing is probably wrong, by stating e.g. that a grammar is ambiguous.

S := A '+' A | A '*' A

A := ...

If you do that in most PEG systems I've tried, you're just going to get the wrong result with no indication of what might have gone wrong, unless you know where to look.

But that's the point - other parsing systems let you design an ambiguous language and then tell you about it. PEGs don't let you design an ambiguous language in the first place. Unambiguous by construction.

why would you recommend using a generated lexer? the machinery is so simple thats its generally not worth trying to deal with the plumbing, esp around types.

I think CPython (as of 3.10?) uses a PEG parser now. That is not mentioned on the page.

Reply on news.ycombinator.com