Описание синтаксиса входного языка
ОБЩИЕ ТРЕБОВАНИЯ К КУРСОВОМУ ПРОЕКТУ
Техническим заданием на разработку компилятора является задание на курсовое проектирование, выдаваемое студентам в начале семестра. При выполнении курсового проекта возможны изменения задания (расширение или упрощение), но все изменения должны быть обоснованы, согласованы с руководителем курсовой работы и документально оформлены.
В процессе выполнения курсовой работы студенты должны разработать описание синтаксиса и семантики входного языка, ориентированное на разработчиков языкового процессора, формальное описание синтаксиса и семантики языка с помощью атрибутных транслирующих грамматик, структуры данных и алгоритмы работы блоков лексического и синтаксического анализа языкового процессора, составить и отладить программные модули, реализующие перевод конструкций входного языка в заданную внутреннюю форму программы.
Результат выполнения курсовой работы оформляется в виде пояснительной записки, содержащей выбор, обоснование и описание принятых решений, внешние и внутренние спецификации модулей.
При защите курсовой работы студент должен уметь обосновывать принятые решения и продемонстрировать программную реализацию перевода для разных входных данных, как правильных, так и содержащих ошибки.
В процессе выполнения курсовой работы возможно использование специализированных программных средств, разработанных на кафедре математического обеспечения и применения ЭВМ и изучаемых в лабораторном практикуме по дисциплине «Теория языков программирования и методы трансляции». Использование других программных средств возможно только при согласовании с руководителем курсовой работы.
ЭТАПЫ ВЫПОЛНЕНИЯ КУРСОВОГО ПРОЕКТА
Описание входного языка
В этом разделе пояснительной записки, который является результатом выполнения первого этапа курсового проекта, приводится описание синтаксиса и семантики входного языка, ориентированное на разработчиков языкового процессора.
Описание синтаксиса входного языка
Для описания синтаксиса входного языка необходимо использовать металингвистические формулы Бэкуса-Наура (БНФ) или их модификации, позволяющие более естественно представлять альтернативные, необязательные и повторяющиеся части металингвистических формул [1].
Одна из таких модификаций допускает использование в металингвистических формулах дополнительных метасимволов [, ]и{,}следующим образом:
· необязательные элементы синтаксической конструкции заключаются в квадратные скобки [ и ];
· повторяющиеся нуль и более раз элементы синтаксической конструкции заключаются в фигурные скобки {и }.
Замечание
Для того чтобы квадратные и фигурные скобки, являющиеся терминальными символами определяемого языка отличались от метасимволов – квадратных и фигурных скобок, последние записываются с использованием полужирного шрифта или выделяются каким-то другим образом.
Описание синтаксиса условного оператора некоторого подмножества языка Паскаль с использованием модифицированных БНФ можно записать в виде:
<условный оператор> ::= if< логическое выражение>
then< оператор> [ else<оператор> ]
< оператор> ::= [<метка> : ] <непомеченный оператор>
<непомеченный оператор> ::= <оператор присваивания> |
<условный оператор | <составной оператор>
<оператор присваивания> ::= <простая переменная> := <выражение>
<составной оператор> ::= begin <оператор> { ;<оператор> } end
<метка> ::= <идентификатор>
<простая переменная> ::= <идентификатор>
<идентификатор> ::= <буква> { <буква> | <цифра> }
<буква> ::= a | b | c | d
<цифра> ::= 0 | 1 | 2 |3|4 | 5 | 6 | 7 | 8 | 9
Замечания
1. В приведенном описании условного оператора определения металингвистических переменных <логическое выражение> и <выражение> опущены.
2. В качестве металингвистических переменных рекомендуется употреблять названия определяемых элементов и конструкций языка.
2.1.2. Описание семантики входного языка
В данном разделе определение семантики входного языка выполняется неформально. Описание семантики рекомендуется выполнять для каждой определяемой синтаксической конструкции в отдельности. Описание семантики задает представление данных в оперативной памяти, приоритет выполнения операций, правила преобразования типов языка, правила выполнения операторов языка и реализации языковых конструкций.
Представление данных различных типов в оперативной памяти (размер в байтах и диапазон возможных значений) удобно задавать с помощью таблицы (см. табл. 2.1).
Таблица 2.1
| Тип | Размер в байтах | Диапазон значений |
| char | -128 …127 | |
| int | -32768 … 32767 | |
| float | ±3.4Е-38 … ±3.4Е38 | |
| double | ±1.7Е-308 …±1.7Е308 |
Для задания правил вычисления выражений необходимо задать приоритет выполнения операций и правила преобразования типов.
Приоритет операций и порядок выполнения операций с одинаковым приоритетом удобно задавать с помощью таблицы, в которой операции с одинаковым приоритетом объединены в одну группу, а операции в группе упорядочены в порядке убывания приоритета. Пример задания приоритета операций для некоторого подмножества языка Си приведен в табл. 2.2.
Правила преобразования типов для бинарных операций включают правила автоматического преобразования операндов к одному общему типу, при этом тип результата выполнения операции, как правило, также имеет общий тип. Обычно операнды бинарных арифметических операций разных типов приводятся к старшему (более длинному) типу. Например, правила преобразования для бинарных арифметических операций для некоторого подмножества языка Си могут иметь следующий вид:
· если один из операндов имеют тип double, то другой операнд всегда преобразуется к типу double;
· операнды типа floatперед выполнением операциипреобразуются к типуdouble;
· если один из операндов типа unsigned long, то другой операнд преобразуется к типу unsigned long;
· если один из операндов имеет тип long, а другой – тип unsigned int, то оба операнда приводятся к типу unsigned long;
· если первый операнд типа int, а второй – типаunsigned int, то первый операнд приводится к типу unsigned int;
· если один из операндов типа int, а другой – типа charили unsigned char, то он приводится к типу int;
· при выполнении операции присваивания результат приводится к типу переменной слева от знака операции присваивания, при этом возможно преобразование как старшего типа к младшему, так и наоборот.
Таблица 2.2
| Знак операции | Название операции | Порядок выполнения |
| ++ | Увеличение на единицу | Справа налево |
| -- | Уменьшение на единицу | Справа налево |
| * | Умножение | Слева направо |
| / | Деление | Слева направо |
| + | Сложение | Слева направо |
| - | Вычитание | Слева направо |
| < | Меньше | Слева направо |
| <= | Меньше или равно | Слева направо |
| > | Больше | Слева направо |
| >= | Больше или равно | Слева направо |
| == | Равно | Слева направо |
| != | Не равно | Слева направо |
| && | Логическое И | Слева направо |
| || | Логическое ИЛИ | Слева направо |
Задание правил выполнения операторов языка заключается в описании порядка выполнения операторов. Например, порядок выполнения условного оператора if-then-else языка Паскаль можно задать следующим образом:
1. Вычисляется логическое выражение.
2. Если значение логического выражения «истина», то выполняется оператор, следующий за ключевым словом then, в противном случае выполняется оператор, следующий за ключевым словом else.
Правила реализации конструкций языка определяют особенности реализации языковых конструкций в разрабатываемом языковом процессоре. Ниже приводится ряд примеров таких определений: «Операции целочисленной арифметики выполняются без учета переполнения»; «Вычисление логических выражений производится ускоренным способом: оставшаяся часть логического выражения не вычисляется, если значение логического выражения уже вычислено (например, результат логической операции Иравен нулю, если хотя бы один из операндов равен нулю)»; «Значение параметра цикла в итерационном операторе цикла при нормальном завершении цикла не определено».
При определении семантики необходимо также описать контекстную зависимость конструкций языка, так как БНФ не позволяет определять контекстные условия. Примерами описаний контекстных условий являются: «Каждая переменная, используемая в программе, должна быть предварительно описана»; «Переменная не может быть описана в одном и том же блоке более одного раза».
2.2. Описание этапа лексического анализа
На этапе лексического анализа решаются следующие задачи:
· чтение исходной программы и выделение из нее лексем;
· построение таблиц идентификаторов и констант;
· преобразование входной программы (поток литер) в поток токенов, в котором каждый токен представляет лексему.
Соотношение между токенами и лексемами для различных языковых конструкций иллюстрируется табл. 2.3.
Таблица 2.3
| Токен | Лексемы | Языковая конструкция |
| id | str, count, index | Идентификатор |
| if | if | Ключевое слово if |
| rel | <, <=, =, <>, >, >= | Операция отношения |
| num | 10, 1024, 255 | Целое число без знака |
| + | +, - | Операция типа «сложение» |
| then | then | Ключевое слово then |
| ; | ; | Символ «;» |
Если в исходной программе при записи лексем были допущены ошибки, лексический анализатор для каждой ошибки должен локализовать место ошибки, выполнить действия по нейтрализации ее последствий (например, прочитать без разбора символы до конца лексемы) и выдать пользователю сообщение об ошибке.
Определим порядок действий, выполняемых при разработке лексического анализатора.