Isso faz parte de uma série de perguntas que se concentram no projeto irmão do Abstraction Project, que visa abstrair os conceitos usados no design de linguagem na forma de uma estrutura. O projeto irmão é chamado OILexer, que visa construir um analisador a partir de arquivos gramaticais, sem o uso de injeção de código em correspondências.
Algumas outras páginas associadas a essas perguntas, relacionadas à tipagem estrutural, podem ser visualizadas aqui , e a facilidade de uso, encontrada aqui . O meta-tópico associado a uma consulta sobre a estrutura e o local apropriado para publicação pode ser encontrado aqui .
Estou chegando ao ponto em que estou prestes a começar a extrair a árvore de análise de uma determinada gramática, seguida por um analisador de Descida Recursiva que usa o DFA para discernir caminhos avançados (semelhante ao LL do ANTLR 4 (*)), então eu achei que eu iria abri-lo para ter uma ideia.
Em um compilador de analisador, que tipos de recursos são ideais?
Até agora, aqui está uma breve visão geral do que é implementado:
- Modelos
- Preveja a previsão, sabendo o que é válido em um determinado momento.
- Regra 'Deliteralização', levando os literais dentro das regras e resolvendo de qual token eles são.
- Autômatos não determinísticos
- Autômatos determinísticos
- Máquina de estado lexical simples para reconhecimento de token
- Métodos de automação de token:
- Varredura - útil para comentários: Comentário: = "/ *" Varredura ("* /");
- Subtrair - Útil para Identificadores: Identificador: = Subtrair (IdentifierBody, Palavras-chave);
- Garante que o identificador não aceite palavras-chave.
- Codificar - Codifica uma automação como uma contagem X da série de transições de base N.
- UnicodeEscape: = "\\ u" BaseEncode (IdentifierCharNoEscape, 16, 4);
- Faz um escape unicode em hexadecimal, com 4 transições hexadecimais. A diferença entre isso e: [0-9A-Fa-f] {4} é que a automação resultante com Encode limita o conjunto permitido de valores hexadecimais ao escopo do IdentifierCharNoEscape. Portanto, se você especificar \ u005c, a versão do código não aceitará o valor. Coisas assim têm uma advertência séria: use com moderação. A automação resultante pode ser bastante complexa.
- UnicodeEscape: = "\\ u" BaseEncode (IdentifierCharNoEscape, 16, 4);
O que não é implementado é a geração de CST, preciso ajustar as automações determinísticas para manter o contexto adequado para que isso funcione.
Para qualquer pessoa interessada, enviei uma linda versão impressa da forma original do projeto T * y♯ . Cada arquivo deve ser vinculado a qualquer outro arquivo. Comecei a vincular as regras individuais para segui-las, mas isso levaria muito tempo (seria mais fácil automatizar!)
Se for necessário mais contexto, poste em conformidade.
Editar 14-14-2013 : escrevi código para criar gráficos GraphViz para as máquinas de estado em um determinado idioma. Aqui está um dígrafo GraphViz da AssemblyPart . Os membros vinculados na descrição do idioma devem ter um rulename.txt em sua pasta relativa, com o dígrafo dessa regra. Parte da descrição do idioma mudou desde que eu postei o exemplo, isso se deve à simplificação das coisas sobre a gramática. Aqui está uma imagem gráfica interessante .
fonte
Respostas:
Esta é uma excelente pergunta.
Eu tenho trabalhado em várias análises recentemente, e IMHO algumas das principais características são:
uma API programática - para que possa ser usada em uma linguagem de programação, de preferência simplesmente importando uma biblioteca. Também pode ter uma interface GUI ou semelhante a BNF, mas a programática é a chave, porque você pode reutilizar suas ferramentas, IDE, análise estática, teste, recursos de abstração de linguagem, familiaridade com o programador, gerador de documentação, processo de construção, etc. Além disso, você pode jogar interativamente com pequenos analisadores, o que reduz drasticamente a curva de aprendizado. Esses motivos o colocam no topo da minha lista de "recursos importantes".
relatório de erros, como @guysherman mencionado. Quando um erro é encontrado, quero saber onde estava o erro e o que estava acontecendo quando aconteceu. Infelizmente, não consegui encontrar bons recursos para explicar como gerar erros decentes quando o backtracking entra em ação. (Embora observe o comentário da Sk-logic abaixo).
resultados parciais. Quando a análise falha, desejo poder ver o que foi analisado com êxito da parte da entrada que estava antes da localização do erro.
abstração. Você nunca pode criar funções suficientes, e o usuário sempre precisará de mais; portanto, tentar descobrir todas as funções possíveis antecipadamente está fadado ao fracasso. É isso que você quer dizer com modelos?
Eu concordo com o seu nº 2 (previsão antecipada). Eu acho que ajuda a gerar bons relatórios de erro. É útil para mais alguma coisa?
suporte para a construção de uma árvore de análise à medida que a análise ocorre, talvez:
algum tipo de registro. Eu não tenho certeza sobre este; talvez para mostrar um rastro das regras que o analisador tentou, ou para acompanhar tokens indesejados, como espaço em branco ou comentários, caso (por exemplo) você queira usar os tokens para gerar documentação em HTML.
capacidade de lidar com linguagens sensíveis ao contexto. Também não tenho certeza do quanto isso é importante - na prática, parece mais limpo analisar um superconjunto de uma linguagem com uma gramática livre de contexto e depois verificar restrições sensíveis ao contexto em outras passagens posteriores.
mensagens de erro personalizadas, para que eu possa ajustar os relatórios de erros em situações específicas e, talvez, entender e corrigir problemas mais rapidamente.
Por outro lado, não acho a correção de erros particularmente importante - embora não esteja atualizado sobre o progresso atual. Os problemas que notei são que as possíveis correções fornecidas pelas ferramentas são: 1) muito numerosas e 2) não correspondem aos erros reais cometidos e, portanto, não são tão úteis. Esperemos que esta situação melhore (ou talvez já o tenha feito).
fonte
Não tenho experiência em design de linguagem, mas já escrevi um analisador uma vez, quando estava criando um IDE para um mecanismo de jogo.
Algo que é importante para seus usuários finais, na minha opinião, são as mensagens de erro que fazem sentido. Não é um ponto particularmente devastador, eu sei, mas, seguindo-o de trás para frente, uma das principais implicações disso é que você precisa ser capaz de evitar falsos positivos. De onde vêm os falsos positivos? Eles vêm do analisador caindo no primeiro erro e nunca se recuperando. O C / C ++ é notório por isso (embora os compiladores mais recentes sejam um pouco mais inteligentes).
Então, o que você precisa? Eu acho que, em vez de apenas saber o que é / não é válido em um momento, você precisa saber como pegar o que não é válido e fazer uma alteração mínima para torná-lo válido - para que você possa continuar analisando sem gerar erros falsos relacionados a sua descida recursiva ficando confusa. A capacidade de criar um analisador que pode gerar essas informações não apenas fornece um analisador muito robusto, mas também abre alguns recursos fantásticos para o software que consome o analisador.
Sei que posso estar sugerindo algo realmente difícil, ou estupidamente óbvio, desculpe se esse for o caso. Se esse não é o tipo de coisa que você procura, excluirei minha resposta.
fonte
A gramática não deve ter restrições como "não deixou regras recursivas". É ridículo que ferramentas amplamente utilizados hoje em dia ter isso e só pode compreender sucção gramáticas LL - quase 50 anos depois yacc fez o certo.
Um exemplo de recursão correta (usando a sintaxe yacc):
Um exemplo de recursão à esquerda (usando yacc synatx):
Agora, isso pode ser "refatorado" para outra coisa, mas em ambos os casos, o tipo específico de recursão é apenas a maneira "certa" de escrever isso, pois (no idioma do exemplo) as listas são recursivas à direita, enquanto a aplicação da função é deixada recursiva .
Pode-se esperar de ferramentas avançadas que elas apóiam a maneira natural de escrever coisas, em vez de exigir que "refatore" tudo para que fique a esquerda / direita, de forma recursiva que a ferramenta impõe a uma.
fonte
*
ou+
quantificadores)? Admito livremente que meu conhecimento nesta área é limitado, mas nunca me deparei com um recurso de recursão à esquerda que não pudesse ser refatorado em repetição. E achei a versão de repetição mais clara também (embora isso seja apenas uma preferência pessoal).list = sepBy1(',', elem)
efunapp = term{+}
(e, é claro,sepBy1
e+
seria implementado em termos de recursão esquerda / direita, e produzir árvores de sintaxe padrão). Portanto, não é que eu ache ruim a recursão esquerda e direita, apenas sinto que eles são de baixo nível e gostariam de usar uma abstração de nível superior sempre que possível para tornar as coisas mais claras. Obrigado novamente!