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

Question

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

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

Answer 1

Могу ли я предложить язык программирования Jack из http://www.nand2tetris.org/?

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

Я нахожусь в середине блогасерия публикаций по написанию компилятора для этого языка в C # с генерацией кода для C. Посты, которые у меня уже есть, находятся здесь: http://blogs.microsoft.co.il/blogs/sasha/archive/tags/Compiler/default.aspx

Answer 2

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

Глава 8 называется Разработка программ .В нем обсуждается разработка нетривиальной программы на разных этапах проектирования.Эта нетривиальная программа - hoc, калькулятор высокого порядка.Подробнее о hoc см. http://en.wikipedia.org/wiki/Hoc_(programming_language)

Это отличное практическое введение в реализацию простого языка с использованием стандартных инструментов yacc и lex.yacc и lex - слишком много, чтобы их здесь охватывать, но, следуя примерам из этой книги и выполняя упражнения, вы развиваете их понимание.

Развитие длится через различные фазы;на первом этапе у вас даже нет переменных в языке.На третьем этапе у вас есть переменные, определенные константы (PI, E и т. Д.) И встроенные функции, такие как sin () и log ().На последнем этапе у вас есть полностью реализованный язык.

Теперь, hoc - это лучший язык, который можно попробовать и реализовать?Я понятия не имею, но я знаю, что Среда программирования Unix была отличной книгой для чтения параллельно с традиционной книгой по компиляторам.Когда я начал читать книгу компилятора Aho (книгу драконов), я перечитал 8-ю главу TUPE и следовал примерам и упражнениям.Конечно, любой может перепечатать код из книги, но упражнения требуют, чтобы вы хорошо понимали, что происходит.

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

Answer 3

Я бы предложил Вирта PL / 0 .

Почему?

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

  program =
      block "." .
  
  block =
      [ "const" ident "=" number {"," ident "=" number} ";"]
          [ "var" ident {"," ident} ";"]
          { "procedure" ident ";" block ";" } statement .
  
  statement =
      [ ident ":=" expression
      | "call" ident
      | "begin" statement {";" statement } "end"
      | "if" condition "then" statement
      | "while" condition "do" statement
      ].
  
  condition =
      "odd" expression
      | expression ("="|"#"|"<"|"<="|">"|">=") expression
      .
  
  expression =
      [ "+"|"-"] term { ("+"|"-") term} .
  
  term =
      factor {("*"|"/") factor} .
  
  factor =
      ident | number | "(" expression ")" .
  

• Вы можете реализовать компилятор виртуальной машины для PL / 0 в C примерно в 1000 строк кода.

  • Достаточно большой, чтобы быть нетривиальным, но достаточно малым, чтобы его можно было выполнить.

• С ним связано три книги:

  • Wirth, Niklaus (1975), Алгоритмы + структуры данных = Программы, ISBN 0-13-022418-9 (оригинальная спецификация PL / 0 и реализация (на Паскале)). Отличное введение в компиляцию.

  • Liffick, Blaise W., Ed (1979), The Byte Book of Pascal, ISBN 0-07-037823-1 (авторы разработали небольшой расширенный набор PL / 0 в Northstar Basic для раннегоКомпьютер CP / M).

  • Wirth, Niklaus (1986), Compilerbau, BG Teubner, Штутгарт ISBN 3-519-32338-9 (небольшой надмножество PL / 0, реализованmented в Modula 2. На немецком языке.

• Сеть полна примеров.

  • Я нашел реализации в C, C ++, Pascal, Modula 2, Java и Ruby.Могу поспорить, что их еще больше.

• Есть запись в Википедии:: -)

  • http://en.wikipedia.org/wiki/PL/0

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

  • groups.yahoo.com / group / compilers101

  • groups.yahoo.com / group / QDepartment

  • Также,группа новостей Usenet comp.compilers является хорошим местом для получения информации.

Answer 4

Спецификация Оберона достаточно мала для ваших целей: http://www -vs.informatik.uni-ulm.de: 81 / projekte / Oberon-2.Report /

R5RS илиего чисто функциональное подмножество не так уж и велико (если вы игнорируете числовую башню).