Просмотр полной версии : Построение компилятора
Andrew771
26.11.2013, 16:08
Решил продолжить копания в теме построения собственного компилятора для z80, скорее всего, на основе Паскаля. С лексическим и синтаксическим анализом вроде разобрался, написал что надо в Coco/R.
Сейчас пытаюсь понять принцип построения синтаксического дерева. Статья Vitamina (http://zxdn.narod.ru/coding/ig7mthex.txt) про распознавание арифметических выражений понравилась, и там же написано вот что:
Таким образом, т.е.согла-
сно алгоритму Дейкстры, можно перевести в
ОПЗ не только арифметическое выражение, но
и программу на ЯВУ (Языке Высокого Уров-
ня).При этом нужно определить дополнитель-
ные классы лексем: описание и вызов функ-
ций, описание и адресация массивов, услов-
ные и безусловные переходы. В результате
получится описание на языке низкоуровневых
конструкций, как нельзя лучше приспособ-
ленных к дальнейшей трансляции в машинный
код. Подробную информацию можно получить в
литературе по данной теме.
Описание алгоритма сортировочной станции (http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_% D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0 %BE%D1%87%D0%BD%D0%BE%D0%B9_%D1%81%D1%82%D0%B0%D0% BD%D1%86%D0%B8%D0%B8) (Дейкстры) нашел, но вот никак фантазии не хватает, что делать в случае встречи операторов типа IF-ELSE, WHILE, GOTO, индексы массива... (BEGIN-END интерпретировать как скобки можно, наверно). Нигде не нашел конкретного описания для них.
Помогите, чем можете :)
ast зачем? можно по мере разбора генерить код, ast нужен для высокоуровневых оптимизаций, типа вынос за цикл итд, LL1 тем и удобен что все что на вход попадает практически сразу можно на выхлоп кодогенератору отдавать
Разбор арифметических выражений с приоритетами итд, делается просто вкладыванием лексем друг в друга в нужном порядке, на верхнем уровне самые низкоприоритетные, чем глубже тем приоритет выше
Andrew771, вообще-то компилятор учат делать в институте на 3ем или 4ом курсе.
Кстати зачем оно тебе?
ЕМНИП, перевод конструкций примерно следующий:
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 действительно могут интерпретироваться как скобки, но исключительно на своем уровне интерпретации (т.е. блочном).
Главное- помнить, что трансляция в машинные коды происходит в несколько этапов. Сначала лексический анализ (программа из текста преобразуется во внутренний код, где токены закодированы более понятным для парсера способом), потом синтаксический анализ (подготовка внутреннего кода в форму ОПЗ, например), потом генерация исходного ассемблерного кода и только потом из ассемблера генерится машинный код. (Могу напутать с названием шагов, давно уже ковырял эту тему).
если кому интересно, на coursera был целый курс видео лекций по компиляторам. правда там для своего выдуманного языка.
1,2 шаг coco/r делает
на выхлопе парсера иногда проще иметь промежуточный либо стековый либо 3х операндный код, а его уже в ассемблер или машкод переводить, правда если сразу в машкод, придется с адресами переходов самому возиться, можно комбинировать, арифметику стековым промежуточным кодом, будет гораздо проще и автоматом ОПЗ получается
Andrew771
26.11.2013, 17:21
ast зачем? можно по мере разбора генерить код, ast нужен для высокоуровневых оптимизаций, типа вынос за цикл итд, LL1 тем и удобен что все что на вход попадает практически сразу можно на выхлоп кодогенератору отдавать
Дерево вот именно для последующих оптимизаций и хочу получить. Пробовал напрямую код генерить, без ОПЗ сложно.
Разбор арифметических выражений с приоритетами итд, делается просто вкладыванием лексем друг в друга в нужном порядке, на верхнем уровне самые низкоприоритетные, чем глубже тем приоритет выше
а для операторов ЯВУ также можно расставить приоритет? :)
Andrew771, вообще-то компилятор учат делать в институте на 3ем или 4ом курсе.
Кстати зачем оно тебе?
Угу. Только я по специальности не программист, так что у нас не было. Хочу кросс-компилятор Паскаля сделать для Спектрума. Причем со встроенными некоторыми библиотечными функциями (вывод спрайтов, текста и т.д.)
перевод конструкций примерно следующий
да, это не сложно. Но приоритет и последовательность операторов вот только из дерева можно получить (?).
потом синтаксический анализ (подготовка внутреннего кода в форму ОПЗ, например)
вот этот этап вызывает у меня затруднения.
---------- Post added at 17:21 ---------- Previous post was at 17:19 ----------
на выхлопе парсера иногда проще иметь промежуточный либо стековый либо 3х операндный код, а его уже в ассемблер или машкод переводить
ОПЗ, как я понимаю, стековый код?
Дерево вот именно для последующих оптимизаций и хочу получить.
такие оптимизации это порви моск в тряпки, ast впринципе не сложно собирать, но его потом читать надо, еще один промежуточный шаг
Пробовал напрямую код генерить, без ОПЗ сложно.
Генери промежуточный код, тут тоже какие то оптимизации можно делать, замены по шаблонам
а для операторов ЯВУ также можно расставить приоритет?
зачем? операторы последовательно выполняются
ОПЗ, как я понимаю, стековый код?
ну да, парсер к примеру из кода
"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] ')'
| "++"
| "--"
}.
Приоритет формируется порядком вложенности одних лексем в другие
Хочу кросс-компилятор Паскаля сделать для Спектрума.
самый быстрый путь в лоб - конвертить его в си, потом sdcc или iar:)
самый быстрый путь в лоб - конвертить его в си, потом sdcc или iar:)
Еще быстрее - взять готовый паскаль под CP/M, и запускать под CP/M-эмулятором. Высокоуровневые (BDOS) эмуляторы прозрачно работают с существующей файловой системой PC.
Andrew771
26.11.2013, 21:04
приоритеты можешь не париться, надо просто правильно нарисовать правила для coco/r, он сам разберет по приоритетам сырок
вот ключевые слова! Теперь до меня дошло, что сильно зависит от описания РБНФ, не только формальные конструкции, но и приоритет. Про приоритет я не думал. Поэтому лепил в одну кучу, например, все математические операции. :) Спасибо, ZEK!
---------- Post added at 21:00 ---------- Previous post was at 21:00 ----------
самый быстрый путь в лоб - конвертить его в си, потом sdcc или iar
да смысл. Я хочу оптимизированный именно для Спека, без посредников.
---------- Post added at 21:04 ---------- Previous post was at 21:00 ----------
Приоритет формируется порядком вложенности одних лексем в другие
!!!
Andrew771
10.12.2013, 17:26
В общем, я решил всё сам написать с нуля. Т.к. на работе 7-я Винда, запароленный админом антивирь и другие админские ограничения не дают устанавливать и запускать проги (Coco/R даже через dosbox). Delphi только есть и EmuZWin.
Уже лексический анализ написал. Зато всё своими руками, во всём сам разбираюсь, можно потом что угодно творить, вплоть до компиляции компилятора компилятором на реальный Спек. :)
Я когда-то пытался написать компилятор Паскаль для платформы 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/704/5dc/b6e7045dcc0a29eb8d79ad92bc0252e5.png
Руководствовался я книгой Джека Креншоу: Давайте создадим компилятор! Это даже не совсем книга, это был цикл статей на английском в период 1988-1995 годов (Let's Build a Compiler, by Jack Crenshaw). Автор пишет простой компилятор паскаля на паскале для 68000. Все доступно и просто расписано, советую начинающим.
Так же в инете я где-то нашел некий PowerPascal by Michael Warot, написанный явно по мотивам этих статей. Компилица Turbo Pascal, на выходе выдает x86 ассемблерный листинг. Его и переведенные статьи прилагаю в архиве на всякий случай.
Andrew771
11.12.2013, 10:22
Спасибо за наводку.
Его и переведенные статьи прилагаю в архиве на всякий случай.
Забыл наверно приложить файл :)
Я по книге Вирта "Построение компилятора" ориентируюсь. У него, правда, Оберон - даже проще Паскаля. Но я еще более упрощаю - выкидываю некоторые команды, зато добавляю специфические для игрописания на Спектруме - вывод спрайтов, текста, возможно, хранение и вывод карт. Т.к. первый блин комом, пока делаю минимальную версию. Не стал делать универсальный файл с РБНФ, а сразу встраиваю синтаксический разбор в код компилятора.
Короче, изобретение велосипеда в какой-то мере. :)
Еще одна из целей - компиляция некоторых моих паскалевских программ для PC на Спектрум.
Забыл наверно приложить файл
Не забыл, а не смог. Сейчас я без инета совсем. Еле еле удалось закачать сюда: http://rghost.ru/50882517 Как доберусь до инета, прикреплю к сообщению
Barmaley_m
12.12.2013, 15:06
зато добавляю специфические для игрописания на Спектруме - вывод спрайтов, текста, возможно, хранение и вывод карт.
Позволь поинтересоваться, зачем нужно включение таких средств в сам язык программирования? Ведь все это сводится к вызову библиотечных процедур. Не будет же сам компилятор для каждого случая генерировать оптимизированный код для рисования спрайтов и т.п.?
Andrew771
12.12.2013, 18:12
Позволь поинтересоваться, зачем нужно включение таких средств в сам язык программирования? Ведь все это сводится к вызову библиотечных процедур. Не будет же сам компилятор для каждого случая генерировать оптимизированный код для рисования спрайтов и т.п.?
Библиотечные процедуры будут встроены в компилятор. Т.е., захотели вывести спрайт, завели переменную X типа sprite и вызываем вывод спрайта процедурой putsprite(X). Сам код процедуры один и тот же встроен будет мной. Потом можно напридумывать несколько разных видов процедур - вывод с атрибутами, вывод без атрибутов, познакоместно, попиксельно. Они все будут встроены изначально.
---------- Post added at 18:12 ---------- Previous post was at 18:10 ----------
Короче, я делаю не просто универсальный Паскаль, это не интересно и уже есть, а адаптированный для написания игр на Спектруме.
Andrew771
30.04.2014, 13:10
Помогите, пжт, с парой процедур. Они взяты из исходника компилятора для PC. Я хочу сконвертить на z80. Что они делают? По-моему, логический результат рассчитывают в зависимости от значения в регистре EAX, но что получают, не догоняю.
1.
Logical
NEG EAX
MOV EAX,0
SBC EAX,EAX
2.
Logical_Not
NEG EAX
MOV EAX,-1
ADC EAX,0
denpopov
30.04.2014, 13:48
миль пардон, но где Вы их раскопали?оО
Andrew771, наверное команда NEG устанавливает флаг переноса, в зависимости числа от знака в EAX.
На выходе 0x00000000h или 0xFFFFFFFFh. Тока регистры 32-х разрядные.
Logical:
NEG
SBC A,A
Logical_Not:
NEG
CCF
SBA A,A
так?
denpopov
30.04.2014, 14:10
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).
Andrew771
30.04.2014, 14:14
миль пардон, но где Вы их раскопали?оО
вот тут большие залежи: http://exmortis.narod.ru/src_compilers.html
так?
Вроде как 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 ----------
Если операнд равен нулю, то признак переноса CF
сбрасывается (=0); во всех остальных случаях он устанавливается
(=1)
ха.. А на Спектруме по-моему наоборот. Вот я и запутался.
denpopov
30.04.2014, 14:23
Andrew771, я взял из описания NortonGuide
Andrew771
30.04.2014, 14:27
Andrew771, я взял из описания NortonGuide
я верю :)
а на Спеке флаг CY наоборот устанавливается или нет при команде NEG? И как влияют на CY команды ADC и SBC?
denpopov
30.04.2014, 14:54
И как влияют на CY команды ADC и SBC?
adc A,n A=A+n+CY
sbc A,n A=A-n-CY
кажется так..
Andrew771
30.04.2014, 15:03
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
Я вот не вижу смысла тут 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
С точностью до наоборот
Logical (eax=eax?-1:0)
Logical Not (eax=eax?0:-1)
Где можно почитать про современные алгоритмы кодогенерации (с оптимизацией)?
alone, я тебе говорил где посмотреть про компиляторы.
Y.N. Srikant, Priti Shankar. The Compiler Design Handbook: Optimizations and Machine Code Generation, Second Edition
http://giant.pourri.ch/FAIL/The%20Compiler%20Design%20Handbook%202nd%20Ed.pdf
denpopov
04.05.2014, 19:16
вряд ли это пригодится:
Sijmen Woutersen, "Building a C Processor"
http://x32.ewi.tudelft.nl
Powered by vBulletin® Version 4.2.5 Copyright © 2026 vBulletin Solutions, Inc. All rights reserved. Перевод: zCarot