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

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

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

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

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

{ ... } - итерация, т.е. элемент повторяется 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.

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