[Cascavel-pm] Quando usar Gramatica e quando usar Regexp? [Was: Artigo - Como Perl Salvou o Projeto Genoma]

[Eden Cardim]

On 5/24/07, Lorn <lorn.br em gmail.com> wrote:
> Eu nunca precisei fazer nenhum parse de html ( sim, eu uso modulos que fazem
> parser de html, mas existem html's que dão medo, então não é sempre que o
> modulo resolve ) ou qualquer tipo de arquivo, tão complexo que seria melhor
> que fosse feito uma gramatica, mas talvez eu tenha perdido 5h fazendo
> regexp, quando podia ter perdido 1h fazendo uma gramatica, tem como
> descobrir quando usar Gramatica e quando usar Regexp? alguma tecnica? :P

Sim, tem um ramo da teoria da computação que estuda as Linguagens
Formais (http://en.wikipedia.org/wiki/Formal_language). Vou resumir
aqui, se quiser ver mais a fundo, olha os links pro wikipedia.
Existem vários tipos de linguagens formais, elas são categorizadas na
hierarquia de Chomsky
(http://en.wikipedia.org/wiki/Chomsky_hierarchy), entre elas está a
classe das linguagens regulares
(http://en.wikipedia.org/wiki/Regular_language). Dentre outras
definições, uma linguagem regular é qualquer linguagem que pode ser
descrita por uma expressão regular
(http://en.wikipedia.org/wiki/Regular_expressions#Formal_language_theory).

Respondendo a sua pergunta, para usar uma expressão regular você tem
que saber se a linguagem que você está avaliando é regular também. Em
qualquer outro caso, você vai ter que utilizar a gramática equivalente
na hierarquia de Chomsky.

Para descobrir se uma linguagem é regular:
http://en.wikipedia.org/wiki/Regular_language#Deciding_whether_a_language_is_regular

ufa...

P.S.: Desculpem, bateu a nostalgia da época que eu tinha tempo pra
estudar Teoria da Computação, espero ter ajudado...

-- 
Eden Cardim
Instituto Baiano de Biotecnologia
Núcleo de Biologia Computacional e Gestão de Informações Biotecnológicas
Laboratório de Bioinformática