Quando usar um Parser Combinator? Quando usar um gerador de analisador?

Recentemente, mergulhei profundamente no mundo dos analisadores, querendo criar minha própria linguagem de programação.

No entanto, descobri que existem duas abordagens um tanto diferentes dos analisadores de gravação: Geradores de Analisadores e Combinadores de Analisadores.

Curiosamente, não consegui encontrar nenhum recurso que explicasse em que casos qual abordagem é melhor; Em vez disso, muitos recursos (e pessoas) que perguntei sobre o assunto não conheciam a outra abordagem, apenas explicando sua abordagem como a abordagem e sem mencionar a outra:

• O famoso livro Dragon trata de lexing / scan e menciona (f) lex, mas não menciona Parser Combinators.
• Os padrões de implementação de linguagem dependem muito do ANTLR Parser Generator, construído em Java, e não menciona Parser Combinators.
• O tutorial Introdução ao Parsec no Parsec, que é um combinador de analisadores em Haskell, não menciona os geradores de analisadores.
• O Boost :: spirit , o C ++ Parser Combinator mais conhecido, não menciona os Geradores de Parser.
• O ótimo post explicativo do blog Você poderia ter inventado os combinadores de analisadores não menciona os geradores de analisadores.

Visão geral simples:

Gerador de Analisador

Um gerador de analisador pega um arquivo gravado em um DSL, que é um dialeto do formato Extended Backus-Naur , e o transforma em código-fonte que pode (quando compilado) se tornar um analisador para o idioma de entrada descrito neste DSL.

Isso significa que o processo de compilação é realizado em duas etapas separadas. Curiosamente, os próprios Geradores de Analisador também são compiladores (e muitos deles são realmente auto-hospedados ).

Combinador de Analisador

Um Parser Combinator descreve funções simples chamadas parsers que usam uma entrada como parâmetro e tentam extrair o (s) primeiro (s) caractere (s) dessa entrada, se corresponderem. Eles retornam uma tupla (result, rest_of_input), onde resultpode estar vazia (por exemplo, nilou Nothing) se o analisador não puder analisar nada desta entrada. Um exemplo seria um digitanalisador. Outros analisadores podem, é claro, considerá-los como primeiros argumentos (o argumento final ainda permanece a sequência de entrada) para combiná- los: por exemplo, many1tenta combinar outro analisador quantas vezes for possível (mas pelo menos uma vez, ou ele próprio falha).

Agora é possível combinar (compor) digite many1, para criar um novo analisador, digamos integer.

Além disso, um choiceanalisador de nível superior pode ser gravado e recebe uma lista de analisadores, tentando cada um deles.

Dessa maneira, lexers / analisadores muito complexos podem ser construídos. Nos idiomas que suportam a sobrecarga do operador, isso também se parece muito com o EBNF, embora ainda seja escrito diretamente no idioma de destino (e você pode usar todos os recursos do idioma de destino que desejar).

Diferenças simples

Língua:

• Os geradores de analisadores são gravados em uma combinação do DSL EBNF-ish e o código que essas instruções devem gerar quando corresponderem.
• Os analisadores de analisadores são escritos diretamente no idioma de destino.

Lexing / Análise:

• Os geradores de analisador têm uma diferença muito distinta entre o 'lexer' (que divide uma sequência em tokens que podem ser marcados para mostrar que tipo de valor estamos lidando) e o 'analisador' (que pega a lista de saída de tokens do lexer e tenta combiná-los, formando uma árvore de sintaxe abstrata).
• Os combinadores de analisadores não têm / precisam dessa distinção; geralmente, analisadores simples executam o trabalho do 'lexer' e os analisadores de mais alto nível os chamam de mais simples para decidir que tipo de nó AST criar.

Pergunta, questão

No entanto, mesmo considerando essas diferenças (e essa lista de diferenças provavelmente está longe de estar completa!), Não posso fazer uma escolha instruída sobre quando usar qual delas. Não vejo quais são as implicações / consequências dessas diferenças.

Quais propriedades do problema indicariam que um problema seria melhor resolvido usando um gerador de analisador? Quais propriedades do problema indicariam que um problema seria melhor resolvido usando e um Parser Combinator?

Pesquisei bastante nos últimos dias para entender melhor por que essas tecnologias separadas existem e quais são seus pontos fortes e fracos.

Algumas das respostas já existentes sugeriram algumas de suas diferenças, mas elas não forneceram o quadro completo e pareciam um pouco opinativas, razão pela qual essa resposta foi escrita.

Esta exposição é longa, mas importante. tenha paciência comigo (ou, se estiver impaciente, role até o final para ver um fluxograma).

Para entender as diferenças entre combinadores e geradores de analisadores, primeiro é necessário entender a diferença entre os vários tipos de análise existentes.

Análise

A análise é o processo de análise de uma sequência de símbolos de acordo com uma gramática formal. (Na Computing Science,) a análise é usada para permitir que um computador entenda o texto escrito em um idioma, geralmente criando uma árvore de análise que representa o texto escrito, armazenando o significado das diferentes partes escritas em cada nó da árvore. Essa árvore de análise pode então ser usada para uma variedade de propósitos diferentes, como traduzi-la para outro idioma (usado em muitos compiladores), interpretar as instruções escritas diretamente de alguma forma (SQL, HTML), permitindo que ferramentas como Linters realizem seu trabalho Às vezes, uma árvore de análise não é explicitamentegerado, mas a ação que deve ser executada em cada tipo de nó na árvore é executada diretamente. Isso aumenta a eficiência, mas debaixo d'água ainda existe uma árvore de análise implícita.

A análise é um problema computacionalmente difícil. Há mais de cinquenta anos de pesquisa sobre esse assunto, mas ainda há muito a aprender.

Grosso modo, existem quatro algoritmos gerais para permitir que um computador analise a entrada:

• Análise de LL. (Análise sem contexto, de cima para baixo.)
• Análise de LR. (Análise de baixo para cima, sem contexto).
• Análise de PEG + Packrat.
• Earley Parsing.

Observe que esses tipos de análise são descrições teóricas muito gerais. Existem várias maneiras de implementar cada um desses algoritmos em máquinas físicas, com diferentes vantagens e desvantagens.

LL e LR podem apenas olhar para gramáticas livres de contexto (ou seja, o contexto em torno dos tokens escritos não é importante para entender como eles são usados).

A análise PEG / Packrat e Earley são usadas muito menos: a análise de Earley é boa, pois pode lidar com muito mais gramáticas (incluindo aquelas que não são necessariamente livres de contexto), mas é menos eficiente (como afirma o dragão livro (seção 4.1.1); não tenho certeza se essas reivindicações ainda são precisas). Análise de Expressão de Análise + Análise de Packrat é um método relativamente eficiente e também pode lidar com mais gramáticas que LL e LR, mas oculta ambiguidades, conforme será abordado rapidamente abaixo.

LL (derivação da esquerda para a direita, mais à esquerda)

Esta é possivelmente a maneira mais natural de pensar em analisar. A idéia é examinar o próximo token na cadeia de entrada e decidir qual das várias chamadas recursivas possíveis a serem executadas para gerar uma estrutura em árvore.

Essa árvore é construída de cima para baixo, o que significa que começamos na raiz da árvore e percorremos as regras gramaticais da mesma maneira que percorremos a string de entrada. Também pode ser visto como a construção de um equivalente 'postfix' para o fluxo de token 'infix' que está sendo lido.

Os analisadores que executam a análise no estilo LL podem ser gravados para se parecerem muito com a gramática original especificada. Isso torna relativamente fácil de entender, depurar e aprimorá-los. Os Combinadores de Analisadores Clássicos nada mais são do que 'peças de lego' que podem ser montadas para criar um analisador no estilo LL.

LR (derivação da esquerda para a direita, mais à direita)

A análise de LR viaja de outra maneira, de baixo para cima: a cada etapa, os elementos superiores da pilha são comparados à lista de gramática, para ver se eles podem ser reduzidos a uma regra de nível superior na gramática. Se não, a próxima marca a partir do fluxo de entrada é deslocar ed e colocado no topo da pilha.

Um programa está correto se, no final, acabarmos com um único nó na pilha, que representa a regra inicial de nossa gramática.

Olhe para frente

Em um desses dois sistemas, às vezes é necessário espiar mais tokens da entrada antes de poder decidir qual escolha fazer. Esta é a (0), (1), (k)ou (*)-syntax você vê depois os nomes destes dois algoritmos gerais, como LR(1) ou LL(k). kgeralmente significa 'tanto quanto a sua gramática precisa', enquanto *normalmente significa 'esse analisador executa backtracking', que é mais poderoso / fácil de implementar, mas tem muito mais uso de memória e tempo do que um analisador que pode apenas continuar analisando linearmente.

Observe que os analisadores no estilo LR já possuem muitos tokens na pilha quando podem decidir 'olhar para o futuro'; portanto, eles já têm mais informações para despachar. Isso significa que eles geralmente precisam de menos atenção do que um analisador no estilo LL para a mesma gramática.

LL vs. LR: Ambiguidade

Ao ler as duas descrições acima, pode-se perguntar por que a análise no estilo LR existe, pois a análise no estilo LL parece muito mais natural.

No entanto, a análise no estilo LL tem um problema: Recursão à esquerda .

É muito natural escrever uma gramática como:

expr ::= expr '+' expr | term term ::= integer | float

Porém, um analisador no estilo LL fica preso em um loop recursivo infinito ao analisar esta gramática: Ao tentar a possibilidade mais à esquerda da exprregra, ele volta a essa regra novamente sem consumir nenhuma entrada.

Existem maneiras de resolver esse problema. O mais simples é reescrever sua gramática para que esse tipo de recursão não ocorra mais:

expr ::= term expr_rest expr_rest ::= '+' expr | ϵ term ::= integer | float (Aqui, ϵ significa a 'string vazia')

Essa gramática agora é recursiva. Observe que imediatamente é muito mais difícil de ler.

Na prática, a recursão à esquerda pode ocorrer indiretamente com muitas outras etapas intermediárias. Isso torna um problema difícil de olhar. Mas tentar resolvê-lo torna sua gramática mais difícil de ler.

Como a Seção 2.5 do Livro do Dragão afirma:

Parece que temos um conflito: por um lado, precisamos de uma gramática que facilite a tradução; por outro, precisamos de uma gramática significativamente diferente que facilite a análise. A solução é começar com a gramática para facilitar a tradução e transformá-la cuidadosamente para facilitar a análise. Ao eliminar a recursão esquerda, podemos obter uma gramática adequada para uso em um tradutor preditivo de descida recursiva.

Os analisadores no estilo LR não têm o problema dessa recursão à esquerda, pois eles constroem a árvore de baixo para cima. No entanto , a tradução mental de uma gramática como acima para um analisador no estilo LR (que geralmente é implementada como um autômato de estado finito )
é muito difícil (e propensa a erros), pois geralmente existem centenas ou milhares de estados + transições de estado a considerar. É por isso que os analisadores no estilo LR são geralmente gerados por um Gerador de Analisadores, também conhecido como 'compilador de compilador'.

Como resolver ambiguidades

Vimos dois métodos para resolver ambiguidades de recursão à esquerda acima: 1) reescrever a sintaxe 2) usar um analisador LR.

Mas existem outros tipos de ambiguidade que são mais difíceis de resolver: e se duas regras diferentes forem igualmente aplicáveis ​​ao mesmo tempo?

Alguns exemplos comuns são:

• expressões aritméticas.
• o Dangling Else

Os analisadores de estilo LL e LR têm problemas com eles. Problemas com a análise de expressões aritméticas podem ser resolvidos com a introdução da precedência do operador. De maneira semelhante, outros problemas como o Dangling Else podem ser resolvidos, escolhendo um comportamento de precedência e mantendo-o. (Em C / C ++, por exemplo, o dangling else sempre pertence ao 'if' mais próximo).

Outra 'solução' para isso é usar a Gramática de Expressão Parser (PEG): É semelhante à gramática BNF usada acima, mas no caso de uma ambiguidade, sempre 'escolha a primeira'. Obviamente, isso realmente não "resolve" o problema, mas oculta a existência de uma ambiguidade: os usuários finais podem não saber qual escolha o analisador faz, e isso pode levar a resultados inesperados.

Mais informações que são muito mais detalhadas do que este post, incluindo por que, em geral, é impossível saber se sua gramática não possui ambiguidades e as implicações disso é o maravilhoso artigo de blog LL e LR no contexto: Por que analisar ferramentas são difíceis . Eu recomendo; isso me ajudou muito a entender tudo o que estou falando agora.

50 anos de pesquisa

Mas a vida continua. Verificou-se que os analisadores de estilo LR 'normais' implementados como autômatos de estados finitos geralmente precisavam de milhares de estados + transições, o que era um problema no tamanho do programa. Assim, variantes como Simple LR (SLR) e LALR (Look-ahead LR) foram escritas que combinam outras técnicas para diminuir o autômato, reduzindo o espaço em disco e memória dos programas analisadores.

Além disso, outra maneira de resolver as ambiguidades listadas acima é usar técnicas generalizadas nas quais, no caso de uma ambiguidade, ambas as possibilidades são mantidas e analisadas: uma delas pode falhar ao analisar a linha (nesse caso, a outra possibilidade é a 'correto'), além de retornar ambos (e dessa maneira mostrar que existe uma ambiguidade), caso ambos estejam corretos.

Curiosamente, depois que o algoritmo Generalized LR foi descrito, descobriu-se que uma abordagem semelhante poderia ser usada para implementar analisadores Generalized LL , que é similarmente rápido ($ O (n ^ 3) $ complexidade de tempo para gramáticas ambíguas, $ O (n) $ para gramáticas completamente inequívocas, embora com mais contabilidade do que um analisador LR simples (LA), o que significa um fator constante mais alto), mas novamente permita que um analisador seja gravado no estilo descendente recursivo (descendente) que é muito mais natural para escrever e depurar.

Combinadores de analisadores, geradores de analisadores

Então, com essa longa exposição, chegamos agora ao cerne da questão:

Qual é a diferença de combinadores e geradores de analisador de analisador e quando um deve ser usado em detrimento do outro?

Eles são realmente diferentes tipos de animais:

Os analisadores de analisadores foram criados porque as pessoas escreviam analisadores de cima para baixo e perceberam que muitos deles tinham muito em comum .

Os geradores de analisadores foram criados porque as pessoas procuravam criar analisadores que não apresentavam os problemas que os analisadores de estilo LL tinham (isto é, analisadores de estilo LR), o que se mostrou muito difícil de fazer manualmente. Os mais comuns incluem o Yacc / Bison, que implementa (LA) LR).

Curiosamente, hoje em dia a paisagem está um pouco confusa:

• É possível escrever Combinadores de Analisadores que funcionam com o algoritmo GLL , resolvendo os problemas de ambiguidade que os analisadores clássicos de estilo LL tinham, sendo tão legíveis / compreensíveis quanto todos os tipos de análise de cima para baixo.

• Os geradores de analisadores também podem ser escritos para analisadores no estilo LL. O ANTLR faz exatamente isso e usa outras heurísticas (LL adaptável (*)) para resolver as ambiguidades que os analisadores clássicos de estilo LL tinham.

Em geral, criar um gerador de analisador de LR e depurar a saída de um gerador de analisador de estilo LR (LA) em execução na gramática é difícil, devido à conversão da gramática original para o formato LR 'de dentro para fora'. Por outro lado, ferramentas como Yacc / Bison tiveram muitos anos de otimizações e foram muito usadas na natureza, o que significa que muitas pessoas agora a consideram a maneira de fazer a análise e são céticas em relação a novas abordagens.

Qual deles você deve usar depende de quão difícil é sua gramática e de quão rápido o analisador precisa ser. Dependendo da gramática, uma dessas técnicas (/ implementações das diferentes técnicas) pode ser mais rápida, ter menor espaço de memória, espaço de disco menor ou ser mais extensível ou mais fácil de depurar do que as outras. Sua milhagem pode variar .

Nota lateral: Sobre o assunto da Análise Lexical.

A análise lexical pode ser usada para combinadores de analisadores e geradores de analisadores. A idéia é ter um analisador "burro" que é muito fácil de implementar (e, portanto, rápido), que realiza uma primeira passagem pelo seu código-fonte, removendo, por exemplo, a repetição de espaços em branco, comentários, etc., e possivelmente "tokenização" de maneira grosseira os diferentes elementos que compõem seu idioma.

A principal vantagem é que este primeiro passo torna o analisador real muito mais simples (e por causa disso possivelmente mais rápido). A principal desvantagem é que você tem uma etapa de tradução separada e, por exemplo, o relatório de erros com números de linha e coluna fica mais difícil devido à remoção do espaço em branco.

Um lexer no final é 'apenas' outro analisador e pode ser implementado usando qualquer uma das técnicas acima. Devido à sua simplicidade, geralmente são utilizadas outras técnicas além do analisador principal e, por exemplo, existem 'geradores de lexer' extras.

Tl; Dr:

Aqui está um fluxograma aplicável à maioria dos casos:

Para entradas que são garantidas como livres de erros de sintaxe ou onde uma aprovação / falha geral na correção sintática é aceitável, os combinadores de analisadores são muito mais simples de trabalhar, especialmente em linguagens de programação funcionais. São situações como quebra-cabeças de programação, leitura de arquivos de dados etc.

O recurso que faz você desejar adicionar a complexidade dos geradores de analisadores é a mensagem de erro. Você deseja mensagens de erro que apontem o usuário para uma linha e coluna e, esperançosamente, também sejam compreensíveis por um ser humano. É preciso muito código para fazer isso corretamente, e os melhores geradores de analisadores, como o antlr, podem ajudá-lo.

No entanto, a geração automática só pode chegar até você, e a maioria dos compiladores de código aberto comercial e de longa duração acaba escrevendo manualmente seus analisadores. Presumo que, se você se sentisse à vontade para fazer isso, não teria feito essa pergunta, por isso recomendo ir com o gerador de analisador.

Sam Harwell, um dos mantenedores do gerador de analisador ANTLR, escreveu recentemente :

Eu encontrei [combinadores] não atendem às minhas necessidades:

1. O ANTLR me fornece ferramentas para gerenciar coisas como ambiguidades. Durante o desenvolvimento, existem ferramentas que podem me mostrar resultados de análise ambíguos para que eu possa eliminar essas ambiguidades na gramática. No tempo de execução, eu posso aproveitar a ambiguidade resultante de entrada incompleta no IDE para produzir resultados mais precisos em recursos como conclusão de código.
2. Na prática, descobri que os combinadores de analisadores não eram adequados para atender às minhas metas de desempenho. Parte disso remonta
3. Quando os resultados da análise são usados ​​para recursos como estrutura de tópicos, conclusão de código e recuo inteligente, é fácil que mudanças sutis na gramática afetem a precisão desses resultados. O ANTLR fornece ferramentas que podem transformar essas incompatibilidades em erros de compilação, mesmo nos casos em que os tipos seriam compilados. Posso prototipar com confiança um novo recurso de linguagem que afeta a gramática, sabendo que todo o código adicional que forma o IDE fornecerá uma experiência completa para o novo recurso desde o início. Meu fork do ANTLR 4 (no qual o destino C # se baseia) é a única ferramenta que eu conheço que até tenta fornecer esse recurso.

Essencialmente, os combinadores de analisadores são um brinquedo legal para brincar, mas eles simplesmente não são projetados para fazer um trabalho sério.

Como Karl menciona, os geradores de analisadores tendem a ter um melhor relatório de erros. Além do que, além do mais:

• eles tendem a ser mais rápidos, pois o código gerado pode ser especializado para a sintaxe e gerar tabelas de salto para o lookahead.
• eles tendem a ter ferramentas melhores, identificar sintaxe ambígua, remover a recursão esquerda, preencher ramificações de erro etc.
• eles tendem a lidar melhor com definições recursivas.
• eles tendem a ser mais robustos, uma vez que os geradores demoram mais tempo e fazem mais do que é necessário, reduzindo a chance de você estragar tudo.

Por outro lado, os combinadores têm suas próprias vantagens:

• eles estão no código; portanto, se sua sintaxe variar em tempo de execução, você poderá alterar com mais facilidade as coisas.
• eles tendem a ser mais fáceis de vincular e realmente consumir (a saída dos geradores de analisadores tende a ser muito genérica e desajeitada de usar).
• eles estão no código; portanto, tendem a ser um pouco mais fáceis de depurar quando sua gramática não faz o que você espera.
• eles tendem a ter uma curva de aprendizado mais superficial, pois funcionam como qualquer outro código. Os geradores de analisadores tendem a ter suas próprias peculiaridades para aprender a fazer as coisas funcionarem.