Системное программное обеспечение. Лабораторный практикум

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

5. Выбор формы внутреннего представления программы, методов оптимизации и генерации результирующего кода – это взаимозависимые процессы. Поскольку рассмотренные ранее методы и алгоритмы были основаны на использовании триад, автор не рекомендует пытаться использовать другие формы внутреннего представления.

Необходимую дополнительную информацию можно найти в литературе по компиляторам и системам программирования [1–4, 7].

Пример выполнения курсовой работы

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

Многие методы, технические приемы и их реализация в курсовой работе будут взяты из лабораторных работ № 1–4, которые были рассмотрены ранее. Другие методы, наоборот, будут реализованы иначе, чтобы проиллюстрировать все существующие возможности, их преимущества и недостатки. В каждом случае будет дано пояснение, почему использован тот или иной метод.

В примере проиллюстрированы следующие интересные моменты:

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

• обнаружение присваивания значений константам на этапе синтаксического разбора (в лабораторных работах № 3 и 4 эта же операция выполнялась на этапе семантического анализа перед генерацией кода);

• возможности преобразования исходной грамматики, изменения синтаксиса входного языка и модификации алгоритма синтаксического разбора на основе анализа правил грамматики (на примере условного оператора);

• модификация остовной грамматики при необходимости различать правила;

• методы обработки логических операций и операций сравнения;

• простейший семантический анализ и модификация результирующего кода на этапе семантического анализа (на примере обработки переменных InpVar и CornpileTest);

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

Для реализации курсовой работы будут использоваться программные модули, созданные при выполнении лабораторных работ № 1–4, код которых не зависит от входного языка. Такой подход иллюстрирует, насколько удобно и эффективно выделять не зависящую от входного языка часть компилятора в отдельные модули или библиотеки.

Задание для примера выполнения работы

В качестве примера возьмем следующие условия для входного языка:

1. Тип допустимых констант: десятичные.

2. Дополнительная операция: унарный арифметический минус (-).

3. Оператор цикла: while (<выражение>) do <оператор>.

4. Оптимизация: оба метода (1 и 2).

5. Тип данных: Long integer (longint, 32 бит).

6. Тип комментария: фигурные скобки ({… }).

Кроме того, модифицируем синтаксис условного оператора (два типа):

• if (<выражение>) <оператор> else <оператор>;

• if (<выражение>) <оператор>;

и дополним перечень операций сравнения операцией «не равно» (<>).

Получим входной язык, сочетающий в себе элементы синтаксиса языков C++ (элементы оператора цикла и условный оператор) и Object Pascal (оператор цикла, составной оператор begin… end, оператор присваивания и комментарии).

В качестве результирующего (выходного) языка компилятора будем использовать язык ассемблера процессоров типа Intel 80386 и более поздних модификаций в модификации для системы программирования Delphi 5 [9, 23, 28, 41, 44]. Чтобы исключить неоднозначности при работе с этой системой программирования, изменим семантические ограничения входного языка:

• сделаем допустимым использование имени переменной CompileTest в любых операторах входного языка (а не только в операторах присваивания);

• запретим использование переменных с именем Result, так как такое имя переменной является предопределенным в целевой вычислительной системе.

Кроме того, в именах переменных во входном языке не должны различаться строчные и прописные буквы (например, переменные с именами i и I должны восприниматься как одна и та же переменная).