В чем разница между реализацией компилятора и интерпретатора?

Question

Я недавно прочитал всю Книгу Дракона (просто для удовольствия, я не собираюсь реализовывать настоящий компилятор), и у меня остался большой вопрос, болтающийся в моей голове.

Чем отличается реализация компилятора от интерпретатора?

Для меня компилятор состоит из:

• лексер
• Парсер (который строит синтаксическое дерево)
• Генерация промежуточного кода (например, 3-х адресный код)
• Делайте все эти сумасшедшие вещи, чтобы оптимизировать, если хотите:-)
• Создайте "сборку" или "собственный код" из 3-х адресного кода.

Теперь, очевидно, интерпретатор также имеет тот же лексер и парсер, что и компилятор.
Но что он делает после этого?

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

• Он генерирует 3-х адресный код и интерпретирует это? (если так, как это делает? Снова, я ищу что-то более изящное, чем заявление переключателя длиной в милю)

• Генерирует ли он настоящий нативный код, загружает ли его в память и запускает ли он? (в этот момент я предполагаю, что это уже не интерпретатор, а скорее JIT-компилятор)

Кроме того, в какой момент понятие "виртуальная машина" врезается? Для чего вы используете виртуальную машину на языке? (чтобы понять мой уровень невежества, для меня виртуальная машина - это VMWare, я понятия не имею, как концепция VM применяется к языкам программирования / исполняющим программам).

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

Спасибо!
Даниил

---

РЕДАКТИРОВАТЬ: Спасибо за ваши ответы до сих пор. Я понял, что мой титул вводит в заблуждение, хотя. Я понимаю "функциональную" разницу между компилятором и интерпретатором.
То, что я ищу, - это разница в том, как вы реализуете интерпретатор против компилятора.
Теперь я понимаю, как реализован компилятор, вопрос в том, чем интерпретатор отличается от этого.

Например: VB6 явно является и компилятором, и интерпретатором. Теперь я понимаю часть компилятора. Тем не менее, я не могу понять, как при запуске внутри среды IDE можно было остановить программу в любой произвольной точке, изменить код и возобновить выполнение с новым кодом. Это только один крошечный пример, это не тот ответ, который я ищу. Как я объясняю ниже, я пытаюсь понять, что происходит после того, как у меня есть дерево разбора. Компилятор сгенерирует из него новый код на "целевом" языке. Что делает переводчик?

Спасибо за помощь!

Answer 1

Короткий ответ:

• компилятор преобразует исходный код в исполняемый формат для последующего выполнения
• интерпретатор оценивает исходный код для немедленного выполнения

есть много возможностей в том, как они будут реализованы. Интерпретатор может сгенерировать собственный машинный код и затем выполнить его, в то время как компилятор для виртуальной машины может генерировать p-код вместо машинного кода. Потоковые интерпретируемые языки, такие как Forth, ищут ключевые слова в словаре и немедленно выполняют связанную с ними функцию нативного кода.

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

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

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

Answer 2

Программа - это описание работы, которую вы хотите сделать.

Компилятор преобразует высокоуровневое описание в более простое описание.

Переводчик читает описание того, что делать, и выполняет работу.

• Некоторые интерпретаторы (например, оболочки Unix) читают описание по одному маленькому фрагменту за раз и воздействуют на каждый фрагмент так, как они его видят; некоторые (например, Perl, Python) читают полное описание, внутренне преобразуют его в более простую форму и затем действуют в соответствии с этим.
• Некоторые интерпретаторы (например, Java JVM или чип Pentium 4) понимают только очень простой язык описания, который слишком утомителен для работы с людьми, поэтому люди используют компиляторы для преобразования своих высокоуровневых описаний в этот язык.

Компиляторы никогда не делают работу. Переводчики всегда делают работу.

Answer 3

Компилятор - это программа, которая переводит программу на одном языке программирования в программу на другом языке программирования. Вот и все - просто и понятно.

Интерпретатор переводит язык программирования в его семантическое значение.

Чип x86 является интерпретатором машинного языка x86.

Javac - это компилятор Java для виртуальной машины Java. java, исполняемое приложение, является интерпретатором для jvm.

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

Обычно переводчики, но не всегда, имеют цикл чтения-чтения-печати.

Answer 4

Оба имеют много общего (например, лексический синтаксический анализатор), и есть разногласия по поводу различия. Я смотрю на это так:

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

Тем не менее, люди называют "javac" компилятором, поэтому неофициальное определение компилятора - это то, что должно быть сделано для исходного кода как отдельный шаг, тогда как у интерпретаторов нет шага "сборки" (например, PHP, Perl).

Answer 5

Это не так ясно, как это было раньше. Раньше он создавал дерево разбора, связывал его и выполнял (часто связывание в последнюю секунду).

БЕЙСИК был в основном сделан таким образом.

Вы можете утверждать, что вещи, которые запускают байт-код (java/.net) без выполнения JIT, являются интерпретаторами - но не в традиционном смысле, так как вам все равно придется "компилировать" в байт-код.

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

Это было гораздо менее формально, чем настоящая книга Дракона, но я надеюсь, что она информативна.

Answer 6

Если мой опыт что-то указывает;

1. Интерпретаторы не пытаются уменьшать / обрабатывать AST дальше, каждый раз, когда ссылаются на блок кода, соответствующий узел AST обходит и выполняет. Компиляторы пересекают блок не более нескольких раз, чтобы сгенерировать исполняемый код в определенном месте и покончить с этим.
2. Таблица символов переводчиков содержит значения и ссылки во время выполнения, таблица символов компиляторов хранит местоположения переменных. Во время выполнения такой таблицы символов не существует.

В кадре разница может быть такой же простой, как

case '+':
    symtbl[var3] = symtbl[var1] + symtbl[var2];
    break;

между,

case '+':
    printf("%s = %s + %s;",symtbl[var3],symtbl[var1],symtbl[var2]);
    break;

(Неважно, нацелены ли вы на другой язык или (виртуальную) инструкцию машины.)

Answer 7

Что касается этой части вашего вопроса, на которую другие ответы на самом деле не обращались:

Кроме того, в какой момент понятие "виртуальная машина" врезается? Для чего вы используете виртуальную машину на языке?

Виртуальные машины, такие как JVM или CLR, представляют собой уровень абстракции, который позволяет повторно использовать оптимизацию компилятора JIT, сборку мусора и другие подробности реализации для совершенно разных языков, скомпилированных для работы на ВМ.

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

Answer 8

Когда дерево разбора доступно, существует несколько стратегий:

1) непосредственно интерпретировать AST (Ruby, оригинальный интерпретатор WebKit) 2) преобразование кода -> в байтовые коды или машинный код

Для достижения Edit-and-Continue счетчик программы или указатель команды должны быть пересчитаны и перемещены. Это требует сотрудничества со стороны IDE, поскольку код мог быть вставлен до или после маленькой желтой стрелки.

Один из способов сделать это - встроить положение счетчика программы в дерево разбора. Например, может быть специальное утверждение, называемое "break". Для продолжения работы счетчик программ должен быть установлен только после команды "перерыв".

Кроме того, вы должны решить, что вы хотите сделать с текущим кадром стека (и переменными в стеке). Возможно вытолкнуть текущий стек и скопировать переменные или сохранить стек, но исправить GOTO и ВОЗВРАТИТЬ текущий код.

Answer 9

Учитывая ваш список шагов:

• лексер
• Парсер (который строит синтаксическое дерево)
• Генерация промежуточного кода (например, 3-х адресный код)
• Делайте все эти сумасшедшие вещи, чтобы оптимизировать, если хотите:-)
• Создайте "сборку" или "собственный код" из 3-х адресного кода.

Очень простой интерпретатор (например, ранние Бейсики или TCL) будет выполнять только шаги один и два по одной строке за раз. А затем отбросьте большинство результатов, переходя к следующей строке, которая будет выполнена. Другие 3 шага никогда не будут выполнены вообще.

Answer 10

Если вы ищете книгу, структура и интерпретация компьютерных программ ("Книга мастеров") - это хорошее место для начала с концепциями интерпретатора. Вы имеете дело только с кодом Scheme, который можно просматривать, оценивать и передавать, как если бы это был AST.

Кроме того, у Питера Норвига есть небольшой пример, объясняющий основную идею использования Python (со множеством примеров в комментариях), и вот еще один небольшой пример из Википедии.

Как вы сказали, это обход дерева, и, по крайней мере, для вызова по значению это просто: всякий раз, когда вы видите оператор, оцените первый операнд, а затем примените оператор. Окончательное возвращаемое значение является результатом программы (или оператором, переданным REPL).

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

Для поддержки деклараций и назначений вам необходимо поддерживать среду. Так же, как вы оцениваете "плюс", добавляя операнды, вы оцениваете имя функции, переменной и т. Д., Просматривая его в среде. Поддержка области действия означает обращение со средой как со стеком, а также своевременное нажатие и извлечение информации. В общем, насколько сложен ваш переводчик, зависит от того, какие языковые функции вы хотите поддерживать. Например, интерпретаторы делают возможным сбор мусора и самоанализ.

Для виртуальных машин: plinth и j_random_hacker описали компьютерное оборудование как своего рода интерпретатор. Обратное также верно - интерпретаторы - это машины; их инструкции более высокого уровня, чем у настоящего ISA. Для интерпретаторов в стиле VM программы фактически напоминают машинный код, а для очень простой машины - albiet. Байт-код Java использует всего несколько "регистров", один из которых содержит счетчик программ. Таким образом, интерпретатор виртуальной машины больше похож на аппаратный эмулятор, чем на интерпретаторы в примерах, которые я привел выше.

Но обратите внимание, что по соображениям скорости Oracle JVM по умолчанию работает путем преобразования прогонов инструкций байт-кода Java в инструкции x86 ("как раз во время компиляции").