# Nested Backreferences #xe5 tests greediness

**URL:** <https://forum.codecrafters.io/t/nested-backreferences-xe5-tests-greediness/2042>\
**Category:** Feature Requests\
**Tags:** challenge:grep\
**Created:** [September 28, 2024, 5:05pm UTC](https://forum.codecrafters.io/t/nested-backreferences-xe5-tests-greediness/2042 "2024-09-28T17:05:18Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![Gamma120](https://yyz1.discourse-cdn.com/flex003/user_avatar/forum.codecrafters.io/gamma120/32/1999_2.png) [@Gamma120](https://forum.codecrafters.io/u/Gamma120)\
**Post date:** [September 28, 2024, 5:05pm UTC](https://forum.codecrafters.io/t/nested-backreferences-xe5-tests-greediness/2042/1 "2024-09-28T17:05:18Z")

</div>

Hello,  
The last stage of the backreferences extension (#xe5) has a case that test greediness:

```auto
echo -n "abc-def is abc-def, not efg, abc, or def" | ./your_program.sh -E "(([abc]+)-([def]+)) is \1, not ([^xyz]+), \2, or \3"

```

`([^xyz]+)` matches the rest of the string `efg...`. To pass the test, you need to take into account greediness and backtracking. This behavior is never tested before. I think this is not a good way to introduce it and would be better in a separated extension.

---

<div class="post-metadata">

**Author:** ![andy1li](https://yyz1.discourse-cdn.com/flex003/user_avatar/forum.codecrafters.io/andy1li/32/10_2.png) [@andy1li](https://forum.codecrafters.io/u/andy1li)\
**Post date:** [October 4, 2024, 1:16am UTC](https://forum.codecrafters.io/t/nested-backreferences-xe5-tests-greediness/2042/2 "2024-10-04T01:16:55Z")

</div>

Thanks @Gamma120 for highlighting this! I’ve shared your feedback with our team, and added an internal +1 for your vote on a new extension.

In the meantime, feel free to personally [vote on a new extension](https://app.codecrafters.io/vote/challenge-extension-ideas?course=grep).

---

<div class="post-metadata">

**Author:** ![pr0g](https://yyz1.discourse-cdn.com/flex003/user_avatar/forum.codecrafters.io/pr0g/32/18738_2.png) [@pr0g](https://forum.codecrafters.io/u/pr0g)\
**Post date:** [January 25, 2026, 2:48pm UTC](https://forum.codecrafters.io/t/nested-backreferences-xe5-tests-greediness/2042/3 "2026-01-25T14:48:12Z")

</div>

I wound up hitting this particular challenge and have got pretty stuck 😖 I have a horrible feeling how I’ve implemented things just won’t handle this nested case of greediness/backtracking 🙈

Before starting this overall challenge, I hadn’t really read up on how regex parsers are implemented ‘properly’ 😅 For this problem is there any recommended reading to help better understand the optimal approach?

The problem I have is the nested pattern will match greedily, but isn’t able to backtrack before updating the matched capture group, so with this case…

text: `not efg, abc, or def`

pattern: `not ([^xyz]+),`

My implementation matches `efg, abc, or def`, instead of `efg`, so the overall match fails instead of succeeding.