Построение компилятора

**Andrew771** · 26.11.2013, 16:08

Решил продолжить копания в теме построения собственного компилятора для z80, скорее всего, на основе Паскаля. С лексическим и синтаксическим анализом вроде разобрался, написал что надо в Coco/R.
Сейчас пытаюсь понять принцип построения синтаксического дерева. Статья Vitamina про распознавание арифметических выражений понравилась, и там же написано вот что:

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

Описание алгоритма сортировочной станции (Дейкстры) нашел, но вот никак фантазии не хватает, что делать в случае встречи операторов типа IF-ELSE, WHILE, GOTO, индексы массива... (BEGIN-END интерпретировать как скобки можно, наверно). Нигде не нашел конкретного описания для них.
Помогите, чем можете

**Advertiser** · 26.11.2013, 16:08

ZEK · 26.11.2013, 16:21

ast зачем? можно по мере разбора генерить код, ast нужен для высокоуровневых оптимизаций, типа вынос за цикл итд, LL1 тем и удобен что все что на вход попадает практически сразу можно на выхлоп кодогенератору отдавать

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

**jerri** · 26.11.2013, 16:21

Andrew771, вообще-то компилятор учат делать в институте на 3ем или 4ом курсе.
Кстати зачем оно тебе?

**Vitamin** · 26.11.2013, 16:23

ЕМНИП, перевод конструкций примерно следующий:

Код:

if (condition)
then
  positive
else
  negative
endif

переводится в

Код:

call check_condition ; C if succeed
jp nc,failed
<positive>
jp endif
failed:
<negative>
endif:

Код:

while (condition)
  body;

переводится в

Код:

while_loop:
call check_condition
jp nc,while_end
<body>
jp while_loop
while_end:

GOTO переводится в JP, очевидно же.
BEGIN/END действительно могут интерпретироваться как скобки, но исключительно на своем уровне интерпретации (т.е. блочном).

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

**psb** · 26.11.2013, 16:28

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

ZEK · 26.11.2013, 16:29

1,2 шаг coco/r делает
на выхлопе парсера иногда проще иметь промежуточный либо стековый либо 3х операндный код, а его уже в ассемблер или машкод переводить, правда если сразу в машкод, придется с адресами переходов самому возиться, можно комбинировать, арифметику стековым промежуточным кодом, будет гораздо проще и автоматом ОПЗ получается

**Andrew771** · 26.11.2013, 17:21

Сообщение от ZEK

ast зачем? можно по мере разбора генерить код, ast нужен для высокоуровневых оптимизаций, типа вынос за цикл итд, LL1 тем и удобен что все что на вход попадает практически сразу можно на выхлоп кодогенератору отдавать

Дерево вот именно для последующих оптимизаций и хочу получить. Пробовал напрямую код генерить, без ОПЗ сложно.

Сообщение от ZEK

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

а для операторов ЯВУ также можно расставить приоритет?

Сообщение от jerri

Andrew771, вообще-то компилятор учат делать в институте на 3ем или 4ом курсе.
Кстати зачем оно тебе?

Угу. Только я по специальности не программист, так что у нас не было. Хочу кросс-компилятор Паскаля сделать для Спектрума. Причем со встроенными некоторыми библиотечными функциями (вывод спрайтов, текста и т.д.)

Сообщение от Vitamin

перевод конструкций примерно следующий

да, это не сложно. Но приоритет и последовательность операторов вот только из дерева можно получить (?).

Сообщение от Vitamin

потом синтаксический анализ (подготовка внутреннего кода в форму ОПЗ, например)

вот этот этап вызывает у меня затруднения.

---------- Post added at 17:21 ---------- Previous post was at 17:19 ----------

Сообщение от ZEK

на выхлопе парсера иногда проще иметь промежуточный либо стековый либо 3х операндный код, а его уже в ассемблер или машкод переводить

ОПЗ, как я понимаю, стековый код?

ZEK · 26.11.2013, 17:51

Сообщение от Andrew771

Дерево вот именно для последующих оптимизаций и хочу получить.

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

Сообщение от Andrew771

Пробовал напрямую код генерить, без ОПЗ сложно.

Генери промежуточный код, тут тоже какие то оптимизации можно делать, замены по шаблонам

Сообщение от Andrew771

а для операторов ЯВУ также можно расставить приоритет?

зачем? операторы последовательно выполняются

Сообщение от Andrew771

ОПЗ, как я понимаю, стековый код?

ну да, парсер к примеру из кода

"var1 * 5 + var2" может делать что то такое

ld var1 // загружает переменную на вершиу стека
const 5 // ложит на вершину стека константу
mul // берет 2 значения с верхушки стека, перемножает и ложит результат обратно
ld var2
add

это на промежуточном коде, его потом в ассемблер перевести не проблема

приортитеты можешь не париться, надо просто правильно нарисовать правила для coco/r, он сам разберет по приоритетам сырок

---------- Post added at 16:51 ---------- Previous post was at 16:40 ----------

Вот пример разбора сишного сырка по сишным приоритетам

Код:

Expr       = AssignExpr {','  AssignExpr}.
AssignExpr = CondExpr [AssignOp AssignExpr]. // relaxed
CondExpr   = LogOrExpr ['?' Expr ':' CondExpr].
LogOrExpr  = LogAndExpr {"||" LogAndExpr}.
LogAndExpr = OrExpr {"&&" OrExpr}.
OrExpr     = XorExpr {'|' XorExpr}.
XorExpr    = AndExpr {'^' AndExpr}.
AndExpr    = EqlExpr {'&' EqlExpr}.
EqlExpr    = RelExpr {("==" | "!=") RelExpr}.
RelExpr    = ShiftExpr {('<' | '>' | "<=" | ">=") ShiftExpr}.
ShiftExpr  = AddExpr {("<<" | ">>") AddExpr}.
AddExpr    = MultExpr {('+' | '-') MultExpr}.
MultExpr   = CastExpr {('*' | '/' | '%') CastExpr}.
CastExpr   = IF(IsType1()) '(' TypeName ')' CastExpr
           | UnaryExpr.

UnaryExpr =
  {"++" | "--"}
  ( PostfixExpr
  | UnaryOp CastExpr
  | "sizeof"  (IF(IsType1()) '(' TypeName ')' | UnaryExpr)
  ).

PostfixExpr =
  Primary
  { '[' Expr ']' 
  | '.'  ident
  | "->" ident
  | '(' [ArgExprList] ')' 
  | "++" 
  | "--"
  }.

Приоритет формируется порядком вложенности одних лексем в другие

**psb** · 26.11.2013, 19:11

Сообщение от Andrew771

Хочу кросс-компилятор Паскаля сделать для Спектрума.

самый быстрый путь в лоб - конвертить его в си, потом sdcc или iar

**Eltaron** · 26.11.2013, 20:10

Сообщение от psb

самый быстрый путь в лоб - конвертить его в си, потом sdcc или iar

Еще быстрее - взять готовый паскаль под CP/M, и запускать под CP/M-эмулятором. Высокоуровневые (BDOS) эмуляторы прозрачно работают с существующей файловой системой PC.

User Tag List

Тема: Построение компилятора

Опции темы

Отображение

Построение компилятора

Информация о теме

Пользователи, просматривающие эту тему

Похожие темы

Interference:построение таблицы

Кодогенерация SDCC: пожелания об улучшении компилятора

3D-View - построение 3D перспективы

Конструктор для компилятора с Си

Ваши права