Live data from Hacker News

Sat solver on top of regex matcher

yurichev.com

51–53 of 53 posts

Re: Sat solver on top of regex matcher

#51
post #10

Earlier quoted context omitted.

I wouldn't say so, but I use the term "regular language" if I mean the mathematical concept.

But a "regular language" is not the same as "regular expression" as mathematical concepts.

(late reply) Hm you've negelected to do the obvious thing and explain the difference.

I don't think there's a difference, and if there is one, it's probably not relevant to programming. Whereas the one I'm highlighting is relevant to programming.

Re: Sat solver on top of regex matcher

#52
post #10

Earlier quoted context omitted.

I wouldn't say so, but I use the term "regular language" if I mean the mathematical concept.

I don’t think it’s pedantic to say that a regular language is not the same thing as a regular expression. The difference between syntax and semantics is real and important.

(late reply) Right that's what I'm saying. Who said it was pedantic? :)

Re: Sat solver on top of regex matcher

#53
post #50
post #49

Earlier quoted context omitted.

Raku allows strings inside of strings. Of course it does this by way of embedded closures. "abc{ "def" }" Which allows it to be arbitrarily deep. "a{ "b{ "c{ "d{ "e{ "f" }g" }h" }i" }j" }k" → "abcdefghijk" This can be handy to generate the correct string. my $count = 3; "I went to $count place{ "s" if $count ≠ 1 } today"

Interesting, thanks for pointing out a use case. But I don't think backreferences will help with that, it needs to be parsed by something more powerful than a regex. And that example reminds me that Bash can do something similar: echo "$(echo "$(echo "$(echo "hi")")")"

The Rakudo implementation actually uses Raku regexes to parse Raku. To be fair though it is a lot easier to do that with the redesigned regexes that Raku has.

Basically you can use backreferences for that if you also allow the regex to be recursive.

    my $regex = /
      :ratchet
      $ = () # the beginning quote

      {}:my $q = ~$; # put it into a more normal lexical var

        # capture between " and {
        $ = ( [   ]* )

        [
          [
            :sigspace
            「{」
                ? # recurse
            「}」
          ]

          {$q = ~$}

          # capture between } and "
          $ = ( [   ]* )
        ]?

      "$q" # match the end quote

      # pass the combined string parts upwards
      { make ($ // '') ~ ($.ast // '') ~ ($ // '') }
    /;

    「'a{ "b{ "c{ "d{ 'e{ "f" }g' }h" }i" }j" }k'」 ~~ /^  $ { make $.ast }/;

    say $/.ast;
    # abcdefghijk
Note that `Regex` is a subtype of `Block`. That is why `&?BLOCK` can be used as a reference to the regex itself.

`` is a way to call `bar`, but also save it under the name of `foo`. `$ = …` is a way to capture `…` and save it under the name of `foo`.

---

It is a lot nicer and modular when you use regexes as part of a grammar:

    # use Grammar::Tracer;
    grammar String::Grammar {
      token TOP {  }

      rule strings {
        # at least one string
        # if there are more than one they are separated by ~
         + % 「~」
      }

      token string {
        $ = 

        # set a dynamic variable to the quote character
        {}:my $*quote = ~$;

        *

        "$"
      }

      # multiple tokens that act like one
      # which is nicer than using |
      proto token string-part {*}
      multi token string-part: {
        [   ]+
      }
      multi token string-part: {
        
      }

      rule block {
        「{」 ~ 「}」 ?
      }
    }

    class String::Actions {
      method TOP     ($/) { make     $.ast }
      method strings ($/) { make [~] @».ast }
      method string  ($/) { make [~] @».ast }
      method block   ($/) { make     $.ast }

      method string-part:   ($/) { make ~$/ }
      method string-part: ($/) { make $.ast }
    }

    say String::Grammar.parse(
        「"a{ "b{ "c{ "d{ "e{ "f" }g" ~ "zz" }h" }i" }j" }k"」,
        :actions( String::Actions ),
    ).ast;
    # abcdefgzzhijk
A `token` is just a `regex` with `:ratchet` mode turned on. (prevents backtracking) A `rule` is just a `token` with `:sigspace` also turned on. (makes it easier to deal with optional whitespace.)

Every instance of `` is basically a method call.

`make` is about generating an `.ast` to pass up and out of the parse. In this case the only thing the actions class does is return what would be the resulting string if it were compiled in Raku.

Post reply on HN