Wednesday, 13 February 2019

Variable-Length Lookbehinds: actually possible in Perl/PCRE!

Get strapped in, because this is as close as you're going to get to breaking news in the world of regular expressions.

You know what the best thing is about being involved in regex circles? It's not the money or the fame or the women.. no no; it's that, on occasion, you get to witness incredible discoveries unfold before your very eyes. This is exactly what happened in a small StackExchange chatroom earlier, when fellow regex tinkerer Grimy cracked a problem that previously seemed insoluble. In doing so, he uncovered a technique for emulating a feature that has been coveted for years by Perl and PCRE users alike: variable-length lookbehinds.

Now, forget \K. That doesn't come close to having the expressive power we want. I'm talking about truly emulating variable-length lookbehinds; that is, doing so for all conceivable scenarios.

The Revelation

In response to a challenge to match an arbitrary string (in the domain of ^.*$) that contains no unique characters, a task I once dismissed as impossible in the general case, Grimy ingeniously came up with the following:

Wonderfully elegant and simple in principle. Let us begin by examining the core concept.

The Concept

((?<=(?= ... |(?3)).))
The trick is to remember that, while lookbehinds can only peek a fixed number of characters behind the current matching point, the lookaheads they contain are not subject to any such restriction. If \1 is a single character, (?<=(?=\1).) succeeds where (?<=\1) fails because in the former case you are telling the regex engine that it needs to go back precisely one character to look for \1.

Because recursive algorithms are tricky to follow, let us expand this subexpression a couple of levels deep to observe what's happening:
((?<=(?= ... |(?<=(?= ... |(?<=(?= ... |(?3)).)).)).))
Notice how we're moving back one character each step of the way. So if (?= ... ) fails to match, move back one character and try again. Thus, it is equivalent in essence to using (?<=(?= ...).*) if actual variable-length lookbehinds were possible.

The Nanny

If you've read and understood everything so far, you may have thought to look back at Grimy's original expression to try and understand it in full. What, then, you ask, is the purpose of \n in the lookahead? After all, \n, which matches a new-line character, should not exist in the domain of ^.*$ since `.` does not match a new-line by default. So why is it there?

Regex engines often have a bunch of nannies in place to prevent you from hurting yourself. One of these employed by PCRE is a compile-time check for recursive calls that appear, from a cursory static inspection, as though they may not terminate. The simplest example of this is the expression (?R), which yields the compile-time error:
40  recursive call could loop indefinitely
With Grimy's expression, the PCRE engine doesn't realize that \2 is guaranteed to match a single character. To work around this, we need to give the engine at least one non-empty path to follow. \n is a contradiction in the domain of ^.*$ and, more importantly, it functions as a non-empty alternative that convinces the nanny that we know what we're doing.

Note that in the more general domain of ^[\s\S]*$, which may include new-line characters, x^ serves as a non-empty contradiction.

The Emulation

Perspicacious readers may have observed that the method above involves an unbounded lookahead, one that may peer far past the position at which we wish to place our emulated lookbehind. This is fine for the problem it aimed to solve, but if we want to expand the method to work in the general case, this issue needs to be addressed.

And so, for a variable-length subexpression X, (?<=X) can be implemented in both Perl and PCRE as:
See it in action on regex101

To negate it and emulate (?<!X), simply enclose the whole thing in a negative lookahead:
Aside from the fact that I've used two capturing groups, that snippet is basically plug-and-play: you may insert it anywhere in your expression where a variable-length lookbehind is desired.

The main difference here is that a new group "a" has been added to capture the portion of the string after the current matching point, so that when we travel backwards and look ahead for X we know where to stop. This solves the issue mentioned above.

Next, X has been moved to the outer group "b" as it would fail to match if X were zero-width since the lookahead only begins at the position one character behind the current matching point, and only moves backwards thereafter.

Here is a breakdown of the various components:
(?=(?'a'[\s\S]*))  # Capture the rest of the string in "a"
  X(?=\k'a'\z)     # Match X followed by the contents of "a" to ensure
                   # the emulated lookbehind stops at the correct point.
  |                # OR
  (?<=             # Look behind (one character) match either:
      x^           # A contradiction; non-empty to appease the nanny
      |            # OR
      (?&b)        # Recurse (match X OR look behind (one character)) etc..
    [\s\S]         # How far we go back each step: one single character

Note that by emulating a positive lookbehind in this way, you lose the luxury of having capture groups in X that return their values to the caller. But are you complaining?

The End

There you have it: another impossibility made possible by the creative application of old tools. I hope you enjoy using this new toy as much as I certainly will. Big shout out once again to Grimy for his stroke of genius.

As usual, I welcome you to follow me on twitter to stay apprised of more regex wackiness in the future.

The Bonus

What about problems that require comparing the substring at the current matching point to multiple substrings at later positions in the string - can we now handle those? Turns out we can! By iterating forwards with a lookahead and using our new toy to look back to the original matching point, we can make short work of any problem of that nature. For example, "match the longest word in a line" can now be solved in the general case:
Figuring out how that works is left as an exercise to the reader :) Suffice it to say, there is now a whole new set of problems for which we can irresponsibly abuse regex.


  1. I have to search sites with relevant information on given topic and provide them to teacher our opinion and the article.
    ExcelR digital marketing courses in mumbai

  2. Our service has been very supportive to our customers and especially in solving their problems and providing them with best boxes which are fully credible and worthy of their trust.
    Custom Boxes Wholesale,

    Paper Cigarette Boxes,

    Bath bomb packaging,

    Pre Roll Packaging,

    Cardboard Cigarette boxes,

    Blank Cigarette Boxes,

    custom burger boxes

    french fries boxes,

  3. keep up the good work. this is an Ossam post. This is to helpful, i have read here all post. i am impressed. thank you. this is our courses in data analytics
    courses in data analytics |

  4. In the present days a large number of candidates are showing interest towards the sarkari result 10+2 latest job. By applying for the various positions candidates are attending for the competitive exams conducting by the various government organizations

  5. Are you looking for data structure assignment help? Are
    you unable to find best experts? Perfect, you landed at
    the right page. “Assignment help website” is one of the
    oldest assignment help providers whose aim is to help
    students with quality and affordable data structure

  6. Ducat provides best java training institute in noida as per the current industry standards. Our training programs will enable professionals to secure placements in MNCs. We are providing our world-class training facilities for all the students who want to become professional java developer.

    1. Amazing Article. Candidates who are eager to get the FreeJobAlert . they can get the all information from this page. The Candidates have to visit our website Sarkari Result .
      Also Candidates Can Get Jobs in India Post Office Post Office Recruitment

  7. Really Very helpful Post & thanks for sharing & keep up the good work.
    Oflox Is The Best Digital Marketing Company In Dehradun Or Website Design Company In Dehradun

  8. Human emotions can be tricky. But It can't be tough to handle, One of those emotions is anger. Let me explain Extreme anger can affect your life in unthinkable ways. Do you have anger issues? If your answer is yes! Get help from MyFloridaGreen they offers medical marijuana card Sarasota , medical marijuana card Saint petersburg , Medical marijuana card naples.

  9. iCustomBoxes are exceptionally well known among blessing packaging products. These Pillow Boxes are extremely attractive in their standpoint and can fill the need of blessing Pillow Boxes packaging in a novel and smart manner. They can be redone as per prerequisites and can be printed with boundless brightening print styles.
    Custom Boxes

  10. This comment has been removed by the author.

  11. Thank you for your outstanding article. I will be your regular visitor. Are you experiencing difficulty in writing business analytics? Well, you don’t have to experience sleepless nights because of business analytics assignments. At our Business Management Assignment Help Service, we have experienced business analytics writers who can provide you with the much-needed help in writing your assignments. Visit Business Analytics Assignment Help. for more

  12. Download Garmin Express To Install & Manage Garmin Updates For all Garmin Devices With Easy Instruction by visiting

  13. Mywifiext Login, Follow the step by step guidelines for Login, account setup and configure your Netgear Extender to experience seamless connectivity.

  14. TurboTax Sign inTurboTax Login - Now you may Sign in to Your TurboTax Online account to start, continue, or amend a tax return, check the e-file and many more

  15. Rand Mcnally Dock Update Rand McNally is a world-leader in providing GPS based Navigation Devices. Its innovative product range covers the diverse needs of various users. These intuitive, user-friendly devices are designed to eliminate stressful navigation out of your travels. However,

  16. - For Office Setup and Activation go to and get started with activation and installation by entering product key.

  17. Garmin express - Register, update and sync your device with Garmin. Manage devices from your desktop. Garmin Express is a computer application.

  18. Magellan Gps Update Magellan Gps Update is a prominent portable GPS navigation consumer electronics company. To take the benefits of the Magellan GPS device, the users have to install and get the latest Magellan GPS updates. Through the GPS Magellan updates, the user can have an up-to-date version of the GPS device. In the year 1986, the company was established, and the Head Quarter is in San Dimas, California.

  19. Very Nice Tips. Currently, there is a national Lock down in Nigeria, Once the effect of COVID-19 has been cushion, JAmbites are expected to know that schools would start releasing their Post UTME Forms, so all students are advised to grab a free copy of Post UTME Past Questions and Answers on

  20. What do you comprehend by the importance of legitimate time the board in your life? Time shows you how to play out each undertaking in the best method to accomplish the chose objectives. At the point when you begin to chip away at any undertaking, you will have a few goals to seek after as its outcome. What's more, when you are thinking to achieve your scholarly errands, you will feel the requirement for an opportunity to complete it valuable. In the event that you need to spare your time and don't wish to compose your schoolwork, take the assistance of Assignment Helper and finish your work on schedule. Specialists of task composing administrations are limited to offer beneficial "Assignment Help In US" to support researchers and spare their time. You won't get any quality issues while getting your request from expert's hands.
    online coursework help
    online coursework writing
    coursework assignment help
    online coursework service
    coursework help online
    coursework writing service

  21. I high appreciate this post. It’s hard to find the good from the bad sometimes, but I think you’ve nailed it! would you mind updating your blog with more information?

    Private Tutor

    Online Tutoring Services UK

  22. Here are the list of best Advertising Agency Riyadh, Branding Agency Riyadh & Marketing Agency In Riyadh. Click and you can check the details from the word which you love to know.

  23. Thanks for Sharing this article, I really impress your work.
    custom book boxes

  24. Thanks for Sharing This Article.It is very so much valuable content. I hope these Commenting lists will help to my website
    servicenow online training
    best servicenow online training
    top servicenow online training

  25. Use Homework help to connect with American academic writers in just a few minutes. Students can take online homework writing services in America when they have no one to ask their queries and find it tough to write your academic papers.

  26. This is very useful website, this article is really helpful thank you so much for
    sharing this great knowledge Assignment Help

  27. Students seek our online assignment help from experienced and talented academic writers for their assignments to be completed within the allotted time frame and in accordance with the required standards. If you are stuck with your research projects, essays, case studies, business reports or need Urgent Assignment Help, then MyAssignmentHelp is the place to be.

  28. Computer Assignment writing is the task which frequently gives students a tension. If you are going through from the same. Then in such situation, you can choose our computer network assignment help service and can get a quality assignment written from us.

  29. wonderful article. Very interesting to read this article.I would like to thank you for the efforts you had made for writing this awesome article. This article resolved my all queries. keep it up.
    data analytics course in Bangalore

  30. Really nice and interesting post. I was looking for this kind of information and enjoyed reading this one. Keep posting. Thanks for sharing.....bangalore digital marketing course

  31. Our service has been very supportive to our customers and especially in solving their problems and providing them with best Pre Roll Packaging which are fully credible and worthy of their trust.

  32. Australian Assignment Help is best in providing cheap assignment help in Australia to students and Student Life Saviour delivers quality assignment help in Ireland to students at reasonable prices.

  33. wonderful article. Very interesting to read this article.I would like to thank you for the efforts you had made for writing this awesome article. This article resolved my all queries.
    Data Science Course

  34. I have to search sites with relevant information on given topic and provide them to teacher our opinion and the article.
    Examination Past Questions and Answers.

  35. This is a great post. Your Blog the very informative, I have learned some information about your blog. Android app development company USA.

  36. I am looking for and I love to post a comment that "The content of your post is awesome" Great work!

    Simple Linear Regression

    Correlation vs Covariance

  37. You have mastered the art of writing. Thank you for sharing. The best nursing essay writers are often difficult to track down. The reason such writers are hard to find is that they don’t always hang out where you think they should. That is, the best nursing essay writers aren’t always working with the biggest dog in the academic writing world. Often times, such uniquely talented writers choose to work alone as freelancers. Or, they may prefer to work with a medium-sized company like us — a community that feels like family. Read more on Best Nursing Essay Writers .

  38. Very interesting to read this article.I would like to thank you for the efforts you had made for writing this awesome article. This article inspired me to read more. keep it up.
    Correlation vs Covariance
    Simple linear regression

  39. Thanks for sharing useful information with us.. It really helpful to me..I always prefer to read the quality content and this thing I found in you post. thanks for sharing with us..



  40. You can reach us at-
    Oz Paper Help

  41. Attractive post. I enjoy your weblog and wanted to say that I have liked browsing your blog posts. After all, I will surely subscribe to your feed, and I hope you will write again soon!

    English Tutors UK

  42. Wow, I can say that this is another great article as expected of this blog. Thanks a million and please keep up the effective work.
    Visit us for online back to back ID cards printing with matt finished.

  43. Bluestacks is one of the best Android emulators utilized by many Android users to operate Android games and social media applications like PUBG and Snapchat on their device. But most users complained about the Snapchat & Bluestacks, not working problem error. So, if you are facing the same issue, then follow this article.

    Best Iphone games

  44. To establish a network by putting towers in a region we can use the clustering technique to find those tower locations which will ensure that all the users receive optimum signal strength.
    Data Science Course in Bangalore

  45. Thank you for such an informative article. I have bookmarked your site for regular checkup. It is not possible to successfully complete pursuing a certain course without doing assignments at one point or the other. Assignments assume different formats and they are used to test the extent to which a certain student has grasped the content that he/she has been taught. Read more on Capstone Project Writers

  46. Very interesting to read this article.I would like to thank you for the efforts you had made for writing this awesome article. This article inspired me to read more. keep it up.
    Correlation vs Covariance
    Simple linear regression
    data science interview questions

  47. Cool stuff you have and you keep overhaul every one of us

    data science interview questions

  48. literaturereviewcentre is an online platform dedicated to serve you with high-quality assignment solutions. It is because of our substantial work ethics, our team of writers adhere to your four types of cardiovascular shock assignment deadlines and provide you flawless and instant assignment help. Also, we truly know the value of marks associated with your college assignments, therefore, we make sure to give you genuine assignment help which ascertains.

  49. I’ve viewed some different blog posts with regards to this topic, and I must state that yours shows the most insight. Thanks a lot for expressing your opinions with everyone here!

    Home Tutors

  50. A very high level post with a knowledgeable information .thanks you for giving me such a nice information. |
    downlaod alexa app for window PC 7,8,10 | |