logoalt Hacker News

bmn__ • last Tuesday at 11:23 PM • 1 reply • view on HN

Many. I don't have enough room on HN to show a representative sample of the shortcomings. Read the relevant literature or converse with an LLM to learn more.

Typical example, ported from <https://news.ycombinator.com/item?id=16600224>:

    (pp
      (peg/match
        '(capture
          '{
            :main (* :B)
            :B (+
              (* :A "x" "y")
              :C)
            :A (+
              true
              (* "x" "z"))
            :C (+
              (* :C "w")
              "v")})
        "xzxy"))
This almost trivial grammar works without any problem in known good parsers. If you want to try out grammars in the wild in Janet, it is nearly guaranteed that they are complex enough for peg to shit itself.

Replies

xigoi • yesterday at 5:51 AM

Of course this grammar does not work; you violated the two rules of writing PEGs:

• do not use left-recursive rules;

• put alternatives in such an order that none can be a prefix of a subsequent one.

These may seem limiting, but can always be fixed by a simple local change. In contrast, transforming a PEG into a conventional grammar often requires complex, wide-scoped changes. I’ve had the Tree-sitter compiler “shit itself” many times at grammars that PEG accepted with no problem, and had to introduce several ugly hacks to work around the problem of Tree-sitter not allowing ambiguous grammars.

➕ show 1 reply