Escrevendo um compilador Compiler - Insight on Use and Features

10

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:

  1. Modelos
  2. Preveja a previsão, sabendo o que é válido em um determinado momento.
  3. Regra 'Deliteralização', levando os literais dentro das regras e resolvendo de qual token eles são.
  4. Autômatos não determinísticos
  5. Autômatos determinísticos
  6. Máquina de estado lexical simples para reconhecimento de token
  7. 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.

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 .

Alexander Morou
fonte
8
Parede de texto. Não leve a mal, aprecio um problema completamente explicado. Nesse caso, é simplesmente um pouco detalhado demais. Pelo que reuni, você está perguntando quais recursos devem ser incluídos em um analisador de gramática ou como fazer um sem começar do zero? Edite para responder às seguintes perguntas (você não precisa reescrever, basta anexar ao final no resumo): Qual é o seu problema? Com quais restrições você está limitado em possíveis soluções para o seu problema (ele deve ser rápido, deve ser LL *, etc.)?
Neil
11
Estou pedindo informações sobre o conjunto de recursos. O foco está na facilidade de uso. A dificuldade está em conseguir que alguém que não conheça o projeto perceba o projeto, para que seja informado sobre seu foco. Não estou perguntando 'como fazer', estou perguntando relacionado à usabilidade. Sugestões sobre como aparar a pergunta são bem-vindas.
Allen Clark Copeland Jr
11
Para mim, não é óbvio do que se trata o projeto. Por exemplo, desde os dias de yacc, vimos muitos geradores de analisadores. O que é diferente no seu OILexer? Qual e a novidade?
Ingo
11
O objetivo deste projeto é simplificar a geração do analisador. Semelhante sim, ao YACC / Bison e FLEX / LEX. A principal diferença é evitar a complexidade envolvida nesses programas. Manter as coisas simples e objetivas é o objetivo principal. É por isso que criei um formato desprovido de seções ímpares, mas o objetivo é torná-lo semelhante à programação regular: específica apenas para o desenvolvimento da linguagem. Os tokens são definidos usando ': =' após o nome, as regras são definidas usando :: = após o nome. Os modelos usam '<' e '>' para seus argumentos, seguidos por ":: =", pois compartilham a sintaxe da regra.
Allen Clark Copeland Jr
3
Esse foco infernal na análise parece fora de lugar; é um problema bem resolvido e dificilmente é o que você precisa para processar linguagens de programação. Google para o meu ensaio sobre "a vida depois de analisar".
Ira Baxter

Respostas:

5

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:

    • uma árvore de sintaxe concreta, para a qual a estrutura da árvore corresponde diretamente à gramática e inclui informações de layout para relatórios de erros de fases posteriores. Nesse caso, o cliente não precisa fazer nada para obter a estrutura de árvore correta - ele deve depender diretamente da gramática.
    • uma árvore de sintaxe abstrata. Nesse caso, o usuário pode mexer com toda e qualquer árvore de análise
  • 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
Editei o corpo da pergunta para incluir um link para o PrecedenceHelper no marcador que diz 'Modelos'. Ele permite tuplas de matriz de parâmetros; portanto, se você tiver quatro parâmetros, cada matriz de parâmetro, o modelo deverá ser usado em conjuntos de argumentos de quatro.
Allen Clark Copeland Jr
O principal motivo para você construir o CST é o layout geral do arquivo analisado. Se você deseja imprimir o documento de maneira bonita, sua melhor aposta é usar um CST porque os ASTs, como o nome indica, carecem de informações para lidar com o espaçamento ímpar que um CST capturaria. Transformar um CST geralmente é bastante fácil se for um bom CST.
Allen Clark Copeland Jr
Editei a pergunta novamente sobre o tópico de funções internas disponíveis para uso.
Allen Clark Copeland Jr
Eu acho que não fiz um ótimo trabalho ao expressar meu ponto de vista sobre modelos / funções: quis dizer que, como você nunca pode ter o suficiente, um sistema não deve tentar descobri-los antes do tempo: o usuário precisa ser capaz de criar seu próprio.
11
Eu achei uma abordagem particularmente útil para o relatório de erros com backtracking infinito (Packrat): cada regra de produção é anotada com mensagens de erro (com a palavra "blá-blá-blá esperado") e, quando falha, essa mensagem é armazenada no fluxo da mesma maneira como tokens memorizados. Se todas as falhas não puderem ser recuperadas (a análise terminou antes de chegar ao final do fluxo), a mensagem de erro mais à direita (ou uma coleção dessas mensagens) é a mais apropriada. Essa é a coisa mais fácil de fazer, é claro que existem maneiras de refinar ainda mais com mais anotações.
SK-logic
5

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.

rapaz
fonte
Esta é uma das coisas que pretendo fazer. Para ajudar no meu conhecimento do domínio, um amigo meu sugeriu escrever um analisador à mão para pegar o jeito de automatizá-lo. Uma coisa eu percebi rapidamente: os analisadores são complexos e existem coisas que fazemos manualmente que simplificam o processo. Regras e modelos compartilham a mesma sintaxe; no entanto, existem elementos de linguagem que são válidos em modelos, mas não em regras; há estados internos que lidam com essa tarefa. O que trouxe uma idéia à mente: as regras devem poder especificar auxílios de caminho para facilitar o compartilhamento de sub-regras.
Allen Clark Copeland Jr
... isso deve ser bastante simples de transportar para a automação, mas exigiria que as automações tivessem condições baseadas em estado. Vou trabalhar nisso um pouco e voltar para você. O ANTLR usa automações de estado finito para lidar com ciclos de digamos: "T" *, onde eu o usarei para lidar com a maior parte do processo de análise, pois as reduções devem ser mais limpas do que quando há mais de 800 variações em uma regra (isso iria inchar rapidamente quanto código espaguete em if / else forma standard).
Allen Clark Copeland Jr
0

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):

list: 
      elem                  { $$ = singleton($1); }
    | elem ',' list         { $$ = cons($1, $2);  }
    ;

Um exemplo de recursão à esquerda (usando yacc synatx):

funapp:
    term                    { $$ = $1; }
    | funapp term           { $$ = application($1, $2); }
    ;

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.

Ingo
fonte
Sim, é bom não ter restrições arbitrárias como essa. No entanto, qual é um exemplo de recursão à esquerda que não pode ser substituído por um operador de repetição (como regexes *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).
11
@MattFenwick Veja minha edição. Observe como a sintaxe diretamente leva a ações semânticas simples e naturais (por exemplo) para criar uma árvore de sintaxe. Enquanto estiver repetindo (que não está disponível no yacc, btw), acho que você frequentemente precisa verificar se tem uma lista vazia, um singleton etc.
Ingo
Obrigado pela resposta. Eu acho que entendo melhor agora - eu preferiria escrever esses exemplos como list = sepBy1(',', elem)e funapp = term{+}(e, é claro, sepBy1e +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!
11
De nada @MattFenwick. Mas então talvez seja uma questão de gosto. Para mim, a recursão é (pelo menos no contexto das línguas, que são inerentemente recursivas ou totalmente desinteressantes) a maneira mais natural de pensar nisso. Além disso, uma árvore é uma estrutura de dados recursiva, portanto não vejo necessidade de voltar à iteração para simular a recursão. Mas, é claro, as preferências são diferentes.
Ingo