Gramática EBNF para Java Regex

[Knitter]

Boa noite,

Estou à procura de uma gramática para descrever expressões regulares, será que algum de vós tem conhecimento de algum local onde possa obter a gramática já escrita em formato EBNF?

Preciso gerar expressões regulares através de um algoritmo genético, e seria um avanço grande ter a gramática já escrita, até porque só conheço a notação de nome e nunca tentei escrever nada nela.

Cumprimentos,

Knitter

Edited March 26, 2014 by Knitter

[Rui Carlos]

Tens aqui uma gramática no formato do YACC (tirando-lhe o "lixo", ficas com uma gramática (E)BNF).

Tens alguma notação de expressões regulares em mente? É que isto pode ser um problema, visto que há várias diferentes.

EDIT: Tens uma versão mais básica ressions.html'>aqui.

[Knitter]

Neste momento ainda estou a tentar juntar possibilidades.

Tenho de usar Java por isso vou ter de escrever/adaptar a notação às regras das REGEX de Java. Uma possibilidade para validar as expressões regulares seria simplesmente compilá-las já que as inválidas dariam erro, mas a criação de tantas excepções (que espero que ocorram com frequência) é capaz de ser demasiado pesado para ter na função de fitness. Mas também não sei se usando a gramática será mais rápido (acho que vou ter de implementar os dois para depois testar).

Obrigado pelos links.

[Rui Carlos]

Eu suspeito que o Java também valida as expressões regulares através de uma gramática (ou de outro mecanismo com desempenho semelhante), pelo que esperaria que não houvesse grande vantagens em fazeres tu a validação (até porque vais estar a duplicar trabalho no caso em que as expressões são válidas).

É claro que podes tentar optimizar a implementação do teu parser, mas pela experiência que tive recentemente num caso em que implementei um parser optimizado à mão, diria que não é fácil ter ganhos significativos.

No entanto, cada caso é um caso, e se conseguires simplificar a linguagem no teu caso (i.e., senão precisares de expressões regulares tão genéricas como as do Java), até é provável que consigas alguns ganhos relevantes.