Дефекты реализации

Здесь перечислены как ошибки, так и просто неоптимальные решения. Их оказалось не так уж мало, но как ни странно, они не помешали реализовать сам компилятор и были выявлены очень поздно. Ошибки перечислены в порядке их обнаружения.

Некорректная загрузка значения

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

struct S char @p1; char @p2; end S @s; begin //Инициализация @s char @p1=@s.p1; char @p2=@s.p2; //Ошибка end

Код:

les DI,DS:[0] mov AX,ES:[DI] mov DX,ES:[DI+2] mov SS:[BP-4],AX mov SS:[BP-2],DX les DI,DS:[0] mov AX,DS:[DI+4] ;Ошибка - вместо регистра ES используется DS mov DX,DS:[DI+6] ; mov SS:[BP-8],AX mov SS:[BP-6],DX

По видимому источник ошибки - использование copy/paste.

Неоптимальный способ проверки типа символа

Компилятор был написан на языке C и в силу непонятных причин вместо макроса isalpha использовался следующий код:

#define ALPHA "AaBbCcDdEeFfGgHhIiJjKkLlMmNnOoPpQqRrSsTtUuVvWwXxYyZz_" if (strchr(ALPHA,Ch)!=NULL) { //Ch - буква }

После перевода исходного текста с C на Context этот код перобразовался в

define @ALPHA "AaBbCcDdEeFfGgHhIiJjKkLlMmNnOoPpQqRrSsTtUuVvWwXxYyZz_" word strpos(char @Buff; char Ch) word P=0; while Buff[P]!=#0 do if Buff[P]=Ch then return 0; end inc P; end return 1; end if strpos(@ALPHA,Ch)=0 then //Ch - буква end

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

word isalpha(char Ch) if 'a'<=Ch & Ch<='z' then return 0; end if 'A'<=Ch & Ch<='Z' then return 0; end if Ch='_' then return 0; end return 1; end

Макрос isalpha обычно реализуется так:

#define isalpha(_c) (_pctype[_c] & (_UPPER | _LOWER)) //_pctype должен быть заполнен заранее

Слишком частый вывод информации о процессе

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

Лишние префиксы замены сегмента

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

Лишняя запись промежуточного результата в стек

begin word A=1; word B=2; word C=A+B+3; end

Код:

mov AL,1 xor AH,AH mov SS:[BP-2],AX mov AL,2 xor AH,AH mov SS:[BP-4],AX mov BX,SS:[BP-4] mov AX,SS:[BP-2] add AX,BX push AX ;Ошибка - регистр AX ниже не используется mov BL,3 xor BH,BH pop AX add AX,BX mov SS:[BP-6],AX

Скорее всего источник ошибки - использование copy/paste. Также по-видимому лучше вместо загрузки байта и обнуления AH/BH загружать в AX/BX слово, хотя различные процессоры могут отнестись к этому по-разному. Приведенный код хоть и не хорош, но по крайней мере правильно работает.

Лишние действия при обращении к элементу массива

char A[256]; begin word I=0; A[I]='A'; end

Код:

mov BX,SS:[BP-2] mov SI,BX mov DI,SI mov AL,65 mov DS:[DI+0],AL

Позже для случаев типа приведенного был реализован специальный вариант генерации кода:

mov DI,SS:[BP-2] mov AL,65 mov DS:[DI+0],AL

Некорректное сравнение ссылки с NULL

begin char @p=NULL; if @p=NULL then return end end

Код:

xor DX,DX xor AX,AX mov SS:[BP-4],AX mov SS:[BP-2],DX mov AX,SS:[BP-4] mov DX,SS:[BP-2] xor CL,CL xor DX,AX ;Ошибка - должна использоваться команда or jnz A mov CL,1 A:mov AL,CL or AL,AL jnz B jmp C B:nop mov AX,4C00H int 21H C:nop

Если случайно окажется, что сегмент и смещение объекта имеют одинаковые ненулевые значения, ссылка на этот объект будет ошибочно посчитана пустой. Разумеется, без записи результата сравнения в CL обойтись можно, но это плата за простоту компилятора выражений. В тексте компилятора нигде не нужно проверять инициализацию ссылок, так что и эта ошибка была выявлена не сразу. Сейчас уже сложно выяснить, почему такая ошибка была сделана.

Зависание при незакрытом комментарии

Ошибка проявлялась если в тексте программы был незакрытый комментарий:

begin /*char c; end

В функции Scan() отсутствовал выход из цикла пропуска пробелов/комментариев при достижении конца файла. Возвращаемый функцией Read() символ EOF (#26) никак не учитывался.

Первое исправление ошибки также было некорректным. Замена возврата EOF завершением работы и выдачей диагностического сообщения устранило эту ошибку, до создало другую - если после завершающего программу слова end не было символов, компиляция завершалась сообщением об обнаружении конца файла. Начав считывать слово, сканер вызывает функцию Read() пока она не вернет символ, не являющийся ни буквой ни цифрой. После считывания буквы d опять взывается функция Read() и на этом все заканчивалось:

word P=0; while isalpha(Read())=0 | isdigit(Read())=0 do Buff[P]=Read(); inc P; if P>=idSIZE then Stop(@emSIZE); end Next(); end

Ошибка не была замечена, поскольку используемый автором текстовый редактор вставлял символы CR/LF и в конце последней строки текста тоже.

Некорректная трактовка вложенного строчного комментария

/*Комментарий //Вложенный комментарий*/

Приведенный фрагмент воспринимается компилятором как завершенный комментарий. В языке C++ это так и есть, комментарии не могут быть вложенными и вторая строка не считается однострочным комментарием. В Context'е комментарии могут вкладываться друг в друга и вторая строка должна считаться вложенным комментарием.

Неоптимальная реализация чтения символа

Для чтения символа из компилируемого файла использовалась пара функций Read() и Next():

char Read() // Чтение текущего символа ... end void Next() // Переход к следующему символу ... end

Если требуется чтение символа, нужно последовательно вызвать обе эти функции. Замена их парой функций Look() и Read() позволяет немного сократить код:

char Look() // Чтение текущего символа (переименованная функция Read()) ... end char Read() // Чтение текущего символа и переход к следующему ... end

Вместо вызова Read() нужно выполнять вызов Look(), вместо вызовов Read() и Next() - только вызов Read().

Некорректное сравнение вещественных чисел

Две ошибки проявлялись при компиляции следующей программы:

begin real a=1.0; real b=a; if a<b then return end if a<b+1.0 then return end end

Код:

fld SS:[BP- 8] fld SS:[BP-16] fcompp sub SP,2 mov BX,SP fstsw SS:[BX] fwait mov AX,SS:[BX] add SP,2 sahf jae A ;Ошибка - должно быть ja jmp B A:nop mov AX,4C00H int 21H B:nop fld SS:[BP-16] mov BX,I ;Загрузка смещения константы 1.0 fld CS:[BX+ 8] faddp fld SS:[BP-8] fcompp sub SP,2 mov BX,SP fstsw SS:[BX] fwait mov AX,SS:[BX] add SP,2 sahf jb C ;Вторая ошибка (некорректная замена jae) скомпенсировала первую jmp D C:nop mov AX,4C00H int 21H D:nop

В отличие от сравнения целых и символьных операндов, которое по умолчанию есть сравнение первого операнда со вторым (результат команды cmp AX/AL, BX/BL и есть результат сравнения), для вещественных чисел по умолчанию используется сравнение второго операнда с первым (первый операнд загружается первым, но на вершине стека сопроцессора оказывается второй операнд). Соответственно требуется замена условия ("меньше" на "больше" и т.п.) и она выполнялась некорректно (в частности условие "меньше" почему-то заменялось на "больше или равно"). Если же второй операнд вычисляется раньше первого, выполнялась еще одна некорректная замена условия. Кроме того, для загрузки значения регистра состояния сопроцессора следует выделять два байта в стеке при входе в функцию.

Некорректный код inc/dec

Ошибка в Context 2.0:

struct S word w1; word w2; end S s; begin s.w2=0; inc s.w2; end

Код:

mov EAX, 0 mov dword ptr @@DATA[4], EAX inc dword ptr @@DATA[0] ;Ошибка - смещение 0 вместо 4

По видимому источник ошибки - использование copy/paste.

Некорректный разбор списка параметров функции

Следующий фрагмент считался корректным:

word f(word w;;;) return 0; end

Желание cъэкономить несколько строк привело к следующему коду:

while TRUE do word K=FindType(@Scan(@Buff)); while (K<nType) do ... Scan(@Buff); select case strcmp(@Buff,")") =0: exit case strcmp(@Buff,";") =0: exit case strcmp(@Buff,",")!=0: Stop(@emCOMMA); end end select case strcmp(@Buff,")") =0: exit case strcmp(@Buff,";")!=0: Stop(@emSEMICOLON); end end Корректные списки параметров этот код разбирает правильно, но вот несколько разделителей он пропускает. Правильный код ниже:

if strcmp(@Scan(@Buff),")")!=0 then while TRUE do word K =FindType(@Buff); if K>=nType then Stop(@emUNDEFINED); end while TRUE do ... Scan(@Buff); select case strcmp(@Buff,")") =0: exit case strcmp(@Buff,";") =0: exit case strcmp(@Buff,",")!=0: Stop(@emCOMMA); end end select case strcmp(@Buff,")") =0: exit case strcmp(@Buff,";")!=0: Stop(@emSEMICOLON); end Scan(@Buff); end end

Некорректная проверка наличия имени в словаре

Ошибка в Context 2.0.

word I= Find(@Buff); if I>nDict then // Ошибка - должно быть >= Stop(@eUNDEFINED); end select case Dict[I].Class=cCONST: P1=Peek(); ... default: Stop(@eUNDEFINED); end

Функция Find может возвращать значение от 0 до nDict, так что условие I>nDict всегда ложно и дальнейшее зависит от значения поля Class неинициализированного элемента массива.

Некорректное завершение кода функции

Ошибка проявлялась при компиляции следующей программы:

void f(word w) if w=0 then return end end begin f(1); end

Код:

jmp F A:push BP mov BP,SP mov AX,00000 sub SP,AX mov BX,0 mov AX,SS:[BP+4] xor CL,CL cmp AX,BX jne B mov CL,1 B:mov AL,CL or AL,AL jnz C jmp D C:nop mov SP,BP pop BP retn 2 D:nop ;Ошибка - нет восстановления SP/BP и retn F:push BP mov BP,SP mov AX,00000 sub SP,AX mov AX,1 push AX call A mov SP,BP pop BP mov AX,4C00H int 21H

После выполнения call управление вновь попадает в начало главной функции (метка F) и call выполняется снова. Со всеми вытекающими последствиями.

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

В первой версии компилятора ошибка отсутствовала - код функции завершался командой ret независимо ни от чего. В последующих ни одна из функций не завершалась выходом по условию. В Windows-версии факт отсутствия оператора возврата устанавливался путем анализа промежуточного представления программы и эта ошибка отсутствовала.

Неполный список зарезервированных слов

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

begin int then=0; int else=0; if then=0 then then=else; else else=then; end end

В Windows-версии список появился и использовался для запрета использования зарезервированных слов в качестве идентификаторов. Но список никак не связан с синтаксическим анализатором и не обязан совпадать с распознаваемыми им словами. При реализации цикла repeat/until (в минимальной версии он отсутстует) оба слова не были добавлены в список. Следовало добавить их еще в минимальной версии - слово function, например, было в списке, хотя типы-функции не были реализованы. А вот inline появилось только в версии 2.14, до нее его необходимость была неочевидна и здесь возможна несовместимость с ранее написанными программами. Основная проблема здесь в том, что некорректное содержание списка слов не проявляется при компиляции правильной программы.

Некорректная вставка файла

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

//inc1.inc - после beg не должно быть никаких символов! include "inc2.inc" *3 beg //inc2.inc define N 1+2 //main.ctx include "inc1.inc"in int n=N; end

Нехорошо в нем почти все:

Нечто похожее возможно и в C++:

//inc1.cpp #include "inc2.cpp" *3; void main( //inc2.cpp const int N=1+2 //main.cpp #include "inc1.cpp" ) { int n=N; }

Ключевое слово не может быть разбито на части, в остальном все то же самое.

Некорректный код косвенного вызова функции

;call dword [EAX] ;Ошибка call EAX

Код был бы правильным, если бы в EAX был не адрес функции, а адрес ячейки памяти, содержащей адрес функции. В DOS-версии компилятора этой ошибки не было.

Некорректное вычисление смещения элемента массива

Ошибка в Context 2.0. Имеет место, в частности, при компиляции следующего примера:

struct S byte M[10][10]; end S T[10]; begin byte B=T[1].M[2][3]; end

Создаваемый код неправильно вычисляет смещение и разрушает стек:

mov EAX, 1 imul EAX, 100 mov EBX, 2 xchg EAX, EBX ;Ошибка - пропущена команда push EAX imul EAX, 10 mov EBX, 3 add EAX, EBX pop EBX add EAX, EBX mov AL, byte [@@DATA+EAX+0] mov byte [EBP-4], AL

Помимо ошибки код включает много лишних действий. В данном случае он легко сводится к двум командам:

mov AL, byte [@@DATA+123] mov byte [EBP-4], AL

Ошибка связана с некорректным использованием признака занятости регистра EAX (fEAX). Исправление потребовало полной замены фрагмента кода, отвечающего за вычисление смещения элемента массива (iINDEX). По-видимому, в простых случаях ошибка не проявляется.

Вообще, использование fEAX нельзя считать хорошим решением, правильнее использовать некую схему предварительного распределения регистров (хотя бы локальную), но по ряду причин это не было сделано.

Длинные функции

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

char @Scan(char @Buff) is word Flag:=0; while Flag =0 do SkipSpaces(); ReadSym(@Buff); Flag:=SkipComment(@Buff); end return @Buff; end

или, если использовать отсутствующий в минимальных версиях компилятора цикл repeat/until:

char @Scan(char @Buff) is repeat SkipSpaces(); ReadSym(@Buff); until SkipComment(@Buff)!=0; return @Buff; end

Вызываемые функции также могут быть разбиты на части.

Отсутствие проверок завершающих символов

В компиляторе Tiny Context не проверяются символы, следующие за выражениями (в частности, оператор присваивания и точка с запятой после присваивания). Это сделано сознательно для сокращения объема кода (было желание получить работающий код короче 1000 строк), но как выяснилось, может приводить к неочевидным и нежелательным результатам, а именно успешой компиляции некорректной программы и генерации отличного от ожидаемого кода. Пример (фрагмент функции val, преобразующей строку в число):

N:=E?N; //Ошибка - несуществующий оператор N:=N+K;

Знак вопроса вызывает завершение компиляции первого выражения и трактуется как точка с запятой, следующая точка с запятой трактуется как оператор присваивания, оператор присваивания - как точка с запятой, а плюс как оператор присваивания:

N:=E; N:=N; N:=K;

Это было обнаружено при переводе компилятора на платформу MOS6502. На месте знака вопроса остался оператор умножения, который не реализовывался и должен был быть заменен вызовом функции mul. В результате код компилировался, но преобразования работали неверно.

Лишние сравнения

В первоначальных вариантах компиляторов Tiny Context для восьмиразрядных систем CP/M-80 и Apple DOS/6502 для сравнения значений двух выражений генерировался следующий код (пример проверки условия A < B в операторе if для i8080, код для MOS6502 аналогичен и не приводится):

... ;Значение B в паре регистров DE pop H ;Значение A в паре регистров HL mov A, H sub D ;Сравнение старших байтов jc T jnz F mov A, L sub E ;Сравнение младших байтов jnc F T:... ;Действия при истинности условия F:... ;Следующие действия

Тот же результат можно получить выполнив два вычитания и одно сравнение:

... ;Значение B в паре регистров DE pop H ;Значение A в паре регистров HL mov A, L sub E mov A, H sbb D jnc F ... ;Действия при истинности условия F:... ;Следующие действия

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

Некорректная проверка равенства порядков ссылок

При инициализации ссылки на функцию не проверяется равенство их порядков. Следующий код код компилируется но, естественно, не работает:

word function F(word X) word g(word X) return X; end begin F @@f1 := @g; //Ошибка - лишний символ @ перед f f1(1); //Segmentation fault end

Такой код тоже компилируется:

begin F @f; f:=@g; //Ошибка - нет символа @ перед f f(1); //Segmentation fault end

Ошибка была обнаружена только при переходе от версии 2 к версии 3.

Поиск включаемых файлов в текущем каталоге

Если в программе встречается директива вставки, например

include "system.inc"

поиск файла system.inc выполняется в текущем каталоге. Если компилируемая программа (и включаемый файл) находятся где-то еще и в командной строке задается путь к ней, то включаемый файл не будет найден (или он будет взят из текущего каталога, если файл с таким именем в нем есть).

Ошибка была обнаружена только при переходе от версии 2 к версии 3.

Преобразование $ и 0x в ноль

Ошибка в преобразующей строку в число функции Val присутстует во всех версиях компилятора кроме самой первой. Ошибка была внесена при реализации преобразования строковых представлений чисел в шестнадцатеричной системе счисления. Если строка начинается с префикса, индекс в ней увеличнивается на его длину, затем выполняется цикл преобразования. Но если для строковых представлений чисел в десятичной системе счисления ошибки нет (функция Val вызывается только если строка начинается с цифры), то для представлений чисел в шестнадцатеричной системе нужно еще проверять наличие хотя бы одного символа после префикса. Это не было сделано.

К слову, заимствованное из Turbo Pascal использование $ в качестве префикса не так уж хорошо. Если будет нужно добавить представления чисел в системах счисления с другим основанием (например 2), сделать это по аналогии сложно, т.к. выбор символов для префикса ограничен и неочевиден. Аналогия с 0x лучше, но и здесь не все хорошо. Например, 0o (ноль-о) в качестве префикса числа в восьмеричной системе может восприниматься как два нуля. А вот 0b в качестве префикса числа в двоичной системе счисления вполне подходит.

Исчезновение инициализированной переменной

При компиляции следующего кода происходит ошибка:

char @P := "QWERTY"; begin char @Q := @P; // Undefined identifier end

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

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

Ошибка при разборе логического выражения

При компиляции следующего кода выдается сообщение о несовместимости типов:

begin word N := 1; char @P := NULL; if N = 0 | @P = NULL then null end end

Результат сравнения ссылки с NULL имеет логический тип для обозначения которого используется константа nDICT (максимально возможное число элементов словаря). Тип устанавливается правильно, но затем при проверке операндов логического сложения выполняется проверка равенства нулю их порядков ссылок (nRef) и это приводит к ошибке т.к. при разборе сравнения с NULL nRef не обнуляется. При проверке типа выражения в условных операторах nRef не анализируется и это не ошибка поскольку ссылок на объекты логического типа быть не может (такие объекты существуют только во время оценки условий и нигде не сохраняются).

Ошибка была обнаружена только в Context 3, куда она благополучно перешла из Context 2. В версиях для DOS этой ошибки не было.

Дефекты в тестовой программе (arctest)

Для тестирования быстродействия создаваемого компиляторм кода (а также быстродействия процессоров) использовался в том числе и архиватор, реализующий алгоритм LZSS. Для поиска совпадений в нем был использован алгоритм KMP (Кнута-Морриса-Пратта), для вычисление массива сдвигов образца (Tmp - образец, D - массив сдвигов) был написан следующий неочевидный код:

int J=pTxt; int K=0; while K<N do Tmp[K]=Txt[J]; inc K; inc J; end int D[STR_LEN1]; D[1]=0; J=1; K=0; while J<N do while Tmp[J]=Tmp[K] do inc J; inc K; select case J>=N: D[J]=K; exit case Tmp[J]!=Tmp[K]: D[J]=K; default: D[J]=D[K]; end end if K>0 then K=D[K]; loop end inc J; D [J]=0; end

Сейчас уже невозможно вспомнить, как он был получен. Сделав ряд преобразований, аналогичных приведенным в описании алгоритма КМП, можно получить эквивалентный код (D[0] в поиске не использовался, так что отсутствие его инициализации значения не имеет):

D[0]=-1; J= 0; K=-1; while J<N do while K>=0 & Tmp[J]!=Tmp[K] do K=D[K]; end inc J; inc K; select case J>=N: D[J]=K; exit case Tmp[J]!=Tmp[K] | K=0: D[J]=K; default: D[J]=D[K]; end end

Это почти тоже самое, что приводится во множестве источников, за исключением условия K=0 во второй ветви select'а. Дополнительное условие приводит к тому, что в ряде случаев элементу D[J] присваивается нуль вместо минус единицы. Работу поиска это не нарушает, но приводит к небольшим дополнительным затратам. Преобразованный код неоптимален и может быть немного улучшен.

Собственно поиск совпадений

byte T=Txt[pTxt]; int M=pTxt+N; int S=0; int L=1; J=I; K=0; while TRUE do while Txt[J]=Tmp[K] do if K>=N then exit end inc J; inc K; end if K>0 then if L<=K then if J>=M then exit end S=J; L=K; end K=D[K]; loop end inc J; while Txt[J]!=T do inc J; end inc J; inc K; end

тоже можно улучшить (и это дает более заметный выигрыш)

byte T=Txt[pTxt]; int M=pTxt+N; int S=0; int L=1; J=I; while Txt[J]!=T do inc J; end inc J; K=1; while TRUE do while K<N & Txt[J]=Tmp[K] do inc J; inc K; end if L<=K then if J>=M then exit end S=J; L=K; end K=D[K]; while K>=0 & Txt[J]!=Tmp[K] do K=D[K]; end if K>=0 then inc J; inc K; loop end inc J; while Txt[J]!=T do inc J; end inc J; K=1; end

Скомпилированный с помощью gcc C-эквивалент исправленного и улучшенного кода на Intel Core i5 работает процентов на двадцать быстрее неоптимального оригинала. Но очень сложно найти те многочисленные машины, на которых тестировался неоптимальный код.

И последнее. Для поиска в словаре использован простой перебор, соответственно время поиска пропорционально квадрату числа имен, уже находящихся в словаре. Но это не ошибка. Точнее проявится она только при компиляции программы, содержащей тысячи или десятки тысяч объектов, например:

word N00001; word N00002; word N00003; ... word N32767; begin N32767=0; end

Эта программа бессмысленна и число объектов в ней значительно превышает возможности DOS-версии компилятора. Реальная же программа, содержащая такое количество объектов должна быть разбита на части (модули или классы), иначе разобраться в ней будет сложно.

Рейтинг@Mail.ru
Сайт создан в системе uCoz