Генерация промежуточного кода в компиляторе. Всегда ли необходимо AST или дерево разбора при работе с условными выражениями?

Question

Я беру класс разработки компилятора, где мы должны реализовать наш собственный компилятор (используя flex и bison). У меня был опыт разбора (написания парсеров EBNF и рекурсивного спуска), но я впервые пишу компилятор.

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

Мне показалось, что это сбивает с толку по двум причинам:

• Что если вы вызываете функцию до того, как будет определено? Как вы можете решить цель филиала? Я предполагаю, что вам нужно будет сделать правило, что вы должны определять функции, прежде чем использовать их, или, может быть, предварительно определить их (как это делает C?)

• Как бы вы справились с условиями? Если у вас есть if-else или даже просто if, как вы можете разрешить цель ветвления для if, когда условие false (если вы генерируете код по ходу дела)?

Я планировал создать AST, а затем пройтись по дереву после его создания, чтобы разрешить адреса функций и целей ветвления. Это правильно или я что-то упустил?

Answer 1

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

В FORTH «список» патчей хранится в стеке управления и разматывается при завершении каждой структуры управления. См. FORTH Размеры

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

Answer 2

Учебное пособие Crenshaw является конкретным примером , а не с использованием AST любого вида.Он создает работающий компилятор (включая, конечно, условные выражения) с немедленной генерацией кода, нацеленной на сборку m68k.

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