Hacker News Reader

Comment by Drup | Hacker News Reader

Well, except Perl doesn't parse regular grammars (it parses much more) and is far from being "one pass" (since the complexity guarantees are not valid anymore) ....

View on HN

Regular grammars a strict subset of what Perl 6 will parse, no? If you stick to that subset it will parse in a single pass.

Except Perl 6 doesn't enforce it, so you have to guess yourself if you are really in the regular case. Additionally, PCRE used to be exponential for certain "bad cases", some of which were (truly) regular expressions.

My point is simply that Perl doesn't give you any guarantee except "we will try to parse it". Maybe you will hit the right case for the right version of Perl, who knows ? The Web is full of DDOS attack based on exponential PCREs.

With actual regular expression, the complexity is guaranteed.

The way regular expressions work in Perl doesn't randomly degrade across Perl versions. For a given regex you can determine what it's complexity would be across versions just like you would for an arbitrary chunk of Perl code. It's true you don't always get a complexity guarantee for free like in a DFA implementation of formal regular expressions.

PCRE isn't Perl.

> My point is simply that Perl doesn't give you any guarantee except "we will try to parse it".

Perl 6 gives you pretty good control over where to use backtracking and where not. It parses regular languages with a NFA or DFA, and can switch to a backtracking engine.

More details in https://www.apress.com/us/book/9781484232279 (sorry for the plug, wrote it myself).

Actually Perl6 does enforce it if you tell it to. The following fails to match.

    'abc' ~~ m:ratchet/ .* c /

The `.*` gobbles everything up, which means there is nothing left for `c`

When writing grammars, use `token` which turns on `:ratchet` for you.

Reply on news.ycombinator.com