<p>All tokens in parsing source code must be unambiguous. Regular expressions are almost always used for lexing, but there is one problem in my mind.</p>
<p>Given the regex: <code>((abc){1,3})+</code>, and the string <span class="math-container">$(``abc")^5$</span>, there can be at least the 2 following ways to match:</p>
<ol>
<li>match the initial 3 repetitions of &quot;abc&quot; and leave 6 characters unparsed,</li>
<li>match the initial 4 repetitions of &quot;abc&quot; and leave 3 characters unparsed (where the inner repetation occurs 2 times and the outter one 2 time as well).</li>
</ol>
<p>Even worse, given the same regex and the string <span class="math-container">$(``abc")^{12}$</span>, there are multiple ways to match the entire string successfully.</p>
<p>Of course, such ambiguity is not allowed in real-world langauge compilers, as delimiting of sub-token boundaries may have significance in semantics. So the <strong>question</strong> goes: how to limit the grouping and repetition capability of regular expressions so that it's simple enough to always produce deterministically unambiguous tokens?</p>
<p><strong>Clarification</strong></p>
<p>In the above example, a non-existing flavor of regex is used, where repetition count in sub-expressions are fixed.</p>

<lexing><regex>
Lexing ambiguity with nested grouping repetition
CC BY-SA 4.0
2024-12-26T06:57:43.800Z
I don’t understand your example and by extension the problem. Every regex dialect (note: this is stronger than just implementation) that I am aware of has well-defined greediness, and for your example I am not aware of any ambiguity. `((abc){1,3})+` will match any non-zero repetition of `abc`. Even if you interpret `(…{1,3})+` to require matching `…` *the same choice* from `{1,3}` on *each repetition* from `+` this would be well-defined (though not matching any regex flavour I know).
MisterMiyagi
CC BY-SA 4.0
2024-12-26T07:33:01.893Z
@MisterMiyagi Yes, I used an non-existing flavor of regex where the choice of repetition count is fixed in the same subexpression. My concern is (quoting the Q), [ambiguity of] delimiting of sub-token boundaries. Michael has provided an answer, which I interpret as "grouping are ultimately expanded, thus vanish when represented in FSM".
DannyNiu
CC BY-SA 4.0
2024-12-26T07:45:25.820Z
It might help if you were to clarify the output of your hypothetical regex/lexer. Right now you only talk about *matches* which would just be a single string/range each. For example, a "match [of] the initial 4 repetitions of "abc" and leave 3 characters unparsed" would be the string `abcabcabcabc` or the range `0..12`. For groups to *possibly* matter for the result one would have to look at *capturing* groups.  However, neither scenario makes regex ambiguous or non-deterministic.
MisterMiyagi
CC BY-SA 4.0
2024-12-26T22:49:56.283Z
Why do you have spaces around your example strings?
Barmar
CC BY-SA 4.0
2024-12-26T23:13:37.320Z
@Barmar Because I need to use LaTeX to format the exponent. "Rested" should be "nested", I'll edit.
DannyNiu
<p>None of this matters for tokenisation. Groups in regular expressions are not real. Both the parenthesisation and the limited repetition syntax is just a shorthand for generating the (N)DFA. In this case, the minimal DFA you can produce from that is:
<a href="https://i.sstatic.net/MTWUZGpB.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/MTWUZGpB.png" alt="The DFA for the language in the question" /></a></p>
<p>which is exactly the language that would be created by <code>(abc)(abc)*</code>.</p>
<p>The groups within the expression as you wrote it are <em>not</em> part of tokenisation: <strong>if you need those groups to have meaning, what you have is a parsing problem, not a tokenisation problem</strong>, and you can apply all of the usual parsing techniques to get what you want. If the totality of the string is what matters, then it doesn't matter how you determine what matched, just that you get the correct string in the end.</p>
<hr />
<p>It is possible to produce this minimal automaton where it's obvious when to stop a few ways, most straightforwardly (but not efficiently) using the double-reverse approach: produce a DFA, reverse all the arrows to produce an NFA, convert that to a DFA, then do the same again. It isn't typical to do so because it's an expensive operation to perform and can result in exponential blowup of states, but if you need to make one then you can. However, none of this is necessary: the standard non-minimised DFA or NFA will already give you exactly the same matching power and accept exactly the same strings.</p>
<p>You can explore and reverse this expression interactively <a href="https://michael.homer.nz/Tools/Regex/#+reverse*((abc)%7B1,3%7D)+" rel="nofollow noreferrer">using this tool</a> to see that process in action. You'll see that the entire string is consumed regardless, and that's a successful match.</p>
<hr />
<p>When used for tokenisation, it is typical to follow the &quot;longest-token rule&quot; or &quot;<a href="https://en.wikipedia.org/wiki/Maximal_munch" rel="nofollow noreferrer">maximal munch</a>&quot; and always take the <em>longest</em> possible match at the tokenisation point. This is necessary even for simple cases: an &quot;identifier&quot; pattern <code>[a-z]+</code> would only match single characters otherwise, but presumably should take all of them. In the example above, this means looping until you reach the acceptor (double circle) state and cannot take the outgoing <code>a</code> edge from it because the next symbol is not an &quot;a&quot;. In an off-the-shelf regular expression engine, which you should probably be using, you want to opt into greedy matching if that's required for the engine you're using, but lexer systems typically do this automatically.</p>

CC BY-SA 4.0
2024-12-26T06:57:49.927Z
2024-12-26T07:05:00.967Z
2024-12-26T07:05:00.967Z
Michael Homer
CC BY-SA 4.0
2024-12-26T07:34:16.830Z
So is it correct say that grouping are expanded and vanish when compiled into FSM representation? In any common-place flavor of regex?
DannyNiu
CC BY-SA 4.0
2024-12-26T07:51:20.787Z
Yes, grouping has been erased (or at most, it's latent in the cycles of the NFA, e.g. [for that pattern](https://i.sstatic.net/pBDq71df.png)). There's just nothing to represent them there. Systems with backreferences can't throw them away like that, but those are not regular expressions and not part this question.
Michael Homer
CC BY-SA 4.0
2024-12-26T07:53:04.187Z
More to the point, though, they simply don't matter. If you accept the string, you accept the string, however you get to that point, and that's all that matters for lexing.
Michael Homer
# Lexing ambiguity with nested grouping repetition
Posted by: username_0 on 2024-12-26
All tokens in parsing source code must be unambiguous. Regular expressions are almost always used for lexing, but there is one problem in my mind.

Given the regex: `((abc){1,3})+`, and the string $(``abc")^5$, there can be at least the 2 following ways to match:

1. match the initial 3 repetitions of "abc" and leave 6 characters unparsed,
2. match the initial 4 repetitions of "abc" and leave 3 characters unparsed (where the inner repetation occurs 2 times and the outter one 2 time as well).

Even worse, given the same regex and the string $(``abc")^{12}$, there are multiple ways to match the entire string successfully.

Of course, such ambiguity is not allowed in real-world langauge compilers, as delimiting of sub-token boundaries may have significance in semantics. So the **question** goes: how to limit the grouping and repetition capability of regular expressions so that it's simple enough to always produce deterministically unambiguous tokens?

**Clarification**

In the above example, a non-existing flavor of regex is used, where repetition count in sub-expressions are fixed.
**Tags:** lexing regex
> **Comments:**
> **username_1**: I don’t understand your example and by extension the problem. Every regex dialect (note: this is stronger than just implementation) that I am aware of has well-defined greediness, and for your example I am not aware of any ambiguity. `((abc){1,3})+` will match any non-zero repetition of `abc`. Even if you interpret `(…{1,3})+` to require matching `…` *the same choice* from `{1,3}` on *each repetition* from `+` this would be well-defined (though not matching any regex flavour I know).  
> **username_0**: @MisterMiyagi Yes, I used an non-existing flavor of regex where the choice of repetition count is fixed in the same subexpression. My concern is (quoting the Q), [ambiguity of] delimiting of sub-token boundaries. Michael has provided an answer, which I interpret as "grouping are ultimately expanded, thus vanish when represented in FSM".  
> **username_1**: It might help if you were to clarify the output of your hypothetical regex/lexer. Right now you only talk about *matches* which would just be a single string/range each. For example, a "match [of] the initial 4 repetitions of "abc" and leave 3 characters unparsed" would be the string `abcabcabcabc` or the range `0..12`. For groups to *possibly* matter for the result one would have to look at *capturing* groups.  However, neither scenario makes regex ambiguous or non-deterministic.  
> **username_2**: Why do you have spaces around your example strings?  
> **username_0**: @Barmar Because I need to use LaTeX to format the exponent. "Rested" should be "nested", I'll edit.  
---
## 1 answers
### Answer by username_3 on 2024-12-26. Score: 3 | Accepted answer
None of this matters for tokenisation. Groups in regular expressions are not real. Both the parenthesisation and the limited repetition syntax is just a shorthand for generating the (N)DFA. In this case, the minimal DFA you can produce from that is:
[![The DFA for the language in the question](https://i.sstatic.net/MTWUZGpB.png)](https://i.sstatic.net/MTWUZGpB.png)

which is exactly the language that would be created by `(abc)(abc)*`.

The groups within the expression as you wrote it are *not* part of tokenisation: **if you need those groups to have meaning, what you have is a parsing problem, not a tokenisation problem**, and you can apply all of the usual parsing techniques to get what you want. If the totality of the string is what matters, then it doesn't matter how you determine what matched, just that you get the correct string in the end.

---

It is possible to produce this minimal automaton where it's obvious when to stop a few ways, most straightforwardly (but not efficiently) using the double-reverse approach: produce a DFA, reverse all the arrows to produce an NFA, convert that to a DFA, then do the same again. It isn't typical to do so because it's an expensive operation to perform and can result in exponential blowup of states, but if you need to make one then you can. However, none of this is necessary: the standard non-minimised DFA or NFA will already give you exactly the same matching power and accept exactly the same strings.

You can explore and reverse this expression interactively [using this tool](https://michael.homer.nz/Tools/Regex/#+reverse*((abc)%7B1,3%7D)+) to see that process in action. You'll see that the entire string is consumed regardless, and that's a successful match.

---

When used for tokenisation, it is typical to follow the "longest-token rule" or "[maximal munch](https://en.wikipedia.org/wiki/Maximal_munch)" and always take the *longest* possible match at the tokenisation point. This is necessary even for simple cases: an "identifier" pattern `[a-z]+` would only match single characters otherwise, but presumably should take all of them. In the example above, this means looping until you reach the acceptor (double circle) state and cannot take the outgoing `a` edge from it because the next symbol is not an "a". In an off-the-shelf regular expression engine, which you should probably be using, you want to opt into greedy matching if that's required for the engine you're using, but lexer systems typically do this automatically.
> **Comments:**
> **username_0** (2024-12-26): So is it correct say that grouping are expanded and vanish when compiled into FSM representation? In any common-place flavor of regex?  
> **username_3** (2024-12-26): Yes, grouping has been erased (or at most, it's latent in the cycles of the NFA, e.g. [for that pattern](https://i.sstatic.net/pBDq71df.png)). There's just nothing to represent them there. Systems with backreferences can't throw them away like that, but those are not regular expressions and not part this question.  
> **username_3** (2024-12-26): More to the point, though, they simply don't matter. If you accept the string, you accept the string, however you get to that point, and that's all that matters for lexing.  
---
