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

Вид для печати

26.11.2013, 16:08
Andrew771

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

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

Цитата:

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

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

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

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

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

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

Код:

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 действительно могут интерпретироваться как скобки, но исключительно на своем уровне интерпретации (т.е. блочном).

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

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

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

Цитата:

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

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

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

Цитата:

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

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

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

Цитата:

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

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

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

Цитата:

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

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

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

Цитата:

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

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

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

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

Цитата:

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

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

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

Цитата:

Сообщение от 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] ')' | "++" | "--" }.

Приоритет формируется порядком вложенности одних лексем в другие
26.11.2013, 19:11
psb

Цитата:

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

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

самый быстрый путь в лоб - конвертить его в си, потом sdcc или iar:)
26.11.2013, 20:10
Eltaron

Цитата:

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

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

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

Цитата:

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

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

вот ключевые слова! Теперь до меня дошло, что сильно зависит от описания РБНФ, не только формальные конструкции, но и приоритет. Про приоритет я не думал. Поэтому лепил в одну кучу, например, все математические операции. :) Спасибо, ZEK!

---------- Post added at 21:00 ---------- Previous post was at 21:00 ----------

Цитата:

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

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

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

---------- Post added at 21:04 ---------- Previous post was at 21:00 ----------

Цитата:

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

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

!!!
10.12.2013, 17:26
Andrew771

В общем, я решил всё сам написать с нуля. Т.к. на работе 7-я Винда, запароленный админом антивирь и другие админские ограничения не дают устанавливать и запускать проги (Coco/R даже через dosbox). Delphi только есть и EmuZWin.
Уже лексический анализ написал. Зато всё своими руками, во всём сам разбираюсь, можно потом что угодно творить, вплоть до компиляции компилятора компилятором на реальный Спек. :)
11.12.2013, 00:23
Tronix

Я когда-то пытался написать компилятор Паскаль для платформы chip8, а потом и для chip16. На выходе оно давало ассемблерный файл, который компилился ассемблером под платформу. В целом - кое чего даже получилось, и были рабочие демки на этом паскале, типа треугольника Серпинского или простенький Мандельброт. Вот, к примеру, код мандельброта на моем паскале:

Код:

var xPixels, yPixels, xStart, yStart, Xsize, YSize, maxiter : integer; xStep, yStep : integer; ix,iy,x,y,x0,y0,iteration,xtemp : integer; dist : byte; temp : byte; xx,yy : byte; begin XPixels := 160; YPixels := 100; XStart := $FF9c; YStart := $FFce; XSize := 160; YSize := 100; MaxIter := 16; XStep := XSize div XPixels; YStep := YSize div YPixels; yy := 20; For iy := 0 to yPixels do begin xx := 0; For ix := 0 to xPixels do begin x := xStart + ix * xStep; y := yStart + iy * yStep; x0 := x; y0 := y; iteration := 0; Repeat xtemp := ((x*x) div 48) - ((y*y) div 48) + x0; y := 2*((x*y) div 48) + y0; x := xtemp; iteration := iteration + 1; dist := ((x*x) div 48) + ((y*y) div 48); If iteration = maxiter then dist := 4000; Until dist > 192; If iteration <> maxiter then If iteration > 1 then begin temp := ((iteration shl 4) or iteration) shl 8; temp := temp or ((iteration shl 4) or iteration); DrawSprite(xx,yy,$0201,^temp); end; xx := xx + 2; end; yy := yy + 2; end; end.

Картинка в эмуляторе:

Скрытый текст

http://habrastorage.org/storage2/b6e...92bc0252e5.png

[свернуть]

Руководствовался я книгой Джека Креншоу: Давайте создадим компилятор! Это даже не совсем книга, это был цикл статей на английском в период 1988-1995 годов (Let's Build a Compiler, by Jack Crenshaw). Автор пишет простой компилятор паскаля на паскале для 68000. Все доступно и просто расписано, советую начинающим.

Так же в инете я где-то нашел некий PowerPascal by Michael Warot, написанный явно по мотивам этих статей. Компилица Turbo Pascal, на выходе выдает x86 ассемблерный листинг. Его и переведенные статьи прилагаю в архиве на всякий случай.
11.12.2013, 10:22
Andrew771

Спасибо за наводку.

Цитата:

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

Его и переведенные статьи прилагаю в архиве на всякий случай.

Забыл наверно приложить файл :)

Я по книге Вирта "Построение компилятора" ориентируюсь. У него, правда, Оберон - даже проще Паскаля. Но я еще более упрощаю - выкидываю некоторые команды, зато добавляю специфические для игрописания на Спектруме - вывод спрайтов, текста, возможно, хранение и вывод карт. Т.к. первый блин комом, пока делаю минимальную версию. Не стал делать универсальный файл с РБНФ, а сразу встраиваю синтаксический разбор в код компилятора.
Короче, изобретение велосипеда в какой-то мере. :)
Еще одна из целей - компиляция некоторых моих паскалевских программ для PC на Спектрум.
11.12.2013, 18:25
Tronix

Цитата:

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

Забыл наверно приложить файл

Не забыл, а не смог. Сейчас я без инета совсем. Еле еле удалось закачать сюда: http://rghost.ru/50882517 Как доберусь до инета, прикреплю к сообщению
12.12.2013, 15:06
Barmaley_m

Цитата:

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

зато добавляю специфические для игрописания на Спектруме - вывод спрайтов, текста, возможно, хранение и вывод карт.

Позволь поинтересоваться, зачем нужно включение таких средств в сам язык программирования? Ведь все это сводится к вызову библиотечных процедур. Не будет же сам компилятор для каждого случая генерировать оптимизированный код для рисования спрайтов и т.п.?
12.12.2013, 18:12
Andrew771

Цитата:

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

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

Библиотечные процедуры будут встроены в компилятор. Т.е., захотели вывести спрайт, завели переменную X типа sprite и вызываем вывод спрайта процедурой putsprite(X). Сам код процедуры один и тот же встроен будет мной. Потом можно напридумывать несколько разных видов процедур - вывод с атрибутами, вывод без атрибутов, познакоместно, попиксельно. Они все будут встроены изначально.

---------- Post added at 18:12 ---------- Previous post was at 18:10 ----------

Короче, я делаю не просто универсальный Паскаль, это не интересно и уже есть, а адаптированный для написания игр на Спектруме.
30.04.2014, 13:10
Andrew771

Помогите, пжт, с парой процедур. Они взяты из исходника компилятора для PC. Я хочу сконвертить на z80. Что они делают? По-моему, логический результат рассчитывают в зависимости от значения в регистре EAX, но что получают, не догоняю.
1.

Код:

Logical NEG EAX MOV EAX,0 SBC EAX,EAX

2.

Код:

Logical_Not NEG EAX MOV EAX,-1 ADC EAX,0
30.04.2014, 13:48
denpopov

миль пардон, но где Вы их раскопали?оО
30.04.2014, 13:49
drbars

Andrew771, наверное команда NEG устанавливает флаг переноса, в зависимости числа от знака в EAX.
На выходе 0x00000000h или 0xFFFFFFFFh. Тока регистры 32-х разрядные.

Logical:
NEG
SBC A,A

Logical_Not:
NEG
CCF
SBA A,A

так?
30.04.2014, 14:10
denpopov

drbars, примерно так:

Цитата:

NEG получение дополнительного кода Признаки: O D I T S Z A P C
* * * * * *

NEG destination

Логика: destination = -destination; дополнительный код

Команда NEG вычитает операнд destinstion из 0 и засылает
результат обратно в destination. Эта команда является реализаци-
ей выполнения операции нахождения дополнительного кода операнда.
Операндом может быть как байт, так и слово.

----------------------------------------------------------------
Операнды Такты Обращения Байты Пример
байты(слова)
регистр 3 - 2 NEG DL
память 16(24)+EA 2 2-4 NEG COEFFICIENT
----------------------------------------------------------------

Примечание : Если операнд равен нулю, то признак переноса CF
сбрасывается (=0); во всех остальных случаях он устанавливается
(=1). Попытка применения операции NEG к байту -128 или слову
-32,768 не приводит к изменению операнда, а только устанавливает
признак переполнения (OF=1).
30.04.2014, 14:14
Andrew771

Цитата:

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

миль пардон, но где Вы их раскопали?оО

вот тут большие залежи: http://exmortis.narod.ru/src_compilers.html

Цитата:

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

так?

Вроде как NEG делает a=-a, флаг переноса устанавливает только в случае a=0.

У меня вот так получается:

Logical:
a=0 => a=-1, cy=1
a<>0 => a=0, cy=0

Logical_Not:
a=0 => a=0, cy=1
a<>0 => a=-1, cy=0

Правильно? :)

---------- Post added at 14:14 ---------- Previous post was at 14:12 ----------

Цитата:

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

Если операнд равен нулю, то признак переноса CF
сбрасывается (=0); во всех остальных случаях он устанавливается
(=1)

ха.. А на Спектруме по-моему наоборот. Вот я и запутался.
30.04.2014, 14:23
denpopov

Andrew771, я взял из описания NortonGuide
30.04.2014, 14:27
Andrew771

Цитата:

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

Andrew771, я взял из описания NortonGuide

я верю :)
а на Спеке флаг CY наоборот устанавливается или нет при команде NEG? И как влияют на CY команды ADC и SBC?
30.04.2014, 14:54
denpopov

Цитата:

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

И как влияют на CY команды ADC и SBC?

adc A,n A=A+n+CY
sbc A,n A=A-n-CY

кажется так..
30.04.2014, 15:03
Andrew771

Цитата:

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

adc A,n A=A+n+CY
sbc A,n A=A-n-CY

кажется так..

это да. А после выполнения операций?

---------- Post added at 15:00 ---------- Previous post was at 14:59 ----------

Проверил сейчас работу NEG на эмуляторе. В общем, я неправильно говорил, она также работает, как и на PC:
CY=1, если A<>0
CY=0, если A=0

---------- Post added at 15:03 ---------- Previous post was at 15:00 ----------

и тогда будет:
Logical:
a=0 => a=-1, cy=0
a<>0 => a=0, cy=1

Logical_Not:
a=0 => a=0, cy=0
a<>0 => a=-1, cy=1
30.04.2014, 20:27
drbars

Я вот не вижу смысла тут EAX обнулять.

Logical
NEG EAX
MOV EAX,0
SBC EAX,EAX

Мой пример должен правильно работать, без всяких ADC — это грабли.

---------- Post added at 23:27 ---------- Previous post was at 23:22 ----------

и тогда будет:
Logical:
a=0 => a=-1, cy=0
a<>0 => a=0, cy=1

Код:

ADD A,#FF CCF SBC A,A или 16 bit версия LD HL,число LD DE,#FFFF ADD HL,DE CCF SBC HL,HL

Logical_Not:
a=0 => a=0, cy=0
a<>0 => a=-1, cy=1

Код:

ADD A,#FF SBC A,A или 16 bit версия LD HL,число LD DE,#FFFF ADD HL,DE SBC HL,HL
02.05.2014, 07:40
Lion17

С точностью до наоборот

Logical (eax=eax?-1:0)
Logical Not (eax=eax?0:-1)
02.05.2014, 16:27
alone

Где можно почитать про современные алгоритмы кодогенерации (с оптимизацией)?
02.05.2014, 16:42
psb

alone, я тебе говорил где посмотреть про компиляторы.
03.05.2014, 22:08
alone

Отбой, сам нашёл.
04.05.2014, 18:44
alone

Y.N. Srikant, Priti Shankar. The Compiler Design Handbook: Optimizations and Machine Code Generation, Second Edition
http://giant.pourri.ch/FAIL/The%20Co...202nd%20Ed.pdf
04.05.2014, 19:16
denpopov

вряд ли это пригодится:
Sijmen Woutersen, "Building a C Processor"

http://x32.ewi.tudelft.nl

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

Скрытый текст