2
$\begingroup$

Real-world regexs are extensions of regular expressions in formal languages.

Do lookahead and lookbehind come from some type of formal languages? (I suspected lookahead in LR(k) grammars, simply because of the same name, but I have difficulty to either confirm or unconfirm it. Not sure about lookbehind.)

Btw: I have been interested in which extensions in regexes come from which types of formal languages. Do you know somethings for me to read?

Thanks.

$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

No, they are pragmatic hacks based on features found to be useful by programmers and implementable by library maintainers.

Most aspects of programming libraries follow this paradigm. The theory is important, and it probably could be used better. But it's s very rare for someone to decide to omit a useful feature just because it is not part of a theoretical framework.

Just to be clear, lookahead assertions in regex libraries have nothing to do with parser lookaheads, except that both represent answers to the question "What comes next?" (but not in the same problem domain).

$\endgroup$
4
  • $\begingroup$ Thanks. Does " lookahead assertions in regex " have no explanation in formal languages: within regular expressions, or in a broader type of formal languages? $\endgroup$
    – Tim
    Jun 22, 2020 at 21:31
  • $\begingroup$ @Tim. None whatsoever. Of course, nothing stops you from trying to construct a parsing theory in which things like that are primitives. But it has proven to be difficult and not very useful. And it wouldn't be an "explanation". The explanation is that real-life programmers find these facilities useful to solve real-life programming problems. What you might find is a parsing mechanism which makes these features more efficient, or at least allows you to limit the damage. But in practice, it doesn't seem to matter much. $\endgroup$
    – rici
    Jun 22, 2020 at 21:59
  • $\begingroup$ Could you elaborate "except that both represent answers to the question "What comes next?" (but not in the same problem domain)"? $\endgroup$
    – Tim
    Jun 24, 2020 at 2:01
  • $\begingroup$ @tim: it was kind of a joke. The two things have similar namesbevause they both refer to looking at the road ahead of you. But that's where the similarity ends; the algorithms being used are different and the application of the information is different. A windshield is not the same as a pair of binoculars although you look through both of them to see what's ahead. One was not inspired by the other; "look at what's coming" is the sort of step which crops up naturally in many algorithms. $\endgroup$
    – rici
    Jun 24, 2020 at 15:29
0
$\begingroup$

The theoretical framework for regular expression matching is about recognising complete strings in a language defined by a regular expression. What you generally need in practice is either (1) the ability to split up a long string into substrings that match one of several regular expressions or (2) the ability to search in a string for a substring that matches one regular expression.

In both cases (1) and (2), the actual problem is a bit different from the more general problem of recognising strings in the language defined by a regular expression. And in both cases there are some technical details that need to be tied down to make the problem well-specified. E.g., in case (2), there can be multiple matches: which one do we choose? It is also useful to give the user extra control over how the matching is done: e.g., by supplying some contextual constraints for the substring to be matched as in the "lookahead" and "lookbehind" constructs that you are asking about.

The theoretical framework is very important for our understanding of the practical problems and their solutions. I think you will find that the usual regex libraries follow the theory quite closely for their core matching algorithms with a few pragmatic additions to handle thinks like contextual constraints and counting constraints.

$\endgroup$
7
  • $\begingroup$ It's well-known that a regular expression (in the mathematical model) can be recognised in time linear to the string being scanned, while "regexes" provided by real-world regex libraries suffer from exponential blowup on pathological patterns (and some of the pathological patterns are pretty easy to write by accident). That's a hint that the "pragmatic additions" are not so trivial. With a few exceptions -- parser generators based on lex, which do not implement most common extensions -- and Russ Cox's excellent re2 library, which works hard to divide patterns into... $\endgroup$
    – rici
    Jun 22, 2020 at 22:56
  • $\begingroup$ ...those for which the DFA algorithm is useful and those which require some form of backtracking (for example, back-references), most regex libraries care little for the theory. Certainly, some parts of the theory are present, but the core matching algorithms are usually NFAs with backtracking (and other pragmatic techniques, like state caches). (That's not intended to be a criticism, and of course it's very useful to understand the theory.) $\endgroup$
    – rici
    Jun 22, 2020 at 22:59
  • $\begingroup$ @rici: this is not intended to be a criticism either, but the regex libraries in the real world don't (directly) offer the functionality to solve the problem "recognise a string that matches a regular expression" that is the subject of the theoretical framework. That was the point of my answer. The ANSI-C regex functions provide the facility to find the first (and then longest) substring that matches in a string. Some implementations render this hopelessly inefficient by calculating the length of the string on each call even for very simple regular expressions.. $\endgroup$
    – Rob Arthan
    Jun 25, 2020 at 22:17
  • $\begingroup$ Most regex libraries will solve the string recognition problem directly if you enclose the regular expression between ^ and $; some provide other mechanisms as well. But that's not their prime purpose nor their most common use case, although it's certainly a use case. But I certainly agree with your point; the only part of your very reasonable answer which troubled me was the assertion that most libraries "follow the theory quite closely". $\endgroup$
    – rici
    Jun 25, 2020 at 22:33
  • $\begingroup$ @rici: not if the pattern has new lines in it. What I meant about the implementations is that they do produce the DFAs that the theory would produce for patterns that don't involve counting or contextual constraints. $\endgroup$
    – Rob Arthan
    Jun 25, 2020 at 22:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .