Разработка лексического и синтаксического анализатора на языке высокого уровня

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

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

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

‹значение_атрибута, тип_токена, подтип_токена, позиция›

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

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

Недетерминированный конечный автомат (НКА) - это пятерка

M = (Q, T, D, q0, F), где

Q - конечное множество состояний;

T - конечное множество допустимых входных символов (входной алфавит);

D - функция переходов (отображающая множество QЧ (T{e}) во множество подмножеств множества Q), определяющая поведение управляющего устройства;

q0 Q - начальное состояние управляющего устройства;

F Q - множество заключительных состояний.

Работа конечного автомата представляет собой некоторую последовательность шагов, или тактов. Такт определяется текущим состоянием управляющего устройства и входным символом, обозреваемым в данный момент входной головкой. Сам шаг состоит из изменения состояния и, возможно, сдвига входной головки на одну ячейку вправо (рис. 2).

Рис. 2. Работа конечного автомата

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

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

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

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

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

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

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

Рис. 3. Взаимодействие лексического анализатора с синтаксическим

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

Иллюстрацией такого случая может служить пример оператора присваивания из языка программирования Си++

k = i+++++j;

который имеет только одну верную интерпретацию (если операции разделить пробелами):

k = i++ + ++j;

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

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

Чтобы избежать параллельной работы лексического и синтаксического анализаторов, разработчики компиляторов и языков программирования часто идут на разумные ограничения синтаксиса входного языка. Например, для языка Си++ принято соглашение, что при возникновении проблем с определением границ лексемы всегда выбирается лексема максимально возможной длины. Для рассмотренного выше оператора присваивания это приводит к тому, что при чтении четвертого знака + из двух вариантов лексем (+ - знак сложения, ++ - оператор инкремента) лексический анализатор выбирает самую длинную, т.е. ++, и в целом весь оператор будет разобран как k = i++ ++ +j;, что неверно. Любые неоднозначности при анализе данного оператора присваивания могут быть исключены только в случае правильной расстановки пробелов в исходной программе.

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

Рис. 4. Скриншот программы - таблица лексем

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

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

bool alyzer:lex (const string& text)

{

position.p = 0;

if (is_spec) {

tokens_buffer.clear();

}

 // если текст text пуст - выход

if (text.empty())

{position.s++;

return false;}

if (text.find_first_not_of (» \n\t\v\r\f»)==text.npos)

{

position.s++;

return true;

}

unsigned prev_position=-1; // предыдущая позиция; для отслеживания смещения

token t; // очередной токен

 // сканиурем токены, пока не дойдем до конца скрипта

bool flag=false;

do

{

 // если смещения на следующую лексему по какой-либо причине не произошло

if (prev_position==position.p)

return false;

prev_position = position.p;

t=skan(text);

unsigned e_p=t.word.find («_the_end\a»);

if (e_p!=text.npos) {

flag=true;

string:size_type p_beg;

p_beg=t.word.find («_the_end\a»);

t.word.erase (p_beg);

}

if (t.word!=»» && t.word.find_first_not_of (» \n\t\v\r\f»)!=text.npos && t.word!= «I_am_empty»)

{

tokens_buffer.push_back(t);

}

}

while(! flag);

return true;

}

2. Синтаксический анализатор

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

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

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

В синтаксическом анализе был применен метод рекурсивного спуска, основанный на «зашивании» правил грамматики непосредственно в управляющие конструкции распознавателя. Идеи нисходящего разбора, принятые в LL(1) - грамматиках, в нем полностью сохраняются:

- происходит последовательный просмотр входной строки слева-направо;

- очередной символ входной строки является основанием для выбора одной из правых частей правил группы при замене текущего нетерминала;

- терминальные символы входной строки и правой части правила «взаимно уничтожаются»;

- обнаружение нетерминала в правой части рекурсивно повторяет этот же процесс.

В методе рекурсивного спуска они претерпевают такие изменения:

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

- во входной строке имеется указатель (индекс) на текущий «закрываемый символ». Этот символ и является основанием для выбора необходимой правой части правила. Сам выбор «зашит» в распознавателе в виде конструкций if или switch. Правила выбора базируются на построении множеств выбирающих символах, как это принято в LL(1) - грамматике;

- просмотр выбранной части реализован в тексте процедуры-распознавателя путем сравнения ожидаемого символа правой части и текущего символа входной строки;

- если в правой части ожидается терминальный символ и он совпадает с очередным символом входной строки, то символ во входной строке пропускается, а распознаватель переходит к следующему символу правой части;

- несовпадение терминального символа правой части и очередного символа входной строки свидетельствует о синтаксической ошибке;

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

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

void parser:declarations_and_definitions_list (TTreeNode *parent)

{

if (! eoi && next_token.word!=»)») {

if (next_token.type== «specifier» || next_token.type== «type») {

 // если встреччен токен спецификатора или типа, то переходим в процедуру проверки правильности объявления переменных

bool need_semi=declaration(parent);

if (need_semi) {

match(»;»);

} // после проверки правильности объявления переменной рекурсивно вызываем текущую процедуру

declarations_and_definitions_list(parent);

}

else if (next_token.word==» (») {

parent=tree->Items->AddChild (parent, "{}»);

match(«(»);

declarations_and_definitions_list(parent);

match(»)»);

}

else if (! eoi) {error («Syntax error: declaration syntax»);

step_up();

declarations_and_definitions_list(parent);}

}

}

Таким образом, необходимо описать все возможные варианты грамматики используя if / switch., что требует большого количества времени. В настоящее время получила распространение программа автоматизированного составления синтаксического анализатора - YACC. Программа YACC (Yet Another Compiler Compiler) предназначена для построения синтаксического анализатора контекстно-свободного языка. Анализируемый язык описывается с помощью грамматики к пиле, близком форме Бэкуса - Наура (нормальная форма Бэкуса-Наура - НФБН). Результатом работы YACC является исходный текст программы синтаксического анализатора. Анализатор, который порождается YACC, реализует восходящий LALR(l) распознаватель.

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

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

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

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

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

void parser:var_list_1 (TTreeNode* parent)

{if (! is_sizeof)

{if (next_token.word==»,» &&! is_argument) { // после константы или идентификатора стоит запятая

parent=change_nodes (parent,»,»); // меняем корень с «=» на «,»

match(»,»);

if (next_token.word==» (» ||

next_token.type== «identifier» ||

next_token.word== "*» ||

next_token.word== "&»)

{

var_init(parent);

var_list_1 (parent);

}

else

{

error («Syntax error: declaration terminated incorrecly»);

}

} // if (next_token.word==»,»)

else if (next_token.word==»,» && is_argument &&

res_a [position+1].type!= «specifier»

&&res_a [position+1].type!= «type») {

error («Syntax error: declaration syntax»);

}}

}

Таким образом, изменив корень дерева, и рекурсивно запустив функции проверки грамматики, мы построим правильное синтаксическое дерево.

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

void parser:step_up()

{

if (position<res_a.size() - 1) {position++; next_token=res_a[position];}

else {eoi=true; next_token.word= «end_of_input\b»; next_token.type= «end_of_input\b»; next_token.subtype= «end_of_input\b»;}

}

3. Работа программного продукта

При запуске приложения, появляется окно пользовательского интерфейса содержащее два пункта меню - «Файл» и «Анализ» рис. 5.

Рис. 5. Скриншот программы - интерфейс пользователя

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

При нажатии на пункт меню «Анализ» - «Лексический анализ» будет выполнено разбиение исходного кода программы на лексемы и создана таблица лексем.

При нажатии на пункт меню «Анализ» - «Синтаксический анализ» программа построит дерево синтаксического разбора, изображенное на рис. 6.

Ошибки полученные в ходе лексического и синтаксического анализов, расположены на соответствующих вкладках рис. 7.

Рис. 6. Скриншот программы - дерево синтаксического разбора

Рис. 7. Скриншот программы - синтаксические ошибки

Выводы