Hacker News Reader

Comment by nsajko | Hacker News Reader

Note that this "regex", unlike the ones in the article, is not actually a regular expression. You could perhaps call it an irregular expression. There can be no such thing as a backreference in a regular expression.

More info: https://swtch.com/~rsc/regexp/regexp1.html

View on HN

I think you’re confusing “regular expression” (RE) for “deterministic finite-state automata” (DFA).

“Regular Expression” is just the name for the grammar/formal language model that REs present. REs are a useful way to encode DFAs, but not all things that can be expressed using RE formal-language are DFAs.

Some REs (i.e. the “Perl-compatible” or “extended” Regular Expressions) are Nondeterministic Finite-state Automata or “NFAs”. This doesn’t change the fact that the language used to express them makes them Regular Expressions.

> I think you’re confusing “regular expression” (RE) for “deterministic finite-state automata” (DFA).

I think it's about descriptivism vs prescriptivism. "Regular expression" did start life with a technical meaning, according to which REs had equivalent expressive power to DFAs. The term has since been appropriated and diluted by other languages, and it is not entirely unreasonable to (though I prefer not to) take "regular expression" to mean "whatever programming languages present as regular expression"; but I think it's not quite right to say that someone is confused who believes in maintaining the original distinction.

I agree with you (obviously), but I'm not sure we should invoke "descriptivism vs prescriptivism" here. As far as I understand that distinction is mostly applicable to English (or other natural language) teaching, which is usually quite prescriptive, but should also have varying descriptive elements. And to dictionaries, which are(?) mostly descriptive (even when that means listing two conflicting definitions for a single word), but have to make some prescriptive editing decisions.

When it comes to actual semantic issues like this one, I think that invoking "p vs d" just muddies the waters, because such issues should be examined on a case-by-case basis.

This issue specifically is quite akin to the "literally" case: different instances of usage of the same phrase have (almost) opposite meanings:

See https://en.wiktionary.org/wiki/literally and https://en.wikipedia.org/wiki/Chomsky_hierarchy

I think it's fair to say the Perl-style semantics are just wrong, because there's no way to use them without being confusing.

The term "Regular Expression" is very often misused, it had a very well defined meaning in the field of formal language theory, but like most terms when barrowed by another field some of that meaning is lost or transformed. Some documentation has shifted to using terms like "pattern" or "pattern matching expression" to convey the meaning without the baggage.

> Some REs (i.e. the “Perl-compatible” or “extended” Regular Expressions) are Nondeterministic Finite-state Automata or “NFAs”.

That those engines are implemented using an NFA or a DFA does not actually matter for the question of being regular or not. A given pattern may be Regular while another may not be. There are multiple technical reasons these engines are built on NFA's and not DFA's, supporting non-regular expressions is one, but not the only, reason.

Ironically the library called "PCRE" or "Perl-compatible Regular Expressions" is in-fact not "Perl-compatible" (nor regular). It is at the same time both named "Perl-compatible" and absolutely not Perl-compatible. Both PCRE library and the Perl language have evolved and added mutually incompatible features which results in a valid PCRE matching expression failing to compile in Perl and a valid Perl matching expression failing to compile in PCRE. Just because that is the name doesn't make it true.

Regular expressions, deterministic finite automata, and nondeterministic finite automata are all equivalent[0][1].

All three of these representations are capable of describing any regular language (set of symbol sequences, or more intuitively a set of strings), and the fact that a language can be described by an NFA, DFA, or RE implies that it is regular.

I am not hugely familiar with Pearl's "extended regular expression" system, however I was under the understanding that the set of languages it can recognize is a superset of the set of all regular languages. Based on [2], it would appear that Perl regexes can recognize all regular languages, and parts of the set of all Turing-recognizable languages.

0 - Introduction to the Theory of Computation 3/e, Michael Sipser, Thm 1.39, pp. 55.

1 - Introduction to the Theory of Computation 3/e, Michael Sipser, Thm 1.54, pp. 67.

2- https://www.perlmonks.org/?node_id=809842

FWIW the equivalence between NFA and DFA requires an exponential space increase to encode the NFA as a DFA, with an exponential space blow up you can encode a lot of things as DFAs (I'm pretty sure you could encode a Turing machine that uses bounded space on the tape as a DFA with exponentially more space, "just" make each possible configuration one state in the DFA)

Reply on news.ycombinator.com