Написание транслятора для языка С

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

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

В данной работе будет представлена частичная реализация транслятора для языка «С» с использованием языка «С++». Данный транслятор будет производить две стадии анализа лексический и синтаксический.

1. Постановка задачи

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

Для демонстрации работы транслятора возьмём в качестве анализируемого следующий код на языке «С»:

#include «dim.h»

int a;

char b='x56';

AnsiString s=" «k'abcd'k» n a 56×56″;

bool c=true;

bool Dim₁ (int v, int e, int d);

void main()

{/* Многострочный

комментарий/*

// Однострочный комментарий

double i_dim₇₈=5465.56, d=321;

double c₁=(013+0Xab+1.*12)*5;

char sim='b';

int i=5*(6+7)+8*sim+++-a;

while (a)

{

switch (sim)

{

case 2: sim='a'; break;

case 3: sim='n'; break;

default: a*=0x56;

}

if (sim==7||sim==8||sim==9)

{

if (sim==-7) {sim++; sim/=2;}

else sim/=2;

if (sim==8) {sim++; sim/=03;}

else sim/=02;

}

else — sim;

a++;

}

for (int j=0; j<3; j++)

Dim₁ (2,4,8);

return 0;

}

bool Dim₁ (int v, int e, int d)

{

return 1;

}

2. Общие сведения

программа транслятор язык лексика

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

Компилятор — это обслуживающая программа, выполняющая трансляцию на машинный язык программы, записанной на исходном языке программирования. Компилятор обеспечивает преобразование программы с одного языка на другой (чаще всего, в язык конкретного компьютера). Вместе с тем, команды исходного языка значительно отличаются по организации и мощности от команд машинного языка. Существуют языки, в которых одна команда исходного языка транслируется в 7−10 машинных команд. Кроме того, в исходных языках достаточно часто используется строгая типизация данных, осуществляемая через их предварительное описание. Программирование может опираться не на кодирование алгоритма, а на тщательное обдумывание структур данных или классов. Процесс трансляции с таких языков обычно называется компиляцией, а исходные языки обычно относятся к языкам программирования высокого уровня (или высокоуровневым языкам). Абстрагирование языка программирования от системы команд компьютера привело к независимому созданию самых разнообразных языков, ориентированных на решение конкретных задач. Появились языки для научных расчетов, экономических расчетов, доступа к базам данных и другие. Структура компилятора с основными фазами компиляции показана на рисунке 1.1.

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

Рисунок 1.1. Обобщенная структура компилятора

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

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

На этапе семантического анализа выявляются зависимости между частями программы, которые не могут быть описаны контекстно-свободным синтаксисом. Это в основном связи «описание-использование», в частности анализ типов объектов, анализ областей видимости, соответствие параметров, метки и другие. В процессе контекстного анализа строится таблица символов, которую можно рассматривать как таблицу имен, пополненную информацией об описаниях (свойствах) объектов Результатом работы фазы контекстного анализа является атрибутированное дерево программы. Информация об объектах может быть как рассредоточена в самом дереве, так и сосредоточена в отдельных таблицах символов. В процессе контекстного анализа также могут быть обнаружены ошибки, связанные с неправильным использованием объектов.

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

3. Решение задачи

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

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

Рисунок 3.1 — Организация взаимодействия блоков транслятора.

Лексический анализатор полностью обрабатывает исходный текст, формируя на выходе цепочку, состоящую из всех полученных лексем. Только после этого управление передается синтаксическому анализатору. Синтаксический анализатор получает сформированную цепочку лексем и на ее основе формирует промежуточное представление или объектную модель. После получения всей объектной модели он передает управление генератору кода. Генератор кода, на основе объектной модели языка, строит требуемый машинный код.

К достоинствам такого подхода можно отнести:

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

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

— Возможность уменьшения объема оперативной памяти, требуемой для работы транслятора, за счет последовательного вызова фаз.

К недостаткам следует отнести:

— Наличие больших объемов промежуточной информации, из которой в данный момент времени требуется только небольшая часть.

— Замедление скорости трансляции из-за последовательного выполнения фаз и использования для экономии оперативной памяти внешних запоминающих устройств.

Лексический анализ

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

- класс лексемы, определяющий общее название для категории элементов, обладающих общими свойствами (например, идентификатор, целое число, строка символов и т. д.);

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

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

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

Рисунок 3.2 — Прямой метод лексического анализа.

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

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

void TScan: MainLex()

str[i]=='.'

// ;

int TScan: Strings (int pos)

{char *endptr;

AnsiString result="", tmp_s="";

int res_i, len=1; /*" */

for (int i=pos+1; str[i]≠'" '; i++)

{

if (str[i]=='\')

{

i++; len++; /*/*/

switch (str[i])

{

case 'a':

{result+='a'; len++; break;}

case 'b':

{result+='b'; len++; break;}

case 'f':

{result+='f'; len++; break;}

case 'n':

{result+='n'; len++; break;}

case 'r':

{result+='r'; len++; break;}

case 't':

{result+='t'; len++; break;}

case 'v':

{result+='v'; len++; break;}

case '\':case ''':case '" ':case '?':

{result+=str[i]; len++; break;}

case '0': {tmp_s= «0»; len++;

if (LowerCase (str[i+1])=='x')

{tmp_s+= «x»; i++; len++;

for (int j=i; isdigit (str[j+1])||(LowerCase (str[j+1])>='a'&&LowerCase (str[j+1])<='f'); tmp_s+=str [j+1], len++, j++, i++){}

res_i=strtol (tmp_s.c_str(),&endptr, 0);

if (res_i>256) {PrintError («Диапазон Char», pos); break;}

else

result+=(char) res_i; break;

}

if (LowerCase (str[i+1])≠'x')

{

for (int j=i; isdigit (str[j+1]); j++)

{

if (str [j+1]>='0'&&str [j+1]<='7')

{tmp_s+=str [j+1];

i++; len++;

}

else {PrintError («Ошибка в управляющей последовательности!», pos); break;}

}

res_i=strtol (tmp_s.c_str(),&endptr, 0);

if (res_i>256) {PrintError («Диапазон Char в последовательности», pos); break;}

else

result+=(char) res_i; break;

}

}

default: PrintError («Ошибка в управляющей последовательности.», pos);

}

}

else {result+=str[i]; len++;}

if (i+1==str. Length())

{

PrintError («Отсутствует конец строки», pos);

break;

}

}

len++; /*" */

ScanLEX->Lex->Add (new TLexema (ltStr, lpNone, String(result), pos, len));

return len/*" «*/;

}

// ;

int TScan: Comment (int pos) // комментарий

{

AnsiString result=str[pos];

if (str [pos+1]=='*') /**/

{result+=str [pos+1];

for (int i=pos+2;)

{if (str[i]=='*'&&str [i+1]=='/') break;

else result+=str[i];

if (i+1==str. Length())

{

PrintError («Отсутствует конец комментария», pos);

break;

}

i++;

}

result+= «*/»;

}

if (str [pos+1]=='/') //

{for (int i=pos+1; str. SubString (i, 2)≠«rn»&&i+1≠str. Length(); result+=str[i], i++){}

result+=«rn»;

}

return result. Length();

}

Результат работы транслятора на фазе лексического анализа для тестового кода представлен на рисунке 3.3.

Рисунок 3.3 — Результат транслятора на фазе лексического анализа.

Синтаксический анализ

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

Разбор предназначен для доказательства того, что анализируемая входная цепочка, записанная на входной ленте, принадлежит или не принадлежит множеству цепочек порождаемых грамматикой данного языка. Выполнение синтаксического разбора осуществляется распознавателями, являющимися автоматами. Поэтому данный процесс также называется распознаванием входной цепочки. Цель доказательства в том, чтобы ответить на вопрос: принадлежит ли анализируемая цепочка множеству правильных цепочек заданного языка. Ответ «да» дается, если такая принадлежность установлена. В противном случае дается ответ «нет». Получение ответа «нет» связано с понятиям отказа. Единственный отказ на любом уровне ведет к общему отказу.

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

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

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

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

bool TSyntax:statement (TTreeNode* tn)

{

if (match (ltSepar, lpNone)) {MainForm->TreeView->Items->AddChild (tn, «пустой оператор»); return true;}

if (Lev0 (tn)&&match (ltSepar, lpNone)) return true;

if (Declare (tn, false)) return true;

if (match (ltReservedWord, lpIf)) return sIf(tn);

if (match (ltReservedWord, lpFor)) return sFor(tn);

if (match (ltReservedWord, lpDo)) return sDo(tn);

if (match (ltReservedWord, lpWhile)) return sWhile(tn);

if (match (ltReservedWord, lpSwitch)) return sSwitch(tn);

if (match (ltBracket, lpLFigBracket)) return sCompose(tn);

if (match (ltReservedWord, lpBreak)&&match (ltSepar, lpNone)&&in_cycle>0)

{MainForm->TreeView->Items->AddChild (tn, «break»); return true;}

if (match (ltReservedWord, lpContinue)&&match (ltSepar, lpNone)&&in_cycle>0)

{MainForm->TreeView->Items->AddChild (tn, «continue»); return true;}

if (match (ltReservedWord, lpReturn))

{TTreeNode *root=MainForm->TreeView->Items->AddChild (tn, «return»);

return Lev1 (root)&&match (ltSepar, lpNone);}

return false;

}

Рисунок 3.4 — Нисходящий разбор слева на право

// ;

bool TSyntax:sIf (TTreeNode* n)

{

TList *LastBlock=new TList;

Synt->ListBlock->Add(LastBlock);

TTreeNode *root=MainForm->TreeView->Items->AddChild (n, «IF»);

if (! match (ltBracket, lpLCirBracket)) return false;

TTreeNode *root2=MainForm->TreeView->Items->AddChild (root, «условие»);

if (! Lev1 (root2)) return false;

if (! match (ltBracket, lpRCirBracket)) return false;

TTreeNode *root3=MainForm->TreeView->Items->AddChild (root, «then»);

if (! statement(root3)) {PrintError («Нет;»); return false;}

if (match (ltReservedWord, lpElse))

{

TTreeNode *root4=MainForm->TreeView->Items->AddChild (root, «else»);

if (! statement(root4)) return false;

}

return true;

}

// ;

bool TSyntax:sFor (TTreeNode* n)

{

TList *LastBlock=new TList;

Synt->ListBlock->Add(LastBlock);

TTreeNode *root=MainForm->TreeView->Items->AddChild (n, «FOR»);

if (! match (ltBracket, lpLCirBracket)) return false;

// нет объявления

if (match (ltSepar, lpNone));

else

if (! (Lev1 (root)&&match (ltSepar, lpNone))&&! Declare (root, false)) return false;

TTreeNode *root3=MainForm->TreeView->Items->AddChild (root, «exit»);

if (! Lev1 (root3)) return false;

if (! match (ltSepar, lpNone)) {PrintError («Нет;»); return false;}

// нет действий после цикла

if (match (ltBracket, lpRCirBracket));

else

{

TTreeNode *root4=MainForm->TreeView->Items->AddChild (root, «действия после цикла»);

if (! Lev0 (root4)) return false;

if (! match (ltBracket, lpRCirBracket)) {PrintError(«Нет)»); return false;}}

in_cycle++;

TTreeNode *root5=MainForm->TreeView->Items->AddChild (root, «выполнить»);

if (! statement(root5)) return false;

in_cycle -;

return true;

}

// ;

bool TSyntax:sWhile (TTreeNode* n)

{

TList *LastBlock=new TList;

Synt->ListBlock->Add(LastBlock);

TTreeNode *root=MainForm->TreeView->Items->AddChild (n, «WHILE»);

if (! match (ltBracket, lpLCirBracket)) {PrintError («Нет («); return false;}

TTreeNode *root2=MainForm->TreeView->Items->AddChild (root, «условие»);

if (! Lev1 (root2)) return false;

if (! match (ltBracket, lpRCirBracket)) {PrintError(«Нет)»); return false;}

TTreeNode *root3=MainForm->TreeView->Items->AddChild (root, «выполнить»);

if (! statement(root3)) return false;

return true;

}

// ;

bool TSyntax:sCompose (TTreeNode* n)

{

TList *LastBlock=new TList;

Synt->ListBlock->Add(LastBlock);

TTreeNode *root=MainForm->TreeView->Items->AddChild (n, «операторные скобки»);

for (;! match (ltBracket, lpRFigBracket);)

if (! statement(root)) return false;

return true;

}

Результат работы транслятора на фазе синтаксического анализа для тестового кода представлен на рисунке 3.5.

Рисунок 3.5 — Результат транслятора на фазе синтаксического анализа.

Заключение

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