Como exatamente um compilador se recupera de um erro de tipo?

Eu li vários artigos, artigos e a seção 4.1.4, capítulo 4 de Compiladores: Princípios, Técnicas e Ferramentas (2ª Edição) (também conhecida como "O Livro do Dragão"), que discutem o tópico da recuperação de erro de compilador sintático. No entanto, depois de experimentar vários compiladores modernos, vi que eles também se recuperam de erros semânticos e de sintaxe.

Entendo muito bem os algoritmos e as técnicas por trás dos compiladores que se recuperam de erros sintaticamente relacionados, mas não entendo exatamente como um compilador pode se recuperar de um erro semântico.

Atualmente, estou usando uma ligeira variação do padrão de visitante para gerar código da minha árvore de sintaxe abstrata. Considere meu compilador compilando as seguintes expressões:

1 / (2 * (3 + "4"))

O compilador geraria a seguinte árvore de sintaxe abstrata:

      op(/)
        |
     -------
    /       \ 
 int(1)    op(*)
             |
          -------
         /       \
       int(2)   op(+)
                  |
               -------
              /       \
           int(3)   str(4)

A fase de geração de código usaria o padrão de visitante para percorrer recursivamente a árvore de sintaxe abstrata e executar a verificação de tipo. A árvore de sintaxe abstrata seria percorrida até que o compilador chegasse à parte mais interna da expressão; (3 + "4"). O compilador verifica cada lado das expressões e vê que elas não são semanticamente equivalentes. O compilador gera um erro de tipo. Aqui é onde está o problema. O que agora o compilador deve fazer ?

Para que o compilador se recupere desse erro e continue verificando as partes externas das expressões, ele precisará retornar algum tipo ( intou str) da avaliação da parte mais interna da expressão para a próxima parte mais interna da expressão. Mas ele simplesmente não tem um tipo para retornar . Como ocorreu um erro de tipo, nenhum tipo foi deduzido.

Uma solução possível que eu postulei é que, se ocorrer um erro de tipo, um erro deve ser gerado e um valor especial que significa que ocorreu um erro de tipo deve ser retornado para as chamadas anteriores da árvore de sintaxe abstrata. Se chamadas transversais anteriores encontrarem esse valor, eles sabem que ocorreu um erro de tipo mais profundo na árvore de sintaxe abstrata e devem evitar tentar deduzir um tipo. Embora esse método pareça funcionar, parece ser muito ineficiente. Se a parte mais interna de uma expressão estiver profunda na árvore de sintaxe abstrata, o compilador precisará fazer muitas chamadas recursivas apenas para perceber que nenhum trabalho real pode ser feito e simplesmente retornar de cada uma.

O método que eu descrevi acima foi usado (duvido). Se sim, não é eficiente? Caso contrário, quais são exatamente os métodos usados ​​quando os compiladores se recuperam de erros semânticos?

Sua ideia proposta é essencialmente correta.

A chave é que o tipo de um nó AST é calculado apenas uma vez e depois armazenado. Sempre que o tipo é necessário novamente, ele simplesmente recupera o tipo armazenado. Se a resolução terminar com um erro, um tipo de erro será armazenado.

Uma abordagem interessante é ter um tipo especial para erros. Quando esse erro é encontrado pela primeira vez, um diagnóstico é registrado e o tipo de erro é retornado como o tipo da expressão. Este tipo de erro tem algumas propriedades interessantes:

• Qualquer operação executada é bem-sucedida (para evitar uma cascata de mensagens de erro causadas pela mesma falha original)
• O resultado de qualquer operação executada em um objeto com tipo de erro também possui um tipo de erro
• Se um tipo de erro chegar até a geração do código, o gerador de código identifica o uso e gera código que falha (por exemplo, gera uma exceção, aborta ou o que for apropriado para o seu idioma)

Com essa combinação, é possível compilar com êxito o código que contém erros de tipo e, desde que esse código não seja realmente usado, nenhum erro de tempo de execução ocorrerá. Isso pode ser útil, por exemplo, para permitir que você execute testes de unidade para partes do código que não são afetadas.

Se houver um erro semântico, uma mensagem de erro de compilação indicando que é emitida para o usuário.

Uma vez feito isso, não há problema em interromper a compilação, pois o programa de entrada está com erro - não é um programa legal no idioma, portanto pode ser simplesmente rejeitado.

Isso é bastante duro, no entanto, então existem alternativas mais suaves. Interrompa qualquer geração de código e geração de arquivos de saída, mas continue procurando algo para obter mais erros.

Por exemplo, ele pode simplesmente interromper qualquer análise de tipo adicional para a árvore de expressões atual e continuar processando expressões de instruções subseqüentes.

Vamos supor que seu idioma permita adicionar números inteiros e concatenar seqüências de caracteres com o +operador.

Como int + stringnão é permitido, avaliar o +resultado resultará em um erro sendo relatado. O compilador pode retornar errorcomo o tipo Ou pode ser mais inteligente, pois, int + int -> inte, se string + string -> stringfor permitido, pode retornar "erro, pode ser int ou string".

Depois vem o *operador, e assumiremos que apenas int + inté permitido. O compilador pode então decidir que +realmente deveria retornar inte o tipo retornado para o *seria int, sem nenhuma mensagem de erro.