As expressões regulares são uma linguagem de programação?

No sentido acadêmico, as expressões regulares se qualificam como uma linguagem de programação?

A motivação para a minha curiosidade é uma pergunta SO que acabei de analisar e que perguntou "pode ​​regex fazer X?" e isso me fez pensar no que pode ser dito no sentido genérico sobre as possíveis soluções para usá-los.

_{Estou basicamente perguntando: "As expressões regulares Turing estão completas"?}

Expressões regulares são um tipo específico de gramática formal usada para analisar seqüências de caracteres e outras informações textuais conhecidas como "Linguagens regulares" na teoria formal da linguagem. Eles não são uma linguagem de programação como tal. Eles são mais uma forma abreviada de codificação que, de outra forma, seria extremamente tediosa de implementar e ainda mais confusa do que o Regex, às vezes misterioso.

Os idiomas de programação são normalmente definidos como idiomas que são Turing Complete . Essas linguagens devem ser capazes de processar qualquer função computável . O Regex não se encaixa nessa categoria.

Se você deseja um idioma parecido com o Regex, tente J.

É difícil responder a perguntas do tipo "é X a Y ", se os participantes do uso debate diferentes definições de X e Y . Pode ser que, para algumas definições, a resposta seja "sim" e, para algumas definições, a resposta seja "não". Especialmente se a resposta depender de detalhes técnicos, onde as diferentes definições diferem. Além disso, esta discussão contém algumas informações erradas; portanto, tenha paciência com uma resposta mais longa.

O que queremos dizer com " linguagem de programação "?

Uma resposta simples pode ser "uma linguagem usada para criar programas". Claro, mas: que tipo de programas? E uma linguagem que poderia ser usada para criar alguns tipos de programas, mas não outros? Aqui estão dois exemplos específicos para ilustrar os casos extremos:

1) Uma linguagem imaginária chamada M funciona assim: Se o programa contiver a única letra "m", ele criará um jogo de caça-minas. Tudo o resto é um erro de sintaxe.

Intuitivamente, não é isso que queremos dizer com "uma linguagem de programação". Mas o departamento de marketing da M poderia argumentar que tecnicamente cumpre a definição, porque pode ser usado para criar um programa. Claro, o compilador faz algumas partes críticas para você, mas é isso que os compiladores fazem, não é? Um compilador da linguagem C também traduz algumas palavras simples em dezenas de instruções do processador. O compilador M apenas vai além e torna seu trabalho ainda mais simples.

2) Se você instalar a versão original do famoso Turbo Pascal, poderá escrever vários tipos de programas. Mas você não pode escrever um jogo que roda no navegador da Web, porque a API necessária simplesmente não existe.

Então, o que exatamente faz do Turbo Pascal uma linguagem de programação, mas o M não possui? Simplesmente falando, você pode fazer mais em Pascal do que em M. Mas imagine que tenhamos um M.NET, que cria um jogo do Campo Minado rodando em um navegador da web. Então agora temos algo que Pascal pode fazer e o M.NET não pode, mas também temos algo que o M.NET pode fazer e Pascal não. Por que devemos considerar importantes as vantagens de Pascal e irrelevantes as vantagens da M.NET?

A resposta é que você pode escrever todos os tipos de algoritmos em Pascal, mas não pode escrever algoritmos em M ou M.NET. Claro, M compila seu comando "m" e C compila seu comando "strcmp". Mas você pode colocar "strcmp" em um contexto maior, por exemplo, comparar dois arquivos linha por linha, ou ler milhares de strings e classificá-las em ordem alfabética, ou ... bem, milhões de outras coisas. E é precisamente essa capacidade de usar determinados comandos em qualquer algoritmo que faz a essência de uma linguagem de programação.

O que exatamente é um algoritmo e, mais importante, o que é "qualquer algoritmo"? Em ciência da computação, usamos as palavras Turing-complete . A idéia é que exista um conjunto de linguagens de computador, onde cada uma delas possa simular todas elas. Uma dessas línguas é a máquina de Turing, e é por isso que elas são chamadas assim. Pascal está lá, C está lá, Java está lá, Python está lá, Lisp está lá, Smalltalk está lá, até XSLT está lá. Nosso hipotético M e M.NET não estão lá. Você pode aprender mais sobre isso em qualquer universidade que oferece um curso decente de ciência da computação, mas a idéia é que uma linguagem completa de Turing possa fazer qualquer coisaque outra linguagem completa de Turing pode fazer, se você fornecer a API mínima necessária. (Se você der uma API do navegador da Web para Pascal, poderá criar todos os tipos de jogos no navegador da Web. Se você fornecer a API do navegador da Web para M, ainda poderá criar o Minesweeper.) Poderíamos dizer metaforicamente que se você remove todas as APIs de uma linguagem de programação, o importante é o que resta.

O que queremos dizer com " expressões regulares "?

Diferentes linguagens de programação as implementam de maneira um pouco diferente. Mas a ideia original era que expressões regulares expressassem as chamadas linguagens regulares . Observe que não falamos sobre linguagens de programação aqui, mas sobre linguagens (pseudo-) humanas. Imagine que você encontre uma tribo exótica falando um idioma que consiste apenas nas palavras "ba", "baba", "bababa" e assim por diante. Você pode descrever esse idioma verbalmente como "uma sílaba 'ba' repetida uma ou mais vezes" ou usando uma expressão regular como "(ba) +".

As expressões regulares devem expressar: "nada", "esta carta", "isto, seguido por isso", "isto ou aquilo", "isto, repetido uma ou mais vezes" e "não isso". - Essa é a definição matemática . Qualquer outra coisa é apenas um atalho conveniente criado a partir dos componentes anteriores. Por exemplo "isto, repetido duas ou três vezes" pode ser traduzido como "isto, seguido por isto, seguido por (isto ou nada)", mas poderia ser mais conveniente escrever "ba {2,3}" do que "baba (BA)?".

Na vida real, uma implementação típica de "expressões regulares" implementa mais do que isso. Por exemplo, usando a definição matemática, uma linguagem de "aba", "aabaa", "aaabaaa" e assim por diante - qualquer número de "a" s, seguido de "b", seguido pelo mesmo número de "a "s - não é um idioma comum. No entanto, muitas "expressões regulares" usadas hoje podem detectá-lo, usando o conceito adicional de "a mesma coisa que encontramos anteriormente", escrito como "(a +) b \ 1". Usando esse conceito adicional, podemos fazer algumas coisas legais, por exemplo, detectar palavras que consistem em número primo de letras. Ainda assim, não podemos fazer nenhum algoritmo ... para uma explicação de por que,

Então, voltando ao tópico original: as expressões regulares (definidas como: expressões que descrevem linguagens regulares na hierarquia de Chomsky; ou como: a primeira, mais a operação \ 1) são uma linguagem de programação (definida como: Turing-complete)? A resposta é não . Não, você não pode implementar nenhum algoritmo usando expressões regulares, e a capacidade de implementar qualquer algoritmo é o que as pessoas que estudam ciência da computação geralmente entendem como a essência da linguagem de programação.

Obviamente, qualquer pessoa pode mudar a resposta insistindo em uma definição diferente . Como escrevi no começo, os detalhes técnicos são importantes aqui. Se você errar, você recebe uma resposta errada.

E se você não estiver interessado em detalhes técnicos, a resposta pode ser: Você pode usar expressões regulares (e nada mais) para criar um programa? Não. Então, por que chamá-lo de linguagem de programação? (No entanto, uma resposta como essa foi baixada e excluída aqui, e é por isso que escrevi esta versão mais longa.)

EDIT: Além disso, qualquer pessoa pode criar uma biblioteca implementando sua própria nova variante de "expressões regulares" com alguns novos recursos adicionados. Em algum momento, os novos recursos podem ser suficientes para que todo o sistema se torne completo em Turing. Um exemplo trivial seria incorporar uma linguagem completa de Turing usando alguma nova sintaxe; mas também pode acontecer menos obviamente. Talvez isso já tenha acontecido.

No .Net, o Regex não apenas pode lidar com várias formas de condicionais, usando diferentes combinações de alternância e lookarounds, mas também pode manipular sua própria pilha.

(?xm)
    (?>
        <(?<Tagname>table)[^>]*>
    )
(?(Tagname)
    (
        </(?(?!\k'Tagname')(?<-Tagname>))*\k'Tagname'>(?<-Tagname>)
    |
        (?>
            <(?<Tagname>[a-z][^\s>]*)[^>]*>
        )
    |
        [^<]+
    )+?
    (?(Tagname)(?!))
)

Este, por exemplo, é um pequeno trecho que escrevi para recuperar uma tabela HTML. Diferente de outros mecanismos de regex, isso controla a pilha de coleções de captura (push, peek e pop) e pode manipular objetos aninhados. Eu tenho um mais complexo, mas é meio proprietário.

Penso que neste exemplo, o Regex pode ser visto como tendo todos os requisitos básicos de uma linguagem de programação. Possui variáveis, memória embutida, condicionais, entrada e saída, compila usando um dos vários mecanismos de compilação regex (.Net neste caso).

Em resposta ao uso excessivo de squawking para (NUNCA) Parse HTML com Regex, fui adiante e publiquei uma resposta pré-digitada que posso postar: Analisando HTML

Um exemplo de Anoter (apenas uma demonstração) é o seguinte:

Function Regex("<(td>)((?:[^<]*(?(?!</\1)<))*)</\1")
    Group(0) = "<"
    Group(1) = "td>"
    Group(0) += Group(1)
    Group(2) = LoopMethod()
    Group(0) += Group(2)
    Group(0) += "</" & Group(1)
    Return Group()
End Function

Function LoopMethod()
    retGroup = ""
    Do
        tmpGroup = Everything that is NOT an Opening HTML Delimeter
        If the Text following tmpGroup Does NOT Equal "</" & Group(1) Then
            tmpGroup += "<"
            retGroup += tmpGroup
        Else
            Exit Do
        End If
    Loop
    Return retGroup
End Function

Novamente, para os papagaios em HTML: Analisando HTML

Isso mostra um regex mais simples executando loops e condicionais (algoritmos?). A única coisa que falta é o cálculo matemático real. Esta é uma expressão regular mais detalhada que apenas extrai uma célula TD com mais eficiência do que o método "(. *?)" Típico.

Mas, mesmo como um entusiasta do Regex e um mestre autoproclamado, eu não diria a ninguém que o Regex é uma linguagem de programação. Meu próprio argumento contra mim mesmo é que ele não pode ficar sozinho, tem que ser executado através de seu próprio mecanismo enquanto é suportado por outro mecanismo de linguagem de programação.

Embora uma localização / substituição na expressão regular não seja uma linguagem de programação completa de Turing, conforme explicado pelas respostas anteriores, se você permitir usar ações repetidas de substituição por expressões regulares, sim, será possível codificar qualquer máquina de Turing usando expressão regular:

A localização / substituição repetida por expressões regulares é uma linguagem de programação completa de Turing

Como conseqüência, você pode calcular qualquer função computável usando a mesma pesquisa e substituir a expressão regular de javascript repetidamente.

Para provar a integridade do turing, é suficiente codificar uma máquina de Turing na expressão regular de busca / substituição. Suponha que o estado do editor seja:

0000#12345:01-5:0#0000000

que pode ser lido como uma fita de símbolos com um leitor:

[left symbols]#[set of states]:[set of symbols]-[current state]:[current symbol]#[right symbols]

Para a regra que lê 0 no estado 5, escrevendo 1 e alterando seu estado para 3 e movendo para a esquerda, abstraímos usando a seguinte notação:

5:0 => 1, 3:[left]

Codificamos a notação anterior em uma expressão regular de pesquisa:

(\d)#(1)(2)(3)(4)(5):(0)(1)-5:0#

e sua expressão de substituição (semelhante a javascript)

#12345:01-$4:$1#$8

Ok, agora como codificar muitas regras? Usamos a concatenação com o oroperador |para a pesquisa de expressões regulares e combinamos os resultados na substituição, numerando números de grupos com deslocamentos. Por exemplo, vamos considerar o conjunto de quatro regras.

5:0 => 1, 3:left
3:0 => 1, 5:right
5:1 => 1, 5:right
3:1 => 1: 3:stop

Nós os codificamos em uma pesquisa e substituímos a expressão:

Search:
(\d)#(1)(2)(3)(4)(5):(0)(1)-5:0#|#(1)(2)(3)(4)(5):(0)(1)-3:0#(\d)|#(1)(2)(3)(4)(5):(0)(1)-5:1#(\d)|#(1)(2)(3)(4)(5):(0)(1)-3:1#

Replace by:
$15$23#12345:01-$4$13$21$27:$1$16$24$31#$8

Experimente no seu mecanismo javascript favorito:

function turingstep(s) {
  return s.replace(/(\d)#(1)(2)(3)(4)(5):(0)(1)-5:0#|#(1)(2)(3)(4)(5):(0)(1)-3:0#(\d)|#(1)(2)(3)(4)(5):(0)(1)-5:1#(\d)|#(1)(2)(3)(4)(5):(0)(1)-3:1#/g,"$15$23#12345:01-$4$13$21$27:$1$16$24$31#$8");
}

var tape = "0000#12345:01-5:0#0000000"
for(var i = 0; i < 6; i++) {
  console.log(tape)
  tape = turingstep(tape)
}