Re:Incremental Regular Expressions (2012)
by chubot on Wednesday April 22, 2020 @10:23PM
(#22952272)
Eggex gives you a more EBNF-like syntax for regexes. CFGs are basically regular languages with recursion, so there's no reason for them to have a wildly different Perl-like syntax. That's basically a historical accident.
Also, regular languages are straightforward and tractable, and you should use them where possible (aside from bad syntax, which Eggex is fixing).
In contrast, CFGs are useful, but if you start using them a lot, you will see they're not really "one thing" as far as programming/engineering is concerned. They sort of explode into a fractal of complexity -- there are many different subsets of CFGs, some of which can be parsed efficiently with particular algorithms.
So basically regexes have bad syntax but relatively good semantics (libc BRE/ERE doesn't have the Perl backtracking issue). CFGs don't have a consistently bad syntax, but the semantics are much more complex when you're talking recognizing vs. generating. And of course in programming (rather than math), we want to recognize, not generate.
If you've written CFGs, then eggex will be very familiar. See the example: http://www.oilshell.org/blog/2019/12/22.html
-----
Also, regular languages are straightforward and tractable, and you should use them where possible (aside from bad syntax, which Eggex is fixing).
In contrast, CFGs are useful, but if you start using them a lot, you will see they're not really "one thing" as far as programming/engineering is concerned. They sort of explode into a fractal of complexity -- there are many different subsets of CFGs, some of which can be parsed efficiently with particular algorithms.
And some people reject CFG in favor of PEG, etc.
https://github.com/oilshell/oil/wiki/Parsing-Models-Cheatshe...
----
That is, the recursive grammar issue is not "settled". Whereas regular expressions have well known algorithms and are "settled" (except for syntax).
https://swtch.com/~rsc/regexp/
So basically regexes have bad syntax but relatively good semantics (libc BRE/ERE doesn't have the Perl backtracking issue). CFGs don't have a consistently bad syntax, but the semantics are much more complex when you're talking recognizing vs. generating. And of course in programming (rather than math), we want to recognize, not generate.
Related:
https://github.com/oilshell/oil/wiki/Why-Lexing-and-Parsing-... (Do the easy thing with the fast algorithm, and the hard thing with the slow algorithm. Don't do the easy thing with the slow algorithm.)