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

Question

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

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

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

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

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

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

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

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

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

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

Спасибо!
Daniel

---

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

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

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

Answer 1

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

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

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

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

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

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

Answer 2

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

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

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

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

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

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

Answer 3

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

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

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

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

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

Answer 4

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

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

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

Answer 5

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

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

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

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

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

Answer 6

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

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

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

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

Answer 7

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

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 8

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

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

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

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

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

Answer 9

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

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

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

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

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

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

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

Answer 10

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

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

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