How to match a regex with backreference in Go?

Question

I need to match a regex that uses backreferences (e.g. \1) in my Go code.

That's not so easy because in Go, the official regexp package uses the RE2 engine, one that have chosen to not support backreferences (and some other lesser-known features) so that there can be a guarantee of linear-time execution, therefore avoiding regex denial-of-service attacks. Enabling backreferences support is not an option with RE2.

In my code, there is no risk of malicious exploitation by attackers, and I need backreferences.

What should I do?

Answer 1

Answering my own question here, I solved this using golang-pkg-pcre, it uses libpcre++, perl regexes that do support backreferences. The API is not the same.

Answer 2

Regular Expressions are great for working with regular grammars, but if your grammar isn't regular (i.e. requires back-references and stuff like that) you should probably switch to a better tool. There are a lot of good tools available for parsing context-free grammars, including yacc which is shipped with the Go distribution by default. Alternatively, you can also write your own parser. Recursive descent parsers can be easily written by hand for example.

I think regular expressions are overused in scripting languages (like Perl, Python, Ruby, ...) because their C/ASM powered implementation is usually more optimized than those languages itself, but Go isn't such a language. Regular expressions are usually quite slow and are often not suited for the problem at all.

Answer 3

When I had the same problem, I solved it using a two-step regular expression match. The original code is:

if m := match(pkgname, `^(.*)\$\{DISTNAME:S(.)(\\^?)([^:]*)(\\$?)\2([^:]*)\2(g?)\}(.*)$`); m != nil {
    before, _, left, from, right, to, mod, after := m[1], m[2], m[3], m[4], m[5], m[6], m[7], m[8]
    // ...
}

The code is supposed to parse a string of the form ${DISTNAME:S|from|to|g}, which itself is a little pattern language using the familiar substitution syntax S|replace|with|.

The two-stage code looks like this:

if m, before, sep, subst, after := match4(pkgname, `^(.*)\$\{DISTNAME:S(.)([^\\}:]+)\}(.*)$`); m {
    qsep := regexp.QuoteMeta(sep)
    if m, left, from, right, to, mod := match5(subst, `^(\^?)([^:]*)(\$?)`+qsep+`([^:]*)`+qsep+`(g?)$`); m {
        // ...
    }
}

The match, match4 and match5 are my own wrapper around the regexp package, and they cache the compiled regular expressions so that at least the compilation time is not wasted.

Answer 4

regexp package funcs FindSubmatchIndex and Expand can capture content by backreferences. It isn't very convenient, but it is still possible. Example

package main

import (
    "fmt"
    "regexp"
)

func main() {
    content := []byte(`
    # comment line
    option1: value1
    option2: value2

    # another comment line
    option3: value3
`)

    pattern := regexp.MustCompile(`(?m)(?P<key>\w+):\s+(?P<value>\w+)$`)

    template := []byte("$key=$value\n")
    result := []byte{}
    for _, submatches := range pattern.FindAllSubmatchIndex(content, -1) {
        result = pattern.Expand(result, template, content, submatches)
    }
    fmt.Println(string(result))
}

output

option1=value1
option2=value2
option3=value3

Answer 5

I think this was an old question, but I haven't found a simple solution from answers above.

In addition, "golang-pkg-pcre" does not work on macOS with M1.

Therefore, I would like to contribute my idea.

For example, to replace <u> or <I> with <b> and replace </u> or </I> with </b>. The search is case-insensitive.

Let me compare how to do it in python and in go

In python, it is easy as below:

import re
content = "<u>test1</u> <i>test2</i>\n<U>test3</U> <I>test4</I>"
content = re.sub(r"<(u|i)>([^<>]+?)</\1>", r"<b>\2</b>", content, flags=re.IGNORECASE)
print(content)

In go, I do it this way:

package main

import (
    "fmt"
    "regexp"
)

func main() {
    content := "<u>test1</u> <i>test2</i>\n<U>test3</U> <I>test4</I>"
    content = changeUITagToBTag(content)
    fmt.Println(content)
}

// change <u> or <i> to <b> and </u> or </i> to </b>
// case-insensitive search
func changeUITagToBTag(content string) string {
    pattern := `<(u|i)>([^<>]+?)</(u|i)>`
    compiledPattern := regexp.MustCompile(fmt.Sprintf(`(?%v)%v`, "i", pattern))
    content = compiledPattern.ReplaceAllStringFunc(content, func(text string) string {
        allSubStrings := compiledPattern.FindAllStringSubmatch(text, -1)
        if allSubStrings[0][1] == allSubStrings[0][3] {
            return fmt.Sprintf(`<b>%s</b>`, allSubStrings[0][2])
        }
        return text
    })
    return content
}