1
$\begingroup$

Pattern matching in programming languages as for example in Racket is some kind of parsing. Which level in the Chomsky hierarchy does this parsing technique have? Is it type-3 like regular expressions or type-2 or even lower?

$\endgroup$

1 Answer 1

1
$\begingroup$

It depends on what types of patterns are supported. If it is only classical regular expressions, as in theoretical computer science, it is the regular languages. If it is Perl-compatible regular expressions (PCRE), then it is the context-sensitive languages; see Which languages do Perl-compatible regular expressions recognize?.

See also When is a regexp not a Regular Expression? and Expressiveness of modern regular expressions and How much more powerful are regexes in modern programming languages compared to regular expressions from the theory of computation? and What can be proven regarding the differences in power between unary ECMAScript regex functions and primitive recursive functions?.

$\endgroup$

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.