Насколько сложно написать интерпретируемый язык, если у вас есть AST?

Обычно вам нужно создать таблицы символов и выполнить проверку типов. Для некоторых языков это можно сделать на лету; для других, я думаю, в значительной степени нужно сначала разрешить имя и проверить тип, иначе вы не сможете правильно его интерпретировать (на ум приходит C++).

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

Скорее всего, вы обнаружите, что вашему языку нужны функции, которые вы не рассматривали. Обработка исключений? Несколько заданий? Локальные области? Лямбды? Закрытия? Вы довольно быстро обнаружите, как много в современных языках того, что делает их полезными.

Когда вы начнете писать более сложные программы, вам понадобится отладчик. Контрольные точки? Единственный шаг? Переменный осмотр? Обновлять? Начинать с произвольных мест? Цикл чтения-оценки-печати?

Вам все еще нужно привязать свой язык к внешним библиотекам; большинство людей хотят общаться с консолями и файлами; вам нужны буферизованные файлы или вы согласны с 1 символом за раз и соответствующим снижением производительности? Вы сможете поспорить с символьными представлениями (7-битный ascii? 8-битный? UTF8 с символами, отличными от единиц измерения? Полный Unicode?) и стандартными библиотеками поддержки (конкатенация строк, поиск, преобразование чисел [включая точные преобразования с плавающей запятой в обоих направлениях] , арифметика больших чисел, ловушки с плавающей запятой, .... Список проблем становится довольно длинным, если вам нужен полезный язык программирования.

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

Далее кто-то будет жаловаться на производительность. Теперь вы можете настроить свою реализацию и начать сожалеть о том, что вы написали интерпретатор вместо компилятора.

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

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

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

data Exp = Lam String Exp 
         | App Exp Exp 
         | Var String 
         | Num Int

Теперь вы можете написать для него интерпретатор в виде простой функции "eval":

eval (App e1 e2) env = (unF (eval e1 env)) (eval e2 env)
eval (Lam x e) env   = F (\v -> (eval e ((x,v):env)))
eval (Num n) env     = N n
eval (Var x) env     = case (lookup x env) of 
                         Just v -> v
                         Nothing -> error ("Unbound variable " ++ x)

Вот и все. Вот несколько скучных вспомогательных определений.

data Val = F (Val -> Val)  | N Int
unF (F x) = x
instance Show Val where 
    show (F _) = "<procedure>"
    show (N n) = show n

Другими словами, если вы скопируете и вставите приведенные выше три блока кода в исходный файл Haskell, у вас будет работающий интерпретатор, который вы можете протестировать с помощью ghci следующим образом:

*Main> eval (App (Lam "x" (Var "x")) (Num 1)) []
1
*Main> eval (Var "x") []
*** Exception: Unbound variable x

Вы можете прочитать о создании языков в классическом SICP или EOPL или маленькая книга. Если вы хотите создать типизированный язык, вам, возможно, придется прочитать еще немного.

Тем не менее, если вы собираетесь создавать языки, могу ли я настоятельно рекомендовать сначала много читать. С одной стороны, это очень полезно. А во-вторых, слишком много отвратительных языков было навязано миру людьми, которые не умеют создавать языки (многие из которых стали очень популярными по разным историческим причинам), и мы с ними застряли.

Я бы сказал, что самая трудная часть (и самая забавная на самом деле) начинается после того, как вы сделали AST.

Взгляните на LLVM, у него есть привязки для многих языков (я использовал только C++ и Haskell, я не могу tell для других языков), и это должно помочь вам написать своевременный компилятор для вашего языка. На самом деле, LLVM упрощает написание компилятора, чем интерпретатора!