Введение в разработку собственного языка и компилятора. Создаем на Rust! - страница 4
· Если уравнение имеет форму X = t, и t содержит переменную X, алгоритм завершится неудачей (это называется проверкой на самопоявление – occurs check).
· Если уравнение имеет форму t = X, и t не является переменной, то уравнение t = X удаляется из множества E, и добавляется уравнение X = t (меняем местами левую и правую часть уравнения).
· Возвращаемся к множеству уравнений E.
Когда алгоритм завершится успешно, множество E будет иметь вид:
X1 = r1, X2 = r2, …, Xm = rm
И эта замена будет являться наиболее общим унификатором для множества уравнений E.
Рассмотрим следующий пример на языке Standard ML:
val x = 1;
val y = x +2;
val z = y * 3;
Пусть X – тип x, Y – тип y, Z – тип z. Тогда:
x = 1 → X = int
y = x +2 → Y = int (так как + требует int для x и 2)
z = y * 3 → Z = int (так как * требует int для y и 3)
Итог: X = int, Y = int, Z = int.
В этой программе тип очевиден только для числа 1, который имеет тип int. Чтобы выполнить вывод типов, заменим неизвестные части на переменные типов. Пусть тип переменной x будет X, тип переменной y – Y, а тип переменной z – Z. Тогда множество типовых уравнений E будет следующим:
E = {X = Y, Y = Z, Z = int}
Теперь проведем унификацию для типов Z и int. Поскольку они совпадают, замена [int/Z] будет применена. После этого множество уравнений будет выглядеть так:
E = {X = Y, Y = int, Z = int}
Далее, рассматривая типы Y и int, мы применяем замену [int/Y]. После применения этой замены множество уравнений становится:
E = {X = int, Y = int, Z = int}
Теперь мы можем сделать вывод, что тип переменной x (то есть X) – это int.
В языке, который мы проектируем, алгоритм Мартелли и Монтанари может быть использован для расширения системы вывода типов, особенно при обработке более сложных выражений, включающих несколько переменных и операций. Хотя наш язык ограничивается типами int и bool, этот подход позволит нам автоматически определять типы переменных и выражений, таких как x+y или x == (1+2), минимизируя необходимость явного указания типов. Такой механизм обеспечит строгую типизации и упростит разработку компилятора, который мы реализуем в последующих главах .
Алгоритм Мартелли и Монтанари, будучи улучшенной версией алгоритма Робинсона, предлагает более эффективное решение для работы с системами уравнений, что делает его ценным инструментом для нашего языка. Для более глубокого изучения можно обратиться к оригинальной работе Мартелли и Монтанари, где описаны детали оптимизации и примеры применения в системах программирования.
1.2 Синтаксис
До сих пор мы рассматривали семантику языка, который мы создаём. Теперь давайте подумаем, какой синтаксис будет достаточно хорош для того, чтобы выразить эту семантику.
Здесь мы будем определять синтаксис для нашего языка, рассматривая различные способы его описания и определяя структуру синтаксиса.
1.2.1 Определение синтаксиса
Давайте начнем с определения синтаксиса для языка, который мы собираемся создать.
Элементы, которые мы хотим реализовать, это: сложение, вычитание, умножение, деление, сравнение на равенство*¹, присваивание, оператор if с ветками then и else, а также оператор print.
Что касается сложения, вычитания, умножения и деления, то здесь нет необходимости сильно углубляться. Для двух выражений просто используем операторы +, -, * или / как инфиксные операторы.
Оператор
Похожие книги
