O que é uma boa ferramenta para calcular automaticamente os conjuntos primeiro e seguir?

Question

Atualmente, estou no meio de brincar com uma gramática BNF que espero poder disputar um formulário LL (1). No entanto, acabei de fazer alterações e calcular o novo primeiro e seguir conjuntos para a gramática à mão pela terceira vez hoje e estou cansado disso. Tem que haver uma maneira melhor!

Alguém pode sugerir uma ferramenta que, dada uma gramática, calculará automaticamente o primeiro e seguirá conjuntos para todos os não terminais?

Answer 1

Há um ano, tínhamos um projeto semestral na universidade em que participei, onde nossa tarefa era criar uma linguagem de programação. Como um grupo, decidimos que queríamos poder escrever manualmente o analisador do zero, então tivemos que buscar uma gramática LL (1), pois seria completamente irrealista escrever um analisador de outra forma.

Obviamente, nosso ponto de partida estava longe de ser LL (1), então também tivemos que arrancá -lo no lugar. Para esse fim, usamos a ferramenta Kfgedit do Atocc pacote. Tudo o que você faz é inserir suas regras e, em seguida, pode verificar se é uma gramática LL (1) com o clique de um botão.

Uma palavra justa de aviso: a ferramenta é um pouco fina sobre o que aceita. Enquanto você costumava usar o EBNF para a gramática real, para poder escrever? e * e + para sinalizar quantas vezes esse token deve aparecer lá, isso não é suportado. O agrupamento também não é suportado. Você pode muito bem achar que leva muito tempo para fazer isso, e quase certamente desejará fazer algum "reorganização" depois de chegar a LL (1) para tornar a gramática até perto de ser legível.

Obviamente, dependendo do tipo de gramática com a qual você está lidando, isso pode não ser um grande problema para você. Tínhamos criado uma espécie de híbrido Pascal/C, com um conjunto bastante restrito de construções (procedimentos, funções, apenas tipos primitivos e matrizes embutidos deles, ses, uma única construção de loop que criamos em lugares no lugar de O padrão 3 ...), e levei pelo menos uma semana para arrancá -lo em uma gramática LL (1) - provavelmente 2, na verdade. Observe que isso está fora de um total de cerca de 4 meses, então isso foi muito tempo gasto lá.

Se você absolutamente deve ter uma gramática LL (1), obviamente precisará continuar se entrar em uma situação como essa, mas se tiver permissão para usar geradores de analisador como YACC/BISON ou SABLECC, então você irá, em O longo prazo, provavelmente acham muito mais fácil seguir esse caminho. Isso não significa que você deve seguir esse caminho - descobri que realmente escrever tudo à mão forneceu algumas dicas que provavelmente não teria ganho de outra forma - mas pode ser melhor você obter essa visão em uma situação diferente da sua atualidade .

TL; dr versão: use kfgedit do Atocc pacote.

Answer 2

Para análise de descida recursiva, valeria a pena olhar Antlr. No entanto, não tenho certeza de que ele fornece uma resposta exata para sua pergunta - encontre os primeiros e siga conjuntos para uma determinada gramática.

Answer 3

o DMS Software Reengeneering Toolkit tem um gerador de pastores que calcula primeiro e segue conjuntos; Também permitirá que você inspecione a máquina de estado L (Al) R que gera.

No entanto, se você tem uma gramática legítima sem contexto, não precisa "arrancá-lo" em forma de LL; O gerador de analisador DMS produz analisadores GLR a partir de qualquer gramática sem contexto.