Калининградский государственный технический университет системное программное обеспечение (спо)
Методические указания к лабораторным работам по курсу СПО для специальностей 230102.65 «Автоматизированные системы обработки информации и управления» и
230101.65 «Вычислительные машины, комплексы, системы и сети». Часть I.
Калининград
2007
УДК 681.3.06 (075)
УТВЕРЖДЕНО
Ректором Калининградского
государственного технического
университета
АВТОР - Высоцкий Л.Г., доцент кафедры систем управления и вычислительной техники Калининградского государственного технического университета
Методические указания рассмотрены и одобрены кафедрой систем управления и вычислительной техники Калининградского государственного технического университета 24 января 2008 г., протокол № 3.
РЕЦЕНЗЕНТ - кафедра систем управления и вычислительной техники Калининградского государственного технического университета
Методические указания рассмотрены и одобрены методической комиссией факультета автоматизации производства и управления Калининградского государственного технического университета 30 января 2008 г., протокол № 5.
Калининградский государственный технический университет
2007 г.
Введение
В соответствии с Государственным образовательным стандартом курс «Системное программное обеспечение» ориентирован на изучением студентами информационных направлений вузов операционных систем и систем программирования. В данном методическом пособии рассматриваются вопросы теоретического изучения и практической реализации, необходимые для построения трансляторов со специализированных языков, являющихся основой любой системы программирования.
В процессе выполнения лабораторного практикума студент осваивает разные средства формального описания грамматики будущего языка программирования, учится реализовывать распознаватель в виде конечного автомата, снабжать его набором диагностических сообщений об ошибках, преобразовывать исходный текст в промежуточный код, который должен в дальнейшем транслироваться в машинный код конкретного компьютера.
В завершение практикума студент осваивает конкретные алгоритмы синтаксического распознавания цепочек некоторого формального языка.
Лабораторная работа №1 Средства описания грамматик
Цель работы: изучение основных средств описания формальных грамматик и закрепление на практике навыков их использования.
Введение
В настоящее время для описания формальных грамматик, в основном, используются три механизма [1]:
-
язык метасимволов;
-
формы Бэкуса-Наура (БНФ);
-
графическая нотация.
Все они базируются на формальном определении грамматики в виде четверки
G = (VT, VN, P, S),
где:
VT - множество терминальных символов грамматики;
VN - множество нетерминальных символов. При этом VT VN = ;
P - множество правил (продукций) грамматики вида , где V+ (V+ - множество всех цепочек из терминальных символов данной грамматики), V* (V* - множество всех цепочек из терминальных символов данной грамматики, включая пустую цепочку );
S - целевой (начальный) символ грамматики. S VN;
V = VN VT - полный алфавит грамматики G.
При использовании БНФ используется следующие правила синтаксиса:
-
Продукции записываются в виде:
1, 2, . . . , n,
или в сокращенном виде
1 | 2 | . . . , | n. (исключающее ИЛИ).
При этом вместо символа может использоваться символ :: =.
2. Терминальные символы записываются в угловых скобках <>.
Для примера ниже описана грамматика вещественного числа:
G({0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, -, .}, {<число>, <знак>, <цифра>, <левая часть>, <правая часть>, <числовая константа>}, Р, <число>)
Р:
<число> <левая часть>.<правая часть>
<правая часть> <числовая константа>
<левая часть> <знак><числовая константа> | <числовая константа>
<знак> + | -
<числовая константа> <цифра> | <числовая константа><цифра>
<цифра> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Названия нетерминальных символов можно сокращать, заменяя их осмысленной аббревиатурой, например: <числовая константа> на <чк> и т.д.
Язык метасимволов использует следующие правила синтаксиса:
-
Круглые скобки () обозначают исключающее ИЛИ, т.е. в каждом случае из перечисленных элементов выбора используется только один. Сами элементы выбора перечисляются через запятую ,.
-
Квадратные скобки обозначают необязательность.
-
Фигурные скобки обозначают повторяемость (в общем случае и нулевую). При этом справа от закрывающей скобки могут ставиться числовые значения, определяющие допустимый диапазон повторяемости, например {цифра
. -
Если некоторый метасимвол необходимо включить в перечень терминальных символов, то перед ним в записи грамматики необходимо поставить апостроф (кавычку).
Описание рассмотренной ранее грамматики на языке метасимволов имеет вид:
G({0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, -, .}, {<число>, <цифра>, <чк>}, Р, <число>)
Р:
<число> [(+ | -)]<чк>.<чк>
<чк>
{<цифра>
<цифра> (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
При графической нотации все правила грамматики фиксируются в виде диаграмм (см. рис. 1.1), в которых:
-
Нетерминальные символы представляются прямоугольниками, а терминальные символы - овалами.
-
Каждый нетерминальный символ описывается отдельной диаграммой с одной точкой входа и одной - выхода.
Т
а
же самая грамматика, рассмотренная
ранее, в графическом представлении
имеет вид:
Выполнение лабораторной работы
-
В соответствии с вариантом выбрать из табл. 1.1 фрагмент листинга программы на языке Паскаль.
-
По справочной литературе найти полное синтаксическое описание данных языковых конструкций программ.
Таблицы 1.1
|
№ п/п |
Структуры языка |
|
|
AC |
BC |
|
|
1 |
Раздел констант |
Описание записей, содержащих поля целого, вещественного типа и типа char |
|
2 |
Раздел типов данных, включающий описание перечисляемых типов и типов-диапазонов |
Раздел типов, включающий описание типов на основе строк определенной длины и одномерных массивов типа integer и boolean |
|
3 |
Описание записей, содержащих поля типов real, word, byte и char |
Описание записей, содержащих поля типов string, word и типов-диапазонов |
|
4 |
Описание вариантных записей, содержащих поля типа word, byte, boolean и char |
Описание вариантных записей, содержащих поля числовых типа. Перед вариантом допускается диапазон меток |
|
5 |
Оператор until, логическое выражение которого включает простые переменные, числа, скобки, логические операции и операции отношения |
Раздел переменных, включающий описание переменных всех пяти вещественных типов и типа boolean |
|
6 |
Раздел переменных, включающий описание переменных - двумерных массивов с элементами типа real, byte или boolean |
Раздел переменных, включающий описание переменных всех числовых типов и типов-диапазонов |
|
7 |
Шапка цикла for, начальным значением которого является целое число, а конечным арифметическое выражение из простых переменных и четырех арифметических операций |
Раздел переменных, включающий описание переменных - одномерных массивов с элементами типа byte, integer или char |
|
8 |
Шапка цикла for, начальным значением которого является простая переменная, а конечным арифметическое выражение из простых переменных, целых числе и четырех арифметических операций |
Оператор writeln, список вывода которого содержит перечень простых переменных с указанием формата вывода, индексированных переменных с индексами-целыми числами |
|
9 |
Раздел переменных, включающий задание файловых переменных и переменных числовых типов |
Арифметическое выражение, включающее простые переменные, стандартные тригонометрические операции, четыре арифметические операции и скобки |
|
10 |
Оператор While, логическое выражение которого включает простые переменные, числа, скобки, логические операции и операции отношения |
Арифметическое выражение, включающее вещественные и целые числа, четыре арифметические операции и скобки |
|
11 |
Арифметическое выражение, включающее индексированные и простые переменные, а также четыре арифметические операции (одинарные индексы – целые числа) |
Шапка процедуры, включающая в качестве формальных параметров переменные всех пяти целых типов. Параметры передаются как в виде значений, так и в виде адресов |
Таблица 1.1 Продолжение
|
12 |
Шапка процедуры, включающая в качестве формальных параметров переменные всех пяти вещественных типов. Параметры передаются как в виде значений, так и в виде адресов |
Шапка процедуры, включающая в качестве формальных параметров переменные типов byte, integer или char. Параметры передаются как в виде значений, так и в виде адресов |
|
13 |
Шапка процедуры, включающая в качестве формальных параметров переменные типов word, byte и char. Параметры передаются как в виде значений, так и в виде адресов |
Шапка функции, включающая в качестве формальных параметров переменные типов word, byte и char, а возвращаемое значение типа boolean |
|
14 |
Шапка функции, включающая в качестве формальных параметров переменные типов byte, integer или char, а возвращаемое значение типа real |
Шапка функции, включающая в качестве формальных параметров переменные типов real, integer или boolean, а возвращаемое значение типа word |
|
15 |
Арифметическое выражение, включающее простые переменные, целые и вещественные числа, а также четыре арифметические операции |
Логическое выражение, включающее операции отношения, логические операции, простые переменные и круглые скобки |
|
16 |
Логическое выражение, включающее операции отношения, логические операции, простые переменные, целые числа и круглые скобки |
Оператор присваивания, в левой части которого простая переменная, а в правой арифметическое выражение из простых переменных, целых чисел и четырех арифметических операций |
|
17 |
Логическое выражение, включающее операции отношения, логические операции, простые и индексированные переменные (индексы – целые числа) и круглые скобки |
Оператор присваивания, в левой части которого индексированная переменная (индекс – целое число), а в правой арифметическое выражение из простых переменных, целых чисел и четырех арифметических операций |
|
18 |
Логическое выражение, включающее операции отношения, логические операции, индексированные переменные (индексы – целые числа), целые числа и круглые скобки |
Оператор присваивания, в левой части которого индексированная переменная (индекс – простая переменная), а в правой арифметическое выражение из простых переменных, целых чисел и четырех арифметических операций |
|
19 |
Логическое выражение, включающее операции отношения, логические операции, простые переменные, вещественные числа и круглые скобки |
Оператор вывода write|writeln, в списке вывода которого можно указывать литералы, целые и вещественные переменные |
|
20 |
Логическое выражение, включающее операции отношения, логические операции, простые переменные, вещественные и целые числа и круглые скобки |
Описание записей, содержащих числовые поля и поля на основе диапазонов |
Таблица 1.1 Продолжение
|
21 |
Оператор присваивания, в левой части которого простая переменная, а в правой арифметическое выражение из простых переменных, целых чисел и четырех арифметических операций |
Оператор write, список вывода которого содержит перечень простых переменных, индексированных переменных, индексами которых являются целые числа, и литералов |
|
22 |
Оператор присваивания, в левой части которого индексированная переменная (индекс – целое число), а в правой арифметическое выражение из простых переменных, целых чисел и четырех арифметических операций |
Оператор write, список вывода которого содержит перечень простых переменных и арифметических выражений из целых чисел, простых переменных и четырех арифметических действий |
|
23 |
Оператор writeln, список вывода которого содержит перечень простых переменных с указанием формата и арифметических выражений из целых чисел, простых переменных и четырех арифметических действий |
Оператор writeln, список вывода которого содержит перечень литералов, простых переменных с указанием формата и арифметических выражений из целых чисел, простых переменных и четырех арифметических действий |
-
Разработать описание грамматики данного фрагмента, рассматривая последнюю как целевой (начальный) символ. Описание провести в трех вариантах:
-
средствами БНФ;
-
на основе метасимволов;
-
графическими средствами.