Hacker News Reader

To be fair, you are not including more advanced operators, like positive/negative lookahead/behind (which is the specific example the article uses), capturing and non-capturing groups, greedy vs non-greedy kleene stars, etc.

As you say, they are implementation specific, but that's part of the problem: the basic regular expression syntax is insufficient for many tasks, so people take to extending it in complicated and syntactically opaque ways. That's the sign of a bad DSL, not a good one.

Maybe I'm arguing semantics here. To be clear, my point is that I do not agree it is reasonable to declare that regular expressions are a bad DSL simply because it is possible (however common) for people to write difficult to read, or difficult to understand regular expressions. It is the responsibility of the author of the expression to ensure that it is readable and understandable - to the extent that they should exercise restraint when possible use of an available feature would hinder readability and understandability.

There is absolutely no need for the example regex of http-like strings to be written the way that it is - there is only the want of the author, because they have a hammer and they are looking for a nail. If anything, using a regex for such a thing sets a bad precedent because anybody who wishes to come along and add user@password support to it is going to extend it and make it worse.

A more understandable way to process such a string would be to split it into constituent parts and use regex only for validation. Split at the :// for schema, split at the next / for path, etc. Turn these into functions, and keep the regexes simple.

Regular expressions are notorious because they are abused, not because they are evil.

> A more understandable way to process such a string would be to split it into constituent parts and use regex only for validation

Split the regex, or split the URL itself? I kinda think the split regex is pretty reasonable:

    protocol = "[a-z]{3,10}://"
    domain = "([^/?#]*)"
    path = "([^?#]*)"
    query = "(?:\?([^#]*))?"
    fragment = "(?:#(.*))?"
    url = protocol + domain + path + query + fragment

Not so terse now though, probably has to be wrapped in a function now (or stored as a constant somewhere else.)

That will certainly work, however for large regular expressions it will become just as unmanageable over time, especially since the concatenation of each part depends on all the previous ones being error free. I was referring to the idea of breaking apart the work done by the regex, into more manageable parts.

One of the complaints is that a regex is too terse. This is because a regex provides you with no internal context of what you're trying to do. You can add context by leveraging additional regex features, but that may potentially make the expression even more difficult for a human to parse. The alternative is to use the regexes more sparingly, and allow whatever the host language is to provide the context. Just because you are able to parse a whole string and capture each part that matches some particular pattern all in one go doesn't mean that it's a good idea. Consider the following quick piece of pseudocode where the URL is split into smaller pieces first, which does a similar job to the regex above:

    protocol, domain, path, query, fragment = explode("<protocol>://<domain>/<path>[?<query>][#<fragment>]")

    if (protocol !~ "[a-z]{3,10}")
        error("invalid protocol")

    if (domain !~ "[a-z]+(\.[a-z]+)*")
        error("invalid domain")

    if (path !~ "[a-z]+(\/[a-z]+)*")
        error("invalid path")

    if (query not nil and query !~ "[a-z]+")
        error("invalid path")

    if (fragment not nil and fragment !~ "[a-z]+")
        error("invalid path")

    success("valid URL!")

Granted, this is much longer relative to the regex-only solution - and it will probably take a bit more effort to implement the magical 'explode' function I've imagined here - however the regexes themselves are now simpler, easier to evaluate, and we have context on what they're there for. Ultimately, we've just stopped using 500 lines worth of features in the regex library in favour of 500 lines of code that does the same thing elsewhere, but arguably have made it all much more understandable.

You'll notice that I've changed the regular expressions for each of the components of the URL. This is because the original regex is essentially only providing the same functionality as the explode() function above, and there is no validation of the contents of each part. Consider this another argument against using regular expressions for this kind of work. Note however, that the language provided to the explode() function itself appears to be regular. This is not unexpected - since URIs are defined using BNF and therefore are either regular or context-free - however it is an example of a scenario where a regular-expression-like language does not have to be cryptic.

Your example is only an example, so this is a minor niggle, but remember you can specify usernames, passwords, and ports in a standard URL too :)

The way Perl 6 makes this more manageable is with grammars. (See previous post for an example)

Since a grammar is just a special type of class you can put regexes into roles and compose them together. You can even inherit from another grammar if you only need to change parts of it.

Also if there is something that is difficult to do regularly in the regex sub-language, it allows you to use regular Perl 6 code inline. (A regex is just a special type of method with a domain specific sub-language.)

Also if there is a bug you can use Grammar::Debugger or Grammar::Tracer to help find it. (I had a bug in the earlier post and used Grammar::Tracer to find and fix it within seconds.)

A Perl 6 grammar can look remarkably similar in structure to BNF. https://github.com/moritz/json/blob/master/lib/JSON/Tiny/Gra... https://trac.ietf.org/trac/json/browser/abnf/json.abnf

I like the way Perl 6 handles this with the grammar feature. (A grammar is just a special type of class, with a regex as just a special type of method.)

It could be simpler, but I want the resulting data structure to be easier to use.

  grammar Url {
  
    # default regex/token/rule/method to call
    # (token disables backtracking)
    token TOP {
      <protocol> <domain> <path> <query> <fragment>
    }
  
    token protocol {
      <(
  
        <[a..z]> ** 3..10
  
      )>     # don't include :// in the stringified result
  
      '://'  # must be escaped as it isn't alphanumeric
    }
  
    token domain-segment {  <-[?#/.]>+  }
    token domain {
      <domain-segment> ** 2..* # at least 2 domain segments
        % '.'                  # separated by .
  
      <?{
        # make sure that the last segment is at least 3 chars
        # (using the Boolean result of regular Perl 6 code)
        @<domain-segment>.tail.chars >= 3
      }>
    }
  
    token path-segment {  <-[?#/\\]>+  }
    token path {
      [
        <[/\\]>
        <path-segment>*
          %% <[/\\]>     # separated by path separator (allow trailing)
      ]?
    }
  
    token query-segment {
      # store as named, rather than positional
      $<key>   = ( <-[#=&]>+ )
      '='
      $<value> = ( <-[#=&]>+ )

      # run regular Perl 6 code in the regex
      {

        # attach a Pair object as the AST
        make ~$<key> => val(~$<value>)
        # (`val` turns a numeric value into an allomorph)

      }
    }
    token query {
      [
        '?'
        <( # don't include ? in the stringified result

          <query-segment>*
            % '&'         # separated by & (no trailing allowed)

        )>
      ]?
  
      {
        # attach a static associative array of the key value pairs
        # as the AST
        make Map.new: (@<query-segment>».ast if @<query-segment>.elems)
      }
    }
  
    token fragment {
      [
        '#'
         <(  .*  )> # don't include '#' in the stringified result
      ]?
    }
  }

Example usage:

  > my $result = Url.parse('http://perl6.org/foo/bar/baz/?a=1&b=2#fragment');
  > say $result;
  ｢http://perl6.org/foo/bar/baz/?a=1&b=2#fragment｣
   protocol => ｢http｣
   domain => ｢perl6.org｣
    domain-segment => ｢perl6｣
    domain-segment => ｢org｣
   path => ｢/foo/bar/baz/｣
    path-segment => ｢foo｣
    path-segment => ｢bar｣
    path-segment => ｢baz｣
   query => ｢a=1&b=2｣
    query-segment => ｢a=1｣
     key => ｢a｣
     value => ｢1｣
    query-segment => ｢b=2｣
     key => ｢b｣
     value => ｢2｣
   fragment => ｢fragment｣

  > say $result<query>.ast;
  Map.new((:a(IntStr.new(1, "1")),:b(IntStr.new(2, "2"))))

  > my %query := $result<query>.ast;
  > say %query<b> ~~ Int; # True (because of val(…))
  True

A more advanced usage would be with an actions class.

Basically Perl 6 treats regular expressions as code that is written in a domain specific sub-language, with grammars acting as a structure to hang them off of.

> I do not agree it is reasonable to declare that regular expressions are a bad DSL simply because it is possible (however common) for people to write difficult to read, or difficult to understand regular expressions.

I would not call RE a bad language - they are simply too useful for that. I would argue, though, that it's a reasonable design criticism to say - not that it's possible to write difficult to read code - but that it difficult to write easy to read code.

Agreed. The problem is the risk of small, relatively hard to spot & nearly impossible to properly debug mistakes.

> A{2,4} -> AA(A|AA)

And this is why we have the syntax sugar.

That introduces problems too. If you try to use sugar like '+' with an implementation that doesn't support it, you don't get any sort of error. Instead you get a different expression.

Unfortunately, there's an inherent tradeoff between encoding efficiency and error detection. Notice that with the VerbalExpressions it would be trivial to return a useful error message if the 'at_least_one' pattern did not exist.

Perl 6 regexes attempt improve upon this situation by making regexes more like a regular programming language. That is it errs on the side of error detection rather than encoding efficiency. (It also adds features that would be difficult to add to Perl 5/PCRE regex design)

For a start if it didn't support using `+`, then any attempt to use it would generate a compiler error because it is not alphanumeric. (regex is code in Perl 6)

All non-alphanumeric characters are presumed to be metasyntactic, and so must be escaped in some way to match literally. Arguably best way is to quote it like a string literal. (Uses the same domain specific sub-language that the main language uses for string literals)

    / "+" + /   # at least one + character

It really is a significant redesign.

    /A{2,4}/    # Perl 5/PCRE
    /A ** 2..4/ # Perl 6

    /A (?:BA){1,3}/x
    /A [BA] ** 1..3/ # Perl 6: direct translation
    /A ** 2..4 % B/  # Perl 6: 2 to 4 A's separated by B

    /A (?:BA){1,3} B?/x
    /A ** 2..4 %% B/   # Perl 6: %% allows trailing separator

    /\" [^"]* \"/x     # Perl 5/PCRE
    /\" <-["]>* \"/    # Perl 6: direct translation
    /｢"｣ ~ ｢"｣ <-["]>*/ # Perl 6: between two ", match anything else
                       # (can be used to generate better error messages)

    ---

    # Perl 5
    my $foo = qr/foo/;
    'abfoo' =~ /ab $foo/x;

    # Perl 6
    my $foo = /foo/;
    'abfoo' ~~ /ab <$foo>/;
    # or
    my token foo {foo}     # treat it as a lexical subroutine
    'abfoo' ~~ /ab <&foo>/;

    ---

    # Perl 5
    my $foo = 'foo';
    'abfoo' =~ /ab \Q $foo \E/x; # treat as string not regex
    # Perl 6
    my $foo = 'foo';
    'abfoo' ~~ /ab $foo/; # that is the default in Perl 6

Well spotted.

I would argue that risk of mistakes should not limit the expressivity of a language or have it added to the pile of bad ideas. It is better for users of the language to be aware of potential pitfalls, and use the language appropriately.

See my reply to shafte for some elaboration.

What drove me crazy at first was that any character can be used as a delimiter. That's very useful, I admit. But it complicates understanding examples found through searching ;)

Minor nitpick: A{2,4} becomes AA(|A|AA), not AA(A|AA).

`AA(|A|AA)` is valid regexp syntax?

Holy moly it is! I had no idea you could put a | right after parens like that! I guess (|A) is nothing or A? Woah.

Yep! It's equivalent to `AA(A|AA)?`, by way of the parent's reduction for `?`, but it's a nice option when you want to emphasize some kind of symmetry.

Well spotted. Thanks for providing the correct derivation.