Hacker News Reader

Comment by orlp | Hacker News Reader

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.

View on HN

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.

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.

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.

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.

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

Reply on news.ycombinator.com