[Feature Request]: Ability to use ^ in regexp

[ccleve]

I'd like to be able to match the beginning of the input in a regular expression:

^"-"|" -" // match "-" if it is at the beginning of the input or preceded by a space

There was some mention of this in #448.

I'm using Rust.

[skvadrik]

I'm not sure I understand. re2c always starts matching at the beginning (it's not like POSIX RE in that regard), so ^ "-" | " -" would be the same as "-" | " -". If you want to match in the middle, you need an explicit rule that skips characters and loops back to the beginning of the lexer block. Can you give a more complete example?

[ccleve]

Sure. Imagine a search engine query language that supports AND, OR, and NOT. Some example searches:

teddy AND bears
teddy AND NOT bears
NOT teddy AND bears
ANDROID 
WHATNOT

It's easy to handle AND and OR, just insist on spaces: " AND ", " OR ". This prevents you from matching AND in ANDROID.

NOT is harder. You don't want to match NOT in WHATNOT, but you can't prefix it with a space because you wouldn't match it in "NOT teddy AND bears".

One way to do it:
not = ^"NOT "|" NOT ";

This says that NOT must be at the beginning of a line or have a space in front of it. The "^" makes it possible.

This is just an example. The actual query language is much more complicated, and there are five keywords or symbols like NOT that should appear only at the beginning of a line or with a preceding space.

[skvadrik]

I don't think it's a good approach to rely on preceding whitespace. It does not scale well with the language complexity:

• You may want to allow something else, not just spaces, that is allowed before NOT, perhaps parenthesis or other punctuation, and the number of combinations of various lexemes may grow too large.
• You may want to handle certain whitespace characters in a special way, e.g. count newlines, and then having a newline followed by NOT will be very inconvenient.
• There may be corner cases related to start/end of input, like the one you mentioned above.

The right approach IMO would be to have a generic catch-all-ID-like rule with low priority, something like [_a-zA-Z][_a-zA-Z0-9]* { /* error: unknown identifier */ }. And then you can just skip spaces and forget about them. Also it would help with error handling, as it's much better to get a message unknown identifier: 'WHATNOT' than some generic syntax error.

[RadhiFadlillah]

I'm the original poster of #448. Back then, I found a workaround for my issue, but since I wasn't sure how safe it was, I didn’t share the solution at the time. Essentially, I added control characters to the input string:

input = "\002" + input // add \x02 to represent the start of the string  
input = input + "\003" // add \x03 to represent the end of the string  
input = input + "\000" // finally, add a terminating null character  

So your regex:

^"NOT "|" NOT "

gets converted into this (I'm using Flex syntax):

[\x02]NOT[ ]|[ ]NOT[ ]

Here is the playground for my re file, and here’s the Go playground to see how it looks when used in code.

By the way, @skvadrik, do you think this is safe to use? Personally, I assume it’s safe enough since \x02 and \x03 seem to be rarely used in typical input, and the worst-case scenario would be an incorrect regex match.

[skvadrik]

By the way, @skvadrik, do you think this is safe to use? Personally, I assume it’s safe enough since \x02 and \x03 seem to be rarely used in typical input, and the worst-case scenario would be an incorrect regex match.

If you mean safety in the sense that the lexer won't read past the end of input, then it should be safe (provided that the rest of the code follows the rules for handling the end of input, as usual). But if you mean safety in the sense of correctness, then it's not safe - as you said, match results may be incorrect. It also requires padding the input, which may be very inefficient due to all the extra copying.

So, it's an curious workaround, but I do not recommend it. As I said in the comment above, it should be possible to do proper tokenization of the input that will correctly recognize longer lexemes containing NOT. I haven't seen your real grammar, but I'd be happy to help.

If you want to go with the workaround, but you'd like to make it safer in the sense of correctness, you can do a manual check of the surrounding context in semantic action. It is awkward, but you can isolate the check into a macro and reuse it for other lexemes.

  cursor = input;
for {
  token = cursor;
/*!re2c
  [ ]?NOT[ ]? {
    if !(input[token] == ' ' || token == 0) || !(input[cursor-1] == ' ' || cursor == limit) {
        // NOT preceded by something other than space or start, handle error
    }
    // do the usual processing
  }
  // other rules
*/
}

Here's a modified example on playground that uses this idea.

By the way the example is a bit overly complicated:

• it doesn't really need to use tags
• it can use simple API with re2c:api = simple;
• it doesn't need YYLESSTHAN as it disables YYFILL

I assume it's cut down from a more complex one.