Поиск по базе сайта:
Методические указания по выполнению лабораторной работы №1 по курсу Системное по (2010 уч год ) “Построение синтаксического анализатора” icon

Методические указания по выполнению лабораторной работы №1 по курсу Системное по (2010 уч год ) “Построение синтаксического анализатора”




Скачати 221.6 Kb.
НазваМетодические указания по выполнению лабораторной работы №1 по курсу Системное по (2010 уч год ) “Построение синтаксического анализатора”
Дата конвертації26.11.2013
Розмір221.6 Kb.
ТипМетодические указания

Методические указания по выполнению лабораторной работы №1 по курсу

Системное ПО (2010 уч.год )
“Построение синтаксического анализатора”.



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

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

< ... > - нетерминал;

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

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

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

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

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

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

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

^

Порядок выполнения лабораторной работы:


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

  2. Построение автоматной грамматики и графа состояний по предложенной КС-грамматике.

  3. Приведение грамматики к детерминированной форме.

  4. Разработка алгоритма работы программы.

  5. Реализация программы синтаксического анализа.

  6. Введение в программу сообщений о синтаксических ошибках.

  7. Отладка программы синтаксического анализа.

  8. Реализация семантических процедур.



^

Требования к выполнению лабораторной работы:


  • Предусмотреть максимальное число сообщений о синтаксических ошибках. Сообщения должны быть интуитивно понятны пользователю (указано место ошибки в исходной строке).

  • Выдавать предупреждающее сообщение при переполнении констант и при превышении длины идентификатора 8-ми символов.

  • Подготовить тесты, проверяющие все ветви программы, все предельные случаи.

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

  • Анализ цепочек из файла производить с выводом сообщений и семантики, как на экран, так и в файл.

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

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


Вариант 1

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

<заголовок цикла> ::= FOR <параметр>:=<значение> 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 в числовой форме. Если все значения в операторе представляют собой выражения над константами, то определить сколько раз будет выполняться цикл.


Вариант 2

Построить синтаксический анализатор для цепочек автоматного языка операторов описания констант (Модула-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;


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

Вариант 3

Построить синтаксический анализатор для цепочек автоматного языка операторов присваивания (ПЛ/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;


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

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

Вариант 4

Построить синтаксический анализатор для цепочек автоматного языка операторов описания типов (Модула-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;

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

Вариант 5

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


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

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

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

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

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

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

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

<атрибут> ::= ? 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);


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


Вариант 6

Построить синтаксический анализатор для цепочек автоматного языка операторов ветвления (Модула-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 в числовой форме.

Вариант 7

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

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

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

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

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


Приме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 Кбайт. Сформировать упорядоченный по именам список-таблицу переменных с указанием имени, типа, размерности, диапазона изменения индексов и объема памяти, выделяемой под переменную (кроме первых двух символьных полей таблицы, все остальные поля представлять в числовой форме).


Вариант 8

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

<заголовок процедуры> ::= PROCEDURE <заголовок>;

<заголовок> ::= ? @[(<параметры>)] ¦ @([<параметры>]):<тип> ?

<параметры> ::= <описание>{;<описание>}

<описание> ::= [VAR] @{,@}:<тип1>

<тип1> ::= [ARRAY <диапазоны> OF ] <тип>

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

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

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

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

PROCEDURE Aabb( ):BOOLEAN;

PROCEDURE n1m2;

PROCEDURE Examp ( s: ARRAY OF CHAR;

aa, AA: ARRAY [0..10],[3..8] OF SHORTCARD;

VAR rez, sum: LONGREAL): CHAR;

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

Вариант 9

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


<цикл> ::= 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]+1 := 1;


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

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


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


Вариант10

Построить синтаксический анализатор для цепочек автоматного языка операторов цикла (Модула-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 в числовой форме.

Вариант 11

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


<заголовок цикла> ::= DO [<переменная>=<параметры>] [WHILE(<условие>)] ;

<параметры> ::= <параметр>{,<параметр>}

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

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

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

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

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

<параметр> ::= ? k [BY k] [TO k] ¦ k [TO k] [BY k] ?

<условие> ::= <выражение>{<опекрация2><выражение>}

<выражение> ::= <операнд2>{<операция1><операнд2>}

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

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


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

DO I=1;

DO J=5 TO 20 BY 2;

DO KLMN(1,J+I-3,21-L)=1 TO 7, 12 TO 36 BY 3;

DO IKL=7 BY 1;

DO IJK(1,I+J)=5 TO 10, 40 TO 15 BY -3 WHILE(AB+K(I,J)*4 > 7 AND AI);

DO I=1 TO 17, WHILE (J


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

Вариант 12

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

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

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

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

где k1 - k7 - целые числа без знака. F – формат числа с плавающей точкой (знак числа, мантисса, порядок), Е – формат числа с плавающей точкой в экспоненциальной форме представления (знак числа, мантисса, порядок).

Семантика: Сообщать об ошибках, если

  • k1 > 10;

  • k2 > 50;

  • k4 > 33 и k4 < 4, если присутствует k5 ;

  • k5 > k4-3;

  • 8 > k6 > 37;

  • k7 > k6-7.

Осуществить вывод на экран информации по заданному формату:

  • SKIP (количество Enter) - переход на новую строку, с обозначением "|" для пустой строки,

  • Х - обозначить символом "-",

  • 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));

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

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

|

|

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

|

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

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

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

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

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

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

Вариант 14

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


<заголовок цикла> ::= FOR <параметр>:=<значение> [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 в числовой форме. Если все значения в операторе представляют собой выражения над константами, то определить сколько раз будет выполняться цикл.


Вариант 15

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


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

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

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

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

где k - целая или вещественная;

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

<текст> ::= 'текст' {+ @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;


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


Вариант 16

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


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

<метка> ::= @

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

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

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

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

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

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

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

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


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

abc: ac123: a1(10,j,10,a2(1,i,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;


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

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

Вариант 17

Построить синтаксический анализатор для цепочек автоматного языка операторов описания типов (Модула-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;

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

Вариант 18

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


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

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

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

<список переменных> ::= <переменная>{,<переменная>}

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

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

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

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

<атрибут> ::= ? 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);


Семантика: По умолчанию, переменные, имена которых начинаются с букв F,G,K,L,M,N имеют тип BIN FIXED, остальные - FLOAT. Сообщать об ошибках, если k1 > k2, размер строки больше 256 символов и размер массива больше 64 Kбайт. Сформировать упорядоченный список-таблицу переменных с указанием имени, типа, размерности, диапазона изменения индексов и объема памяти, выделяемой под переменную (кроме первых двух полей формируемой таблицы, все остальные поля в числовой форме). Напоминаем, что переменная типа BIN FIXED занимает 2 байта памяти, FLOAT - 4 байта, CHAR(1) - 1 байт.

Вариант 19

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


<ветвление> ::= IF <условие> 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 в числовой форме.

Вариант 20

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


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

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

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

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


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

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 Кбайт. Сформировать упорядоченный по именам список-таблицу переменных с указанием имени, типа, размерности, диапазона изменения индексов и объема памяти, выделяемой под переменную (кроме первых двух символьных полей таблицы, все остальные поля представлять в числовой форме).

Вариант 21

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


<заголовок процедуры> ::= PROCEDURE <заголовок>;

<заголовок> ::= @[(<параметры>)]

<параметры> ::= <описание>{;<описание>}

<описание> ::= [VAR] @{,@}:<тип1>

<тип1> ::= [ARRAY <диапазоны> OF ] <тип>

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

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

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


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


PROCEDURE n1m2;

PROCEDURE Examp ( s: ARRAY OF CHAR;

aa, AA: ARRAY [0..10],[3..8] OF SHORTCARD;

VAR rez, sum: LONGREAL);


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


Вариант 22

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


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

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

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

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

<индекс> ::= ? <левая часть> ¦ 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]);

REPEAT

aaa:=a+b-c[11,i[2,3,f]]*1234 MOD 25;

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

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

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


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

Вариант 23

Построить синтаксический анализатор для цепочек автоматного языка операторов цикла (Модула-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 в числовой форме.

Вариант 24

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


<заголовок цикла> ::= DO <переменная>=<параметры> [WHILE(<условие>)] ;

<параметры> ::= <параметр>{,<параметр>}

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

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

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

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

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

<параметр> ::= ? k [BY k] TO k ¦ k [TO k] BY k ?

<условие> ::= <выражение>{<опекрация2><выражение>}

<выражение> ::= <операнд2>{<операция1><операнд2>}

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

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


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

DO J=5 TO 20 BY 2;

DO KLMN(1,J+I-3,21-L)=1 TO 7, 12 TO 36 BY 3;

DO IKL=7 BY 1;

DO IJK(1,I+J)=5 TO 10, 40 TO 15 BY -3 WHILE(AB+K(I,J)*4 > 7 AND AI);

DO I=1 TO 17, WHILE (J


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

Вариант 25

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

<описание форматов> ::= 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 (количество Enter) - переход на новую строку, с обозначением "!" для пустой строки,

  • Х - обозначить символом "-",

  • 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]);

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

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

!

!

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

!

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

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

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

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

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


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




Схожі:




База даних захищена авторським правом ©lib.exdat.com
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації