Как написать переводчика?

Question

Я решил написать небольшого переводчика в качестве моего следующего проекта на Ruby. Какие знания / навыки мне понадобятся, чтобы добиться успеха?
Я еще не определился с языком для интерпретации, но я ищу что-то, что не является игрушечным языком, но было бы относительно легко написать переводчика. Заранее спасибо.

Answer 1

Вам придется выучить как минимум:

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

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

Answer 2

Я еще не выбрал язык для интерпретации, но я ищу то, что не является игрушечным языком, но было бы относительно легко написать переводчик для. Заранее спасибо.

Попробуйте какой-нибудь диалект Лиспа, например, Схему или Clojure. (Теперь есть идея: Clojure-in-Ruby, которая интегрируется с Ruby так же, как Clojure с Java.)

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

Answer 3

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

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

Если вы хотите проверить мою (буквально двухдневную) реализацию lisp на Java, ознакомьтесь с mylisp.googlecode.com . Я все еще работаю над этим, но невероятно, как быстро ушло время, чтобы заставить работать существующий материал.

Answer 4

Вы можете оформить черновой вариант спецификации Ruby http://ruby -std.netlab.jp /

Answer 5

Существует проект «Верх дерева», который может быть полезен для вас http://treetop.rubyforge.org/

Answer 6

В этой главе SICP показано, как написать интерпретатор Lisp в Lisp (мета-круговой оценщик). На мой взгляд, это лучшее место для начала. Затем вы можете перейти к Lisp в Small Pieces , чтобы научиться писать расширенные интерпретаторы и компиляторы для Lisp. Преимущество реализации такого языка, как Лисп (в самом Лиспе!), Заключается в том, что вы получаете лексический анализатор, парсер, AST, представление данных / программ и REPL бесплатно. Вы можете сконцентрироваться на задаче заставить ваш прекрасный язык работать!

Answer 7

Это не реализовано в Лиспе, но я нашел Создание схемы за 48 часов очень полезным документом, когда я начинал с Haskell (хотя я этого не делал доберитесь почти до конца через 48 часов, YMMV). Это также дает вам глубокое понимание переводчиков в целом.

Answer 8

Если вы просто делаете это для удовольствия, придумайте свой собственный простой язык и просто попробуйте. Моя рекомендация была бы что-то вроде действительно простого классического бейсика (без визуальной основы или объектно-ориентированного материала). С номерами строк, GOTO, INPUT и PRINT и все. Вы получаете базовые знания и лучше понимаете, как все работает.

Знания, которые вам понадобятся?

• Токенизация (превращение огромного куска символов во что-то более удобочитаемое, деление его на «слова»)
• Парсинг (переход по токенам и построение из него структуры данных)
• Интерпретация (зацикливание структуры данных и выполнение каждой команды)

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

Answer 9

Это не так сложно. вот интерпретатор LISP в ruby ​​, а источник настолько мал, что его нужно скопировать / вставить но ты собираешься изучать LISP сейчас? хехе.

Answer 10

Я могу порекомендовать эту книгу. Здесь обсуждаются шаблоны написания синтаксических анализаторов и интерпретаторов и многое другое:

http://www.amazon.co.uk/s/ref=nb_sb_noss?url=search-alias%3Daps&field-keywords=language+implementation+patterns&x=0&y=0