[SP-pm] Boas Vindas ao Ricardo Bittencourt

[Eden Cardim]

>>>>> "Luis" == Luis Motta Campos <luismottacampos em yahoo.co.uk> writes:

    Luis> Nope. Expressões Regulares em Perl são "apenas" gramáticas
    Luis> regulares...  mas acho que as expressões regulares do Perl se
    Luis> tornam turing-complete se você acrescentar a opção '/e'... mas
    Luis> eu ainda não me arrisquei a tentar demonstrar isso.

Na verdade, são sim, já que você pode fazer executar código perl até
interpolar código (use re 'eval';) dentro de uma regex perl rodando no
escopo da própria regex, então se perl for turing-complete, regexps
também são. Para demonstrar é só provar que um programa perl que não
contenha uma regex é turing complete.  E acho que regexes perl são
turing-complete mesmo sem apelar para perl inline, já que tem match
condicional: (?(condition)yes-pattern|no-pattern) e buffers de
captura. Por exemplo, essa "regex" recursiva (entre aspas porque regexes
não são turing-complete) só casa com palíndromos:

/^((.)(?1)\2|.?)$/

perl -le'print 1 if "foo"=~/^((.)(?1)\2|.?)$/'

perl -le'print 1 if "oo"=~/^((.)(?1)\2|.?)$/'
1
perl -le'print 1 if "ooo"=~/^((.)(?1)\2|.?)$/'
1
perl -le'print 1 if ""=~/^((.)(?1)\2|.?)$/'
1

p.s.: string vazia é um palíndromo por conta da seguinte propriedade:
perl -le'print "".""."" eq ""'
1

(string vazia tem uma string vazia no meio, uma no começo e outra no
fim)