Precisa de visão geral de conceitos e ferramentas para traduzir uma DSL para expressões regulares

5

Estou procurando uma pequena orientação. Até esta manhã, tudo isso estava em cima da minha cabeça. Depois de gastar hoje pesquisando Wikipedia, StackOverflow, etc, eu diria que eu tenho meu nariz acima da água. Tenho a tarefa de pesquisar um projeto que, no meu entender, envolveria a engenharia reversa de uma linguagem específica de domínio que é basicamente um tipo de sintaxe de expressão regular e a traduz em expressões regulares convencionais (ou seja, semelhantes a Perl). Eu estou esperando que alguém possa preencher as lacunas no meu entendimento, então deixe-me explicar o que eu tenho e o meu entendimento, até agora.

Em relação à DSL, ela basicamente tem dois componentes. Uma é a expressão regular grep-like, mais ou menos. O outro componente consiste no que você poderia chamar de macros. Essas macros são usadas quando você deseja encontrar números de CPF, números de cartão de crédito e assim por diante no texto que está sendo analisado. O DSL é uma maneira mais simples para o usuário final especificar texto e exceções correspondentes. (Honestamente, ainda é bastante complicado de usar - mas mais fácil do que expressões regulares.)

A DSL é usada para escrever "regras", uma regra sendo uma declaração de uma linha descrevendo o texto de destino.

O que eu quero fazer é, tomando uma regra como entrada, traduzir essa regra em uma expressão regular convencional sempre que possível. Se uma macro não se dividir em uma única expressão regular, eu traduzirei a macro em um ou mais REs, ou qualquer tipo de código de processamento de texto necessário.

Meu maior ponto de ignorância é a "tradução". Aqui está minha primeira pergunta: isso envolverá o que é chamado de "análise"? (Como você pode imaginar, eu sou um programador autodidata.) Eu estaria usando uma ferramenta como ANTLR ou PyParsing, ou algo assim? (Acabei de descobrir sobre essas ferramentas hoje, durante a minha pesquisa.) Eu estou supondo que sim, mas gostaria de confirmação.

Quanto eu tenho que aprender? Eu não vou precisar pegar o "Dragon book", certo? Eu não estou escrevendo uma DSL, mas se eu estou fazendo uma engenharia reversa, então eu acho que eu vou mais ou menos precisar aprender como criar uma DSL em primeiro lugar (já que de outra forma eu saberia como fazer a DSL? análise). Sim?

O que eu preciso para entrar no meu currículo? É o que estou tentando descobrir. Eu analisei arquivos de configuração; Eu escrevi um simples YAML para o gerador de código Java Bean; Eu escrevi um simples HTML-stripper; Eu sei um pouco sobre expressões regulares e processamento de texto; mas esse esforço em particular é mais sofisticado do que qualquer coisa que eu tenha feito antes. Parece factível, mas como um teste de sanidade, por favor, diga-me se, na minha ignorância, eu calculei mal e o que estou descrevendo realmente precisa de 4 anos para ser uma grande ciência da computação.

Alguém pode me apontar na direção certa ou me dar algumas dicas? Obrigado.

    
por Mario 20.06.2014 / 22:24
fonte

2 respostas

2

Eu nunca escrevi um compilador, então estou fora da minha profundidade aqui, mas aqui está uma tentativa:

Eu começaria escrevendo um léxico e parser para o idioma. Existem muitas ferramentas para isso. ANTLR é um deles; Ele pode lidar com lexing e parsing. Alternativamente, você pode usar o Lex ou o GNU Flex para criar um léxico e criar uma árvore de análise com o Yacc e sua implementação Bison são outros. Tenho certeza de que existem muitos outros geradores de lexer e parser que eu não abordei aqui.

No que diz respeito à geração de código, não sei qual é a melhor maneira de fazer isso. No entanto, existem muitos recursos sobre o assunto.

A principal resposta para esta pergunta lista muitos recursos que você pode usar para ambos o lexing / parsing e geração de código.

Se você conhece uma linguagem funcional (como o OCaml), esta seria uma boa linguagem para implementar seu compilador, pois acredito que (nunca fiz isso) tornam o trabalho com árvores relativamente fácil.

    
por 22.07.2014 / 18:22
fonte
2

Recomendo que você se familiarize com várias linguagens de programação (incluindo Scheme ou CommonLisp e Ocaml ou Haskell).

É provável que a implementação do seu tradutor nesses idiomas seja boa para você.

Então sugiro ler Pragmática da Linguagem de Programação (por M.Scott) e Lisp In Small Pieces (por C.Queinnec).

Claro, você precisará ler um bom livro de compilação.

A lexagem & A fase de análise é provavelmente a mais simples. A maioria dos problemas está em outro lugar.

É claro que você pode querer usar um gerador de parser como menhir ou antlr . Você também pode evitá-los e escrever seu próprio analisador manualmente ( esta resposta explica por que você gostaria de fazer isso ). Mas a análise é bastante "fácil" (mas muito trabalho!). A maioria dos problemas está em outro lugar.

BTW, você está reimplementando uma DSL. Você pode tentar (compativelmente) melhorá-lo. E é uma quantidade significativa de trabalho (meses, não dias).

É claro que o seu tradutor irá fazer algumas árvore sintática abstrata do código DSL analisado (e o mal está em os detalhes) e transformá-los em alguma outra AST representando o código de saída.

Meu artigo do DSL2011 sobre o MELT pode ser relevante para você.

A leitura do Manual da Coleta de Lixo também deve ser útil.

    
por 22.07.2014 / 18:37
fonte