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

L → Р| L;P | L;

О → if(B) О; else Р | if(B) R else Р | if(B) Р | while(B) Р | а:=Е

R → begin L end

Р → О | R

И показанный выше оператор будет выглядеть так:

if (а<0) while (а<10) а:=а+1; else а:=1;

В языках C и C++ операторным скобкам begin и end соответствуют лексемы { и }, а оператор присваивания обозначается одним символом: =. Но суть подхода этот пример иллюстрирует верно: в этих языках для условного оператора правила различны в зависимости от того, входит в него составной оператор или одиночный оператор (точка с запятой ставится перед else для одиночных операторов в отличие от языка Pascal, где этой проблемы нет, так как конфликт между then и else может быть разрешен указанным выше способом, как в табл. 5.7). Желающие могут построить для такого языка матрицу операторного предшествования и убедиться, что она строится без конфликтов.

После того как заполнена матрица операторного предшествования, на основе исходной грамматики G можно построить остовную грамматику G'({prog,end.,if, else,begin,end,while,do,or,xor,and,not,<,>,=,<>,(,), – ,+,um,a,c,=}, {E},P',E) с правилами P':

E → prog E end. – правило № 1

E → E | E;E | E; – правила № 2, 3 и 4

Е → if(E) Е else Е | if(E) Е | begin Еend | while(£)do Е | а:=Е – правила № 5-9

Е → Е or Е | Е хог Е|Е – правила № 10, 11 и 12

Е → Е andE | Е – правила № 13 и 14

Е → Е<���Е | Е>Е | £=.£ | Е<>Е | (Е) | not(E) – правила № 15-20

Е → Е-Е | Е+Е | Е – правила № 21, 22 и 23

Е → urn Е|Е – правила № 24 и 25

Е → (_Е) | а | с – правила № 26, 27 и 28

Всего имеем 28 правил. Жирным шрифтом в грамматике и в правилах выделены терминальные символы.

При внимательном рассмотрении видно, что в остовной грамматике неразличимы правила 2, 12, 14, 23 и 25, а также правила 19 и 26. Но если первая группа правил не имеет значения, то во втором случае у распознавателя могут возникнуть проблемы, связанные с тем, что некоторые ошибочные входные цепочки он будет считать допустимыми (например оператор а:=(а or b);, который во входном языке недопустим). Это связано с тем, что круглые скобки определяют приоритет как логических, так и арифметических операций, и хотя они несут одинаковую синтаксическую нагрузку, распознаватель должен их различать, поскольку семантика этих скобок различна. Для этого дополним остовную грамматику еще одним нетерминальным символом B, который будет обозначать логические выражения. Подставив этот символ в соответствующие правила, получим новую остовную грамматику G»({prog,end.,if,else,begin,end,while,do,or,xor,and,not,<,>,=,<>,(,), – ,+,um,a,c,=}, {E,B},P», E) с правилами P»:

E → prog E end. – правило № 1

E → E | E;E | E; – правила № 2-4

E → if(B) EelseE | if(B) E | begin Eend | while(B)do E | a:=E – правила № 5-9

В → В or В | В хог В | В – правила № 10-12

В → В and В | В – правила № 13 и 14

В → Е<���Е | Е>Е | Е=Е | Е<>Е | (В) | not(B) – правила № 15-20

Е → Е-Е | Е+Е | Е – правила № 21-23

Е → urn Е | Е – правила № 24 и 25

Е → (Е) | а | с – правила № 26-28

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

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

Модуль SyntSymb (листинг П3.7, приложение 3), который реализует функционирование алгоритма «сдвиг-свертка» для грамматик операторного предшествования, можно использовать, не внося в него никаких изменений, так как он не зависит от входного языка. Требуется перестроить только модуль SyntRulе, внеся в него новые правила грамматики и новую матрицу операторного предшествования. Полученный в результате программный модуль представлен в листинге П3.6 в приложении 3 (обратите внимание на функцию MakeSymbolStr, которая возвращает имена нетерминальных символов для правил остовной грамматики!).

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

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

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

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

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

Для порождения результирующего кода будет использоваться рекурсивный алгоритм порождения списка триад на основе дерева синтаксического разбора. Схемы СУ-перевода для такого алгоритма были рассмотрены ранее (при выполнении лабораторной работы № 4).

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

• логические операции (or, xor, and и not);

• операции сравнения (<, >, = и <>);

• арифметические операции (сложение, вычитание, унарное отрицание);

• оператор присваивания;

• полный условный оператор (if… then … else …) и неполный условный оператор (if… then…);

• оператор цикла с предусловием (while(…)do…);

• операции, не несущие смысловой нагрузки, а служащие только для создания синтаксических конструкций исходной программы (заголовок программы, операторные скобки begin…end, круглые скобки и точка с запятой).

Схемы СУ-перевода для арифметических операций (которые являются линейными операциями), оператора присваивания и условных операторов были построены при выполнении лабораторной работы № 4. Здесь их повторять не будем.

Схему СУ-перевода для оператора цикла с предусловием построим аналогично схемам СУ-перевода для условных операторов (которые были приведены на рис. 4.1 в лабораторной работе № 4).

Генерация кода для цикла с предусловием выполняется в следующем порядке:

• Порождается блок кода№ 1, вычисляющий логическое выражение, находящееся между лексемами while ((первая и вторая нижележащие вершины) и) (четвертая нижележащая вершина) – для этого должна быть рекурсивно вызвана функция порождения кода для третьей нижележащей вершины.