Aprender mais sobre Parsing

Question

Eu tenho sido programação desde 1999 para trabalho e diversão. Eu quero aprender coisas novas, e ultimamente tenho sido focada em análise, como uma grande parte do meu trabalho é ler, integração e análise de dados. Eu também tenho um grande número de tarefas repetitivas que eu acho que eu poderia expressar em muito simples linguagens específicas de domínio, se a sobrecarga foi baixo o suficiente. Eu tenho algumas perguntas sobre o assunto.

1. A maioria do meu código de análise atual não define uma gramática formal. Eu costumo cortar alguma coisa juntos no meu idioma de escolha, porque isso é fácil, eu sei como fazê-lo e eu posso escrever esse código muito rápido. É também fácil para outras pessoas com quem trabalho para manter. Quais são as vantagens e desvantagens de se definir uma gramática e gerando um analisador real (como se poderia fazer com ANTLR ou YACC ) para as coisas de análise em comparação com os hacks que a maioria dos programadores usados ??para analisadores de escrita?
2. Quais são as melhores ferramentas de geração de analisador para escrever analisadores baseados em gramática em C ++, Perl e Ruby? Eu olhei ANTLR e não ter encontrado muito sobre usando ANTLRv3 com um alvo C ++, mas por outro lado que parece interessante. Quais são as outras ferramentas que são semelhantes aos ANTLR que eu deveria estar lendo sobre?
3. Quais são os livros e artigos canônicos que alguém interessado em aprender mais sobre análise? Um curso de compiladores, infelizmente, não era parte da minha educação, para material básico é muito bem-vindos. Já ouvi falar grandes coisas sobre o Dragão Livro , mas o que mais está lá fora?

Answer 1

No 1., eu diria que a principal vantagem é manutenção - fazer uma pequena mudança para a língua significa apenas fazer uma correspondentemente-pequena alteração para a gramática, ao invés de cortar minuciosamente através dos vários manchas no código que pode ter algo a ver com o que você quer mudado ... ordens de magnitude melhor produtividade e menor risco de erros.

Em 2. e 3., não posso sugerir muito além do que você já encontrou (Eu use Python e pyparsing, e poderia comentar com a experiência de muitos marcos de análise Python-centrados, mas para C ++ Eu use o bom e velho yacc ou bison qualquer maneira, e minha cópia retorcida velho do Livro Dragon - não a última edição, na verdade -. é tudo o que eu manter a meu lado com a finalidade ...)

Answer 2

Aqui está a minha opinião sobre os seus (muito bom) perguntas:

1. Eu acho que um benefícios analisador maioria das situações não-triviais, onde uma gramática realmente existe. Você tem que saber sobre como analisadores e gramáticas trabalhar a pensar que a técnica, e não a cada desenvolvedor faz.
2. lex / yacc são ferramentas mais antigas do Unix que podem ser útil para você como um desenvolvedor C ++. Talvez Bison também.
3. ANTRL e seu livro atendente são muito bons. "Escrever Compiladores e Intérpretes" tem exemplos C ++ que você pode gostar.

O padrão GoF Interpreter é uma outra técnica para escrever "pequenos idiomas". Dê uma olhada nisso.

Answer 3

Vamos construir um compilador é um tutorial passo-a-passo sobre como escrever um simples compilador. O código é escrito em Delphi (Pascal), mas é o suficiente básica para facilmente traduzir-se na maioria dos outros idiomas.

Answer 4

Eu teria um olhar sério análise baseada em combinator monádico (que muitas vezes também lida com análise léxica) em Haskell. Eu achei bastante um abridor de olho; é incrível como você pode facilmente construir um analisador a partir do zero usando este método. É tão fácil, na verdade, que muitas vezes é mais rápido para escrever seu próprio analisador do que está a tentar usar bibliotecas existentes.

O exemplo mais famoso é provavelmente Parsec que tem uma boa usuário guia que explica como usá-lo . Há uma lista de portas desta biblioteca para outras línguas (incluindo C ++ e rubi ) listados na Parsec página do Haskell wiki , embora eu não estou familiarizado com eles e por isso não posso dizer o quão perto estão a usar Parsec em Haskell.

Se você quiser aprender como estes trabalham internamente e como escrever o seu próprio, eu recomendo começar com o capítulo 8 ( "Analisadores funcionais") de Graham Hutton do Programação em Haskell . Depois de entender esse capítulo bem (o que provavelmente terá várias leituras), você vai ser definido.

Answer 5

Em perl, os módulos Parse :: RecDescent é o primeiro lugar para começar. Adicionar tutorial para o nome do módulo e Google deve ser capaz de encontrar uma abundância de tutoriais para você começar.

Answer 6

A definição de uma gramática usando BNF, EBNF ou algo semelhante, é mais fácil e mais tarde você vai ter um melhor tempo mantê-la. Além disso, você pode encontrar um monte de exemplos de definições de gramática. Por último, mas não menos importante, se você estiver indo para falar sobre a sua gramática para alguém no campo, é melhor se você estiver ambos falando a mesma língua (BNF, EBNF etc.).

Escrevendo seu próprio código de análise é como reinventar a roda e é propenso a erros. Também é menos sustentável. Claro, ele pode ser mais flexível, e para pequenos projetos pode também ser uma escolha boa, mas usando um gerador de analisador existente que leva uma gramática e cospe o código deve cobrir a maior parte das nossas necessidades.

Para C ++ Também gostaria de sugerir lex / yacc. Para Ruby Isto parece uma escolha razoável: Coco / R (UBY)

Answer 7

Engraçado tempo:. Passei muito esta manhã perguntando sobre máquinas de estado e analisadores, e tentando descobrir como eu poderia aprender mais sobre eles

Para 2, você pode dar uma olhada em Ragel (É bom para C ++ e Ruby) .

Answer 8

Aqui está um tutorial sobre um auto-suficiente (10 páginas!), Compilador de compilador totalmente portátil que pode ser usado para projetar e implementar DSLs "low gerais" muito rapidamente:

http://www.bayfronttechnologies.com/mc_tutorial.html

Este site percorre papel 1964 Val Schorre em MetaII. Sim, 1964. E é incrível. É assim que eu aprendi sobre compiladores em 1970.