Какова общая процедура, используемая, когда компиляторы статически проверяют тип «сложных» выражений?

Примечание: когда я использовал «сложный» в заголовке, я имею в виду, что выражение имеет много операторов и операндов. Не то чтобы само выражение было сложным.

Недавно я работал над простым компилятором для сборки x86-64. Я закончил основной внешний интерфейс компилятора - лексер и парсер - и теперь могу генерировать представление абстрактного синтаксического дерева моей программы. И так как мой язык будет статически типизирован, я сейчас делаю следующий этап: проверка типа исходного кода. Тем не менее, я пришел к проблеме и не смог ее решить.

Рассмотрим следующий пример:

Парсер моего компилятора прочитал эту строку кода:

int a = 1 + 2 - 3 * 4 - 5

И преобразовал его в следующий AST:

       =
     /   \
  a(int)  \
           -
         /   \
        -     5
      /   \
     +     *
    / \   / \
   1   2 3   4

Теперь он должен проверить тип AST. он начинается с первой проверки типа =оператора. Сначала проверяется левая сторона оператора. Он видит, что переменная aобъявлена ​​как целое число. Поэтому теперь он должен проверить, что выражение в правой части имеет целое число.

Я понимаю, как это можно сделать, если выражение было только одно значение, например, 1или 'a'. Но как это сделать для выражений с несколькими значениями и операндами - сложного выражения, такого как приведенное выше? Чтобы правильно определить значение выражения, похоже, что средство проверки типов действительно должно быть выполнено само выражение и записать результат. Но очевидно, что это противоречит цели разделения фаз компиляции и выполнения.

Единственный другой способ, которым я могу представить, - это рекурсивно проверить лист каждого подвыражения в AST и убедиться, что все типы листа соответствуют ожидаемому типу оператора. Таким образом, начиная с =оператора, средство проверки типов затем сканирует все AST левой стороны и проверяет, что все листы являются целыми числами. Затем он будет повторять это для каждого оператора в подвыражении.

Я пытался исследовать эту тему в своей копии «Книги Дракона» , но она, похоже, не вдавалась в подробности, а просто повторяет то, что я уже знаю.

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

Рекурсия - это ответ, но вы опускаетесь в каждое поддерево перед обработкой операции:

int a = 1 + 2 - 3 * 4 - 5

в виде дерева:

(assign (a) (sub (sub (add (1) (2)) (mul (3) (4))) (5))

Вывод типа происходит сначала путем обхода левой стороны, затем правой стороны, а затем обработки оператора, как только будут выведены типы операндов:

(assign*(a) (sub (sub (add (1) (2)) (mul (3) (4))) (5))

-> спуститься в лхс

(assign (a*) (sub (sub (add (1) (2)) (mul (3) (4))) (5))

-> делать вывод a.aкак известно int. Мы вернулись в assignузел сейчас:

(assign (int:a)*(sub (sub (add (1) (2)) (mul (3) (4))) (5))

-> опуститься в правую часть, затем в левую часть внутренних операторов, пока мы не натолкнемся на что-нибудь интересное

(assign (int:a) (sub*(sub (add (1) (2)) (mul (3) (4))) (5))
(assign (int:a) (sub (sub*(add (1) (2)) (mul (3) (4))) (5))
(assign (int:a) (sub (sub (add*(1) (2)) (mul (3) (4))) (5))
(assign (int:a) (sub (sub (add (1*) (2)) (mul (3) (4))) (5))

-> сделать вывод о типе 1 , который есть int, и вернуть родителю

(assign (int:a) (sub (sub (add (int:1)*(2)) (mul (3) (4))) (5))

-> перейти в RHS

(assign (int:a) (sub (sub (add (int:1) (2*)) (mul (3) (4))) (5))

-> выводим тип 2, которыйint, и вернуть родителю

(assign (int:a) (sub (sub (add (int:1) (int:2)*) (mul (3) (4))) (5))

-> выводим тип add(int, int), которыйint, и вернуть родителю

(assign (int:a) (sub (sub (int:add (int:1) (int:2))*(mul (3) (4))) (5))

-> спуститься в rhs

(assign (int:a) (sub (sub (int:add (int:1) (int:2)) (mul*(3) (4))) (5))

и т.д., пока не закончится

(assign (int:a) (int:sub (int:sub (int:add (int:1) (int:2)) (int:mul (int:3) (int:4))) (int:5))*

Является ли само присвоение также выражением с типом, зависит от вашего языка.

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

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

Читайте wikipages на системы типа и вывода типов и системы типов Хиндли-Милнера , который использует объединение . Читайте также о денотационной семантике и операционной семантике .

Проверка типа может быть проще, если:

• все ваши переменные, как a явно объявлены с типом. Это похоже на C или Pascal или C ++ 98, но не на C ++ 11, который имеет некоторый вывод типа auto.
• все литеральные значения, такие как 1, 2или 'c'имеют собственный тип: у литерала int всегда есть тип int, у литерала символа всегда есть типchar ,….
• функции и операторы не перегружены, например, +оператор всегда имеет тип (int, int) -> int. C имеет перегрузку для операторов ( +работает для целочисленных типов со знаком и без знака и для двойников), но не перегружает функции.

При этих ограничениях может быть достаточно алгоритма рекурсивного декорирования типа AST снизу вверх (это касается только типов , а не конкретных значений, как и подход во время компиляции):

• Для каждой области вы сохраняете таблицу типов всех видимых переменных (называемых средой). После объявления int aвы добавляете запись a: intв таблицу.

• Типизация листьев является тривиальным базовым случаем рекурсии: тип литералов, подобных лайку, 1уже известен, а тип переменных, подобных лайку, aможно найти в среде.

• Чтобы ввести выражение с некоторым оператором и операндами в соответствии с ранее вычисленными типами операндов (вложенных подвыражений), мы используем рекурсию для операндов (поэтому сначала вводим эти подвыражения) и следуем правилам ввода, связанным с оператором. ,

Таким образом, в вашем примере, 4 * 3и 1 + 2набираются, intпотому что 4& 3и 1& 2были набраны ранее, intи ваши правила печатания говорят, что сумма или произведение двух- ints является int, и так далее для (4 * 3) - (1 + 2).

Затем прочитайте книгу Пирса « Типы и языки программирования» . Я рекомендую немного изучить Ocaml и λ-исчисление

Для более динамически типизированных языков (например, Lisp) читайте также Lisp Queinnec In Small Pieces

Читайте также книгу Прагматики Скотта " Языки программирования"

Кстати, у вас не может быть независимого от языка кода, потому что система типов является неотъемлемой частью семантики языка .

В C (и, честно говоря, наиболее статически типизированных языках на основе C) каждый оператор может рассматриваться как синтаксический сахар для вызова функции.

Таким образом, ваше выражение может быть переписано как:

int a{operator-(operator-(operator+(1,2),operator*(3,4)),5)};

Затем сработает разрешение перегрузки и решит, что каждая функция имеет тип (int, int)или (const int&, const int&).

Этот способ облегчает понимание и отслеживание разрешения типов и (что более важно) прост в реализации. Информация о типах течет только 1 путём (из внутренних выражений наружу).

Это причина, по которой double x = 1/2;результат будет, x == 0потому что 1/2оценивается как выражение int.

Сосредоточив внимание на вашем алгоритме, попробуйте изменить его снизу вверх. Вы знаете переменные и константы типа pf; пометьте узел с оператором типом результата. Позвольте листу определить тип оператора, также противоположный вашей идее.

На самом деле это довольно просто, если вы считаете, +что это множество функций, а не единый концепт.

    int operator=(int)
     /   \
  a(int)  \
        int operator-(int,int)
         /                  \
    int operator-(int,int)    5
         /              \
int operator+(int,int) int operator*(int,int)
    / \                      / \
   1   2                    3   4

На этапе синтаксического анализа правой стороны анализатор извлекает 1, знает, что это int, затем анализирует +и сохраняет это как «неразрешенное имя функции», затем анализирует 2, знает, что это int, и затем возвращает это в стек. Узел +функции теперь знает оба типа параметров, поэтому может разрешить +в int operator+(int, int), поэтому теперь он знает тип этого подвыражения, и синтаксический анализатор продолжает свой веселый путь.

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

char* ptr = itoa(3);

Здесь дерево это:

    char* itoa(int)
     /           \
  ptr(char*)      3

Основой для проверки типов является не то, что делает компилятор, а то, что определяет язык.

В языке Си каждый операнд имеет тип. «abc» имеет тип «массив константных символов». 1 имеет тип "int". 1L имеет тип «длинный». Если x и y являются выражениями, то существуют правила для типа x + y и так далее. Таким образом, компилятор, очевидно, должен следовать правилам языка.

На современных языках, таких как Swift, правила намного сложнее. Некоторые случаи просты, как в C. В других случаях компилятор видит выражение, ему заранее было сказано, какой тип выражения должен иметь, и на основании этого определяем типы подвыражений. Если x и y являются переменными разных типов, и присваивается идентичное выражение, это выражение может быть оценено по-другому. Например, назначение 12 * (2/3) назначит 8.0 для Double и 0 для Int. И у вас есть случаи, когда компилятор знает, что два типа связаны, и выясняет, на каких типах они основаны.

Быстрый пример:

var x: Double
var y: Int

x = 12 * (2 / 3)
y = 12 * (2 / 3)

print (x, y)

печатает "8.0, 0".

В назначении x = 12 * (2/3): Левая сторона имеет известный тип Double, поэтому правая сторона должна иметь тип Double. Оператор "*", возвращающий Double, имеет только одну перегрузку: Double * Double -> Double. Следовательно, 12 должен иметь тип Double, а также 2/3. 12 поддерживает протокол IntegerLiteralConvertible. Double имеет инициализатор, принимающий аргумент типа «IntegerLiteralConvertible», поэтому 12 преобразуется в Double. 2/3 должно иметь тип Double. Оператор "/", возвращающий Double, имеет только одну перегрузку: Double / Double -> Double. 2 и 3 конвертируются в Double. Результат 2/3 составляет 0,6666666. Результат 12 * (2/3) составляет 8,0. 8.0 назначен на х.

В присваивании y = 12 * (2/3) у y с левой стороны есть тип Int, поэтому с правой стороны должен быть тип Int, поэтому 12, 2, 3 преобразуются в Int с результатом 2/3 = 0, 12 * (2/3) = 0.