2

I have a syn match item like this:

syn match txr_num "[+\-]\?\([0-9]\|[0-9][,0-9]*[0-9]\)\?[.]\([0-9]\|[0-9][,0-9]*[0-9]\)\([eE][+\-]\?[0-9]\+\)\?"

Given an input like 1.234e13 it matches only one digit after the decimal point, causing only 1.2 to be colored, regardless of what combination of digits, commas or e or E exponent follows that 1.2.

If I remove the following underlined part of the regex, it handles that case fine; all of 1.234e13 is colored:

syn match txr_num "[+\-]\?\([0-9]\|[0-9][,0-9]*[0-9]\)\?[.]\([0-9]\|[0-9][,0-9]*[0-9]\)\([eE][+\-]\?[0-9]\+\)\?"
                                                             ^^^^^^^

The subexpression there is this (using more readable regex syntax):

\([0-9]\|[0-9][,0-9]*[0-9]\)
  ^^^^^^^

This matches either a single digit, or else a digit, followed by a any mixture of digits and periods (including empty) and a digit.

Exactly the same pattern is found before the [.], and on that side it works; for instance in the case 123.456, the 123.4 part is matched.

Somehow, Vim's regex is getting stuck on that underlined term. If it is included, it's as if that whole subexpression is just matching a single [0-9], ignoring the branch which matches two or more digits, possibly with interior separating commas.

Am I doing something wrong in that expression anywhere? This is Vim 8.0 on Ubuntu 18.

Update:

Workaround found. It goes away when I exchange the terms of the | branch:

\([0-9]\|[0-9][,0-9]*[0-9]\)   ->   \([0-9][,0-9]*[0-9]\|[0-9]\)

Does Vim's regex branch operator some special ordering semantics such that A|B is not always the same as B|A, or is this a bug?

9
  • 1
    Note that vim supports some "abbreviations" like \d
    – D. Ben Knoble
    Oct 6, 2022 at 13:56
  • Also, \v to use very magic mode would probably make these regexs more readable, I think. And you don't need to escape the minus in [+-] because it's at the end.
    – Rich
    Oct 6, 2022 at 15:41
  • @Rich The regex is generated, by code where 0-9 looks like @dig. I could make @dig expand to \d but it would only make the expansion more readable.
    – Kaz
    Oct 6, 2022 at 19:27
  • I have updated my Answer , giving two Possible Solutions ; Do try it & let me know if it helps or there is no improvement ! @Kaz
    – Prem
    Oct 6, 2022 at 19:52
  • 1
    The “problematic” semantics are documented, FWIW. :help /bar.
    – D. Ben Knoble
    Oct 6, 2022 at 22:28

3 Answers 3

3

Obviously, this is your bug.

Why so? Well, let's suppose we have input of 12.34. The "left" expression could match "one" only, but then it can't match "dot". So the engine steps back and re-matches "twelve" and then also "dot" successfully. Then "right" expression matches "three" and... that's all. No one will care of "four", as only "three" was enough to do the job.

11
  • 1
    @Kaz they don't have non-greedy semantics, but there's no reason for the engine to go chasing after B in A|B when A is matched without problems. You could write [0-9]|[0-9][,0-9]*[0-9] as [0-9]\([,0-9]*[0-9]\)\?
    – muru
    Oct 6, 2022 at 7:13
  • 1
    In fact, this is documented: :h /|: "If more than one branch matches, the first one is used."
    – muru
    Oct 6, 2022 at 7:21
  • 1
    Regex "or" is not commutative. Just consider "A or AA".
    – Matt
    Oct 6, 2022 at 8:51
  • 1
    @Rich: lex, which in many ways is THE regexp engine, works in precisely the opposite way. Alternation is commutative as it ought to be, and the longest match is always taken, however it appears in the expression. That's partly connected with the fact that the matching is not done by backtracking. Oct 6, 2022 at 18:23
  • 1
    @Rich There is a very good reason for it too. A regular expression R is a representation for a set of strings S(R). E.g a(b|c|de) represents the set {"ab", "ac", "ade" }. The branch operator has the important prperty that S(R1|R2) is S(R1) U S(R2). When we combine regexes with |, we are doing a set union between their string sets. This is not true of the PCRE/Vim/ECMA left over right semantics. I came up with the regex using set reasoning: combining the set of strings "digit, mixture of digits and commas, digit" with the set "single digit" that is missing from that set.
    – Kaz
    Oct 7, 2022 at 19:11
1

The way I am viewing it :

You have 3 optional Parts with 2 non-optional Parts in the middle.

SIGN - INITIAL DIGITS before DOT - [[ DOT - DIGITS after DOT ]] - EXPONENT

Here the Parts in [[ - ]] are non-optional.

DOT is not the Issue.

The DIGITS after DOT :
\([0-9]\|[0-9][,0-9]*[0-9]\)

This has (A|B) where A matches Single DIGIT & B matches multiple Digits.

It is matching the Single DIGIT & moving on to the EXPONENT , which is not there but that is optional.

It is working correctly , but the way to settle your Issue is to make it match all DIGITS (using a +) before moving to the EXPONENT :
\([0-9]+\|[0-9][,0-9]*[0-9]\)

I think this will work.

Alternative Solution :

When (A|B) matches A & the Engine moves on , it has only the optional EXPONENT Part , hence it never comes back to try B , which suggests this Alternative Solution :
At the End of the regex , after the EXPONENT , try to include some non-optional Part , eg (SPACE|Letter-Other-than-E|END-of-line) , which will either match together with A or together with B , in which case the Engine has to come back to that Point.

You could even use both the Solutions together !

1

It turns out that Vim has uses procedural logic for matching branches, whereby if the left side of the | operator matches, the right is ignored.

It is like effectively like a case statement. If overlapping cases occur in a case statement, the order matters; if a superset match occurs first (.e.g. "match all inputs starting with a) before a subset of that ("match all inputs starting with "abc"`), then the second case never occurs:

if (starts_with("a", string)) {
   // taken for "abc..." strings
} else if (starts_with("abc", string)) {
   // thus, dead code
}

I don't see any issues when the expression is reordered:

\([0-9]\|[0-9][,0-9]*[0-9]\)   ->   \([0-9][,0-9]*[0-9]\|[0-9]\)

The expression is inserted by code generation, which defines it in one place, so I fixed in all places where it occurs, whether necessary or not.

It doesn't seem like a huge issue in an editor; I've been using nothing but Vim for editing since 1994 and didn't notice. Syntax highlighting can use some complex regular expressions, which are similar to the ones used by the corresponding languages for lexical analysis.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.