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

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

Если это не оговорено дополнительно, то используются следующие группы метасимволов: <... > - нетерминал;

:: = - разделитель левой и правой частей правил и обозна­ча­ет: “это есть” или “состоит из”;

[... ] - факультативный (необязательный) элемент;

{... } - итерация, т.е. элемент повторяется 0 или более раз;

?... ¦... ¦...? - альтернатива;

Используются также следующие сокращения: @ - произвольный идентификатор; k - константа, если не оговорено, то целая. Терминальные символы, а к ним здесь относятся и идентификаторы, и константы, выделены жирно.

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

Вариант 1

Построить синтаксический анализатор для цепочек автоматного языка операторов присваивания (ПЛ/1), имеющих вид:

< оператор присваивания>:: = {< метка>: }< левая часть> =< правая часть>;

< метка>:: = @

< левая часть>:: = @[(< список индексов>)]

< список индексов>:: = < индекс> {, < индекс> }

< индекс>:: =? < левая часть> {< оп1> < левая часть> } ¦ k?

< оп1>:: =? + ¦ - ¦ * ¦ /?

< правая часть>:: = < операнд> {< оп2> < операнд> }

< операнд>:: =? < левая часть> ¦ k1?

где k1 - целая или действительная константа

< оп2>:: =? < оп1> ¦ OR ¦ AND?

Примеры правильных цепочек:

abc: ac123: a1(i+j/10, j*k, 10, a2(1, i, 15)-a2(1, 2*i, 7)+15, l)=

1234+a2(1, i, 15)*1234.56E-3/aqs(3, a2(j, a2(1, 2, 3), 15));

abcde=123; aaa=aaa OR bbb OR ccc AND 1;

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

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

Вариант 2

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

< описания типов>:: = TYPE < описание типа>; {< описание типа>; }

< описание типа>:: = @=? < простой тип> ¦ < массив> ¦ < множество> ¦ < запись> ¦ < указатель>?

< простой тип>:: =? CARDINAL ¦ INTEGER ¦ REAL ¦ CHAR ¦ SHORTCARD ¦ SHORTINT ¦ LONGCARD ¦ LONGINT ¦ LONGREAL ¦ BOOLEAN ¦ ADDRESS ¦ BYTE ¦ WORD ¦ < перечисление> ¦ < диапазон>?

< перечисление>:: = (@{, @})

< диапазон>:: = [k1..k2]

< массив>:: = ARRAY < диапазоны> OF < тип>

< диапазоны>:: = < диап1> {, < диап1> }

< диап1>:: =? < диапазон> ¦ @T1?

< тип>:: =? < простой тип> ¦ @T?,

где @T - имя типа, определенного выше в анализируемом Вами операторе, @T1 - имя типа-дипазона

< множество>:: = SET OF < простой тип>

< запись>:: = RECORD < элемент> {; < элемент> } END

< элемент>:: = @{, @}: < тип>

< указатель>:: = POINTER TO < тип_1>

< тип_1>:: =? < простой тип> ¦ @T2?,

где @T2 - имя типа, определенного выше или ниже в анализируемом Вами операторе. Пример правильной цепочки:

TYPE Color = (Red, Blue, White, Black);

diap = [10..25]; BitSet = SET OF WORD;

Mas = ARRAY [0..100], [0..3], diap OF BitSet;

PTab = POINTER TO Tab;

Tab = RECORD a1, a2, a3: CARDINAL; col: Color;

St: ARRAY [0..79] OF CHAR;

left, right: PTab

END;

MTab = ARRAY [0..100] OF Tab;

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

Вариант 3

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

< описания констант>:: = CONST < описание>; {< описание>; }

< описание>:: = @=< выражение>

< выражение>:: =? < операнд> {< операция> < операнд> } ¦ '< текст> '?

< операнд>:: =? k ¦ @C?,

где k - целая или вещественная; @C - имя константы, определенной выше в анализируемом Вами операторе;

< текст> - произвольный набор символов.

< операция>:: =? + ¦ - ¦ * ¦ / ¦ DIV ¦ MOD?

Пример правильной цепочки:

CONST Abc = 1024 DIV 7 + 35 MOD 17; text = 'All right';

Cde = 1234 - 32*13; rur = 3.14;

rir= 123.*rur/12.3E-5+rur; Fg = Abc - Cde + 15;

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

Вариант 4

Построить синтаксический анализатор для цепочек автоматного языка операторов описания пеpеменных (ПЛ/1), имеющих вид:

< описания пеpеменных>:: =? DCL ¦ DECLARE? < список описа­ний>;

< список описа­ний>:: = < описание> {, < описание> }

< описание>:: =? < пеpеменная> [< атpибут> ] ¦ (< список пеpемен­ных>)< атpибут>?

< пеpеменная>:: = @[(< список pазмеpностей>)]

< список pазмеpностей>:: = < pазмеpность> {, < pазмеpность> }

< pазмеpность>:: = k1[: k2],

где k1 и k2 - целые числа со знаком

< атpибут>:: =? BIN[ARY] FIXED ¦ FLOAT ¦ CHAR[ACTER](k)?

Примеры правильных цепочек:

DCL IND1, JIG, LOO, SUM, E123 BIN FIXED, III FLOAT, ST CHAR(10),

STR CHARACTER(25), SUSPEED BINARY FIXED, IMAS(100),

(ABC(10, -15: 20, 0: 23), MICRO, MACRO(5: 40), ERCOD) BIN FIXED;

DECLARE SSS(10: 20, 50) CHAR(1);

Семантика: По умолчанию, пеpеменные, имена котоpых начинаются с букв I, J, K, L, M, N имеют тип BIN FIXED, остальные - FLOAT. Сообщать об ошибках, если k1 > k2, pазмеp стpоки больше 256 символов и pазмеp массива больше 64 Kбайт. Сфоpмиpовать упорядоченный список-табл-

ицу пеpеменных с указанием имени, типа, pазмеpности, диапазона изменения индексов и объема памяти, выделяемой под переменную (кроме первых двух полей формируемой таблицы, все остальные поля в числовой форме). Напоминаем, что переменная типа BIN FIXED занимает 2 байта памяти, FLOAT - 4 байта, CHAR(1) - 1 байт.

Вариант 5

Построить синтаксический анализатор для цепочек автоматного языка операторов описания форматов (ПЛ/1), имеющих вид:

< описание форматов>:: = FORMAT(< элемент> {, < элемент> });

< элемент>:: =? < формат> ¦ k1(< формат> {, < формат> })?

< формат>:: =? A(k2) ¦ X(k2) ¦ SKIP(k1) ¦ F(k4[, k5]) ¦ E(k6, k7) ¦ < элемент>?

где k1 - k7 - целые числа без знака.

Семантика: Сообщать об ошибках, если k1 > 10; k2 > 50; k4 > 33 и k4 < 4, если присутствует k5; k5 > k4-3; 8 > k6 > 37; k7 > k6-7. Осуществить вывод на экран информации по заданному формату: SKIP - переход на новую строку, с обозначением " |" для пустой стpоки, Х - обозначить символом " -", A - " А", знак числа и порядка - " З", цифр мантиссы и порядка - " Ц".

Пример правильной цепочки:

FORMAT (X(5), 3(A(2), X(2), F(3), X(1)), SKIP(3), X(7), 2(F(10, 5)), X(2), E(10, 4), SKIP(2), 4(X(10), A(5), F(5), 2(X(3), A(2), 3(F(2), A(1))), SKIP(1)), X(20), A(10));

Результат работы программы для данного оператора:

-----АА--ЗЦЦ-АА--ЗЦЦ-АА--ЗЦЦ-

|

|

-------ЗЦЦЦ.ЦЦЦЦЦЗЦЦЦ.ЦЦЦЦЦ--ЗЦ.ЦЦЦЦЕЗЦЦ

|

----------АААААЗЦЦЦЦ---ААЗЦАЗЦАЗЦА---ААЗЦАЗЦАЗЦА

----------АААААЗЦЦЦЦ---ААЗЦАЗЦАЗЦА---ААЗЦАЗЦАЗЦА

----------АААААЗЦЦЦЦ---ААЗЦАЗЦАЗЦА---ААЗЦАЗЦАЗЦА

----------АААААЗЦЦЦЦ---ААЗЦАЗЦАЗЦА---ААЗЦАЗЦАЗЦА

--------------------АААААААААА

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

Вариант 6

Построить синтаксический анализатор для цепочек автоматного языка операторов описания пеpеменных (Модула-2), имеющих вид:

< описание пеpеменных>:: = VAR < описание>; {< описание>; }

< описание>:: = @{, @}: [ARRAY < диапазон> {, < диапазон> } OF]< тип>

< диапазон>:: = [k1..k2]

< тип>:: =? CARDINAL ¦ INTEGER ¦ REAL ¦ CHAR ¦ SHORTCARD ¦ SHORTINT ¦ LONGCARD ¦ LONGINT ¦ LONGREAL ¦ BOOLEAN ¦ ADDRESS ¦ BYTE ¦ WORD?

Пpимеp пpавильного оператора:

VAR abc, A12C3, Ijk: CARDINAL;

s, st, S: ARRAY [0..79] OF CHAR; abcdef: LONGINT;

MasF: ARRAY [10..20], [5..19] OF BOOLEAN; Re: REAL;

Семантика: Сообщать об ошибках, если k1 > k2, объем памяти под переменную больше 64 Кбайт. Сфоpмиpовать упорядоченный по именам список-таблицу пеpеменных с указанием имени, типа, pазмеpности, диапазона изменения индексов и объема памяти, выделяемой под переменную (кроме первых двух символьных полей таблицы, все остальные поля представлять в числовой форме).

Вариант 7

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

< заголовок цикла>:: = FOR < паpаметp>: =< значение> TO < значение>

[BY < значение> ] DO

< параметр>:: = @[[< список индексов> ]]

< список индексов>:: = < индекс> {, < индекс> }

< индекс>:: = < операнд1> {< операция> < операнд1> }

< операнд1>:: =? @ ¦ k?

< операция>:: =? + ¦ - ¦ * ¦ MOD ¦ DIV?

< значение>:: = < операнд2> {< операция> < операнд2> }

< операнд2>:: =? < параметр> ¦ k?

Примеры правильных цепочек:

FOR par[1, yy+23 MOD 7 DIV 2-1*3, kkk]: =ijk+aa[1, h-2] TO kkk*24 DIV 3

BY aa[3, 4]-3 DO

FOR ijk: =1444-7 DIV 12 * 3 TO 12345 BY 23-1*5 DIV 2 DO

Семантика: Сформировать списки @ и k в числовой форме. Если все значения в операторе представляют собой выражения над константами, то определить сколько раз будет выполняться цикл.

Вариант 8

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

< цикл>:: = REPEAT {< присваивание>; } UNTIL < условие>;

< присваивание>:: = < левая часть>: =< правая часть>

< левая часть>:: = @[[< список индексов> ]]

< список индексов>:: = < индекс> {, < индекс> }

< индекс>:: = < операнд1> {< операция1> < операнд1> }

< операнд1>:: =? @ ¦ k?

< операция1>:: =? + ¦ - ¦ * ¦ MOD ¦ DIV ¦ > > ¦ < <?

< правая часть>:: = < операнд2> {< операция1> < операнд2> }

< операнд2>:: =? < левая часть> ¦ k?

< условие>:: = < правая часть1> {< операция2> < правая часть1)}

< операция2>:: =? = ¦ # ¦ < ¦ > ¦ > = ¦ < = ¦ < > ¦& ¦ AND ¦ OR?

< правая часть1>:: = [? NOT ¦ ~? ]< правая часть2>

< правая часть2>:: =? (< правая часть>) ¦ (k IN < левая часть>)?

Примеры правильных цепочек:

REPEAT UNTIL (7 IN abcd) & ~(5 IN aa[1, i+k MOD 4]);

REPEAT

aaa: =a+b-c[11, i*j DIV 2 -1, k+zzz123z]*1234 MOD 25;

bb[j+i> > 2, 12, 34, ikj]: =bb[j+i> > 2, 12, 34, ikj]+1;

i: =i-2; j: =i*k+3;

UNTIL (aaa) > (j+2) OR (i+c[1, i DIV 2, k+zzz123z] MOD 5)=(0) AND NOT(3 IN xx);

Семантика: Сформировать безповторные упорядоченные списки @ и k в числовой форме.

Вариант 9

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

< цикл>:: = WHILE < условие> DO {< присваивание>; } END;

< присваивание>:: = < левая часть>: =< правая часть>

< левая часть>:: = @[[< список индексов> ]]

< список индексов>:: = < индекс> {, < индекс> }

< индекс>:: = < операнд1> {< операция1> < операнд1> }

< операнд1>:: =? @ ¦ k?

< операция1>:: =? + ¦ - ¦ * ¦ MOD ¦ DIV ¦ > > ¦ < <?

< правая часть>:: = < операнд2> {< операция1> < операнд2> }

< операнд2>:: =? < левая часть> ¦ k?

< условие>:: = < правая часть1> {< операция2> < правая часть1)}

< операция2>:: =? = ¦ # ¦ < ¦ > ¦ > = ¦ < = ¦ & ¦ AND ¦ OR?

< правая часть1>:: = [? NOT ¦ ~? ]< правая часть2>

< правая часть2>:: =? (< правая часть>) ¦ (k IN < левая часть>)?

Примеры правильных цепочек:

WHILE (7 IN abcd) & ~(5 IN aa[1, i+k MOD 4]) DO END;

WHILE (aaa) > (j+2) OR (i+c[1, i DIV 2, k+zzz123z] MOD 5)=(0)

AND NOT(3 IN xx) DO

aaa: =a+b-c[11, i*j DIV 2 -1, k+zzz123z]*1234 MOD 25;

bb[j+i> > 2, 12, 34, ikj]: =bb[j+i> > 2, 12, 34, ikj]+1;

i: =i-2; j: =i*k+3;

END;

Семантика: Сформировать безповторные упорядоченные списки @ и k в числовой форме.

Вариант 10

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

< ветвление>:: = IF < условие> THEN {< присваивание>; }

{ELSIF < условие> THEN {< присваивание>; }}

[ELSE {< присваивание>; }]

END;

< присваивание>:: = < левая часть>: =< правая часть>

< левая часть>:: = @[[< список индексов> ]]

< список индексов>:: = < индекс> {, < индекс> }

< индекс>:: = < операнд1> {< операция1> < операнд1> }

< операнд1>:: =? @ ¦ k?

< операция1>:: =? + ¦ - ¦ * ¦ MOD ¦ DIV ¦ > > ¦ < <?

< правая часть>:: = < операнд2> {< операция1> < операнд2> }

< операнд2>:: =? < левая часть> ¦ k?

< условие>:: = < правая часть1> {< операция2> < правая часть1)}

< операция2>:: =? = ¦ # ¦ < ¦ > ¦ > = ¦ < = ¦ & ¦ AND ¦ OR?

< правая часть1>:: = [? NOT ¦ ~? ]< правая часть2>

< правая часть2>:: =? (< правая часть>) ¦ (k IN < левая часть>)?

Пример правильной цепочки:

IF (7 IN abcd) & ~(5 IN aa[1, i+k MOD 4]) THEN l: =l+1;

ELSIF (aaa) > (j+2) OR (i+c[1, i DIV 2, k+zzz123z] MOD 5)=(0)

AND NOT(3 IN xx) THEN

aaa: =a+b-c[11, i*j DIV 2 -1, k+zzz123z]*1234 MOD 25;

bb[j+i> > 2, 12, 34, ikj]: =bb[j+i> > 2, 12, 34, ikj]+1;

i: =i-2; j: =i*k+3;

ELSIF aabbcc THEN

i: =i+1;

ELSE i: =j+b< < 4*kkk[1, hg]; END;

Семантика: Сформировать безповторные упорядоченные списки @ и k в числовой форме.

Список рекомендуемой литературы

1. Ахо, А. Теория синтаксического анализа, перевода и компиляции. Том 1. Синтаксический анализ/ А. Ахо, Д. Ульман. - М.: Мир, 1978.

2. Ахо, А. Теория синтаксического анализа, перевода и компиляции. Том 2. Компиляция/ А.Ахо, Д. Ульман. - М.: Мир, 1978.

3. Братчиков, И.Л. Синтаксис языков программирования/И.Л. Братчиков. - М.: Наука, 1975.

4. Гилл, А. Введение в теорию конечных автоматов/А.Гилл. - М.: Наука, 1966.

5. Гинзбург, С. Математическая теория контекстно-свободных языков/С.Гинзбург. - М.: Мир, 1970.

6. Гладкий, А.В. Формальные грамматики и языки/А.В.Гладкий. - М.: Наука, 1973.

7. Грис, Д. Конструирование компиляторов для цифровых вычислительных машин/Д.Грис. - М.: Мир, 1975.

8. Гросс, М. Теория формальных грамматик/ М.Гросс, А. Лантен. - М.: Мир, 1971.

9. Донован, Д. Системное программирование/Д.Донован.- М.: Мир, 1975.

10.Лебедев, В.Н. Введение в системы программирования/В.Н.Лебедев.- М.: Статистика, 1975.

11. Льюис, Ф. Теоретические основы проектирования компиляторов/Ф.Льюис, Д.Розенкранц, Р.Стирнз - М.: Мир, 1979.

12. Семантика языков программирования. Сборник статей.- М.: Мир, 1980.

13.Шамашов, М.А.Теория формальных языков. Грамматики и автоматы. Учебное пособие./М.А.Шамашов.-Самара: Самарский муниципальный комплекс непрерывного образования «Университет Наяновой», 1996, 92 с.

14.Хантер, Р. Проектирование и конструирование компиляторов/Р.Хантер. – М.: Финансы и статистика, 1984.

15.Хомский, Н. Формальные свойства грамматик/Н.Хомский// Кибернетический сборник, новая серия - вып. 2. - М.: ИЛ, 1966.

16.Хомский, Н. Алгебраическая теория контекстно-свободных языков/ Н. Хомский, М. Шютценберже // Кибернетический сборник, новая серия, вып. 3. - М.: ИЛ, 1966.

17.Хопгуд, Ф. Методы компиляции/Ф. Хопгуд.- М.: Мир, 1972.

18. Форстер, Дж. Автоматический синтаксический анализ/Дж. Фостер.-М.: Мир, 1972.

19.Шамашов, М.А. Основные структуры данных и алгоритмы компиляции: учеб. пособие/М.А.Шамашов.- Самара: Научно-внедренческая фирма «Сенсоры, модули, системы», 1999. –115 с.

20.Шамашов, М.А. Синтаксический анализ автоматных языков. Метод. указания/ М.А. Шамашов, Л.Ф. Штернберг. - Куйбышев: КуАИ, 1990.

21. Штернберг, Л.Ф. Теория формальных грамматик/Л.Ф. Штернберг. - Куйбышев: КуАИ, 1979.

22. Языки и автоматы: сб. статей. - М.: Мир, 1975.

Учебное издание