КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Приложение. Здесь приведены варианты индивидуальных лабораторных работ, которые можно выполнять на ЭВМ параллельно с изучением рассматриваемого курсаЗдесь приведены варианты индивидуальных лабораторных работ, которые можно выполнять на ЭВМ параллельно с изучением рассматриваемого курса. Во всех вариантах заданий цепочки языка, для которого необходимо построить анализатор, заданы в виде правил, близких к расширенной форме Бэкуса-Наура. Если это не оговорено дополнительно, то используются следующие группы метасимволов: < ... > - нетерминал; ::= - разделитель левой и правой частей правил и обозначает: “это есть” или “состоит из”; [ ... ] - факультативный (необязательный) элемент; { ... } - итерация, т.е. элемент повторяется 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.
Учебное издание
|