Como faço para implementar a frente referências em um compilador?

Question

Estou criando um compilador com Lex e YACC (na verdade Flex e Bison). A linguagem permite referências à frente ilimitadas para qualquer símbolo (como C #). O problema é que é impossível analisar a linguagem sem saber o que um identificador é.

A única solução que eu conheço é a lex toda a fonte, e depois fazer uma análise "em largura", as coisas nível tão superiores, como declarações de classe e declarações de função ter analisado antes das funções que os utilizam. No entanto, isso levaria uma grande quantidade de memória para arquivos grandes, e seria difícil de lidar com YACC (eu teria que criar gramáticas separadas para cada tipo de declaração / corpo). Eu também teria de mão-escrever o lexer (que não é muito de um problema).

Eu não me importo muito sobre a eficiência (embora ainda seja importante), porque eu vou reescrever o compilador em si mesma uma vez que eu terminá-lo, mas eu quero que a versão a ser rápido (por isso, se existem qualquer técnicas rápido gerais que não pode ser feito em Lex / YACC, mas pode ser feito à mão, por favor sugerir-lhes também). Então, agora, facilidade de desenvolvimento é o fator mais importante.

Existem boas soluções para este problema? Como isso é feito geralmente em compiladores para linguagens como C # ou Java?

Answer 1

É inteiramente possível analisá-lo. Embora haja uma ambigüidade entre identificadores e palavras-chave, lex terá todo o prazer lidar com isso, dando a prioridade palavras-chave.

Eu não ver o que outros problemas existem. Você não precisa para determinar se os identificadores são válidos durante a fase de análise. Você está construindo ou uma árvore de análise ou uma árvore de sintaxe abstrata (a diferença é sutil, mas irrelevante para os fins desta discussão) como você analisar. Depois que você construir suas estruturas símbolo tabela aninhada realizando uma passagem sobre a AST você gerou durante a análise. Então você faz uma outra passagem sobre a AST para verificar se identificadores utilizados são válidos. Siga este com um ou mais parses sobre a AST para gerar o código de saída, ou alguma outra estrutura de dados intermediário e está feito!

EDIT: Se você quiser ver como ele é feito, verificar o código-fonte para o compilador Mono C #. Este é escrito em C #, em vez de C ou C ++, mas não porta uso .NET de Jay, que é muito similar ao yacc.

Answer 2

Uma opção é lidar com referências à frente por apenas digitalização e armazenamento em cache os tokens até que você bater em alguma coisa você sabe como real com (algo como a recuperação de erros "pânico-mode"). Depois de ter executado pensou que o arquivo completo, volte e tente re parse os bits que não o fizeram análise antes.

Como a ter que escrever a mão do lexer; não, o uso lex para gerar um analisador normal e apenas lê-lo através de um calço escrito à mão que lhe permite voltar e alimentar o analisador de um cache, bem como o lex marcas.

Como a fazer várias gramáticas, um pouco de diversão com um pré-processador no arquivo yacc e você deve ser capaz de fazê-los todos para fora da mesma fonte original