O que há de errado com expressões regulares?

TL;DR: não são exatamente regulares e são mal implementadas

DisclaimerO conteúdo desta apresentação é fortemente baseado

nos dois artigos vinculados abaixo:

http://nikic.github.io/2012/06/15/The-true-power-of-regular-expressions.html

http://swtch.com/~rsc/regexp/regexp1.html

Considere lê-los com calma, são muito bons.

(a?a)+b

Expressão Linguagem

abcd abcd

abc?d abd, abcd

abcd+ abcd, abcdd, abcddd, ...

Expressões regulares

Hierarquia de Chomskypara gramáticas formais

IRRESTRITAS

SENSÍVEIS AO CONTEXTO

LIVRES DE CONTEXTO

REGULARES

Linguagem Regular

Linguagem vazia é regular.Linguagem com uma string vazia é regular.

Linguagem com string de um caractere é regular.

A união de linguagens regulares é regular.A concatenação de linguagens regulares é regular.O fecho Kleene de linguagens regulares é regular.

Nada mais é regular.

Gramática Regular

S = aS = aT

abc?d

abcd+

a b c d

a b c d

abc?d

abcd+

a b c d

a b c d

Expressão Autômato

a

PQ

P|Q

P?

P+

P*

P Q

P

P

P

a

P Q

Expressão Autômato Array

abc?d 'a', 'b', [1, 2], 'c', 'd'

abcd+ 'a', 'b', 'c', 'd', [1, -1]

(a?a)+b [1, 2], 'a', 'a', [1, -3], 'b'

a b c d

a b c d

a a b

Expressão Autômato Array

abc?d 'a', 'b', [1, 2], 'c', 'd'a b c d

0000: CONSUME 'a'0001: CONSUME 'b'0002: JUMP +1 OR +20003: CONSUME 'c'0004: CONSUME 'd'0005: YAY_MATCH!

c d

NFA: Autômato Finito Não Determinístico

ESTE CARA É O CULPADO

c d

NFA: Autômato Finito Não Determinístico

ESTE CARA É O CULPADO ?

Expressão Autômato Array

(a?a)+b [1, 2], 'a', 'a', [1, -3], 'b'a a b

0000: JUMP +1 OR +20001: CONSUME 'a'0002: CONSUME 'a'0003: JUMP +1 OR -30004: CONSUME 'b'0005: YAY_MATCH!

PCREPerl Compatible Regular Expressions

a

Backtracking do tinhoso

a

a

a

a

a

ba

a

a

b

b b b b b b b b b b

Para uma entrada com n caracteres e um autômato

com m estados:

Cada estado pode se desdobrar em até dois fluxos diferentes.

O(2n)

Thompson's NFAEm 1968 um cara escreveu regexps corretamente

(enquanto escrevia o Unix). E até hoje copiam errado.

a a b

aaaaaainput

Simular todos os estados simultaneamente

a a b

aaaaaainput

Inicialmente, há apenas um estado: o primeiro.

a a b

aaaaaainput

Antes de cada caractere da entrada, avança-se todos os estados para os próximos que requerem consumo (os retângulos).

a a b

aaaaaainput

Depois de consumir o caractere, lembrar de avançar para o próximo estado que consome. Ou próximos estados, no caso.

a a b

aaaaaainput

Eventualmente dois estados, durante a transição, irão colidir num único estado, eliminando assim o caráter exponencial da avaliação.

Para uma entrada com n caracteres, e um autômato

com m estados:

No máximo m estados são ativados por caractere.

O(m×n)

Prova de Conceitohttps://github.com/juanplopes/pyrex

Mas e a hierarquia?

IRRESTRITAS

SENSÍVEIS AO CONTEXTO

LIVRES DE CONTEXTO

REGULARES

Linguagens não-regulares

Exemplos

Parênteses aninhados

(()()(())), (((()))), ...

"Squares" DogDog, CatCat, WikiWiki, ...

anbn ab, aabb, aaabbb, ...

Linguagens não-regulares

IRRESTRITAS

SENSÍVEIS AO CONTEXTO

LIVRES DE CONTEXTO

REGULARES

anbn, parênteses

anbncn, "squares"

Em teoria, expressões regulares não conseguem

sequer reconhecer expressões regulares.

Na prática...

Expressão

Parênteses aninhados (\((?1)*\))1

"Squares" (.*)\1

anbn (a(?1)?b)1

1 sintaxe do Perl para recursive capture buffers

Match de regexps com backreferences é um

problema NP-completo.

3-SAT (NP-completo)

(!x1 || x2 || x4) && (x1 || !x3 || x4) &&

(x1 || !x2 || !x4) && (x2 || !x3 || !x4) &&

(!x1 || x3 || !x4) && (x1 || x2 || x3) &&

(!x1 || !x2 || !x3)

3-SAT com Regexp

^(x?)(x?)(x?)(x?).*;

(!x1 || x2 || x4) (?:x\1|\2|\4),

(x1 || !x3 || x4) (?:\1|x\3|\4),

(x1 || !x2 || !x4) (?:\1|x\2|x\4),

(x2 || !x3 || !x4) (?:\2|x\3|x\4),

(!x1 || x3 || !x4) (?:x\1|\3|x\4),

(x1 || x2 || x3) (?:\1|\2|\3),

(!x1 || !x2 || !x3) (?:x\1|x\2|x\3),$

match 'xxxx;x,x,x,x,x,x,x,'

resultado: ['xxxx;x,x,x,x,x,x,x,', 'x', 'x', '', '']

Quais features comuns podem ser resolvidas de

forma segura?

Counted repetitions?(abcd){1000,1000000}

a b c d

a b c d

a b c d

a b c d

Alguma chance de rolar backreferences?

NO WAY!

E zero-width assertions? \b, ^, $, (?<, (?=

a

<some state that looks around the

input and takes lots of time, but well... it's still polynomial>

c

E (named) submatches?a(b)c

a(?<name>b)c

a b cpush

\1pop

\1

a b cpush

'name'pop

'name'

RE2

https://code.google.com/p/re2/Russ Cox (Google, Go)

Em suma

Match de expressões regulares pode ser feito em tempo polinomial, mas normalmente não é.

Regexps na maior parte das linguagens não tem muito a ver com expressões regulares stricto sensu.

PCRE consegue definir qualquer gramática livre de contexto e algumas sensíveis a contexto também.

Match de backreferences é NP-completo.