Теория формальных языков и компиляторов (для студентов дневного отделения) — Методические указания и программное обеспечение

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

В прилагаемом файле "WebTransLab Tomcat.zip" находится установочный комплект учебного клиент-серверного пакета программ автоматизации пректирования трансляторов Вебтранслаб.

В файле "TFLandC TrainingSoftwareManual.zip" находится руководство по использованию пакета Вебтранслаб.

Разработка грамматики методом «сверху вниз» с использованием пакета Вебтранслаб

Вначале пишется единственное правило, определяющее наиболее общую синтаксическую конструкцию – правильная программа – которая обозначается, например, нетерминальным символом RightProgram:

RightProgram : FileHeader [ DataOrFunction ]+

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

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

Строится совокупность лексического и синтаксического автоматов по выбранному шаблону.

Рекомендуется использовать для формирования лексического анализатора графовое представление lexAsGRaph…, а для синтаксического – один из нисходящих, т.е.  либо …SyntAsRD…, либо …SyntAsSingleFSM…, либо …SyntAsMultiFSM… . По грамматике, пригодной для построения нисходящего анализатора, всегда можно построить восходящий, но наоборот – не всегда.

Если синтаксический анализатор построить не удалось (этого не случится при самом первом построении, но впоследствии после добавления новых правил – это возможно), то необходимо открыть множества выбора правил (пункт меню «Показать/Множества выбора», найти пары правил с пересекающимися множествами (терминалы, входящие более, чем в одно множество выбора правил с одним нетерминалом в левой части, выделяются фоном), и переработать их. Для этого нужно четко понимать, как формируются множества выбора. После каждого изменения системы правил ее нужно сохранять и автоматы перестраивать.

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

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

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

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

RightProgram : "FileHeader" [ "DataOrFunction" ]+

Нужно только убедиться, что в системе лексических правил есть правило, порождающее такие строки, например keywords : [A-Za-z_]+. Если, например, разработчик использует нетерминалы, имена которых включают только заглавные буквы или начинаются с такой буквы, а все ключевые слова языка содержат только строчные буквы и правило для них выглядит как keywords : [a-z_]+, то нужно временно добавить в лексику правило nonTerminals : [A-Z][a-zA-Z]+. В результате всех этих действий FileHeader и DataOrFunction временно стали псевдотерминалами.

Впоследствии после «отладки» этого правила и включения в грамматику правил для нетерминалов FileHeader и DataOrFunction кавычки вокруг них в правиле для RightProgram нужно не забывать убирать.

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

FileHeader : [@][F][H]                 определяет слово @FH

DataOrFunction : [#][D][F]          определяет слово #DF

Цепочки символов @FH и #DF стали псевдотерминалами. Впоследствии после«отладки» этого правила и включения в грамматику правил для нетерминалов FileHeader и DataOrFunction эти лексические правила нужно не забывать удалять.

Теперь нужно заново строить транслятор, запускать его для тестирования и набирать такой текст, который «ожидает» синтаксический анализатор. При использовании первого способа, этот текст может выглядеть так:

FileHeader    DataOrFunction DataOrFunction DataOrFunction

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

@FH #DF    #DF    #DF    #DF    #DF    #DF    #DF    #DF

Или так:

@FH #DF

Рекомендуется также предъявить тестируемому транслятору неверные последовательности, например:

#DF @FH

или

@FH

Убедившись, что транслятор ожидаемым образом обрабатывает тестовые примеры, нужно выбрать ровно один из не определенных на данный момент нетерминалов (FileHeader или DataOrFunction, но ни в коем случае не оба сразу) и написать для него правило (или правила). Для примера:

DataOrFunction : FunctionHeader FunctionBody

Один нетерминал (DataOrFunction) теперь должен быть удален из набора псевдотерминалов, но в этот набор нужно включить два новых неопределенных нетерминала FunctionHeader и FunctionBody. Теперь нужно выполнить очередной цикл «отладки», т.е. превращения новых неопределенных нетерминалов в псевдотерминалы, построения автоматов, проверки множеств выбора, запуска и тестирования транслятора.

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

Основные ограничения, которые следует соблюдать, иначе можно «забрести» не туда, куда нужно:

1. На каждом повторении цикла «отладки» переводить из неопределенных в определенные нужно ровно по одному нетерминалу. Любые поспешные действия в целях ускорить процесс обычно приводят только к его замедлению.
2. Любое, даже самое незначительное, изменение грамматики нужно обязательно тестировать.
3. При формировании новых правил не следует вводить больше двух-трех новых неопределенных нетерминалов.
4. Новые правила нельзя писать слишком длинными. Правая часть каждого правила не должна содержать больше четырех, максимум пяти символов (и терминалов, и нетерминалов). Вот три примера расшифровки нетерминала CycleOperator:

CycleOperator : "for" "(" Initiation ";" Testing ";" NextIteration ")" CycleBody

CycleOperator : CycleHeader CycleBody

CycleOperator : "for" HeaderFor CycleBody

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

Нужно внимательно изучить презентацию TFLandC13.ppt из общего архива презентаций SlidesTFLandC.zip, который можно загрузить со страницы https://dispace.edu.nstu.ru/didesk/course/show/8639/3.

Далее нужно помнить о том, что каждая строка (фрагмент, элемент) программы на Вашем языке для чего-то нужна. Другими словами – кто-то/что-то будет выполнять некоторые действия, обусловленные наличием этой строки/фрагмента/элемента. Речь идет о тех элементах программы, которые не ассоциируются с выполняемыми операторами, такими как присваивание, цикл, условный оператор, переключатель, оператор возврата значения, выхода из цикла, … Речь идет об объявлениях переменных (локальных или глобальных), определениях функций и их формальных аргументов. Все эти объявления должны преобразовываться в ПФЗ точно так же, как и выполняемые операторы.

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

((a + 2 * sin(b)) * c – d / 3) / (e +4)

ПФЗ этого выражения выглядит так (sin – это знак унарной операции, такой же как + или *):

a 2 b sin * + c * d 3 / - e 4 + /

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

Так вот, преобразование в ПФЗ (или АСД) нужно выполнять с прицелом на то, что получающееся представление программы может содержать только вышеописанные операции.

В презентации TFLandC13.ppt приведены два примера: формирование ПФЗ для оператора присваивания с вычислением произвольного арифметического выражения и формирование ПФЗ для оператора цикла while. Приведем еще один пример – вычисление нигде не реализованного квадрупольного условного выражения, кое в чем аналогичного условному выражению в языке Си, которое мы определим так:

ArithmExpr ??? ExprForMinus : ExprForZero : ExprForPlus

Смысл таков: вначале вычисляется ArithmExpr, затем, если полученное значение меньше нуля, то вычисляется ExprForMinus, если равно нулю, то ExprForZero, и если больше нуля, то вычисляется ExprForPlus. Значение всего этого выражения будет последнее вычисленное значение. Вот пример:

x – y ??? 2 * x – y : x + y : -5

Последовательность действий описана, теперь ее надо реализовать в виде постфиксной записи

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

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

QuadroExpr : Expression "???" Expression ":" Expression ":" Expression

(пронумеруем выражения: Expression1 "???" Expression2 ":" Expression3 ":" Expression4)

1. Теперь нужно записать требуемый вид постфиксной записи вычисления этого квадрупольного выражения, имея в виду, что:

• В псевдокоде нет знаков операций "???" и двух разных ":"
• ПФЗ всех входящих в него выражений будут формироваться при обработке синтаксическим анализатором правил для нетерминала Expression (пока не обращаем внимания, что каждое из них тоже может быть квадрупольным выражением; об этом вспомним чуть позже).

Вот возможный вариант:

• defineVar QEVar ПФЗ(Expression) "=" QEVar 0 "<" QElabel1 GoOnFalse ПФЗ(Expression) QElabel3 Go QElabel1: QEVar 0 "==" QElabel2 GoOnFalse ПФЗ(Expression) QElabel3 Go QElabel2: ПФЗ(Expression) QElabel3:

Здесь объявляется (знак операции defineVar) и используется переменная QEVar (при реализации транслятора на языке JavaScript тип этой переменной не нужен, она всегда будет объявляться со словом var), которой нет в тексте программы (и потом надо будет хорошенько подумать, как избежать возможного совпадения имен переменных, объявленных в транслируемой программе с именами, вводимыми для нужд синтаксического и семантического анализа). Вычисляется значение первого выражения и сохраняется в QEVar, затем значение этой переменной операцией "<" сравнивается с нулем  и выполняется передача управления на метку QElabel1:, если сравнение вырабатывает ложь. Если же значение QEVar действительно меньше нуля, то вычисляется значение Expression2 и управление передается на метку QElabel3:, т.е. в точку выхода из ПФЗ. Ну и т.д.

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

1. Теперь нужно вспомнить о том, что в тексте программы в разных точках может быть записано несколько разных квадрупольных выражений и что каждое из выражений, встречающихся в некотором квадрупольном выражении, может оказаться тоже квадрупольным выражением. А это означает, что для каждого квадрупольного выражения нужно формировать свои собственные имена вспомогательных переменных и всех меток. Другими словами, для k-го по тексту квадрупольного выражения нужно формировать его собственную переменную QEVar<k> и метки QElabel1<k>, QElabel2<k> и QElabel3<k>. Для подсчета квадрупольных выражений, обнаруженных в транслируемой программе, в любой точке расширения грамматики должна быть доступна целочисленная переменная-счетчик с именем, например, QEcount. Объявление этой переменной с инициализацией нулевым значением нужно написать в боксе «Расширение лексического анализатора» (или «Расширение синтаксического анализатора») основного окна Вебтранслаба. Однако, одной такой переменной недостаточно для организации правильного формирования ПФЗ. При каждом входе в обработку квадрупольного выражения значение этой переменной нужно укладывать на верхушку специального стека для хранения этих счетчиков и копировать его с верхушки стека при каждом формировании имени переменной или метки. Стек также нужно объявить и инициализировать в «Расширении … анализатора» (а также определить операции с этим стеком, функцию putToPfr() и нужные ей структуры данных, например, так, как сделано в 8Actions.xml,):

var QEstack = [];

1. Вот теперь, наконец, приступаем к добавлению действий, расширяющих правило грамматики для нетерминала QuadroExpr:

QuadroExpr : {QECount++; QEstack.put(QECount); putToPFR("QEVar" + QEstack.peek(); putToPFR("var"); putToPFR("defineVar"); putToPFR("QEVar" + QEstack.peek()); }

Expression

{ putToPFR("="); putToPFR("QEVar" + QEstack.peek()); putToPFR("0"); putToPFR("<"); putToPFR("QElabel1" + QEstack.peek()); putToPFR("GoOnFalse");}

"???" Expression

{ putToPFR("QElabel3" + QEstack.peek()); putToPFR("Go"); putToPFR("QElabel1" + QEstack.peek() + ":"); putToPFR("QEVar"+QEstack.peek()); putToPFR("0"); putToPFR("=="); putToPFR("QElabel2" + QEstack.peek()); putToPfr("GoOnFalse"); }

":" Expression

{ putToPFR("QElabel3" + QEstack.peek()); putToPFR("Go"); putToPFR("QElabel2" + QEstack.peek() + ":");}

":" Expression

{ putToPFR("QElabel2" + QEstack.peek() + ":"); QEstack.pop(); }