Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Regex

 Regex

Uma introdução a expressões regulares e bibliotecas regex.

Daniel Capo Sobral

June 25, 2012
Tweet

More Decks by Daniel Capo Sobral

Other Decks in Programming

Transcript

  1. Verifica se número é primo  Isso não é uma

    expressão regular  (mas é aceito por quase todas bibliotecas regex)
  2. Verifica se número é primo  Isso não é uma

    expressão regular  (mas é aceito por quase todas bibliotecas regex)  É difícil de entender
  3. Verifica se número é primo  Isso não é uma

    expressão regular  (mas é aceito por quase todas bibliotecas regex)  É difícil de entender  É fácil de errar
  4. Verifica se número é primo  Isso não é uma

    expressão regular  (mas é aceito por quase todas bibliotecas regex)  É difícil de entender  É fácil de errar  É extremamente compacta
  5. Verifica se número é primo  Isso não é uma

    expressão regular  (mas é aceito por quase todas bibliotecas regex)  É difícil de entender  É fácil de errar  É extremamente compacta  Na verdade, checa se número não é primo
  6. Histórico  Conceito matemático introduzido na década de 50 

    SNOBOL implementou pattern matching, mas não expressões regulares  Ken Thompson introduzir expressões regulares no editor QED, depois ed (Unix), e finalmente grep (abreviação do comando g/re/p do ed)  Padronizado pelo POSIX  Repadronizado pelo Perl e Tcl (baseado em biblioteca de Henry Spencer)  Biblioteca PCRE (Philip Hazel)
  7. Para que servem Regex?  Verificar se um determinado padrão

    ocorre em um texto  Verificar se um determinado padrão não ocorre em um texto  Localizar as ocorrências de um padrão  Obter as ocorrências de um padrão  Obter partes das ocorrências de um padrão  Substituir ocorrências de um padrão por outro texto, possivelmente usando partes da ocorrência  Dividir texto de acordo com um padrão
  8. Exemplos  Acha linhas com configurações:  grep "^ *[^#

    ]" php.ini  Acha linhas que não estejam em branco:  grep –v "^$" .profile  Índice de todas palavras em um texto:  [w.start() for w in re.finditer(r'\b\w', text)]  Todas palavras de um texto:  @words = $text =~ /\w+/  Dia, mês e ano de uma data:  ($d, $m, $a) = text =~ /(\d\d)/(\d\d)/(\d{4})/  Remove espaços do fim da linha:  sed -p'' -e 's/ *$//‘  Divide linha em palavras e símbolos  text split """\b\s*|\s*\b"""
  9. Expressões Regulares  Descrevem Linguagens Regulares  Mesmo poder expressivo

    de Gramáticas Regulares  Mesmas linguagens aceitas por Autômatos Finitos Determinísticos  Livres de Contexto  Exemplo de linguagem não regular:  Número de b depende do número de a: anbn
  10. Dois switches e um loop // Texto termina em \n?

    int state = 0; while(ch = getc()) { switch(state) { case 0: switch(ch) { case '\n': state = 1; break; default : break; } case 1: switch(ch) { case '\n': break; default : state = 0; break; } } } return state == 1;
  11. Estrutura de uma Regex  Composta de:  Um caracter

    (literal)  Ou nada (string vazia)  Ou uma composição de uma ou duas outras regex
  12. Operações de Composição  Da maior precedência para a menor:

     Repetição (kleene star): r*  Concatenação: r1 r2  Alternativa: r1 | r2  Todas expressões regulares podem ser compostas a partir desses elementos  Muitas regex não podem ser compostas só com esses elementos
  13. Tipos de Regex  POSIX Basic Regex (grep)  POSIX

    Extended Regex (grep –E)  Preg (Perl regex)  PCRE (Perl Compatible(*) Regular Expression)  (*) Só que não  Etc... (cada biblioteca tem suas particularidades)
  14. Regex Compilado vs JIT  Compilar um regex transforma a

    string representando o regex em uma estrutura de dados otimizada para seu uso  Disponível com Java, Perl, Python, Ruby  Regex Just In Time recompilam a expressão todas as vezes, para diminuir a cerimônia de seu uso  Disponível com Java(*), Perl, PHP, Python, Ruby  (*) Somente para alguns usos
  15. Outras operações de Composição  Qualquer caracter: .  Qualquer

    um de um conjunto: [r1 r2 -r3 ]  Qualquer um não em um conjunto: [^r1 r2 ]  Classes de caracteres: [[:alpha:]], \w,  Negação de classes: [^[:alpha:]], \W  Classes POSIX: \p{Upper}, \P{InGreek}  Zero ou um: r?  Um ou mais: r+  Entre n e m repetições: r{n, m}
  16. Classes úteis  [:alnum:]  \w – inclui sublinhado (não

    palavras como \W)  [:alpha:]  [:blank:]  [:cntrl:]  [:digit] ou \d (não dígito como \D)  [:graph:]  [:lower:]  [:print:]  [:punct:]  [:space:] ou \s (não espaço como \S)  [:upper:]  [:xdigit:]
  17. Greediness  As expressões r* e r+ retornam a maior

    quantidade possível de caracteres que satisfaçam a expressão  Elas são greedy – gananciosas  Algumas bibliotecas suportam relutância:  r*? e r+?  Elas retornam a menor quantidade possível de caracteres que satisfaçam a expressão  Em alguns casos, a performance das repetições relutantes é muito superior
  18. Relembrando Precedência  Lembrando a precedência: repetição, concatenação e alternativa

     Textos que satisfazem a expressão ab*|cd:  a  ab  abb  cd  Os textos abab e acd não satisfazem a expressão
  19. Agrupamento  POSIX Basic Regular Expression: \( e \) 

    Todo o resto: ( e )  Grupos também capturam o conteúdo, e podem ser extraídos separadamente ou usados na substituição  Sem captura(*): (?:r)  (*) as partes de uma ocorrência correspondentes a expressões dentro de parênteses são retornadas como grupos ou subgrupos
  20. Contexto  Eu falei que expressões regulares são linguagens sem

    contexto  Mas esses “contextos” são válidos, pois podem ser representados como estados  Âncoras:  Início do texto ou de uma linha: ^  Fim do texto ou de uma linha: $  Borda de palavras: \b ou \< e \> (POSIX BRE)  Look-ahead: (?=r)  Look-behind: (?<=r)  Negações: (?!r) e (?<!r)
  21. Contexto de verdade  Não suportados por expressões regulares 

    Suportados por quase todas bibliotecas regex  Podem levar a tempos exponenciais  Back references: \n (para n de 1 a 9)
  22. Alterações de Comportamento  Formato:  Ativa/Desativa: (?idmsux-idmsux)  Somente

    para o subgrupo: (?idmsux-idmsux:r)  Flags:  Case insensitive: i  Unix new lines: d  Multiline: m  “.” pega new lines: s  Unicode-aware: u  Comentários: x
  23. Escaping (citando caracteres)  PCRE:  \ antes de símbolos

    cita o símbolo  \ antes de letras tem tem significado especial  POSIX Basic RE: uma zona – consulte o manual  Citando um grupo de caracters:  \Qgrupo de caracteres\E
  24. Explicando Números Primos (?x) # Dado uma sequência de dígitos

    1, aceita se o # tamanho da sequência não for um número primo # Primeiro caso, números menores que 2 ^ # Início da string 1? # 0 ou 1 ocorrênicas do dígito 1 $ # Fim da String | # Segundo caso, números maiores ou igual a 2 # Verifica se a string pode ser reduzida a # XX...X, onde X é uma string de tamanho fixo # com dois ou mais dígitos 1 ^ # Início da string ( # Início do primeiro subgrupo -- o “X” da questão 11+? # Sequência de dois ou mais dígitos 1 # A sequência acima é relutante por questões de performance ) # Fim da sequência \1+ # Uma ou mais (novas) ocorrências do subgrupo 1 $ # Fim da string
  25. Moral da História  Coisas que não são regex as

    vezes podem ser resolvidas com regex  Coisas que são regex as vezes não valem a pena serem resolvidas com regex  Algumas coisas não são regex e não são resolvidas com regex  Resolver com código expressões regulares simples é muito mais complicado do que as pessoas assumem  Não usem regex com xml!
  26. Criando e Testando Regex  RegexBuddy (produto comercial): o melhor

    de todos  DFA/Regex: http://osteele.com/tools/reanimator/  .Net: http://www.nregex.com/nregex/default.aspx  Java: http://www.myregexp.com/  JavaScript: http://www.regexpal.com/  Perl: http://www.regextester.com/ (tb PHP, POSIX)  PHP: http://regex.larsolavtorvik.com/ (tb Javascript)  Python: http://www.pythonregex.com/  Ruby: http://www.rubular.com/
  27. Exemplo Java import java.util.regex.Pattern; import java.util.regex.Matcher; Pattern pattern = Pattern.compile("pattern");

    Matcher matcher = pattern.matches("text"); Matcher.find(); matcher.matches(); matcher.replaceFirst("replacement"); matcher.replaceAll(Matcher.quoteReplacement("replacement")); MatchResult matchResult = matcher.toMatchResult(); text.split("pattern");
  28. Exemplo Python # Compila & Busca prog = re.compile(r"pattern") result

    = prog.match("text") # Atalho result = re.match(r"pattern", "text") re.search("text") re.findall("text"); re.finditer("text") re.sub("replacement", "text") re.split("text")