Unofficial LSL Reference

[[articles:regex]]


Unofficial LSL reference

User Tools

Login

You are currently not logged in! Enter your authentication credentials below to log in. You need to have cookies enabled to log in.

Login

Forgotten your password? Get a new one: Set new password

This is an old revision of the document!


Regular expressions

Regular expressions are a language for matching strings to certain patterns. In this language, certain symbols are reserved for things like "match one or more of these", "match any of these possibilities", "match any character", etc.

We present here an implementation of regular expressions in LSL. Albeit very limited, it provides a good subset of POSIX extended regular expressions. Due to these limitations, it's basically restricted to validating strings and nothing else.

  • It does not perform captures; it only supports checking whether the given string matches the RE or not.
  • Pre-defined sets like \d, \s, or special functions like \b, are not available. In general, only escaping symbols with \ is allowed, plus \n for newline (but LSL already allows \n so that's not really a gain). But inside brackets, the \ loses its special meaning and is just one more character.
  • POSIX {n,m} suffixes are not supported.
  • POSIX collation-related syntax is not supported ([=...=], [:...:], [.....]).
  • Non-greedy matching operators ??, *?, +? are not supported.
  • Special groups starting with (? or (* are not supported.
  • No flags supported. Matches are always case-sensitive.
  • There's no error checking; errors in the expression may have bad consequences.

So what *is* supported?

Regex language accepted

  • c → matches the given character
  • . → matches any character including newline \n
  • \n → matches a newline
  • \<symbol> → matches the symbol as a character, e.g. \+ \\
  • expr1expr2 → matches the first expression followed by the second
  • expr1|expr2 → matches when expr1 matches or expr2 matches
  • (expr) → groups a sub-expression
  • expr+ → matches one or more expressions
  • expr* → matches zero or more expressions
  • expr? → matches zero or one expressions
  • ^ → matches at the beginning of the string
  • $ → matches at the end of the string
  • [...] → range
Range syntax
  • [abcd] → matches any of a, b, c, d
  • [a-dgj-m] → matches any of a, b, c, d, g, j, k, l, m
  • [^a-d] → matches anything except a, b, c, d
  • []a-d] → matches any of ], a, b, c, d. If there is a ] in the set, it must be right at the beginning (or immediately after the ^ for negative sets).
  • [a-d-] → matches any of -, a, b, c, d. If there is a - in the set, it must appear right at the beginning (or after the leading ^ if used) or right at the end.
  • [-a-d] → same as the previous one
  • [^]a-d-] → matches anything except ], a, b, c, d, -
  • [\] → the character \. All symbols lose their special meaning in brackets, except ] and - (and ^ at the beginning).

Usage

The regular expression must first be compiled before being used; the result of the compilation is a list. This compiled list can be used to check if any number of strings matches the original expression that was compiled.

If you intend to use this code for something like validating strings against pre-defined patterns, it may be best to compile the expression to a list in advance, then use this list and only the matching code in the final script. To that end, we've divided the script into the common section, the compiling section, the matching section and the test code.

Common section

This must be included with both the compilation section and the matching section.

// Regular Expression Engine in LSL
// Copyright © 2020 Sei Lisa
//
// Thanks to Russell Cox for showing the way.
// https://swtch.com/~rsc/regexp/regexp1.html

// Usage:
//  list my_compiled_regex = compile("regex");
//  if (match(my_compiled_regex, "string"))
//      llOwnerSay("matches!");
//  else
//      llOwnerSay("does not match!");

integer p; // parse position
list mono=[p]; // If you get an error here, you're not compiling in Mono mode.
                // This program requires Mono. It won't work otherwise.
Compilation section
// Limitations:
// - Only matches / does not match. No captures.
// - The accepted syntax is:
//     - c   -> character
//     - .   -> any character including newline (\n)
//     - \n  -> newline
//     - \<symbol> -> matches the symbol as a character e.g. \+, \\
//     - e1|e2 -> either e1 or e2
//     - (e) -> subexpression
//     - e*  -> zero or more
//     - e+  -> one or more
//     - e?  -> zero or one
//     - ^   -> matches at the beginning
//     - $   -> matches at the end
//     - [abc]  -> any of a, b, c
//     - [a-df] -> any of a, b, c, d or f
//     - [^abc] -> anything except a, b or c
//     - []abc] -> the character ] or a or b or c
//     - [-abc] -> the character - or a or b or c
//     - [abc-] -> the character - or a or b or c
//     - [+--]  -> the character + (2B), comma (2C) or - (2D)
//     - [^]a-c-] -> anything except ], a, b, c or -
//     - [*]    -> the character * (works for all symbols except ^)
// - The \ character is NOT special within brackets.
// - Does NOT support:
//     - Any predefined range or special like \S, \s, \b, \d, \a, etc.
//     - {[n][,[m]]} for "between n and m times"
//     - POSIX collations [= ... =], [: ... :], [. ... .]
//     - Non-greedy matching operator, e.g. a*?
//     - Special groups that begin with (? or (*
// - No error checking. For example a ) without a matching ( terminates the
//   expression prematurely.

string rx; // regular expression being parsed

// Compile a regular expression into an NFA
//
// The compiled format is a strided list of stride 2.
// - If the 1st element is a string, it's a match range, positive or negative.
//   - The second element is an integer: the offset of the next state relative
//     to the first element of the stride.
// - If the 1st element is an integer, it's an edge of the graph that does
//   not consume characters.
//   - If the second element is an integer, the node is a split; both elements
//     are offsets for the next state in that case.
//   - If the second element is a string, it's either "^" for a left anchor,
//     "$" for a right anchor, or "" for a node that always matches. The first
//     element is the state to go to (as an offset) when the current position
//     is the expected one or when the second element is "".

// Find and process suffixes
list _suff(list rc)
{
    string c = llGetSubString(rx, p, p);
    integer rclen = llGetListLength(rc);
    if (c == "*")
    {
        ++p;
        // Add a split at the beginning that goes to the end of the list,
        // and a dummy node to go back to the split. This last state could
        // be avoided by patching the list, but that's harder.
        //return [2, rclen] + rc + [-2 - rclen, ""];
        // optimized version:
        return 2 + (rclen + 4 + (rc + -(2 + rclen) + ""));
    }
    if (c == "+")
    {
        ++p;
        // Add a split after the list, that goes back to the list
        return rc + 2 + -rclen;
    }
    if (c == "?")
    {
        ++p;
        // Add a split before the list, that skips the list
        return 2 + (2 + rclen + rc);
    }
    return rc;
}

// Main compilation engine
list _compile()
{
    list rc;
    list aux;

    string c;

    @again;

    c = llGetSubString(rx, p, p+!llSubStringIndex(rx, "\\")); // grab 1 or 2 chars

    if (c == "" | c == ")")
        jump break;

    if (c == "(")
    {
        ++p;
        aux = _compile();
        // assume we're in a matching ")"
        ++p;
        rc += _suff(aux);
        jump again;
    }
    if (c == "|")
    {
        ++p;
        aux = _compile();

        // We're adding here an extra state which could be avoided by patching the list
        rc = 2 + (4 + llGetListLength(rc) + rc + (2 + llGetListLength(aux)) + "" + aux);
        jump break;
    }
    if (c == "^" | c == "$")
    {
        ++p;
        rc = rc + 2 + c;
        jump again;
    }
    if (c == "[")
    {
        integer p2 = p + 1;
        if (llGetSubString(rx, p2, p2) == "^")
            ++p2;
        c = llGetSubString(rx, p2 + -1, p = p2 + llSubStringIndex(llGetSubString(rx, p2 + 1, -1), "]"));
        p += 2; // skip ]
    }
    else if (c == "\\n")
    {
        c = "[\n";
        p += 2;
    }
    else if (1 < llStringLength(c))
    {
        c = "[" + llGetSubString(c, 1, 1);
        p += 2;
    }
    else if (c == ".")
    {
        ++p;
    }
    else
    {
        c = "[" + c;
        ++p;
    }
    rc += _suff((list)c + 2);

    jump again;
    @break;
    return rc;
}

list compile(string s)
{
    p = 0;
    // Our match engine only performs anchored matches; modify the regex to allow
    // anything before and after it, as usual. Anchoring will sill work.
    rx = ".*(" + s + ").*";
    return _compile();
}
Matching section

This section provides the function match(compiled_regex, string_to_match). It needs the common section above.

// Match section - Run the NFA one input character at a time

// Tell whether a character is between two others, Unicode-wise
integer _between(string s, string a, string b)
{
    // Works for same-length arguments
    return a + s + b == (string)llListSort((list)a + s + b, 1, TRUE);
/*
    // Works for arguments of any length
    list aux = llListSort((list)a + s + b, 1, TRUE);
    return a == llList2String(aux, 0) & b == llList2String(aux, 2);
*/
}

integer L; // length of input string, used to evaluate anchors

// Follow the edges that are not associated to an input character
// Returns the input list plus the first state which *is* associated
// to a character, if it wasn't in the list already.
list _follow(integer st, list rc, list new)
{
    if (TYPE_INTEGER == llGetListEntryType(rc, st))
    {
        // Split or anchor - follow if condition met
        string s = llList2String(rc, st+1);
        if (s != "^" & s != "$" | s == "^" & !p | s == "$" & p == L)
          new = _follow(st + llList2Integer(rc, st), rc, new);
        if (s != "" & s != "^" & s != "$")
          new = _follow(st + (integer)s, rc, new);
        return new;
    }
    if (!~llListFindList(new, (list)st))
        new += st;
    return new;
}

// Match a compiled regular expression against a string
// Return 0 (FALSE) if it doesn't match; something else if it matches
integer match(list rc, string s)
{
    L = llStringLength(s);
    integer st;
    p = st;
    list jobs = _follow(st, rc, []);
    string m; // current match being tested
    integer acceptState = llGetListLength(rc);

    @again;

    list new = [];
    string c = llGetSubString(s, p, p);
    ++p;
    integer job = llGetListLength(jobs);
    while (job)
    {
        st = llList2Integer(jobs, --job);
        if (st == acceptState)
            jump continue; // the current character can't advance from accept;
                           // this happens when there are extra chars after
                           // the RE
        m = llList2String(rc, st);

        if (!llSubStringIndex(m, "[") | !llSubStringIndex(m, "^"))
        {
            // starts with [ or ^, it's a range or single character
            integer mlen = llStringLength(m);
            integer match;
            integer inv = !llSubStringIndex(m, "^");

            if (mlen == 2)
            {
                // Fast-track single-character matches/non-matches
                match = "[" + c == m | "^" + c == m;
            }
            else if (mlen > 2)
            {
                // Multi-character matches are more difficult
                integer pm = 1;
                @loop;

                if (mlen > pm+2 & "-" == llGetSubString(m, pm+1, pm+1))
                {
                    // Range
                    match = match | _between(c, llGetSubString(m, pm, pm), llGetSubString(m, pm+2, pm+2));
                    pm += 3;
                }
                else
                {
                    match = match | c == llGetSubString(m, pm, pm);
                    ++pm;
                }

                if (pm < mlen)
                    jump loop;
            }
            if (inv ^ match)
            {
                // Match found; advance this job
                new = _follow(st + llList2Integer(rc, st+1), rc, new);
            }
        }
        else if (m == ".")
        {
            // always matches
            new = _follow(st + llList2Integer(rc, st+1), rc, new);
        }

        @continue;
    }
    jobs = new;

    if (jobs != [] & -(p != L))
        jump again;

    return ~llListFindList(jobs, (list)acceptState);
}
Testing section (with list dumping tool)

This section also includes a function to dump a list to LSL format, allowing you to copy paste it to another script.

string QuoteString(string s)
{
    s = llDumpList2String(llParseStringKeepNulls(s, ["\\"], []), "\\\\");
    s = llDumpList2String(llParseStringKeepNulls(s, ["\n"], []), "\\n");
    return "\"" + llDumpList2String(llParseStringKeepNulls(s, ["\""], []), "\\\"") + "\"";
}

string AddLine(string lines, string lineToAdd)
{
    if (llStringLength(llStringToBase64(lines + "\n, " + lineToAdd)) > 1364)
    {
        llOwnerSay(lines);
        lines = "\n, " + lineToAdd;
        llSleep(1);
    }
    else
    {
        if (lines == "")
            lines = "\n[ " + lineToAdd;
        else
            lines = lines + ", " + lineToAdd;
    }
    return lines;
}

DumpListLSL(list L)
{
    string ret = "";
    integer len = llGetListLength(L);
    integer i;
    for (i = 0; i < len; ++i)
    {
        integer typ = llGetListEntryType(L, i);
        if (typ == TYPE_KEY | typ == TYPE_STRING)
        {
            if (typ == TYPE_KEY)
                ret = AddLine(ret, "((key)" + QuoteString(llList2String(L, i)) + ")");
            else
                ret = AddLine(ret, QuoteString(llList2String(L, i)));
        }
        else if (typ == TYPE_VECTOR | typ == TYPE_ROTATION)
        {
            if (typ == TYPE_VECTOR)
            {
                vector v = llList2Vector(L, i);
                ret = AddLine(ret, "<" + llList2CSV((list)v.x + v.y + v.z) + ">");
            }
            else
            {
                rotation v = llList2Rot(L, i);
                ret = AddLine(ret, "<" + llList2CSV((list)v.x + v.y + v.z + v.s) + ">");
            }
        }
        else
            ret = AddLine(ret, llList2CSV(llList2List(L, i, i)));
    }
    llOwnerSay(ret + "]");
}

test(string pattern, list subjects)
{
    integer i;
    llOwnerSay("pattern: " + pattern);
    list rc = compile(pattern);
    llOwnerSay("compiled pattern:");
    DumpListLSL(rc);
    for (i = 0; i < llGetListLength(subjects); ++i)
    {
        string s = llList2String(subjects, i);
        string result = "no";
        if (match(rc, s))
          result = "yes";
        llOwnerSay("match(compiled," + QuoteString(s) + "): " + result);
    }
}

default
{
    state_entry()
    {
        // Try matching (ab)*c against several strings
        string F = "";

        test("^abc$", ["abc", "abcc", "abcd", "aabc", "ab"]);
        test("^a*b$", ["abc", "bb", "b", "aab", "ba"]);
        test("^(ab)+c$", ["abc", "ababc", "abac", "bac", "ab"]);
        test("^(a|b)+c$", ["abc", "ababc", "abac", "bac", "ab"]);
        test("abc", ["abc", "ababc", "abac", "bac", "ababcde"]);

        // Validate strings like "19xx-1-1" or "20xx-01-01", no leap years
        test("^((19|20)[0-9][0-9])-(0?[1-9]|1[012])-(0?[1-9]|[12][0-9]|3[01])$", [
          "2020-01-31", "2020-01-32", "2099-12-31", "2100-01-01", "2020-2-28",
          "2020-02-19", "2099-02-31"
        ]);

        // Validate dates of the form YYYY-MM-DD including leap years
        // (valid for years 1600 to 9999)
        test("^((1[6-9]|[2-9][0-9])[0-9][0-9]-(0[13578]|1[02])-(0[1-9]|[12][0-9]|3[01]))$|^((1[6-9]|[2-9][0-9])[0-9][0-9]-(0[469]|11)-(0[1-9]|[12][0-9]|30))$|^((16|[248][048]|[3579][26])00)|(1[6-9]|[2-9][0-9])(0[48]|[13579][26]|[2468][048])-02-(0[1-9]|[12][0-9])$|^(1[6-9]|[2-9][0-9])[0-9][0-9]-02-(0[1-9]|1[0-9]|2[0-8])$", [
          "2020-01-31", "2020-01-32", "2099-12-31", "2100-01-01", "2020-02-28",
          "2020-02-29", "2021-02-29", "2030-04-31", "2030-04-30"
        ]);

        // Regex for 'string that does not contain the word "string"'
        test("^([^s]|s(s|t(s|r(s|i(s|ns))))*([^st]|t([^rs]|r([^is]|i([^ns]|n[^gs])))))*(s(s|t(s|r(s|i(s|ns))))*(t(r?|rin?))?)?$", [
          "no strings allowed", "stringstringstring", "it's stringalicious", "this does not contain the word s-t-r-i-n-g even if it ends in strin"
        ]);

    }
}

Motivation

There's a page in the Second Life wiki that introduces a so-called "regex engine", to disprove the argument that a "regular expression engine in LSL will not work well". However, the argument is basically framed as a straw-man: it builds an engine that is so limited that it isn't even capable of parsing most regular languages, and therefore can't really be characterized as a regular expression engine in the theoretical sense.

So I (Sei Lisa) set up to build an engine that is able to parse any regular language (limited in practice by LSL memory of course), using a large enough subset of the syntax of POSIX EREs as to guarantee that all regular languages are covered. The result is not too practical, but it also isn't as bad as I though. It is able to understand somewhat complex regular expressions (see tests), though the cost of parsing (compiling) is prohibitive with complex expressions for run-time use; however, the cost of matching is not extremely bad, and it might even find some practical applications. My advice is not to use it with very long input text (say 1K or more), because matching is not too fast. Matching speed also depends on the complexity of the (compiled version of the) regular expression itself, so be careful with that if using it in any serious application. Run some benchmarks with your regex and be careful to limit the length of the input text if necessary.