News for hackers. Stuff that matters.

A comment on PEG Parsers.

Re:PEG Parsers by jchook on Monday July 22, 2019 @10:18PM (#20503933)
From Wikipedia...

> Unlike CFGs, PEGs cannot be ambiguous; if a string parses, it has exactly one valid parse tree. It is conjectured that there exist context-free languages that cannot be recognized by a PEG, but this is not yet proven.

Does this mean that PEG grammars are a form of regular grammar?

[ Parent | on HN ]
Re:PEG Parsers by curryhoward on Monday July 22, 2019 @10:34PM (#20503994)
No. One can come up with a PEG for a language consisting only of strings with balanced parentheses. That language cannot be described by a regular grammar.
[ Parent | on HN ]