1.2. Применение компиляторов и задачи их разработки
Одной из важных задач, решаемых при создании любой программной системы, является разработка средств взаимодействия пользователя с этой системой.
В настоящее время широко распространен способ взаимодействия при помощи диалоговых процедур с использованием "меню" и "шаблонов". Меню и шаблоны предназначены для выбора функций из состава меню и ввода данных в информационные поля шаблонов. Этим обеспечивается управление работой системы со стороны пользователя.
Однако для многих классов систем организация взаимодействия только при помощи диалога оказывается не эффективной в силу ее недостаточной гибкости и больших затрат времени на ввод информации.
Пример 1.1. Пакеты прикладных программ (ППП). Если ППП имеет сложную структуру, то последовательность вызываемых процедур пакета формируется в зависимости от входных данных. Кроме того, после отработки текущей процедуры, выбор очередной процедуры может зависеть от результатов, полученных в текущей процедуре. В этом случае управлять работой пакета в диалоговом режиме невозможно (или неудобно). Проще заранее подготовить инструкцию, которая будет управлять работой пакета. Эта инструкция пишется на входном языке пакета и для ее трансляции в машинный язык необходим соответствующий языковый процессор(компилятор, интерпретатор и т.п.).
Пример 1.2. Системы автоматизированного проектирования (САПР). В САПР пользователь описывает задачу или объект проектирования на проблемно-ориентированном языке. В некоторых САПР необходимо описывать и проектные процедуры, регламентирующие использование технических средств САПР на различных этапах проектирования. Следовательно, в составе ее программного обеспечения должен быть языковый процессор.
Пример 1.3. Автоматизированные обучающие системы (АОС). В АОС широко используются средства компьютерной мультипликации. Изображения различных объектов и процессов (технологических процессов, схем технологического оборудования и т.п.), показываются в процессе обучения в статическом или динамическом режимах. Последовательность показа "экранных кадров" зависит от целей конкретного урока и от действий обучаемого. Для описания сценария уроков и экранных кадров необходимы соответствующие языки, а для их трансляции в машинное представление - соответствующие интерпретаторы.
Из этих примеров ясно, что разработчик программной системы
должен уметь решать следующие задачи:
- выбирать или разрабатывать оригинальный проблемно-ориентированный язык для конкретного пользователя;
- разрабатывать и реализовывать языковый процессор системы.
Если организация взаимодействия с системой осуществляется при помощи диалога, то могут использоваться синтаксические и семантические анализаторы для контроля корректности вводимой информации,т.е “усеченные” версии компилятора.
Глава 2 способы задания формальных языков
2.1. Математический аппарат теории
Формальных языков, перевода и компиляции
Математический аппарат, применяемый при разработке формальных языков и конструировании трансляторов, в значительной мере, сформирован из аппаратов других математических теорий, таких как теория множеств, теория графов и др. Мы перечислим только те понятия и определения из этого аппарата, которые непосредственно будут использоваться в этой книге.
Множества. Множества будут определяться при помощи предикатов (высказываний):
А={x | P(x)}, где P(x) - высказывание.
Эту запись следует понимать как: А - множество элементов х таких, что Р(х) или удовлетворяющих Р(х).
Пример 2.1. А={x | x - четное} - множество четных чисел.
Напомним основные операции над множествами:
а) объединение
;
б) пересечение
;
в) разность
;
г) дополнение
;
д) декартово
произведение
.
Отношение.
Отношением R
из A
в B
называется любое подмножество множества
,
причем А
называется областью определения, а В
- областью значений.
Пример 2.2. Если А={1,2} и B={a,b,c}, тогда R может принять следующее значение: R={(1,a),(1,c),(2,b)}.
Обратным
отношением
(обозначается
)
называется
отношение
Вместо записи
можно использовать запись aRb.
Если А=В,
то говорят, что R
определено на
А.
Отношение R удобно представлять в виде помеченных узлов решетки, звенья которой соответствуют элементам множества А.
Пример
2.3. Пусть
А={1,2,3,4},
а R-
отношение "больше" (>) заданное
на А,
тогда R и
можно представить в следующих формах:
R=">"={(2,1),(3,1),(3,2),(4,1),(4,2),(4,3)};
="<"={(1,2),(1,3),(2,3),(1,4),(2,4),(3,4)}.
Для этих отношений можно записать:
2R1, 3R1, ... или 2>1, 3>1,.... ;
1 2, 1 3, ..., или 1<2,1<3,... .
Отношение, заданное на множестве А может обладать следующими свойствами:
1)
рефлексивность:
R
рефлексивно, если aRa
для всех
(в этом случае главная диагональ решетки входит в отношение);
2) симметричность: R симметрично, если из aRb следует, что и bRa (помеченные узлы решетки симметричны относительно главной диагонали);
3) транзитивность: R транзитивно, если из aRb и bRc следует, что aRc.
Если отношение R удовлетворяет всем трем свойствам, то оно называется отношением эквивалентности.
Отношение эквивалентности разбивает множество А на непересекающиеся подмножества, которые называются классами эквивалентности. Для каждого а из А класс эквивалентности [а] есть множество таких элементов b, что aRb:
.
Пример 2.4. R - отношение сравнения по модулю N, определенное на множестве А неотрицательных целых чисел. Это отношение определяется следующим образом: а сравнивается с b по модулю N (записывается а=b(modN)), если существует такое целое k, что а-b=kN.
Пусть N=3, тогда R разбивает А на три класса эквивалентности:
[0]={0,3,6,9,......},
[1]={1,4,7,10,....},
[2]={2,5,8,11,....}.
Очевидно, что
объединение всех трех классов дает само
множество А,
т.е.
Индексом отношения эквивалентности называется число классов эквивалентности, на которые это отношение R разбивает множество А(в приведенном примере индекс R равен 3).
Рассмотрим теперь операции над отношениями.
K-я
степень отношения
на множестве А
(обозначается
)
определяется следующим образом:
1)
тогда и только тогда, когда
aRb;
2)
(i>1) тогда
и только тогда, когда существует такое
,
что aRc
и cRi-1b.
Транзитивное
замыкание отношения
R на
множестве А
(обозначается
)
определяется следующим образом:
тогда и только тогда, когда
для некоторого
(т.е. если существует такая последовательность
элементов
,
что
).
Из этого определения следует, что
.
Рефлексивное
и транзитивное замыкание
отношения
R
на множестве А
(обозначается
)
определяется следующим образом: