8
$\begingroup$

We know that regular expressions (RE) are implemented with finite automata (FA). In some language (like JavaScript) in RE there are features like 'capturing parenthesis' with 'backreferences':

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Regular_Expressions#special-capturing-parentheses

(x) Matches 'x' and remembers the match, as the following example shows. The parentheses are called capturing parentheses. The '(foo)' and '(bar)' in the pattern /(foo) (bar) \1 \2/ match and remember the first two words in the string "foo bar foo bar". The \1 and \2 in the pattern match the string's last two words.

I want to know if this pattern /(foo) (bar) \1 \2/ is in fact a RE according the definition of RE that we have in theoretical formal language or it is something more powerful. And if it is so I would like to know if this kind of feature is implemented also with FA or in another way (in particualr how it is implemented).

Improve this question
$\endgroup$
2

4 Answers 4

Reset to default
8
$\begingroup$

The RE in the Automata Theory are equivalent to FA, but for the programming languages (regexp) this is no longer true.

The regular expressions in the programming languages (like PCRE) are far more powerfull than Regular Expressions (type 3) in the Automata Theory.

The matching parenthesis is neither regular nor context-free, it is a context-sensitive feature. But the RegExp from the question does not fully support Type 2 or Type 1.

The bracket matching is not implemented via FA. In case of PCRE it is implemented by guessing and backtracking.

Take a look at Perl Monks description about PCRE.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you. Then, in this case, RegExp is an abuse of (formal) language. $\endgroup$
    – asv
    Jan 23, 2017 at 21:31
  • 5
    $\begingroup$ Well, it is the name collision. The very initial idea was something like RE, but even when it evolved, the name remained. $\endgroup$
    – Evil
    Jan 23, 2017 at 21:35
  • 1
    $\begingroup$ @asv: For some time after capturing was introduced the RE with capture groups was called extended regexp or ERE. Then for some time after Perl introduced their version of RE it was called regex to differentiate it from POSIX standardised regexp and ERE (note regex vs regexp). These days people don't care. $\endgroup$
    – slebetman
    Jan 24, 2017 at 3:27
9
$\begingroup$

These extended notions of regular expressions capture more than just the regular languages. For example, ([ab]*)\1 matches the language $\{ww\mid w\in\{a,b\}^*\}$, which isn't regular and isn't even context-free (Example 2.38 of Sipser, Introduction to the Theory of Computation, 3rd edition).

"Regular" expressions that don't match regular langauges can't be translated to finite automata, since finite automata match only the regular languages. A side-effect of this is that many libraries don't even try to compile to automata, which can lead to extremely slow matching, even when a "regular" expression is a true regular expression. Russ Cox wrote an excellent article about this, which goes into a lot of the history, too.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you for your example and for these informations. :) $\endgroup$
    – asv
    Jan 23, 2017 at 23:41
8
$\begingroup$

The answers are probably answering what you're intending to ask, but not what you're asking.

I want to know if this pattern /(foo) (bar) \1 \2/ is in fact a RE according the definition of RE that we have in theoretical formal language or it is something more powerful. And if it is so I would like to know if this kind of feature is implemented also with FA or in another way (in particualr how it is implemented).

In fact this is a regular expression that can be implemented with a finite automaton, because \1 is guaranteed to evaluate to foo and \2 is guaranteed to evaluate to bar.

Therefore a regex engine could use this fact to actually create a finite automaton that exactly describes the language you proposed.

However, if you make any captures conditional, then this may become false, as others have mentioned.

(Note that I say you may have trouble, because a language like /(a(aa|aa)|(aa|aa)a)\1\2/ can still be described via a FA. I only gave you a necessary condition, not a sufficient one. Edit: It just occurred to me that having a conditional is neither necessary nor sufficient, as /(a*)\1/ can also be turned into a finite automaton whereas /(ab*)\1/ cannot. So I guess it was just a rule of thumb.)

Improve this answer
$\endgroup$
3
  • $\begingroup$ Ok some particual pattern with 'capturing parenthesis' can be RE. Good observation. $\endgroup$
    – asv
    Jan 24, 2017 at 11:49
  • $\begingroup$ @asv: Yup. Also, I think another thing that is misleading about all answers here (including mine) is that the problem isn't the capturing parentheses themselves, but the backreferences that refer to them. I remember reading that capturing parentheses can be handled without backtracking as long as there are no backreferences. However, I don't know the details behind whether this can be really done using finite automata or not (my impression is it can, but I don't exactly know how). But there should be other ways to handle them without backtracking, such as via LR parsing or something like that. $\endgroup$
    – user541686
    Jan 24, 2017 at 11:59
  • $\begingroup$ Yes, the question is: backreferences $\endgroup$
    – asv
    Mar 8, 2018 at 22:03
0
$\begingroup$

Certain regex implementation does not build a DFA. For example, java.util.regex OpenJDK implementation does not. As a result, its matching time is slower than DFA compiled implementation like dk.brics.automaton. Yet the later does not support capturing group as a result of underlying implementation.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Remember that NFA->DFA construction can be very expensive (2^#nodes). $\endgroup$
    – mevets
    Dec 17, 2018 at 7:13
  • $\begingroup$ Oh yes, thank you for pointing that out. I've updated my answer to reflect that only matching time of DFA based impl is shorter. $\endgroup$
    – vuamitom
    Dec 17, 2018 at 7:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.