Greedy/Non-Greedy pattern matching and optional suffixes in Lua

Question

In Lua, I'm trying to pattern match and capture:

+384 Critical Strike (Reforged from Parry Chance)

as

(+384) (Critical Strike)

where the suffix (Reforged from %s) is optional.

Long version

I'm trying to match a string in Lua using patterns (i.e. strfind)

Note: In Lua they don't call them regular expressions, they call them patterns because they're not regular.

Example strings:

+384 Critical Strike
+1128 Hit

This is broken down into two parts that I want to capture:

• The number, with the leading positive or negative indicator; int his case is +384
• The string, in this case is Critical Strike.

I can capture these using a fairly simple pattern:

And this pattern in lua works:

local text = "+384 Critical Strike";
local pattern = "([%+%-]%d+) (.+)";
local _, _, value, stat = strfind(text, pattern);

• value = +384
• stat = Critical Strike

The Tricky Part

Now I need to expand that regular expression pattern to include an optional suffix:

+384 Critical Strike (Reforged from Parry Chance)

Which is broken down into:

Note: I don't particularly care about the optional trailing suffix; meaning that I have no requirement to capture it, Although capturing it would be handy.

This is where I start to get into issues with greedy capturing. Right away the pattern I already have does what I don't want it to:

• pattern = ([%+%-]%d+) (.+)
• value = +384
• stat = Critical Strike (Reforged from Parry Chance)

But let's try to include the suffix in the pattern:

with the pattern:

pattern = "([%+%-]%d+) (.+)( %(Reforged from .+%))?"

And I'm using the ? operator to indicate 0 or 1 appearances of the suffix but that matches nothing.

I blindly tried changing the optional suffix group from parenthesis ( to brackets [:

pattern = "([%+%-]%d+) (.+)[ %(Reforged from .+%)]?"

But now the match is greedy again:

• value = +384
• stat = Critical Strike (Reforged from Parry Chance)

Based on the Lua pattern reference):

• x: (where x is not one of the magic characters ^$()%.[]*+-?) represents the character x itself.
• .: (a dot) represents all characters.
• %a: represents all letters.
• %c: represents all control characters.
• %d: represents all digits.
• %l: represents all lowercase letters.
• %p: represents all punctuation characters.
• %s: represents all space characters.
• %u: represents all uppercase letters.
• %w: represents all alphanumeric characters.
• %x: represents all hexadecimal digits.
• %z: represents the character with representation 0.
• %x: (where x is any non-alphanumeric character) represents the character x. This is the standard way to escape the magic characters. Any punctuation character (even the non-magic) can be preceded by a '%' when used to represent itself in a pattern.
• [set]: represents the class which is the union of all characters in set. A range of characters can be specified by separating the end characters of the range with a '-'. All classes %x described above can also be used as components in set. All other characters in set represent themselves. For example, [%w_] (or [_%w]) represents all alphanumeric characters plus the underscore, [0-7] represents the octal digits, and [0-7%l%-] represents the octal digits plus the lowercase letters plus the '-' character. The interaction between ranges and classes is not defined. Therefore, patterns like [%a-z] or [a-%%] have no meaning.
• [^set]: represents the complement of set, where set is interpreted as above.

For all classes represented by single letters (%a, %c, etc.), the corresponding uppercase letter represents the complement of the class. For instance, %S represents all non-space characters.

The definitions of letter, space, and other character groups depend on the current locale. In particular, the class [a-z] may not be equivalent to %l.

and the magic matchers:

• *, which matches 0 or more repetitions of characters in the class. These repetition items will always match the longest possible sequence;
• +, which matches 1 or more repetitions of characters in the class. These repetition items will always match the longest possible sequence;
• -, which also matches 0 or more repetitions of characters in the class. Unlike '*', these repetition items will always match the shortest possible sequence;
• ?, which matches 0 or 1 occurrence of a character in the class;

I noticed that there's a greedy *, and a non-greedy - modifier. Since my middle string matcher:

(%d) (%s) (%s)

seems to be absorbing text until the end, perhaps i should try to make it non-greedy, by changing the * to a -:

oldPattern = "([%+%-]%d+) (.*)[ %(Reforged from .+%)]?"
newPattern = "([%+%-]%d+) (.-)[ %(Reforged from .+%)]?"

Except now it fail to match:

• value = +384
• stat = nil

Rather than the middle group capturing "any" character (i.e. .), I tried a set that contains everything except (:

pattern = "([%+%-]%d+) ([^%(]*)( %(Reforged from .+%))?"

and from there the wheels came off the wagon:

local pattern = "([%+%-]%d+) ([^%(]*)( %(Reforged from .+%))?"
local pattern = "([%+%-]%d+) ((^%()*)( %(Reforged from .+%))?"
local pattern = "([%+%-]%d+) (%a )+)[ %(Reforged from .+%)]?"

I thought that I was close with:

local pattern = "([%+%-]%d+) ([%a ]+)[ %(Reforged from .+%)]?"

which captures

- value = "+385"
- stat = "Critical Strike "  (notice the trailing space)

So this is where I bang my head against the pillow and go to sleep; I can't believe I've spent four hours on this regex....pattern.

---

@NicolBolas The set of all possible strings, defined using a pseudo-regular expression language, are:

+%d %s (Reforged from %s)

where

• + represents either the Plus Sign (+) or the "Minus Sign" (-)
• %d represents any latin digit character (e.g. 0..9)
• %s represents any latin uppercase or lowercase letters, or embedded spaces (e.g. A-Za-z)
• the remaining characters are literals.

If i had to write a regular expression that obviously tries to do what i want:

\+\-\d+ [\w\s]+( \(Reforged from [\w\s]+\))?

But I can give you near practically complete list of all values I'm likely to encounter in the wild if I didn't explain it well enough.

• +123 Parry positive number, single word
• +123 Critical Strike positive number, two words
• -123 Parry negative number, single word
• -123 Critical Strike negative number, two words
• +123 Parry (Reforged from Dodge) positive number, single word, optional suffix present with single word
• +123 Critical Strike (Reforged from Dodge) positive number, two words, optional suffix present with two words
• -123 Parry (Reforged from Hit Chance) negative number, single word, optional suffix present with two words
• -123 Critical Strike (Reforged from Hit Chance) negative number, two words, optional suffix present with two words

There are bonus patterns it would seem obvious that the patterns would also match:

• +1234 Critical Strike Chance four digit number, three words
• +12345 Mount and run speed increase five digit number, five words
• +123456 Mount and run speed increase six digit number, five words
• -1 MoUnT aNd RuN sPeEd InCrEaSe one digit number, five words
• -1 HiT (Reforged from CrItIcAl StRiKe ChAnCe) negative one digit number, one word, optional suffix present with 3 words

And while the ideal pattern should match the above bonus entries, it does not have to.

Localization

In reality all "numbers" i am attempting to parse out will be localized, e.g.:

• +123,456 in English (en-US)
• +123.456 in Germany (de-DE)
• +123'456 in French (fr-CA)
• +123 456 in Estonian (et-EE)
• +1,23,456 in Assamese (as-IN)

Any answer must not attempt to account for these localization issues. You do not know the locale a number will be presented from, that is why the number localization has been removed from the question. You must strictly assume that numbers contain plus sign, hyphen minus, and latin digits 0 through 9. I already know how to parse localized numbers. This question is about trying to match the optional suffix with a greedy pattern parser.

Edit: You really didn't have to try to handle localized number. At some level trying to handle them, without knowing the locale, is wrong. For example, I didn't include all possible localizations of numbers. For another: I don't know what future localizations might exist in the future.

Answer 1

Hmm I don't have Lua4 installed but this pattern works under Lua5. I would expect it to work for Lua4 as well.

Update 1: Since additional requirements have been specified (localization) I've adapted the pattern and the tests to reflect these.

Update 2: Updated the pattern and tests to deal with an additional class of text containing a number as mentioned by @IanBoyd in the comments. Added an explanation of the string pattern.

Update 3: Added variation for the case where the localized number is dealt with separately as mentioned in the last update to the question.

Try:

"(([%+%-][',%.%d%s]-[%d]+)%s*([%a]+[^%(^%)]+[%a]+)%s*(%(?[%a%s]*%)?))"

or (no attempt to validate number localization tokens) - just take anything which is not a letter with a digit sentinel at the end of the pattern:

"(([%+%-][^%a]-[%d]+)%s*([%a]+[^%(^%)]+[%a]+)%s*(%(?[%a%s]*%)?))"

Neither of the patterns above are meant to deal with numbers in scientific notation (e.g: 1.23e+10)

Lua5 test (Edited to clean up - tests getting cluttered):

function test(tab, pattern)
   for i,v in ipairs(tab) do
     local f1, f2, f3, f4 = v:match(pattern)
     print(string.format("Test{%d} - Whole:{%s}\nFirst:{%s}\nSecond:{%s}\nThird:{%s}\n",i, f1, f2, f3, f4))
   end
 end

 local pattern = "(([%+%-][',%.%d%s]-[%d]+)%s*([%a]+[^%(^%)]+[%a]+)%s*(%(?[%a%s]*%)?))"
 local testing = {"+123 Parry",
   "+123 Critical Strike",
   "-123 Parry",
   "-123 Critical Strike",
   "+123 Parry (Reforged from Dodge)",
   "+123 Critical Strike (Reforged from Dodge)",
   "-123 Parry (Reforged from Hit Chance)",
   "-123 Critical Strike (Reforged from Hit Chance)",
   "+122384    Critical    Strike      (Reforged from parry chance)",
   "+384 Critical Strike ",
   "+384Critical Strike (Reforged from parry chance)",
   "+1234 Critical Strike Chance (Reforged from CrItIcAl StRiKe ChAnCe)",
   "+12345 Mount and run speed increase (Reforged from CrItIcAl StRiKe ChAnCe)",
   "+123456 Mount and run speed increase (Reforged from CrItIcAl StRiKe ChAnCe)",
   "-1 MoUnT aNd RuN sPeEd InCrEaSe (Reforged from CrItIcAl StRiKe ChAnCe)",
   "-1 HiT (Reforged from CrItIcAl StRiKe ChAnCe)",
   "+123,456 +1234 Critical Strike Chance (Reforged from CrItIcAl StRiKe ChAnCe)",
   "+123.456 Critical Strike Chance (Reforged from CrItIcAl StRiKe ChAnCe)",
   "+123'456 Critical Strike Chance (Reforged from CrItIcAl StRiKe ChAnCe)",
   "+123 456 Critical Strike Chance (Reforged from CrItIcAl StRiKe ChAnCe)",
   "+1,23,456 Critical Strike Chance (Reforged from CrItIcAl StRiKe ChAnCe)",
   "+9 mana every 5 sec",
   "-9 mana every 20 min (Does not occurr in data but gets captured if there)"}
 test(testing, pattern)

Here's a breakdown of the pattern:

local explainPattern =  
   "(" -- start whole string capture
   ..
   --[[
   capture localized number with sign - 
   take at first as few digits and separators as you can 
   ensuring the capture ends with at least 1 digit
   (the last digit is our sentinel enforcing the boundary)]]
   "([%+%-][',%.%d%s]-[%d]+)" 
   ..
   --[[
   gobble as much space as you can]]
   "%s*"
   ..
   --[[
   capture start with letters, followed by anything which is not a bracket 
   ending with at least 1 letter]]
   "([%a]+[^%(^%)]+[%a]+)"
   ..
   --[[
   gobble as much space as you can]]
   "%s*"
   ..
   --[[
   capture an optional bracket
   followed by 0 or more letters and spaces
   ending with an optional bracket]]
   "(%(?[%a%s]*%)?)"
   .. 
   ")" -- end whole string capture

Answer 2

Why parse this in one pattern when you can use several?

First, get the number:

local num, rest = string.match(test_string, "([%+%-]?%d+)%S*(.+)")

Then make a table that enumerates the possibilities for the hit type.

local hitTypes =
{
  "Hit",
  "Critical Strike",
  -- Insert more.
}

Now, iterate over the list, testing against each one.

local hitIndex = nil
local reforge = nil

for i, htype in ipairs(hitTypes) do
  local final = string.match(rest, htype .. "%S*(.*)")
  if(final) then
    hitIndex = i
    reforge = string.match(final, "%(Reforged from (.+)%)")
  end
end

Lua patterns are limited, so it's best to use actual code to avoid their limitations.