Задания к лабораторному практикуму

1. Определите грамматику языка описания констант, переменных и арифметических выражений, использующих

- бинарные арифметические операции (+, -, *, /),

- целые числа.

- унарный минус,

- переменные и константы,

- круглые скобки, определяющие приоритеты выполнения операций

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

2. Определите грамматику языка описания констант, логических переменных и логических выражений, использующих

- бинарные операции конъюнкции, дизъюнкции, импликации (&, OR, ->),

- логические константы (TRUE, FALSE),

- унарную операцию, отрицания (NOT).

- переменные,

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

3. Определите грамматику языка описания теоретико-множественных выражений, использующих

- бинарные операции пересечения, объединения и разности множеств (*, +, -),

- символы пустого и универсального множеств (О и I),

- унарную операцию дополнения множества (@),

- переменные множественного типа,

- круглые скобки, определяющие приоритеты выполнения операций.

Определите также синтаксические структуры для описания опера­торов присваивания значений односимвольным переменным множест­венного типа и средства для вычисления значений теоретико-множественных выражений. Предусмотрите выдачу сообщений об ошиб­ках в случае несоответствия количества открывающих и закрывающих скобок в выражениях.

4. Определите грамматику языка описания полиномов вида Р_n = a_nxⁿ + a_n-1x^n-1 +... + a₁x + а₀ с целыми коэффициентами (х может принимать целые или вещественные значения).

Любой полином степени n определяется выражением, которое представляет собой сумму слагаемых вида а_iхⁱ, упорядоченных по убыва­нию степени х. Слагаемые вида 0*хⁱ могут быть опущены в определении полинома.

Язык должен содержать операторы, выполняющие следующие дей­ствия над полиномами:

- сложение двух полиномов Р_n(х) и Р_m(х);

- перемножение двух полиномов;

- вычисление значения полинома Р_n(х) по заданному значению х (х - вещественное).

Результатом первой операции должен быть полином Р_max(n,m) (х), второй -полином Р_(n+m) (х), третьей - вещественное число.

Напишите семантические процедуры, реализующие действия над полиномами.

5. Определите грамматику языка описания структуры "фазового портрета". Такая структура представляет собой декартову систему коор­динат, размещаемую на графическом экране монитора (в определенном окне) и предназначенную для вывода значений двух переменных в виде точки в этой системе.

Описание "фазового портрета" должно определять следующие ос­новные параметры:

- параметры окна наблюдения,

- точку начала координат, "привязанную" к возможным значениям отображаемых переменных,

- диапазоны значений переменных, связанных с окном.

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

6. Определите грамматику языка описания размеченных графов. Любая вершина такого графа специфицируется именем, может иметь не­сколько исходящих и входящих дуг, каждая дуга помечается весом, пред­ставляющим собой целое число. Описание графа должно определяться последовательностью операторов связей между вершинами. Например, описание вида

А - (4) -> В;

В - (3) -> С;

С -(1)-> А;

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

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

А - (4) -> В, (3) -> С;

С -(1)-> А;

В - (2) -> А;

Здесь описан двухконтурный граф с разветвлением в вершине А. Его же можно описать оператором, определяющим несколько путей, ведущих из одной вершины:

А - [ (4) -> В - (2) -> А; (3) -> С - (1) -> А ];

Реализуйте семантическую процедуру преобразования графа, за­данного его описанием, в структуру квадратной матрицы связей между вершинами (матрицы смежности).

7. Определите грамматику для описания интерполированных функ­ций (И-функций). Любая И-функция является функцией одного аргумен­та и задается узлами интерполяции (точками в декартовой системе коор­динат) и видом интерполяции (линейной или кусочно-постоянной). Оп­ределение функции должно включать в себя спецификацию следующих элементов:

- имя функции,

- имя аргумента,

- вид интерполяции,

- набор узлов интерполяции.

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

& Некоторые языки программирования разрешают использование в выражениях нескольких операторов присваивания, например,

a:=b+(c:=3)*(b:=d:=(h+4))-6+r:=e.

Определите грамматику языка описания арифметических выраже­ний со множественным присваиванием, использующих

- односимвольные переменные,

- целые числа,

- бинарные арифметические операции (+, -, *, /),

- оператор присваивания (:=),

- круглые скобки, определяющие приоритеты выполнения операций.

Реализуйте вычисление значения арифметического выражения со множественным присваиванием. Предусмотрите выдачу сообщения об ошибке в случае, если какая-либо переменная, входящая в арифме­тическое выражение, не определена значением.

9. Определите грамматику квалидентов. учитывающую все возмож­ные методы доступа к данным (именование, индексацию, ссылки). В качестве индексов могут использоваться целые числа и односимвольные целочисленные переменные.

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

А[1,7]^.С[20]

А^.В^.С^[1] и т.д.

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

10. Определите грамматику квалидентов, использующих именование и индексацию как методы доступа к данным. В качестве индексов могут использоваться арифметические выражения. Арифметические вы­ражения используют

- бинарные арифметические операции (+, -),

- целые числа,

- односимвольные целочисленные переменные.

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

А[1+2 - B+5),7].C[F+3-20], A.B.C [I] и т.д.

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

11. Определите грамматику языка описания геометрических фигур: окружностей, прямоугольников, квадратов, треугольников. Обеспечьте проверку корректности описания геометрических фигур.

Треугольник корректен, если длины его сторон положительны, а сумма длин двух различных его сторон больше длины третьей стороны.

Окружность корректна, если ее радиус больше 0.

Квадрат корректен, если существуют два таких числа а и b (a>b), что для любой вершины расстояние от нее до одной из трех других равно а, а до каждой из двух оставшихся равно b.

Прямоугольник корректен, если существуют три таких числа а,b и с (а, b, с>0), что для любой вершины расстояние от нее до одной из остав­шихся вершин равно а, до другой - b и до третьей - с, причем а² + b² = с².

12. Определите грамматику разделов описания модулей языка Мо-дула-2. Примеры правильных цепочек языка приведены ниже.

DEFINITION MODULE NameMod1; (* Раздел определений *)

EXPORT Т1,Т2,V3; (* Список экспорта *)

TYPE T1;T2 = REAL; VAR V3: INTEGER;

END NameMod1.

IPLEMENTATIOM MODULE NameMod1; (* Раздел реализаций *)

FROM NameMod2 IMPORT V4; (* Список импорта *)

TYPE T1 = CARDINAL; VAR V5:TI;

BEGIN V3:=5; V5:=V4; (* Тело модуля *)

END NameMod1.

DEFINITION MODULE NameMod2;

FROM NameMod3 IMPORT ABC; (* Список импорта *)

VAR V4: CARDINAL;

END NameMod2.

IMPLEMENTATION MODULE NameMod2;

BEGIN

END NameMod2.

DEFINITION MODULE NameMod3;

EXPORT ABC; (* Список экспорта*)

VAR ABC: CARDINAL;

END NameMod3.

IMPLEMENTATION MODULE NameMod3;

BEGIN

END NameMod3.

MODULE NameMod[l];

(* Главный модуль: в прямоугольных скобках указан приоритет, который не

является обязательным *) FROM NameMod1 IMPORT T2,V3,T1; VAR V6: T2; V7: T1; V8: INTEGER; V9: CHAR; BEGIN V6:=-20; V8:=V3; V7:=65535; V9:='A'; END NameMod.

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

13. Определите грамматику разделов описания констант, типов (диапазон, перечисление, массив и множество), а также переменных язы­ка Модула-2. Один или несколько разделов описаний могут отсутство­вать. Примеры правильных цепочек языка приведены ниже.

MODULE Abc;

CONST С1=99; С2=-3; С3=5;

TYPE T1 = CARDINAL; (* Стандартный тип *)

Т2 = [1..10]; (* Тип диапазон *)

ТЗ = (красный, зеленый, синий); (* Тип перечисление *)

T4 = ARRAY[1..10] OF CHAR; (* Тип массив *)

Т5 = ARRAY T2 OF CARDINAL;

Т6 = ARRAY [0..5] OF Array[0..99] OF CHAR;

T7 = ARRAY[O..C1],[O..C3] OF Char;

T9 = ARRAY CHAR OF BOOLEAN; T1O = T7;

T10 = SET OF T3; (* Тип множество *)

T11 = ARRAY T2 OF T10;

VAR V1:T1; V2,V3: T3; V4: SET OF (красный.зеленый, синий); V5: REAL; BEGIN END Abc.

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

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

MODULE Abc: TYPE

Arr = ARRAY[1..3] OF REAL;

M = ARRAY[1..2] OF INTEGER;

Matrix = ARRAY[I..3] OF M;

Data = RECORD

Year: CARDINAL; Month: [1..12]; Day:[1..31];

END;

A = ARRAY[1..3] OF CHAR; В = ARRAY[1..4] OF A;

Charset = SET OF CHAR;

Colour = (красный, зеленый, синий);

ТЗ = SET OF Colour; CONST

Ml =Arr(l.,2.,3.):

Matr = Matrix (M(l,2), M(3,4), M(5,6));

SS = B(A('asd'), A('bcd'), A('dfg'), A('bmv'));

Birthday = Data(1971, 12, 9);

С = Charset{'A'..'Z','0'..'9'};

Т = ТЗ{синий);

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

15. Определите грамматику разделов описания типа запись и запись с вариантами, а также переменных соответствующего типа языка Моду-ла-2. Примеры правильных цепочек языка приведены ниже.

TYPE

Rec = RECORD A: INTEGER; В: CARDINAL;

CASE Т: CHAR OF (* именованная вариантная часть *)

'А': C,D: REAL |
'В': Е: CARDINAL |
'С': F: REAL |

ELSE G,H,M: CHAR; (* необязательная часть *)

END; Z: REAL; END;

location = RECORD Value: CARDINAL;

CASE: BOOLEAN OF (* неименованная вариантная часть *)

TRUE: A: CARDINAL | FALSE: B: INTEGER END; END;

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

16. Постройте грамматику языка, определяющего

• операторы присваивания значений переменным стандартных типов, встроенных в язык;

• условный оператор.

Составьте бесповторную упорядоченную таблицу переменных с указанием имени, признака типа и объема памяти, отводимого для эле­мента хранения.

Определите уровень вложенности условных операторов. Преду­смотрите выдачу сообщения об ошибке, если встретится условный опера­тор, не закрытый операторными скобками.

17. Постройте грамматику языка, содержащего

•операторы присваивания значений переменным стандартных типов, встроенных в язык;

•оператор выбора.

Составьте бесповторную упорядоченную таблицу переменных с указанием имени, признака типа и объема памяти, отводимого для эле­мента хранения.

Определите уровень вложенности операторов выбора. Предусмот­рите выдачу сообщения об ошибке, если встретится оператор выбора, не закрытый операторными скобками.

18, Постройте грамматику языка, определяющего

•раздел описания переменных стандартных типов языка;

•операторы присваивания значений переменным стандартных типов, встроенных в язык;

•арифметические выражения, использующие

- бинарные арифметические операции (+, -, *, /, DIV),

- натуральные, целые и вещественные числа,

- переменные и константы;

• операторы цикла с шагом.

Составьте бесповторную упорядоченную таблицу переменных с указанием имени, признака типа и объема памяти, отводимого для эле­мента хранения. Проверьте совместимость типов операндов в выражени­ях и вычислите значения выражений.

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

19. Постройте грамматику языка, определяющего

•раздел описания типов массив и запись;

•операторы присваивания значений переменным стандартных типов, встроенных в язык;

• арифметические выражения, использующие

- бинарные арифметические операции (+, -),

- целые числа,

- односимвольные целочисленные переменные;

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

Составьте бесповторную упорядоченную таблицу типов с указани­ем имени типа, имен и типов атрибутов, бесповторную упорядоченную таблицу переменных с указанием имени, признака типа и объема памя­ти, отводимого для элемента хранения.

Определите уровень вложенности операторов присоединения. Пре­дусмотрите выдачу сообщений об ошибках, если встретится оператор присоединения, не закрытый операторными скобками, в случае измене­ния значения присоединяемой переменной внутри оператора присоединения, а также в случае несоответствия типа присоединяемой переменной и атрибутов внутри оператора присоединения.

20. Постройте грамматику языка, определяющего

• оператор присваивания значений переменным стандартных типов, встроенных в язык;

• выражения, использующие

- бинарные арифметические операции (*, /),

- операции отношения (=,<>,<,>),

- целые числа,

- односимвольные целочисленные переменные;

• операторы цикла с постусловием.

Составьте бесповторную упорядоченную таблицу типов с указани­ем имени типа, безповторную упорядоченную таблицу переменных с указанием имени, признака типа и объема памяти, отводимого для эле­мента хранения.

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

21. Постройте грамматику языка, определяющего

•раздел описания типов запись и ссылка;

•операторы присваивания значений переменным стандартных типов, встроенных в язык, и переменным ссылочных типов;

•выражения, использующие

- квалиденты со ссылкой,

- целые числа,

- односимвольные переменные;

• операторы присоединения, использующие квалиденты со ссылкой.

Составьте бесповторную упорядоченную таблицу типов с указани­ем имени типа, имен и типов атрибутов, бесповторную упорядоченную таблицу переменных с указанием имени, признака типа и объема памя­ти, отводимого для элемента хранения.

Определите уровень вложенности операторов присоединения. Пре­дусмотрите выдачу сообщений об ошибках, если встретится оператор, не закрытый операторными скобками, в случае изменения значения присое­диняемой переменной внутри оператора присоединения, а также в случае несоответствия типа присоединяемой переменной и атрибутов внутри оператора присоединения.

22. Постройте грамматику языка, определяющего

•операторы присваивания значений переменным стандартных типов, встроенных в язык;

•выражения, использующие

- бинарные арифметические операции (+,-),

- операции отношения (=,<>,<,>),

- целые числа,

- односимвольные целочисленные переменные;

• операторы цикла с предусловием.

Составьте бесповторную упорядоченную таблицу типов с указани­ем имени типа, безповторную упорядоченную таблицу переменных с указанием имени, признака типа и объема памяти, отводимого для эле­мента хранения.

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

23. Определите грамматику описания "пустых" процедур (заглушек) и операторов вызова процедур языка МОДУЛА-2 с исполь­зованием формальных и фактических параметров стандартных типов. Примеры правильных цепочек языка приведены ниже.

MODULE Mod1;

VAR x: CARDINAL; q,w,v: REAL; b: BOOLEAN; i,j: CARDINAL;

PROCEDURE proc1(): CARDINAL;

(* Процедура-функция без параметров *)

BEGIN

END proc1;

PROCEDURE Sum(a,b: REAL): REAL; (* Процедура-функция с параметрами *) BEGIN END Sum;

PROCEDURE proc2(a,b: CARDINAL; VAR b: REAL; VAR s: BOOLEAN); (* Процедура-подпрограмма *) BEGIN END proc2;

BEGIN

i:=proc1(); q:=Sum(w,v); proc2(i,j,w,b); END Mod1.

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

СПИСОК ЛИТЕРАТУРЫ

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

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

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

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

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

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

ПРИЛОЖЕНИЕ 1