O idioma das expressões regulares precisa de um autômato para analisá-lo?

Desejo converter uma expressão regular inserida pelo usuário em um NFA, para que eu possa executar o NFA em uma string para fins de correspondência. Qual é a máquina mínima que pode ser usada para analisar expressões regulares?

Suponho que deve ser um autômato push down, porque a presença de colchetes significa a necessidade de contar e um DFA / NFA não pode executar uma contagem arbitrária. Esta suposição está correta? Por exemplo, a expressão a (bc *) d exigiria um PDA para que a subexpressão entre parênteses seja manipulada corretamente.

formal-languages parsers regular-expressions pushdown-automata Phil Wright
fonte

O que você quer dizer exatamente com "análise"? Você quer dizer verificar se a entrada é realmente uma expressão regular ou se tem algo mais complicado em mente, por exemplo, uma máquina exibindo uma descrição do NFA correspondente? (se você não tem certeza se a entrada é realmente uma expressão regular e você precisa verificar isso, então você precisa ser capaz de verificar que parênteses são corretas e que normalmente significa usar uma pilha.)

Kaveh

Para uma resposta prática, você pode olhar para o Plan 9 fonte Grep para grep.y .

Bruce Ediger #

Respostas:

Você está certo. É fácil mostrar que a sintaxe das expressões regulares não é regular usando técnicas padrão .

Uma possibilidade é usar um homomorfismo (que é fechada contra) para se livrar de todos os símbolos, mas os parênteses, que deixa você com a linguagem Dyck , que é bem conhecido por ser não-regular. Em caso de dúvida, use o lema Pumping na . $\mathrm{REG}$ $(^p)^p$

Dito isto, você provavelmente não deseja codificar um PDA manualmente. Considere usar um gerador de analisador como ANTLR ou byacc . Se, por outro lado, você deseja investigar a análise de linguagens programando analisadores, você deve continuar com outros algoritmos básicos de análise, como CYK , Earley , descida recursiva e LR .

Rafael
fonte

obrigado. escrever código para estas tarefas cria uma melhor compreensão e não se destina a ser tão eficiente quanto utilitários existentes, como lex, yacc, bisontes etc.

Phil Wright

@ PhilWright: Entendo, que legal! Eu editei em mais ponteiros para este caso.

Raphael

Eu preferiria um analisador de descida recursiva codificado à mão para este.

Dave Clarke

Se escrever um analisador manualmente para isso, uma descida recursiva (após fatorar e massagear) é uma opção, o analisador LCC para C < sites.google.com/site/lccretargetablecompiler > tem uma abordagem interessante para lidar com muitos operadores. Mas talvez o mais fácil para a construção manual seja a análise de precedência.

vonbrand

Sugiro que você leia também a boa resposta do Jukka para a pergunta " Combinando expressões regulares usando expressões regulares " na história. Um trecho:

Por exemplo, podemos modificar a notação padrão da seguinte maneira para obter expressões regulares "compactadas" :

Você tem permissão para remover qualquer prefixo que consiste em uma sequência de ('s

Você tem permissão para remover qualquer sufixo que consista em uma sequência de)

Ou seja, ((a|b)*c)de(f|g)pode ser expresso na notação "compactada" usando, por exemplo, qualquer uma das seguintes formas: a|b)*c)de(f|gou ((a|b)*c)de(f|gou (a|b)*c)de(f|g).

[...]

A notação "compactada" (de uma expressão regular) é uma linguagem regular.

Este é apenas um link para uma interessante "visão diferente" (na minha opinião) sobre a linguagem da expressão regular; conforme sublinhado nos comentários abaixo, não é útil para criar uma árvore de sintaxe. Se você quiser codificar manualmente seu analisador, sugiro este artigo simples no projeto de código " Writing-own-regular-expression-parser ".

Vor
fonte

Jukka remove essencialmente a exigência de que os parênteses sejam equilibrados. Não conheço nenhum caso em que isso seja realmente feito, mas vale a pena observar que, alterando a semântica, você pode "simplificar" a sintaxe.

Raphael

Você (e Jukka) não estão analisando regexps, apenas os reconhecendo. "Sim, isso é um regexp (compactado)."

Gilles 'SO- stop be evil'