Как именно компилятор восстанавливается после ошибки типа?

Я прочитал несколько статей, статей и раздел 4.1.4, глава 4 « Компиляторы: принципы, методы и инструменты» (2-е издание) (он же «Книга Дракона»), в которых все обсуждается тема исправления синтаксических ошибок компилятора. Однако, после экспериментов с несколькими современными компиляторами, я увидел, что они также восстанавливаются после семантических ошибок, а также синтаксических ошибок.

Я достаточно хорошо понимаю алгоритмы и методы, лежащие в основе компиляторов, восстанавливающихся после синтаксически связанных ошибок, однако я не совсем понимаю, как компилятор может восстанавливаться после семантической ошибки.

В настоящее время я использую небольшой вариант шаблона посетителя для генерации кода из моего абстрактного синтаксического дерева. Рассмотрим мой компилятор, компилирующий следующие выражения:

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

Компилятор сгенерирует следующее абстрактное синтаксическое дерево:

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

Фаза генерации кода будет затем использовать шаблон посетителя для рекурсивного обхода абстрактного синтаксического дерева и выполнения проверки типов. Абстрактное синтаксическое дерево будет проходить до тех пор, пока компилятор не перейдет к самой внутренней части выражения; (3 + "4"), Затем компилятор проверяет каждую сторону выражений и видит, что они не являются семантически эквивалентными. Компилятор вызывает ошибку типа. Вот в чем проблема. Что теперь должен делать компилятор ?

Чтобы компилятор восстановился после этой ошибки и продолжил проверку типов внешних частей выражений, он должен был бы вернуть некоторый тип ( intили str) из оценки самой внутренней части выражения в следующую самую внутреннюю часть выражения. Но у него просто нет типа для возврата . Поскольку произошла ошибка типа, тип не был выведен.

Одно возможное решение, которое я постулировал, заключается в том, что если ошибка типа действительно возникает, она должна возникать, и к предыдущим вызовам обхода дерева абстрактного синтаксиса должно возвращаться специальное значение, которое означает, что произошла ошибка типа. Если предыдущие вызовы обхода встречают это значение, они знают, что ошибка типа произошла глубже в абстрактном синтаксическом дереве, и должны избегать попыток определить тип. Хотя этот метод, похоже, работает, он кажется очень неэффективным. Если самая внутренняя часть выражения находится глубоко в абстрактном синтаксическом дереве, то компилятору придется совершать много рекурсивных вызовов только для того, чтобы понять, что никакая реальная работа не может быть выполнена, и просто возвращаться из каждого из них.

Используется ли метод, который я описал выше (я сомневаюсь в этом). Если так, разве это не эффективно? Если нет, какие именно методы используются, когда компиляторы восстанавливаются после семантических ошибок?

Ваша предложенная идея по существу верна.

Ключ в том, что тип узла AST вычисляется только один раз, а затем сохраняется. Всякий раз, когда тип нужен снова, он просто извлекает сохраненный тип. Если разрешение заканчивается ошибкой, вместо нее сохраняется тип ошибки.

Один интересный подход - иметь специальный тип для ошибок. Когда такая ошибка встречается впервые, регистрируется диагностика, и тип ошибки возвращается в качестве типа выражения. Этот тип ошибки имеет некоторые интересные свойства:

• Любая операция, выполняемая над ним, завершается успешно (чтобы предотвратить каскад сообщений об ошибках, вызванных одной и той же первоначальной ошибкой)
• Результат любой операции, выполненной над объектом с типом ошибки, также имеет тип ошибки
• Если тип ошибки доходит до генерации кода, генератор кода обнаруживает использование и генерирует код, который дает сбой (например, генерирует исключение, прерывает или что-либо, что подходит для вашего языка)

С помощью этой комбинации вы можете фактически успешно скомпилировать код, содержащий ошибки типов, и пока этот код фактически не используется, ошибки времени выполнения не возникнут. Это может быть полезно, например, чтобы позволить вам запускать модульные тесты для частей кода, которые не затрагиваются.

Если есть семантическая ошибка, пользователю выдается сообщение об ошибке компиляции, указывающее на это.

Как только это будет сделано, можно прервать компиляцию, поскольку входная программа содержит ошибку - это не является допустимой программой на языке, поэтому ее можно просто отклонить.

Это довольно резко, так что есть более мягкие альтернативы. Прервите генерацию кода и генерацию выходного файла, но продолжайте искать другие ошибки.

Например, он может просто прервать любой дальнейший анализ типов для текущего дерева выражений и продолжить обработку выражений из последующих операторов.

Давайте предположим, что ваш язык позволяет добавлять целые числа и позволяет объединять строки с +оператором.

Поскольку int + stringэто не разрешено, оценка +приведет к сообщению об ошибке. Компилятор может просто вернуться errorкак тип. Или это может быть более умным, так как int + int -> intи string + string -> stringдопускается, он может возвращать «ошибка, может быть int или string».

Затем приходит *оператор, и мы будем предполагать, что только int + intразрешено. Затем компилятор может решить, что +фактически должен был быть возвращен int, и тип, возвращаемый для, *будет intбез каких-либо сообщений об ошибках.