Сист. прогр. Ч2 (Лекции по СПО), страница 13

16. ФОРМАЛЬНЫЕ СИСТЕМЫ И ЯЗЫКИ ПРОГРАММИРОВАНИЯ. ВВЕДЕНИЕ

Цели данной главы следующие:

1. Дать неформальное введение в формальные системы и грамматики.

2. Показать применимость теоретических результатов к практической работе в области языков программирования,

3. Представить формальные системы и общеупотребитель­ную для данной области терминологию.

4. Дать некоторые теоретические средства, пригодные для построения компиляторов.

5. Разобрать два способа описания языков программирования: форма Бэкуса - Наура и канонические системы.

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

Данная глава кратко касается сложных и разнообразных вопросов. Более детальное их рассмотрение можно найти в библиографии.

ИСПОЛЬЗОВАНИЕ ФОРМАЛЬНЫХ СИСТЕМ В ЯЗЫКАХ ПРОГРАММИРОВАНИЯ

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

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

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

ОПИСАНИЕ ЯЗЫКА

Формальные системы используются для описания формы (синтаксиса) языка программирования. Такое описание играет важную роль как для пользователя, так и для создателя компиляторов. Пользователь нуждается в ясном описании языка. Создатель компилятора сталкивается с проблемами мобильности и сопровождения. Если один и тот же язык должен быть реализован на разных машинах, допустимые строки языка должны быть так определены, чтобы их представление на пользовательском уровне (насколько это практически возможно) было инвариантным. При реализации языка следует также думать о проблеме сопровождения. Как пользователь, так и создатель компилятора нуждаются в точном описании допустимых строк соответствующего языка.

СИНТАКСИЧЕСКИ-ОРИЕНТИРОВАННЫЕ КОМПИЛЯТОРЫ

Синтаксически-ориентированный компилятор использует базу данных, содержащую синтаксические правила исходного языка, для проведения грамматического разбора (распознавания — нахождения последовательности правил, необходимых для порождения заданной строки языка). Формальные системы используются в этом случае как база данных. Поскольку число языков программирования и вычислительных машин постоянно увеличивается, возникла необходимость в автоматизации процесса создания компиляторов. Для этого требуется формальное описание как исходного языка L_исх, так и выходного L_{объектн,} выходом генератора компиляторов является транслятор Т, осуществляющий перевод L_исх→ L_{объектн.}

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

ИЗУЧЕНИЕ СЛОЖНОСТИ СТРУКТУРЫ

Формальные системы используются для изучения сложности языков программирования и компиляторов. Создатели и языка, и компилятора хотят знать, какие свойства языка наиболее существенным образом увеличивают в компиляторе сложность фазы распознавания. Создатель компилятора, кроме того, хочет иметь некоторую основу для оценки производительности компилятора. Он хотел бы знать теоретически оптимальный уровень этой характеристики (выраженный в требуемом числе шагов). После реализации определенной версии компилятора он мог бы сравнить его характеристики с теоретическими оценками; если значение производительности находится в допустимых пределах, дальнейшие попытки улучшить компилятор можно было бы отложить. Но если производительность оказывается на два порядка хуже теоретической, необходимо улучшить компилятор.

Можно провести аналогию с шенноновской теорией информации. Шеннон определил меру информации и применил ее для кодирования. Теория давала границы эффективности при кодировании и передаче информации. Исследователи фирмы Bell Telephone Laboratories, создающие технику для кодирования и передачи информации, получили возможность сравнивать производительность разрабатываемых схем с шенноновской границей, используя ее как критерий оценки. Шенноновская теория не определяет схему кодирования. Она просто обеспечивает средство измерения ее эффективности. Аналогично при определении сложности создатель компилятора должен говорить не о том, какой конкретно метод следует использовать, а о том может ли существовать какой-либо другой, лучший метод.

АНАЛИЗ СТРУКТУРЫ.

Формальные системы используются при попытках доказательства эквивалентности и правильности программ. Работа по доказательству эквивалентности программ мотивируется перспективой глобальной оптимизации. Если бы существовал алгоритм, определяющий эквивалентность двух различных программ, можно было бы использовать более быструю программу взамен медленной.

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

1. Что является базовыми элементами языка?

2. Какие конструкции допустимы в языке? Как могут комбинироваться элементы языка для построения новых конструкций?

3. Какие классы задач могут быть запрограммированы на данном языке?

4. Какова стоимость и трудность написания программы?

К решению этих ключевых вопросов можно приблизиться только с помощью определенного формализма. Ответы на эти вопросы представляют интерес и для проектировщиков вычислительных машин, поскольку идеальная ЭВМ должна эффективно выполнять операции, соответствующие базовым возможностям языка.

ФОРМАЛЬНОЕ ОПИСАНИЕ ЯЗЫКА

ВВЕДЕНИЕ В ФОРМАЛИЗАЦИЮ

Прежде чем углубиться в рассмотрение формализма, полезно проанализировать некоторые проблемы формального описания языков и рассмотреть интуитивную форму такого описания. Язык можно представить как некоторое множество предложений или формул - строк символов - с корректно определенной структурой и, обычно, со значением. Правила, определяющие допустимые конструкции языка, составляют его синтаксис: синтаксис языка описывает его форму. Например, когда мы говорим, что х + 2 является выражением, а х2+ таковым не является, мы оперируем синтаксисом алгебры. Присваивание значений (интерпретация) символам и формулам есть семантика языка. Когда мы говорим, например, что x+2 есть сумма значения х и 2 или что 2∙х =x+x есть истина, мы апеллируем к обычной семантике алгебры.

Если бы все языки состояли из конечного числа допустимых предложений или формул, проблема описания синтаксиса вообще бы не стояла: достаточно было бы просто перечислить все допустимые предложения - строка символов представляла бы предложение языка только в том случае, если бы она попадала в список допустимых. Но проблема описания существует, поскольку почти все языки содержат неограниченное (или очень большое) число допустимых предложений. Невозможно запомнить список всех правильных строк для бесконечного языка. Однако в этом нет необходимости, если любой элемент списка может быть сгенерирован, когда это необходимо, даже если генерация всех предложений является процессом бесконечным, Если существует алгоритм, который будет последовательно порождать правильные строки, любая строка будет отнесена к языку, если только она когда-либо появляется в генерируемом описании. Заметим, что, если строка является допустимой, она будет обязательно сгенерирована за конечное (возможно очень большое) время. Такой алгоритм называется порождающим описанием языка.

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

Для описания языка может использоваться и другой тип алгоритма. При этом втором подходе проверяемая строка выступает в виде исходных данных в разрешающем алгоритме. После необходимых вычислений алгоритм вырабатывает ответ «да, строка правильная» или «нет, это неправильная строка». Такое определение языка называется аналитическим. Язык с аналитическим описанием разрешим, если анализатор для каждой входной строки завершает свою работу за конечное число шагов. К сожалению, формальные аналитические описания часто очень трудны для вывода; поэтому данная глава в основном посвящается порождающим описаниям языка.

Естественный язык не подходит для формального описания из-за его неопределенности, что приводит к неоднозначным определениям. Необходимо разработать такой формализм, в котором понятия языка могли быть выражены вполне определенно. Такой язык называется синтаксическим метаязыком. Когда мы используем какой-либо язык для описания другого языка (его самого или другого), мы называем последний объектным языком, а первый метаязыком. Формальная система является метаязыком. Символы объектного языка называются терминальными символами. Символы метаязыка, обозначающие строки объектного языка, называются нетерминальными. Чтобы формально описать метаязык, требуется метаметаязык; поэтому мы надеемся, что понятие метаязыка интуитивно ясно.

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

Определение 1. Алфавит Т есть конечное множество символов (терминальных символов). Формула (называемая также строкой или предложением) есть конкатенация символов.

Удобно было бы иметь какое-то обозначение для класса всех возможных конечных строк алфавита Т. Обозначим его через Т*. Для любого множества U множество всех возможных конкатенаций элементов этого множества обозначим через U*. Для обозначения строк будем использовать строчные греческие буквы. Буквой λ будем обозначать «нулевую» или «пустую» строку (т. е. строку, в которой отсутствуют элементы).

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

Определение 2. Язык L есть подмножество множества конечных строк в алфавите Т. Мы будем писать Lс Т*.

ПОСТРОЕНИЕ ФОРМАЛЬНОГО ОПИСАНИЯ

Обратимся к примеру из синтаксиса английского языка. Английский язык - не просто произвольные группы слов, в нем имеется вполне определенная структура.

каречав

предложение

N P VP

а ртикль существительное глагол наречие

T he student studies hard

Рис.16.1

Например, предложение «The student studies hard» может быть представлено в виде структуры, показанной на рис. 16.1. Здесь можно выделить именную группу (NP) и глагольную группу (VP), которые затем подразделяются на отдельные слова. Поскольку все предложения имеют определенную структуру, ее можно порождать последовательными шагами, тем самым строя сложные предложения. Мы будем представлять структуры графически в виде синтаксического дерева; ветви, исходящие из узла дерева, указывают логические разветвления.

Например, мы можем начать разбор с узла «предложение» и заменить его на пару NP и VP, построив тем самым одну из возможных форм предложения. Это удобно записывать в таком виде:

предложение → NP VP