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

Question

У меня уже есть парсер для языка, на котором я работаю.Трудно ли это интерпретировать?Я думал, это просто.Синтаксический анализ и проверка синтаксиса выполнены.У меня просто дерево объектов.Каждый раз, когда создается объект, я создаю ветвь и сохраняю ее тип (string, int, float, class / obj).Затем каждый раз, когда новый объект добавляется к объекту, я создаю ветвь и повторяю.

Я стараюсь, чтобы это звучало просто.Мне все еще нужно проверить, что объект A может быть добавлен к объекту B и тому подобное.

Действительно ли это достаточно просто после того, как AST и проверка синтаксиса выполнены, или еще много работы?

Answer 1

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

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

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

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

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

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

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

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

Answer 2

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

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

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

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

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 или маленькой книге .Если вы хотите создать типизированный язык, вам, возможно, придется прочитать еще немного.

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

Answer 3

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

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