УЗБЕКСКОЕ АГЕНТСТВО СВЯЗИ И ИНФОРМАТИЗАЦИИ

ТАШКЕНТСКИЙ УНИВЕРСИТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

 

 

 

 

 

 

 

 

 

 

 

 

 

Конспект лекций

По предмету

Системное программное обеспечение

 

 

 

Ташкент 2008.

 

 

 

 

1. Введение. Предмет "Системное программное обеспечение", основные поня­тия.

 

Операционные системы и среды

В англоязычной технической литературе термин System Software (системное программное обеспечение) означает программы и комплексы программ, являющиеся общими для всех, кто совместно использует технические средства компьютера и применяемые как для автоматизации разработки (создания) новых программ так и для организации выполнения программ существующих. С этих позицию системное программное обеспечение может быть разделено на следующие пять групп:

1.         Операционные системы.

2.         Системы управления файлами.

3.         Интерфейсные оболочки для взаимодействия пользователя с ОС и программ ные среды.

4.         Системы программирования.

5.         Утилиты.

Рассмотрим вкратце эти группы системных программ.

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

                                     Рис.1. Обобщенная структура программного обеспечения вычислительной системы

Основными функциями, которые выполняет ОС, являются следующие:

- прием от пользователя (или от оператора системы) заданий или команд, сформулированных на соответствующем языке — в виде директив (ко­манд) оператора или в виде указаний (своеобразных команд) с помощью соответствующего манипулятора (например, с помощью мыши), — и их обработка;

- прием и исполнение программных запросов на запуск, приостановку, оста­новку других программ;

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

- обеспечение работы систем управлений файлами (СУФ) и/или систем управления базами данных (СУБД), что позволяет резко увеличить эф­фективность всего программного обеспечения;

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

- обеспечение функций по организации и управлению всеми операциями ввода/вывода;

- удовлетворение жестким ограничениям на время ответа в режиме реаль­ного времени (характерно для соответствующих ОС);

- распределение памяти, а в большинстве современных систем и организа­ция виртуальной памяти;

О планирование и диспетчеризация задач в соответствии с заданными стра­тегией и дисциплинами обслуживания;

- организация механизмов обмена сообщениями и данными между выпол­няющимися программами;

- защита одной программы от влияния другой; обеспечение сохранности данных;

- предоставление услуг на случай частичного сбоя системы;

- обеспечение работы систем программирования, с помощью которых поль­зователи готовят свои программы.

2. Назначение системы управления файлами — организация более удобного доступа к данным, организованным как файлы. Именно благодаря системе управления файлами вместо низкоуровневого доступа к данным с указанием конкретных физических адресов нужной нам записи используется логиче­ский доступ с указанием имени файла и записи в нем. Как правило, все совре­менные ОС имеют соответствующие системы управления файлами. Однако выделение этого вида системного программного обеспечения в отдельную ка­тегорию представляется целесообразным, поскольку ряд ОС позволяет рабо­тать с несколькими файловыми системами (либо с одной из нескольких, либо сразу с несколькими одновременно). В этом случае говорят о монтируемых файловых системах (дополнительную систему управления файлами можно установить), и в этом смысле они самостоятельны. Более того, можно назвать примеры простейших ОС, которые могут работать и без файловых систем, а значит, им необязательно иметь систему управления файлами, либо они мо­гут работать с одной из выбранных файловых систем. Надо  понимать, что любая система управления  с  файлами не существует сама по себе — она разработана для работы в конкретной ОС и с конкретной файловой систе­мой. Можно сказать, что всем известная файловая система FAT (file allocation table)1 имеет множество реализаций как система управления файлами, напри­мер FAT-16 для самой MS-DOS, super-FAT для OS/2, FAT для Windows NT

Здесь и далее без указания на источник заимствования приводятся английские эквива­ленты слов и словосочетаний.

т. д. Другими словами, для работы с файлами, организованными в соответ-вии с некоторой файловой системой, для каждой ОС должна быть разра-1тана соответствующая система управления файлами; и эта система управ-ния файлами будет работать только в той ОС, для которой она и создана.

гя удобства взаимодействия с ОС могут использоваться дополнительные гтерфейсные оболочки. Их основное назначение — либо расширить возможности по управлению ОС, либо изменить встроенные в систему возможности, в качестве классических примеров интерфейсных оболочек и соответствующих операционных сред выполнения программ можно назвать различные варианты графического интерфейса X Window в системах семейства UNIX апример, К Desktop Environment в Linux), PM Shell или Object Desktop OS/2 с графическим интерфейсом Presentation Manager; наконец, можно :азать разнообразные варианты интерфейсов для семейства ОС Windows Алании Microsoft, которые заменяют Explorer и могут напоминать либо NTX с его графическим интерфейсом, либо OS/2, либо MAC OS. Следует метить, что о семействе ОС компании Microsoft с общим интерфейсом, реа-[зуемым программными модулями с названием Explorer (в файле system.ini, •торый находится в каталоге Windows, имеется строка SHELL=EXPLORER.EXE), е же можно сказать, что заменяемой в этих системах является только ин-рфейсная оболочка, в то время как сама операционная среда остается неиз-;нной; она интегрирована в ОС. Другими словами, операционная среда феделяется программными интерфейсами, то есть API (application program terface). Интерфейс прикладного программирования (API) включает в себя управление процессами, памятью и вводом/выводом.

ад операционных систем могут организовывать выполнение программ, соз-нных для других ОС. Например, в OS/2 можно выполнять как программы, зданные для самой OS/2, так и программы, предназначенные для выполнения в среде MS-DOS и Windows 3.x. Соответствующая операционная среда танизуется в операционной системе в рамках отдельной виртуальной ма-ины. Аналогично, в системе Linux можно создать условия для выполнения некоторых программ, написанных для Windows 95/98. Определенными воз-шностями исполнения программ, созданных для иной операционной среды, ■ладает и Windows NT. Эта система позволяет выполнять некоторые про-аммы, созданные для MS-DOS, OS/2 1.x, Windows 3.x. Правда, в своем по-еднем семействе ОС Windows XP разработчики решили отказаться от 'Ддержки возможности выполнения DOS-программ.

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

жим образом, термин операционная среда означает соответствующий ин-Рфейс, необходимый программам для обращения к ОС с целью получить определенный сервис1 — выполнить операцию ввода/вывода, получить или освободить участок памяти и т. д. 3.  Система программирования на рис. 1 представлена прежде всего такими компонентами, как транслятор с соответствующего языка, библиотеки подпро­грамм, редакторы, компоновщики и отладчики. Не бывает самостоятельных (оторванных от ОС) систем программирования. Любая система программи­рования может работать только в соответствующей ОС, под которую она  создана, однако при этом она может позволять разрабатывать программное обеспечение и под другие ОС. Например, одна из популярных систем про­граммирования на языке C/C++ от фирмы Watcom для OS/2 позволяет по­лучать программы и для самой OS/2, и для DOS, и для Windows. В том случае, когда создаваемые программы должны работать совсем на другой аппаратной базе, говорят о кросс-системах. Так, для ПК на базе микропроцес­соров семейства i80x86 имеется большое количество кросс-систем, позволяю,-щих создавать программное обеспечение для различных микропроцессоров и микроконтроллеров. 4. Наконец, под утилитами понимают специальные системные программы, с по­мощью которых можно как обслуживать саму операционную систему, так и подготавливать для работы носители данных, выполнять перекодирование данных, осуществлять оптимизацию размещения данных на носителе и про­изводить некоторые другие работы, связанные с обслуживанием вычислитель­ной системы. К утилитам следует отнести и программу разбиения накопителя на магнитных дисках на разделы, и программу форматирования, и программу переноса основных системных файлов самой ОС. Также к утилитам относят­ся и небезызвестные комплексы программ от фирмы Symantec, носящие имя Питера Нортона (создателя этой фирмы и соавтора популярного набора ути­лит для первых IBM PC). Естественно, что утилиты могут работать только в соответствующей операционной среде.

Сервис (service) - обслуживание, выполнение соответствующего запроса.

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

Традиционная архитектура компьютера (архитектура фон Неймана) остается неизменной и преобладает в современных вычислительных системах. Столь же неизменными остаются и базовые принципы, на основе которых строятся сред­ства разработки программного обеспечения для компьютеров — трансляторы, компиляторы и интерпретаторы. Видимо, этим объясняется практически полное отсутствие современных публикаций в этой области, а те, что известны, являют­ся не достаточно широко доступными (автор может выделить книги и публика­ции [4, 13, 18, 26, 27, 35, 40, 45, 47]). Тем не менее современные средства разра­ботки, оставаясь на тех же базовых принципах, что и компьютеры традиционной архитектуры, прошли долгий путь совершенствования и развития от командных систем до интегрированных сред и систем программирования. И это обстоятель­ство нашло отражение в предлагаемом учебном пособии.

Ныне существует огромное количество разнообразных языков программирова­ния. Все они имеют свою историю, свою область применения, и перечислять даже наиболее известные из них здесь не имеет смысла. Но все эти языки по­строены на основе одних и тех же принципов, основы которых определяет тео­рия формальных языков и грамматик. Именно теоретическим основам посвящены четыре первые главы пособия, поскольку для построения транслятора необходи­мо знать все те принципы, на основе которых он работает. Первая глава посвя­щена общим принципам и определениям, на которых построена теория формаль­ных языков и грамматик; вторая глава посвящена регулярным языкам, а третья и четвертая — контекстно-свободным языкам и грамматикам.

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

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

 

 

 

 

 

2. Формальные языки и грамматики. Способы задания языков. символов. Операции над цепочками символов. Понятие языка. Способы задания языков. Синтаксис и семантика языка. Особенности языков программирования.

 

Цепочки символов. Операции над цепочками символов

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

Далее цепочки символов будем обозначать греческими буквами: а, р\ у.

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

Для цепочки символов важен состав и количество символов в ней, а также поря­док символов в цепочке. Один и тот же символ может произвольное число раз входить в цепочку. Поэтому цепочки «а» и «аа», а также «аб» и «ба» — это раз­личные цепочки символов. Цепочки символов аир равны (совпадают), а = р, если они имеют один и тот же состав символов, одно и то же их количество и одинаковый порядок следования символов в цепочке.

Количество символов в цепочке называют длиной цепочки. Длина цепочки сим­волов а обозначается как |а|. Очевидно, что если а = р, то и |А| = |В|.

Основной операцией над цепочками символов является операция конкатенации (объединения или сложения) цепочек.

Конкатенация (сложение, объединение) двух цепочек символов — это дописы­вание второй цепочки в конец первой. Конкатенация цепочек аир обозначает­ся как ар. Выполнить конкатенацию цепочек просто: например, если а = «аб», а р = «вг», то ар = «абвг».

Так как в цепочке важен порядок символов, то очевидно, что операция конкате­нации не обладает свойством коммутативности, то есть в общем случае Заир такие, что ар*ра. Также очевидно, что конкатенация обладает свойством ассо­циативности, то есть (аР)у = а(Ру). Можно выделить еще две операции над цепочками.

Обращение цепочки — это запись символов цепочки в обратном порядке. Обра­щение цепочки  а обозначается как aR. Если a = «абвг», то aR = «гвба». Для опе­рации обращения справедливо следующее равенство V a,p: (aP)R = pRaR.

Итерация (повторение) цепочки п раз, где neN, n > 0 — это конкатенация це­почки самой с собой п раз. Итерация цепочки a n раз обозначается как an. Для операции повторения справедливы следующие равенства V а: а1 = а, а2 = аа, а3 = ааа, ... и т. д.

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

Для пустой цепочки справедливы следующие равенства:

1. N = 0;

2.         Va: Ха = аХ = а;

3.         XR = X;

4.         \/п>0:Хп = Х;

5.         Va:a°=l.

Понятие языка. Формальное определение языка

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

Алфавит — это счетное множество допустимых символов языка. Будем обозна­чать это множество символом V. Интересно, что согласно формальному опре­делению, алфавит не обязательно должен быть конечным (перечислимым) мно­жеством, но реально все существующие языки строятся на основе конечных алфавитов.

Цепочка символов а является цепочкой над алфавитом V: a(V), если в нее вхо­дят только символы, принадлежащие множеству символов V. Для любого алфа­вита V пустая цепочка X может как являться, так и не являться цепочкой Х(У). Это условие оговаривается дополнительно

Если V — некоторый алфавит, то:

□     V+ — множество всех цепочек над алфавитом V без X;

□     V* — множество всех цепочек над алфавитом V, включая А,.

Справедливо равенство: V* = V+ u {X}.

Языком L над алфавитом V:L(V) называется некоторое счетное подмножес цепочек конечной длины из множества всех цепочек над алфавитом V. Из эп определения следуют два вывода: во-первых, множество цепочек языка не обя но быть конечным; во-вторых, хотя каждая цепочка символов, входящая в яз: обязана иметь конечную длину, эта длина может быть сколь угодно больше формально ничем не ограничена.

Все существующие языки подпадают под это определение. Большинство реа ных естественных и искусственных языков содержат бесконечное множество почек. Также в большинстве языков длина цепочки ничем не ограничена (нап мер, этот длинный текст — пример цепочки символов русского языка). Цепо1 символов, принадлежащую заданному языку, часто называют предложением язь а множество цепочек символов некоторого языка L(V) — множеством предло: ний этого языка.

Для любого языка L(V) справедливо: L(V) с V*.

Язык L(V) включает в себя язык L'(V): L'(V)cL(V), если V aeL(V): aeL'( Множество цепочек языка L'(V) является подмножеством множества цепо языка L(V) (или эти множества совпадают). Очевидно, что оба языка доля строится на основе одного и того же алфавита.

Два языка L(V) и L'(V) совпадают (эквивалентны): L'(V) = L(V), если L'(V)cL и L(V)cL'(V); или, что то же самое: V aeL'(V): aeL(V) и V aeL'(V): aeL( Множества допустимых цепочек символов для эквивалентных языков доля быть равны.

Два языка L(V) и L'(V) почти эквивалентны: L'(V) = L(V), если L'(V)u{/ = L(V)u{A.}. Множества допустимых цепочек символов почти эквивалент языки могут различаться только на пустую цепочку символов.

 Способы задания языков

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

Язык задать можно тремя способами:

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

2.          Указанием способа порождения цепочек языка (заданием грамматики языка)

3.          Определением метода распознавания цепочек языка.

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

Например, запись Ц{0,1}) = {0nln, n > 0} задает язык над алфавитом V п {0,1}, со­держащий все последовательности с чередующимися символами 0 и 1, начинаю­щиеся с 0 и заканчивающиеся 1. Видно, что пустая цепочка символов в этот язык не входит. Если изменить условие в этом определении с п > 0 на п>0, то получим почти эквивалентный язык L'({0,1}), содержащий пустую цепочку.

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

Третий способ предусматривает построение некоторого логического устройства (распознавателя) — автомата, который на входе получает цепочку символов, а на выходе выдает ответ: принадлежит или нет эта цепочка заданному языку. На­пример, читая этот текст, вы сейчас в некотором роде выступаете в роли распо­знавателя (надеюсь, что ответ о принадлежности текста русскому языку будет положительным).

Синтаксис и семантика языка

Говоря о любом языке, можно выделить его синтаксис и семантику. Кроме того, трансляторы имеют дело также с лексическими конструкциями (лексемами), ко­торые задаются лексикой языка. Ниже даны определения для всех этих понятий.

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

Например, любой окончивший среднюю школу может сказать, что строка «3+2» является арифметическим выражением, а «3 2 +» — не является. Правда, не каж­дый задумается при этом, что он оперирует синтаксисом алгебры.

Семантика языка — это раздел языка, определяющий значение предложений языка. Семантика определяет «содержание языка» — задает значение для всех допустимых цепочек языка. Семантика для большинства языков определяется неформальными методами (отношения между знаками и тем, что они обозначают, изучаются семиотикой). Чисто формальные языки лишены какого-либо смыс/ Возвращаясь к примеру, приведенному выше, и используя семантику алгебр мы можем сказать, что строка «3 + 2» есть сумма чисел 3 и 2, а также то, ч «3 + 2 - 5» — это истинное выражение. Однако изложить любому ученику си таксис алгебры гораздо проще, чем ее семантику, хотя в данном случае семант ку как раз можно определить формально.

Лексика — это совокупность слов (словарный запас) языка. Слово или лексическая единица (лексема) языка — это конструкция, которая состоит из элементов алфавита языка и не содержит в себе других конструкций. Иначе говоря, лексическая единица может содержать только элементарные символы и не может с держать других лексических единиц.

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

Особенности языков программирования

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

□     определить множество допустимых символов языка;

□     определить множество правильных программ языка;

□     задать смысл для каждой правильной программы.

Только первые два вопроса полностью или частично удается решить с помоп

теории формальных языков.

Первый вопрос решается легко. Определяя алфавит языка, мы автоматиче

определяем множество допустимых символов. Для языков программирова:

алфавит — это чаще всего тот набор символов, которые можно ввести с юш

туры. Основу его составляет младшая половина таблицы международной кс

ровки символов (таблицы ASCII), к которой добавляются символы национ;

ных алфавитов.

Второй вопрос решается в теории формальных языков только частично. ,

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

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

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

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

□     изложить смысл программы, написанной на языке программирования, на дру­гом языке, более понятном тому, кому адресована программа;

□     использовать для проверки смысла некоторую «идеальную машину», которая предназначена для выполнения программ, написанных на данном языке.

Все, кто писал программы, так или иначе обязательно использовали первый под­ход. Комментарии в хорошей программе — это и есть изложение ее смысла. По­строение блок-схемы, а равно любое другое описание алгоритма программы — это тоже способ изложить смысл программы на другом языке (например, языке графических символов блок-схем алгоритмов, смысл которого в свою очередь, изложен в соответствующем ГОСТе). Да и документация к программе — тоже способ изложения ее смысла. Но все эти способы ориентированы на человека, которому они, конечно же, более понятны. Однако не существует пока универ­сального способа проверить, насколько описание соответствует программе.

Машина же понимает только один язык — язык машинных команд. Но изложить программу на языке машинных команд — задача слишком трудоемкая для чело­века, как раз для ее решения и создаются трансляторы.

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

Например, предложение в программе на языке Pascal вида: i:=0; while i=0 do i:=0; может быть легко оценено любой машиной как бессмысленное. Но если в задачу входит обеспечить взаимодействие с другой параллельно выполняемой программой или, например, просто проверить надежность и долговечность про­цессора или какой-то ячейки памяти, то это же предложение покажется уже не лишенным смысла.

Некоторые успехи в процессе проверки осмысленности программ достигнуты в рамках систем автоматизации разработки программного обеспечения (CASE-системы). Их подход основан на проектировании сверху вниз — от описания за­дачи на языке, понятном человеку, до перевода ее в операторы языка программирования. Но такой подход выходит за рамки возможностей трансляторов, поэто­му здесь рассматриваться не будет.

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

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

 

3. Определение грамматики. Форма Бэкуса-Наура. Принцип рекурсии в правилах грамматики. Другие способы задания грамматик.

Определение грамматики. Форма Бэкуса—Наура

Понятие о грамматике языка

Грамматика — это описание способа построения предложений некоторого язы­ка. Иными словами, грамматика — это математическая система, определяющая язык.

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

Правило (или продукция) — это упорядоченная пара цепочек символов (а,(3). В правилах очень важен порядок цепочек, поэтому их чаще записывают в виде х->(3 (или а::=Р). Такая запись читается как «а порождает р» или «(3 по опреде­лению есть а».

Грамматика языка программирования содержит правила двух типов: первые ^определяющие синтаксические конструкции языка) довольно легко поддают-;я формальному описанию; вторые (определяющие семантические ограничения ?зыка) обычно излагаются в неформальной форме. Поэтому любое описание ^или общепринятый стандарт) языка программирования обычно состоит из двух частей: вначале формально излагаются правила построения синтаксических кон-:трукций, а потом на естественном языке дается описание семантических пра­вил. Естественный язык понятен человеку, пользователю, который будет писать программы на языке программирования; для компилятора же семантические эграничения необходимо излагать в виде алгоритмов проверки правильности про­граммы (речь, как уже было сказано выше, не идет о смысле программ, а только лишь о семантических ограничениях на исходный текст). Такой проверкой в компиляторе занимается семантический анализатор — специально для этого раз­работанная часть компилятора.

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

Язык, заданный грамматикой G, обозначается как L(G).

Две грамматики G и G' называются эквивалентными, если они определяют один и тот же язык: L(G) = L(G'). Две грамматики G и G' называются почти эквива­лентными, если заданные ими языки различаются не более чем на пустую цепоч­ку символов: L(G) u {A,} = L(G') и {Ц.

Формальное определение грамматики. Форма Бэкуса—Наура

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

Формально грамматика G определяется как четверка G(VT,VN,P,S), где:

□     VT — множество терминальных символов;

□    VN — множество нетерминальных символов: VNnVT = 0;

Р — множество правил (продукций) грамматики вида а-»р, где aeV+, PeV*; Q S- целевой (начальный) символ грамматики SeVN. Множество V = VNuVT называют полным алфавитом грамматики G.

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

Эти два множества не пересекаются: каждый символ может быть либо терми­нальным, либо нетерминальным. Ни один символ в алфавите грамматики не может быть нетерминальным и терминальным одновременно. Целевой символ грамматики — это всегда нетерминальный символ.

Во множестве правил грамматики может быть несколько правил, имеющих оди­наковые правые части, вида: а->р(, ач>р2, ... а->рп. Тогда эти правила объединя­ют вместе и записывают в виде: a—>p1|p2|—lPn • Одной строке в такой записи соот­ветствует сразу  правил.

Такую форму записи правил грамматики называют формой Бэкуса—Наура. Форма Бэкуса—Наура предусматривает, как правило, также, что нетерминальные сим­волы берутся в угловые скобки: < >. Иногда знак «->» в правилах грамматики заменяют на знак «::=» (что характерно для старых монографий), но это всего лишь незначительные модификации формы записи, не влияющие на ее суть.

Ниже приведен пример грамматики для целых десятичных чисел со знаком:

G({0,1.2.3.4.5.6.7.8.9.-.+}.{<число>.<чс>,<цифра>},Р.<число>) Р:

<число> -» <чс> | +<чс> | -<чс>

<чс> -> <цифра> | <чс><цифра>

<цифра> ->0|1|2|3|4|5|6|7|8|9

Рассмотрим составляющие элементы грамматики G:

□     множество терминальных символов VT содержит двенадцать элементов: де­сять десятичных цифр и два знака;

□     множество нетерминальных символов VN содержит три элемента: символы <число>, <чс> и <цифра>;

□     множество правил содержит 15 правил, которые записаны в три строки (то есть имеются только три различных правых части правил);

□     целевым символом грамматики является символ <число>.

Следует отметить, что символ <чс> — это бессмысленное сочетание букв русско­го языка, но это обычный нетерминальный символ грамматики, такой же, как и два других. Названия нетерминальных символов не обязаны быть осмысленны­ми, это сделано просто для удобства понимания правил грамматики человеком. В принципе в любой грамматике можно полностью изменить имена всех нетер-минальных символов, не меняя при этом языка, заданного грамматикой, — точно также, например, в программе на языке Pascal можно изменить имена идентифи­каторов, и при этом не изменится смысл программы.

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

Бот, например, та же самая грамматика для целых десятичных чисел со знаком, в которой нетерминальные символы обозначены большими латинскими буквами (далее это будет часто применяться в примерах):

G'({0.1.2.3.4.5.6.7.8.9,-.+}.{S,T.F}.P,S)

Р:

S -» Т | +Т |  -Т

Т -> F | TF

F-»0|l|2|3|4|5|6|7|8|9

Здесь изменилось только множество нетерминальных символов. Теперь VN = = {S,T,F}. Язык, заданный грамматикой, не изменился — грамматики G и G' эк­вивалентны.

 

Принцип рекурсии в правилах грамматики

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

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

В рассмотренной выше грамматике G непосредственная рекурсия присутствует в правиле: <чс>-»<чс><цифра>, а в эквивалентной ей грамматике G' — в правиле: T-»TF.

Чтобы рекурсия не была бесконечной, для участвующего в ней нетерминального символа грамматики должны существовать также и другие правила, которые оп­ределяют его, минуя самого себя, и позволяют избежать бесконечного рекурсив­ного определения (в противном случае этот символ в грамматике был бы просто не нужен). Такими правилами являются <чс>-»<цифра> — в грамматике G и T-»F — в грамматике G'.

□     В теории формальных языков более ничего сказать о рекурсии нельзя. Но, чтобы полнее понять смысл рекурсии, можно прибегнуть к семантике языка — в рас­смотренном выше примере это язык целых десятичных чисел со знаком. Рас­смотрим его смысл.

Если попытаться дать определение тому, что же является числом, то начать мож­но с того, что любая цифра сама по себе есть число. Далее можно заметить, что любые две цифры — это тоже число, затем — три цифры и т. д. Если строить определение числа таким методом, то оно никогда не будет закончено (в матема­тике разрядность числа ничем не ограничена). Однако можно заметить, что каж­дый раз, порождая новое число, мы просто дописываем цифру справа (посколь­ку привыкли писать слева направо) к уже написанному ряду цифр. А этот ряд цифр, начиная от одной цифры, тоже в свою очередь является числом. Тогда определение для понятия «число» можно построить таким образом: «число — это любая цифра, либо другое число, к которому справа дописана любая цифра». Именно это и составляет основу правил грамматик G и G' и отражено во второй строке правил в правилах <чс>—><цифра> j <чс><цифра> и T-»F|TF. Другие правила в этих грамматиках позволяют добавить к числу знак (первая строка правил) и дают определение понятию «цифра» (третья строка правил). Они элементарны и не требуют пояснений.

Принцип рекурсии (иногда его называют «принцип итерации», что не меняет сути) — важное понятие в представлении о формальных грамматиках. Так или иначе, явно или неявно рекурсия всегда присутствует в грамматиках любых ре­альных языков программирования. Именно она позволяет строить бесконечное множество цепочек языка, и говорить об их порождении невозможно без пони­мания принципа рекурсии. Как правило, в грамматике реального языка програм­мирования содержится не одно, а целое множество правил, построенных с помо­щью рекурсии.

Другие способы задания грамматик

Форма Бэкуса—Наура — удобный с формальной точки зрения, но не всегда дос­тупный для понимания способ записи формальных грамматик. Рекурсивные определения хороши для формального анализа цепочек языка, но не удобны с точки зрения человека. Например, то, что правила <чс>—><цифра> | <чс><цифра> отражают возможность для построения числа дописывать справа любое число цифр, начиная от одной, неочевидно и требует дополнительного пояснения.

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

Далее рассмотрим два наиболее распространенных из этих способов: запись пра­вил грамматик с использованием метасимволов и запись правил грамматик в графическом виде.

Запись правил грамматик

с использованием метасимволов

Запись правил грамматик с использованием метасимволов предполагает, что в строке правила грамматики могут встречаться специальные символы — мега-символы, — которые имеют особый смысл и трактуются специальным образом. В качестве таких метасимволов чаще всего используются следующие символы:  (круглые скобки),  (квадратные скобки),  (фигурные скобки),  (запя­тая) и "" (кавычки).

Эти метасимволы имеют следующий смысл:

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

□     квадратные скобки означают, что указанная в них цепочка может встречать­ся, а может и не встречаться в данном месте правила грамматики (то есть мо­жет быть в нем один раз или ни одного раза);

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

□     запятая служит для того, чтобы разделять цепочки символов внутри круглых скобок;

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

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

<число> -» [(+.-)]<цифра>{<цифра>}

<цифра> ->0|1|2|3|4|5|6|7|8|9

Вторая строка правил не нуждается в комментариях, а первое правило читается так: «число есть цепочка символов, которая может начинаться с символов + или - должна содержать дальше одну цифру, за которой может следовать последова­тельность из любого количества цифр». В отличие от формы Бэкуса—Наура, в форме записи с помощью метасимволов, как видно, во-первых, убран из грам­матики малопонятный нетерминальный символ <чс>, а во-вторых — удалось пол­ностью исключить рекурсию. Грамматика в итоге стала более понятной.

Форма записи правил с использованием метасимволов — это удобный и понят­ный способ представления правил грамматик. Она во многих случаях позволяет полностью избавиться от рекурсии, заменив ее символом итерации  (фигур­ные скобки). Как будет понятно из дальнейшего материала, эта форма наиболее употребительна для одного из типов грамматик — регулярных грамматик.

Запись правил грамматик в графическом виде

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

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

□     точка входа (на диаграмме никак не обозначена, из нее просто начинается входная дуга графа);

□     нетерминальный символ (на диаграмме обозначается прямоугольником, в ко­торый вписано обозначение символа);

□     цепочка терминальных символов (на диаграмме обозначается овалом, кругом или прямоугольником с закругленными краями, внутрь которого вписана це­почка);

□     узловая точка (на диаграмме обозначается жирной точкой или закрашенным кружком);

□     точка выхода (никак не обозначена, в нее просто входит выходная дуга графа).

Каждая диаграмма имеет только одну точку входа и одну точку выхода, но сколь­ко угодно вершин других трех типов. Вершины соединяются между собой на­правленными дугами графа (линиями со стрелками). Из входной точки дуги могут только выходить, а во входную точку — только входить. В остальные вер­шины дуги могут как входить, так и выходить (в правильно построенной грам­матике каждая вершина должна иметь как минимум один вход и как минимум один выход).

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ztjz^^=-=^~l~

■©•

Цифра

t^m

-о

Число:

 

 

Рис. 9.1. Графическое представление грамматики целых десятичных чисел со знаком: вверху — для понятия «число»; внизу — для понятия «цифра»

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

Классификация языков и грамматик

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

Для компиляторов языки также можно разделить на простые и сложные, но в данном случае существуют жесткие критерии для этого разделения. Как будет показано далее, от того, к какому типу относится тот или иной язык програмирования, зависит сложность распознавателя для этого языка. Чем сложнее язык, тем выше вычислительные затраты компилятора на анализ цепочек исходной программы, написанной на этом языке, а следовательно, сложнее сам компиля­тор и его структура. Для некоторых типов языков в принципе невозможно по­строить компилятор, который бы анализировал исходные тексты на этих языках за приемлемое время на основе ограниченных вычислительных ресурсов (имен­но поэтому до сих пор невозможно создавать программы на естественных язы­ках/например на русском или английском).

Классификация грамматик.

Четыре типа грамматик по Хомскому

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

Тип 0: грамматики с фразовой структурой

На структуру их правил не накладывается никаких ограничений: для граммати­ки вида G(VT,VN,P,S), V » VNuVT правила имеют вид: а-»р, где aeV\ (3eV*. Это самый общий тип грамматик. В него подпадают все без исключения фор­мальные грамматики, но часть из них, к общей радости, может быть также отне­сена и к другим классификационным типам. Дело в том, что грамматики, которые относятся только к типу 0 и не могут быть отнесены к другим типам, являются самыми сложными по структуре. Практического применения грамматики, относящиеся только к типу 0, не имеют.

Тип 1: контекстно-зависимые (КЗ) и неукорачивающие грамматики

В этот тип входят два основных класса грамматик.

Контекстно-зависимые грамматики G(VT,VN,P,S), V = VNuVT имеют правила вида: сцАаг-юцрсхг, где а^еУ, AeVN, PeV+.

Неукорачивающие грамматики G(VT,VN,P,S), V = VNu VT имеют правила вида: а->Р, где a,PeV+, ]p|>|a|.

Структура правил КЗ-грамматик такова, что при построении предложений за­данного ими языка один и тот же нетерминальный символ может быть заменен на ту или иную цепочку символов в зависимости от того контекста, в котором он встречается. Именно поэтому эти грамматики называют «контекстно-зависимы­ми». Цепочки а) и а2 в правилах грамматики обозначают контекст (щ — левый контекст, а а2 — правый контекст), в общем случае любая из них (или даже обе) Может быть пустой. Говоря иными словами, значение одного и того же символа может быть различным в зависимости от того, в каком контексте он встречаетсяНеукорачиваювдие грамматики имеют такую структуру правил, что при построе­нии предложений языка, заданного грамматикой, любая цепочка символов мо­жет быть заменена на цепочку символов не меньшей длины. Отсюда и название «неукорачивающие».

Доказано, что эти два класса грамматик эквивалентны. Это значит, что для лю­бого языка, заданного контекстно-зависимой грамматикой, можно построить неукорачивающую грамматику, которая будет задавать эквивалентный язык, и наоборот: для любого языка, заданного неукорачивающей грамматикой, мож­но построить контекстно-зависимую грамматику, которая будет задавать эквива­лентный язык.

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

Тип 2: контекстно-свободные (КС) грамматики

Контекстно-свободные (КС) грамматики G(VT,VN,P,S), V = VNuVT имеют правила вида: А-»р\ где AeVN, |3eV+. Такие грамматики также иногда называют неукорачивающими контекстно-свободными (НКС) грамматиками (видно, что в правой части правила у них должен всегда стоять как минимум один символ).

Существует также почти эквивалентный им класс грамматик — укорачивающие контекстно-свободные (УКС) грамматики G(VT,VN,P,S), V = VNuVT, правила которых могут иметь вид: А->р\ где AeVN, PeV*.

Разница между этими двумя классами грамматик заключается лишь в том, что в УКС-грамматиках в правой части правил может присутствовать пустая це­почка (X), а в НКС-грамматиках — нет. Отсюда ясно, что язык, заданный НКС-грамматикой, не может содержать пустой цепочки. Доказано, что эти два класса грамматик почти эквивалентны. В дальнейшем, когда речь будет идти о КС-грамматиках, уже не будет уточняться, какой класс грамматики (УКС или НКС) имеется в виду, если возможность наличия в языке пустой цепочки не имеет принципиального значения.

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

Внутри типа КС-грамматик кроме классов НКС и УКС выделяют еще целое множество различных классов грамматик, и все они относятся к типу 2. Далее, когда КС-грамматики и КС-языки будут рассматриваться более подробно, на не­которые из этих классов грамматик и их характерные особенности будет обраще­но особое внимание.

Тип 3: регулярные грамматики

К типу регулярных относятся два эквивалентных класса грамматик: леволиней­ные и праволинейные.

Леволинейные грамматики G(VT,VN,P,S), V = VNuVT могут иметь правила двух видов: А-»Ву или А->у, где A,BeVN, yeVT.

В свою очередь, праволинейные грамматики G(VT,VN,P,S), V = VNuVT могут иметь правила тоже двух видов: А~-»уВ или А-»у, где A.BeVN, yeVT*.

Эти два класса грамматик эквивалентны и относятся к типу регулярных грам­матик.

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

Типы грамматик соотносятся между собой особым образом. Из определения типов 2 и 3 видно, что любая регулярная грамматика является КС-грамматикой, но не наоборот. Также очевидно, что любая грамматика может быть отнесена и к типу 0, поскольку он не накладывает никаких ограничений на правила. В то же время существуют укорачивающие КС-грамматики (тип 2), которые не являют­ся ни контекстно-зависимыми, ни неукорачивающими (тип 1), поскольку могут содержать правила вида «А-»Ъ>, недопустимые в типе 1. В целом можно сказать, что сложность грамматики обратно пропорциональна тому максимально воз­можному номеру типа, к которому может быть отнесена грамматика. Граммати­ки, которые относятся только к типу 0, являются самыми сложными, а грамма­тики, которые можно отнести к типу 3 — самыми простыми.

Классификация языков

Языки классифицируются в соответствии с типами грамматик, с помощью кото­рых они заданы. Причем, поскольку один и тот же язык в общем случае может быть задан сколь угодно большим количеством грамматик, которые могут отно­ситься к различным классификационным типам, то для классификации самого языка среди всех его грамматик всегда выбирается грамматика с максимально возможным классификационным типом. Например, если язык L может быть за­дан грамматиками Gt и G2, относящимися к типу  (контекстно - зависимые), грамматикой G3, относящейся к типу 2 (контекстно-свободные), и грамматикой G4, относящейся к типу 3 (регулярные), то сам язык должен быть отнесен к типу 3 и является регулярным языком.

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

Сложность языка убывает с возрастанием номера классификационного типа языка. Самыми сложными являются языки типа 0, самыми простыми — языки типа 3.

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

Тип О: языки с фразовой структурой

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

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

Далее языки с фразовой структурой рассматриваться не будут.

Тип 1: контекстно-зависимые (КЗ) языки

Тип 1 — второй по сложности тип языков. В общем случае время на распознава­ние предложений языка, относящегося к типу 1, экспоненциально зависит от длины исходной цепочки символов.

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

В компиляторах КЗ-языки не используются, поскольку языки программирова­ния имеют более простую структуру, поэтому здесь они подробно не рассматри­ваются.

Тип 2: контекстно-свободные (КС) языки

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

В общем случае время на распознавание предложений языка, относящегося к типу 1, полиномиально зависит от длины исходной цепочки символов (в зависи­мости от класса языка это либо кубическая, либо квадратичная зависимость).

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

КС-языки подробно рассматриваются в главе «Контекстно-свободные языки» данного учебного пособия.

Тип 3: регулярные языки

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

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

Регулярные языки — очень удобное средство. Для работы с ними можно исполь­зовать регулярные множества и выражения, конечные автоматы. Регулярные языки подробно рассматриваются в следующей главе учебного пособия.

Примеры классификации языков и грамматик

Классификация языков идет от простого к сложному. Если мы имеем дело с ре­гулярным языком, то можно утверждать, что он также является и контекстно-свободным, и контекстно-зависимым, и даже языком с фразовой структурой. В то же время известно, что существуют КС-языки, которые не являются регу­лярными, и существуют КЗ-языки, которые не являются ни регулярными, ни контекстно-свободными.

Далее приводятся примеры некоторых языков указанных типов.

Рассмотрим в качестве первого примера ту же грамматику для целых десятич­ных чисел со знаком G({0,1,2,3,4>5,6,7,8,9,-I+},{S,T,F},P.S):

Р:

S -> Т | +Т |   -Т

Т -> F  | TF

F->0|1|2|3|4|5|6|7|8|9

По структуре своих правил данная грамматика G относится к контекстно-сво­бодным грамматикам (тип 2). Конечно, ее можно отнести и к типу 0, и к типу 1, но максимально возможным является именно тип 2, поскольку к типу 3 эту грамматику отнести никак нельзя: строка Т—»F | TF содержит правило Т—»TF, которое недопустимо для типа 3, и, хотя все остальные правила этому типу соот­ветствует, одного несоответствия достаточно.

Для того же самого языка (целых десятичных чисел со знаком) можно построить и другую грамматику G'({0,1,2.3,4,5,б,7,8,9,-,+}.{S,T},P.S):

Р:

S -> Т | +Т | -Т

Т -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | ОТ | IT | 2Т | ЗТ | 4Т | 5Т | 6Т | 7Т | 8Т | 9Т

По структуре своих правил грамматика G' является праволинейной и может быть отнесена к регулярным грамматикам (тип 3).

Для этого же языка можно построить эквивалентную леволинейную грамматику (тип 3) G"({0,l>2,3,4,5.6,7.8,9>-,+},{SJ},P,S):

Р:

Т^+ | - | X

S -> ТО | Т1 | Т2 | ТЗ | Т4 | Т5 | Т6 | Т7 | Т8 | Т9 | SO | S1 | S2 | S3 | S4 | S5 | S6 | S7 | S8 | S9

Следовательно, язык целых десятичных чисел со знаком, заданный грамматика­ми G, G' и G", относится к регулярным языкам (тип 3).

В качестве второго примера возьмем грамматику G2({0,1},{A,S},P>S) с правила­ми Р:

S -> 0А1 ОА -» 00А1 А -> X

Эта грамматика относится к типу 0. Она определяет язык, множество предложе­ний которого можно было бы записать так: L(G2) = {0nln |'n > 0}.

Для этого же языка можно построить также контекстно-зависимую грамматику G2'({0.1},{A,S},P',S) с правилами Р":

S -t 0A1 | 01 ОА -> 00А1  |  001

Однако для того же самого языка можно использовать и контекстно-свободную грамматику G2"({0,1},{S},P",S) с правилами Р":

S —> 0S1 | 01

Следовательно, язык L = {0nln | n > 0} является контекстно-свободным (тип 2).

В третьем примере рассмотрим грамматику G3({a,b,c},{B,C,D,S},P,S) с правила­ми Р:

S -» BD

В -> аВЬС | ab СЬ -> ЬС CD -> Dc bDc -> bcc abD -» abc

Эта грамматика относится к типу 1. Очевидно, что она является неукорачиваю-щей. Она определяет язык, множество предложений которого можно было бы за­писать так: L(G3) = {anbncn | n > 0}. Известно, что этот язык не является КС-язы­ком, поэтому для него нельзя построить грамматики типов 2 или 3. Язык L - {anbncn | п > 0} является контекстно-зависимым (тип 1). Конечно, для произвольного языка, заданного некоторой грамматикой, в общем случае довольно сложно так легко определить его тип. Не всегда можно так просто построить грамматику максимально возможного типа для произвольного языка. К тому же при строгом определении типа требуется еще доказать, что две грамматики (первоначально имеющаяся и вновь построенная) эквивалентны, а также то, что не существует для того же языка грамматики с большим по номе­ру типом. Это нетривиальная задача, которую не так легко решить.

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

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

Цепочки вывода. Сентенциальная форма

Вывод. Цепочки вывода

Выводом называется процесс порождения предложения языка на основе правил определяющей язык грамматики. Чтобы дать формальное определение процессу вывода, необходимо ввести еще несколько дополнительных понятий. Цепочка Р = 5ty52 называется непосредственно выводимой из цепочки а = 5!(о52 в грамматике G(VT,VN,P,S), V = VTuVN, 8Ь у, 52 е V", со е V+, если в граммати­ке G существует правило: ш-»у е Р. Непосредственная выводимость цепочки Р из цепочки а обозначается так: а=>р. Иными словами, цепочка р выводима из цепочки а в том случае, если можно взять несколько символов в цепочке а, заме­нить их на другие символы согласно некоторому правилу грамматики и полу­чить цепочку р. В формальном определении непосредственной выводимости любая из цепочек 5t или 52 (а равно и обе эти цепочки) может быть пустой. В предельном случае вся цепочка а может быть заменена на цепочку р, тогда в грамматике G должно существовать правило: а-»Р е Р.

Цепочка Р называется выводимой из цепочки а (обозначается а=>*Р) в том слу­чае, если выполняется одно из двух условий:

□     р непосредственно выводима из а (а=>Р);

□     3 у, такая, что: у выводима из а и р непосредственно выводима из у (а=>*у и у=>Р).

Это рекурсивное определение выводимости цепочки. Суть его заключается в том, что цепочка р выводима из цепочки а, если а=>р или же если можно построить последовательность непосредственно выводимых цепочек от а к р следующеговида: a^Yi^-^Yi^-^Yn^P, п>1. В этой последовательности каждая последую­щая цепочка у{ непосредственно выводима из предыдущей цепочки ум-Такая последовательность непосредственно выводимых цепочек называется вы­водом или цепочкой вывода. Каждый переход от одной непосредственно выводи­мой цепочки к следующей в цепочке вывода называется шагом вывода. Очевидно, что шагов вывода в цепочке вывода всегда на один больше, чем промежуточных цепочек. Если цепочка р непосредственно выводима из цепочки а: а=>р, то име­ется всего один шаг вывода.

Если цепочка вывода из а к р содержит одну или более промежуточных цепочек (два или более шагов вывода), то она имеет специальное обозначение а=>+Р (го­ворят, что цепочка р нетривиально выводима из цепочки а). Если количество шагов вывода известно, то его можно указать непосредственно у знака выводи­мости цепочек. Например, запись а=>4Р означает, что цепочка Р выводится из це­почки а за 4 шага вывода1.

Возьмем в качестве примера ту же грамматику для целых десятичных чисел со знаком G({0.1.2>3,4,5.6,7,8.9.-.+}.{S.T.F},P,S):

Р:

S -> Т | +Т |  -Т Т -> F  |  TF

F -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 Построим в ней несколько произвольных цепочек вывода:

1.     S => -Т => -TF => -TFF => -FFF => -4FF => -47F => -479

2.     S ==> Т => TF => Т8 => F8 => 18

3.Т => TF => ТО => TF0 => Т50 => F50 => 350

4.TFT => TFFT => TFFF => FFFF => 1FFF => 1FF4 => 10F4 => 1004

5.         F=>5

Получили следующие выводы:

1.  S => * -479 или S => + -479 или S => 7 -479

2.         S => * 18 или S => + 18 или S => 5 18

3.         Т => * 350 или Т => + 350 или Т => 6 350

4.         TFT => * 1004 или TFT => + 1004 или TFT => 7 1004

5.         F => * 5 или F =>' 5 (утверждение F => + 5 неверно!)

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

Возьмем в качестве второго примера грамматику G3 ({a,b,c},{B,C,D,S}.P,S) с пра­вилами Р, которая уже рассматривалась выше:

1 В литературе встречается также обозначение а=>°(3, которое означает, что цепочка а вы­водима из цепочки р за 0 шагов — иными словами, в таком случае эти цепочки равны: а = р. Подразумевается, что обозначение вывода а=>*р допускает и такое толкование — включает в себя вариант а=> р. S -» BD

В -> аВЬС | ab СЬ -> ЬС CD -» Dc bDc -* bcc abD -» abc

Как было сказано ранее, она задает язык L(G3) = {0nln | п > 0}. Рассмотрим npi мер вывода предложения «aaaabbbbcccc » языка L(G3) на основе грамматики G

S => BD => aBbCD => aaBbCbCD => aaaBbCbCbCD => aaaabbCbCbCD => aaaabbbCCbCD = aaaabbbCbCCD => aaaabbbbCCCD => aaaabbbbCCDc => aaaabbbbCDcc => aaaabbbbDccc s aaaabbbbcccc. Тогда для грамматики G3 получаем вывод: S => * aaaabbbbcccc.

Иногда, чтобы пояснить ход вывода, над стрелкой, обозначающей каждый ш; вывода, пишут обозначение того правила грамматики, на основе которого сдела этот шаг (для этой цели правила грамматики проще всего просто пронумеровать! в порядке их следования). Грамматика, рассмотренная в приведенных здесь npi мерах, содержит всего 15 правил, и на каждом шаге в цепочках вывода можг понять, на основании какого правила сделан этот шаг (читатели могут легко сделать это самостоятельно), но в более сложных случаях пояснения к шагам вывода с указанием номеров правил грамматики могут быть весьма полезными.

Сентенциальная форма грамматики. Язык, заданный грамматикой

Вывод называется законченным, если на основе цепочки р\ полученной в резул: тате вывода, нельзя больше сделать ни одного шага вывода. Иначе говоря, вывс называется законченным, если цепочка р, полученная в результате вывода, пу тая или содержит только терминальные символы грамматики G(VT,VN,P,S PeVT*. Цепочка р, полученная в результате законченного вывода, называете конечной цепочкой вывода.

В рассмотренном выше примере все построенные выводы являются закончеными, а, например, вывод S =>* -4FF (из первой цепочки в примере) будет незако] ченным.

Цепочка символов asV* называется сентенциальной формой грамматики G(V VN,P,S), V = VTuVN, если она выводима из целевого символа грамматики S =>* а. Если цепочка ae VT* получена в результате законченного вывода, то oi называется конечной сентенциальной формой.

Из рассмотренного выше примера можно заключить, что цепочки в символе «—479>> и «18» являются конечными сентенциальными формами грамматики цель Десятичных чисел со знаком, так как существуют выводы S =>* -479 и S =>* 1 (примеры 1 и 2). Цепочка F8 из вывода 2, например, тоже является сентенциальнс формой, поскольку справедливо S =>* F8, но она не является конечной цепочке вывода. В то же время в выводах примеров 3—5 явно не присутствуют сентенц: эльные формы. На самом деле цепочки «350», «1004» и «5» являются конечнг Ми сентенциальными формами. Чтобы доказать это, необходимо просто построить другие цепочки вывода (например,  для цепочки «5» строим: S => Т => F => и получаем S => * 5). А вот цепочка «TFT» (пример 4) не выводима из целевого символа грамматики S, а потому сентенциальной формой не является. Язык L, заданный грамматикой G(VT,VN,P,S), — это множество всех конечных сентенциальных форм грамматики G. Язык L, заданный грамматикой G, обозна­чается как L(G). Очевидно, что алфавитом такого языка L(G ) будет множество терминальных символов грамматики VT, поскольку все конечные сентенциаль­ные формы грамматики — это цепочки над алфавитом VT. Следует помнить, что две грамматики G(VT,VN,P,S) и G'(VT',VN',P',S') называ­ются эквивалентными, если эквивалентны заданные ими языки: L(G) = L(G'). Очевидно, что эквивалентные грамматики должны иметь, по крайней мере, пере­секающиеся множества терминальных символов VTnVT * 0 (как правило, эти множества даже совпадают VT = VI"), а вот множества нетерминальных симво­лов, правила грамматики и целевой символ у них могут кардинально отличаться.

Левосторонний и правосторонний выводы

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

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

Если рассмотреть цепочки вывода из того же примера, то в нем выводы 1 и 5 яв­ляются левосторонними, выводы 2, 3 и 5 — правосторонними (вывод 5 одновре­менно является и лево- и правосторонним), а вот вывод 4 не является ни лево­сторонним, ни правосторонним.

Для грамматик типов 2 и 3 (КС-грамматик и регулярных грамматик) для любой сентенциальной формы всегда можно построить левосторонний или правосто­ронний выводы. Для грамматик других типов это не всегда возможно, так как по структуре их правил не всегда можно выполнить замену крайнего левого или крайнего правого нетерминального символа в цепочке.

Рассмотренный выше вывод S => * aaaabbbbcccc для грамматики G3, задающей язык L(G3) = {Onln|n > 0}, не является ни левосторонним, ни правосторонним. Грамматика относится к типу 1, и в данном случае для нее нельзя построить та­кой вывод, на каждом шаге которого только один нетерминальный символ заме­нялся бы на цепочку символов.

 

Дерево вывода. Методы построения дерева вывода

Деревом вывода грамматики G(VT,VN,P,S) называется дерево (граф), которое соответствует некоторой цепочке вывода и удовлетворяет следующим условиям:

□     каждая вершина дерева обозначается символом грамматики Ae(VT uVN);

□     корнем дерева является вершина, обозначенная целевым символом граммати­ки — S;

□     листьями дерева (концевыми вершинами) являются вершины, обозначенные терминальными символами грамматики или символом пустой цепочки X;

□     если некоторый узел дерева обозначен символом AeVN, а связанные с ним узлы — символами Ь^.-.^! п > 0, Vn > i > 0: bje(VTuVNu{A.}), то в грамма­тике G(VT,VN,P,S) существует правило А-^Ь^Ьг     bn e Р.

Из определения видно, что по структуре правил дерево вывода в указанном виде всегда можно построить только для грамматик типов 2 и 3 (контекстно-свобод­ных и регулярных). Для грамматик других типов дерево вывода в таком виде можно построить не всегда (либо же оно будет иметь несколько иной вид).

На основе рассмотренного выше примера построим деревья вывода для цепочек вывода 1 и 2. Эти деревья приведены на рис. 9.2.

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

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

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

Построение дерева вывода снизу вверх начинается с листьев дерева. В качестве листьев выбираются терминальные символы конечной цепочки вывода, которые на первом шаге построения образуют последний уровень (слой) дерева. Построе­ние дерева идет по слоям. На втором шаге построения в грамматике выбирается правило, правая часть которого соответствует крайним символам в слое дерева (крайним правым символам при правостороннем выводе и крайним левым — при левостороннем). Выбранные вершины слоя соединяются с новой вершиной, которая выбирается из левой части правила. Новая вершина попадает в слой де­рева вместо выбранных вершин. Построение дерева закончено, если достигнута корневая вершина (обозначенная целевым символом), а иначе надо вернуться ко второму шагу и повторить его над полученным слоем дерева. Поскольку все известные языки программирования имеют нотацию записи «сле­ва — направо», компилятор также всегда читает входную программу слева на­право (и сверху вниз, если программа разбита на несколько строк). Поэтому для построения дерева вывода методом «сверху вниз», как правило, используется ле­восторонний вывод, а для построения «снизу вверх» — правосторонний вывод. На эту особенность компиляторов стоит обратить внимание. Нотация чтения программ «слева направо» влияет не только на порядок разбора программы компилятором (для пользователя это, как правило, не имеет значения), но и на порядок выполнения операций — при отсутствии скобок большинство равно­правных операций выполняются в порядке слева направо, а это уже имеет суще­ственное значение.

Проблемы однозначности

и эквивалентности грамматик

Однозначные и неоднозначные грамматики

Рассмотрим некоторую грамматику G ({+,-.*,/,(,). а, b}, {S}, Р, S):

Р: S -> S+S | S-S | S*S | S/S |  (S)  | а | b Видно, что представленная грамматика определяет язык арифметических выра­жений с четырьмя основными операциями (сложение, вычитание, умножение и деление) и скобками над операндами а и Ь. Примерами предложений этого язы­ка могут служить: a*b+a, a*(a+b), а*Ь+а*а и т. д.

Возьмем цепочку а*Ь+а и построим для нее левосторонний вывод. Получится два варианта:

S => S+S => S*S+S о a*S+S => a*b+S => a*b+a S => S*S => a*S => a*S+S => a*b+S => a*b+a Каждому из этих вариантов будет соответствовать свое дерево вывода. Два вари­анта дерева вывода для цепочки «а*Ь+а» приведены на рис. 9.3. С точки зрения формального языка, заданного грамматикой, не имеет значения, какая цепочка вывода и какое дерево вывода из возможных вариантов будут построены. Однако для языков программирования, которые не являются чисто

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

Рис. 9.3. Два варианта дерева цепочки «а*Ь+а» вывода для неоднозначной грамматики арифметических выражений

Такая ситуация называется неоднозначностью в грамматике. Естественно, для построения компиляторов и языков программирования нельзя использовать грам­матики, допускающие неоднозначности. Дадим более точное определение неод­нозначной грамматики.

Грамматика называется однозначной, если для каждой цепочки символов языка, заданного этой грамматикой, можно построить единственный левосторонний (и единственный правосторонний) вывод. Или, что то же самое: грамматика называется однозначной, если для каждой цепочки символов языка, заданного этой грамматикой, существует единственное дерево вывода. В противном случае грамматика называется неоднозначной.

Рассмотренная в примере грамматика арифметических выражений, очевидно, является неоднозначной.

Эквивалентность и преобразование грамматик

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

Q  как проверить, является ли данная грамматика однозначной? □ если заданная грамматика является неоднозначной, то как преобразовать ее к однозначному виду?

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

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

Если грамматика все же является неоднозначной, то необходимо преобразовать ее в однозначный вид. Иногда это возможно. Например, для рассмотренной выше неоднозначной грамматики арифметических выражений над операциями а и b существует эквивалентная ей однозначная грамматика следующего вида G'({+,-.*,/,(.),a,b}.{S,T,E},P\S):

Р':

S _> S+T | S-T | Т

Т -> Т*Е  | Т/Е  |  Е

Е -> (S)   |  а  | b В этой грамматике для рассмотренной выше цепочки символов языка а*Ь+а воз­можен только один левосторонний вывод:

S => S+T => Т+Т => Т*Е+Т Ь Е*Е+Т =* а*Е+Т => а*Ь+Т => a*b+E => a*b+a Этому выводу соответствует единственно возможное дерево вывода. Оно приве­дено на рис. 9.4. Видно, что хотя цепочка вывода несколько удлинилась, но при­оритет операций в данном случае единственно возможный и соответствует их порядку в арифметике.

Рис. 9.4. Дерево вывода для однозначной грамматики арифметических выражений

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

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

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

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

В общем случае вопрос об алгоритмической неразрешимости проблем однознач­
ности и эквивалентности грамматик сводится к вопросу об алгоритмической
неразрешимости проблемы, известной как «проблема соответствий Поста». Про­
блема соответствий Поста формулируется следующим образом: имеется задан­
ное множество пар непустых цепочек над алфавитом V: {(ctj,Pi)> (а2,р2)............. (ап>Рп)}>

п > 0, Vn > i > 0: oippieV*; необходимо проверить, существует ли среди них такая последовательность пар цепочек: (cq.Pi), (a2,P2),..., (am,pm), m > 0 (необязательно различных), что a^.-.a,,, = p1p2...prn- Доказано, что не существует алгоритма, ко­торый бы за конечное число шагов мог дать ответ на этот вопрос, хотя на первый взгляд постановка задачи кажется совсем несложной.

То, что проблема не решается в общем виде, совсем не значит, что ее нельзя ре­шить в каждом конкретном случае. Например, для алфавита V - {а,Ь} можно по­строить множество пар цепочек {(abbb.b). (a.aab), (ba.b)} и найти одно из реше­ний: (a,aab),(a,aab),(ba,b),(abbb,b) - видно, что (a)(a)(ba)(abbb) = (aabKaab) (b)(b). А для множества пар цепочек {(ab,aba),(aba,baa),(baa,aa)} очевидно, что решения не существует.

Точно так же неразрешимость проблем эквивалентности и однозначности грам­матик в общем случае совсем не означает, что они не разрешимы вообще. Для не­которых частных случаев — например, для определенных типов и классов грам­матик (в частности, для регулярных грамматик) — эти проблемы решены. Также их иногда удается решить полностью или частично в каждом конкретном случае, и для конкретной заданной грамматики доказать, является ли она однозначной или нет. Например, приведенная выше грамматика G' для арифметических вы­ражений над операндами а и b относится к классу грамматик операторного пред­шествования из типа КС-грамматик. На основе этой грамматики возможно по­строить распознаватель в виде детерминированного расширенного МП-автомата, а потому можно утверждать, что она является однозначной (см. раздел «Восхо­дящие распознаватели КС-языков без возвратов», глава 12).

Правила, задающие неоднозначность в грамматиках

В общем виде невозможно проверить, является ли заданная грамматика одно­значной или нет. Однако для КС-грамматик существуют определенного вида правила, по наличию которых в множестве правил грамматики G(VT,VN,P,S) можно утверждать, что она является неоднозначной. Эти правила имеют сле­дующий вид:

1.        А -» АА | а,

2.        А -» АаА | (3,

3.        А -> аА | Ар | у,

4.        А -> аА | аАрА | у,

здесь AeVN; a,p,ye(VNuVT)*. Если в заданной грамматике встречается хотя бы одно правило подобного вида (любого из приведенных вариантов), то доказано, что такая грамматика точно будет неоднозначной. Однако если подобных правил во всем множестве правил грамматики нет, это совсем не означает, что грамматика является однозначной. Такая грамматика может быть однозначной, а может и не быть. То есть отсутст­вие правил указанного вида (всех вариантов) — это необходимое, но не достаточ­ное условие однозначности грамматики.

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

В рассмотренном выше примере грамматики арифметических выражений с опе­рандами а и b — G({+,-,*,/,(.),а,b},{S},P,S) — во множестве правил Р: S -> S+S | S-S | S*S | S/S | (S) | а | b встречаются правила 2 типа. Поэтому данная грам­матика является неоднозначной, что и было показано выше.

Распознаватели. Задача разбора

Общая схема распознавателя

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

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

В общем виде распознаватель можно отобразить в виде условной схемы, пред­ставленной на рис. 9.5.

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

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

По видам устройства управления распознаватели бывают детерминированные и недетерминированные.

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

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

По видам внешней памяти распознаватели бывают следующих типов:

□     распознаватели без внешней памяти;

□     распознаватели с ограниченной внешней памятью;

□     распознаватели с неограниченной внешней памятью.

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

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

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

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

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

Классификация распознавателей по типам языков

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

Выше было определено четыре основных типа языков. Доказано, что для каждого из этих типов языков существует свой тип распознавателя с определенным со­ставом компонентов и, следовательно, с заданной сложностью алгоритма работы. Для языков с фразовой структурой (тип 0) Необходим распознаватель, равномощной машине Тьюринга — недетерминированный двусторонний автомат, имею­щий неограниченную внешнюю память. Поэтому для языков данного типа нель­зя гарантировать, что за ограниченное время на ограниченных вычислительных ресурсах распознаватель завершит работу и примет решение о том, принадлежит или не принадлежит входная цепочка заданному языку. Отсюда можно заклю­чить, что практического применения языки с фразовой структурой не имеют (и не будут иметь), а потому далее они не рассматриваются. Для контекстно-зависимых языков (тип 1) распознавателями являются двусто­ронние недетерминированные автоматы с линейно ограниченной внешней памя­тью. Алгоритм работы такого автомата в общем случае имеет экспоненциальную сложность — количество шагов (тактов), необходимых автомату для распознава­ния входной цепочки, экспоненциально зависит от длины этой цепочки. Следо­вательно, и время, необходимое на разбор входной цепочки по заданному алго­ритму, экспоненциально зависит от длины входной цепочки символов. Такой алгоритм распознавателя уже может быть реализован в программном обес­печении компьютера — зная длину входной цепочки, всегда можно сказать, за какое максимально возможное время будет принято решение о принадлежности цепочки данному языку и какие вычислительные ресурсы для этого потребуют­ся. Однако экспоненциальная зависимость времени разбора от длины цепочки существенно ограничивает применение распознавателей для контекстно-зависи­мых языков. Как правило, такие распознаватели применяются для автоматизи­рованного перевода и анализа текстов на естественных языках, когда временные ограничения на разбор текста несущественны (следует также напомнить, что, по­скольку естественные языки более сложны, чем контекстно-зависимый тип, то после такой обработки часто требуется вмешательство человека). В компилято-

 

Входная цепочка символов
|ai|a2|                                 |an|

+ Считывающая головка

УУ К-

Рабочая

(внешняя)

память

Рис. 9.5. Условная схема распознавателя

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

Как видно из рисунка, распознаватель состоит из следующих основных компо­нентов:

□     ленты, содержащей исходную цепочку входных символов, и считывающей го­ловки, обозревающей очередной символ в этой цепочке;

□     устройства управления (УУ), которое координирует работу распознавателя, имеет некоторый набор состояний и конечную память (для хранения своего состояния и некоторой промежуточной информации);

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

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

В процессе своей работы распознаватель может выполнять некоторые элемен­тарные операции, такие как чтение очередного символа из входной цепочки, сдвиг входной цепочки на заданное количество символов (вправо или влево), доступ к рабочей памяти для чтения или записи информации, преобразование информации в памяти, изменение состояния УУ. То, какие конкретно операции должны выполняться в процессе работы распознавателя, определяется в УУ.

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

□     содержимое входной цепочки символов и положение считывающей головки в ней;

□     состояние УУ;

□     содержимое внешней памяти.

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

Кроме начального состояния для распознавателя задается одна или несколько конечных конфигураций. В конечной конфигурации считывающая головка, как правило, находится за концом исходной цепочки (часто для распознавателей вводят специальный символ, обозначающий конец входной цепочки). Распознаватель допускает входную цепочку символов а, если, находясь в началь­ной конфигурации и получив на вход эту цепочку, он может проделать последо­вательность шагов, заканчивающуюся одной из его конечных конфигураций. Формулировка «может проделать последовательность шагов» более точна, чем прямое указание «проделает последовательность шагов», так как для многих распознавателей при одной и той же входной цепочке символов из начальной конфигурации могут быть допустимы различные последовательности шагов, не все из которых ведут к конечной конфигурации.

Язык, определяемый распознавателем, — это множество всех цепочек, которые допускает распознаватель.

Далее в главах этого пособия рассмотрены конкретные типы распознавателей для различных типов языков. Но все, что было сказано здесь, относится ко всем без исключения типам распознавателей для всех типов языков.

Виды распознавателей

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

По видам считывающего устройства распознаватели могут быть двусторонние и односторонние.

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

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

Поэтому в рамках этого учебного пособия контекстно-зависимые языки также не рассматриваются.

Для контекстно-свободных языков (тип 2) распознавателями являются односто­ронние недетерминированные автоматы с магазинной (стековой) внешней па­мятью — МП-автоматы. При простейшей реализации алгоритма работы такого автомата он имеет экспоненциальную сложность, однако путем некоторых усо­вершенствований алгоритма можно добиться полиномиальной (кубической) за­висимости времени, необходимого на разбор входной цепочки, от длины этой цепочки. Следовательно, можно говорить о полиномиальной сложности распо­знавателя для КС-языков.

Среди всех КС-языков можно выделить класс детерминированных КС-языков, распознавателями для которых являются детерминированные автоматы с мага­зинной (стековой) внешней памятью — ДМП-автоматы. Эти языки обладают свойством однозначности — доказано, что для любого детерминированного КС-языка всегда можно построить однозначную грамматику. Кроме того, для таких языков существует алгоритм работы распознавателя с квадратичной сложно­стью. Поскольку эти языки являются однозначными, именно они представляют наибольший интерес для построения компиляторов.

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

Тем не менее следует помнить, что только синтаксические конструкции языков программирования допускают разбор с помощью распознавателей КС-языков. Сами языки программирования, как уже было сказано, не могут быть полностью отнесены к типу КС-языков, поскольку предполагают некоторую контекстную зависимость в тексте исходной программы (например, такую, как необходимость предварительного описания переменных). Поэтому кроме синтаксического раз­бора практически все компиляторы предполагают дополнительный семантиче­ский анализ текста исходной программы. Этого можно было бы избежать, если построить компилятор на основе контекстно-зависимого распознавателя, но ско­рость работы такого компилятора была бы недопустима низка, поскольку время разбора в таком варианте будет экспоненциально зависеть от длины исходной программы. Комбинация из распознавателя КС-языка и дополнительного семан­тического анализатора является более эффективной с точки зрения скорости разбора исходной программы. Для регулярных языков (тип 3) распознавателями являются односторонние неде­терминированные автоматы без внешней памяти — конечные автоматы (KA'i Это очень простой тип распознавателя, который всегда предполагает линейную зависимость времени на разбор входной цепочки от ее длины. Кроме того, конеч­ные автоматы имеют важную особенность: любой недетерминированный КА всегда может быть преобразован в детерминированный. Это обстоятельство су­щественно упрощает разработку программного обеспечения, обеспечивающего функционирование распознавателя.

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

В компиляторах распознаватели на основе регулярных языков используются для лексического анализа текста исходной программы — выделения в нем про­стейших конструкций языка, таких как идентификаторы, строки, константы и т. п. Это позволяет существенно сократить объем исходной информации и упрощает синтаксический разбор программы. Более подробно взаимодействие лексическо­го и синтаксического анализаторов текста программы рассмотрено дальше, в гла­ве, посвященной структуре компилятора. На основе распознавателей регулярных языков функционируют ассемблеры — компиляторы с языков ассемблера (мне­мокода) в язык машинных команд.

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

Регулярные языки и связанные с ними математические методы рассматриваются в отдельной главе данного учебного пособия.

Задача разбора (постановка задачи)

Грамматики и распознаватели — два независимых метода, которые реально мо­гут быть использованы для определения какого-либо языка. Однако при разра­ботке компилятора для некоторого языка программирования возникает задача, которая требует связать между собой эти методы задания языков. Разработчики компилятора всегда имеют дело с уже определенным языком про­граммирования. Грамматика для синтаксических конструкций этого языка из­вестна. Она, как правило, четко описана в стандарте языка, и хотя форма опи­сания может быть произвольной, ее всегда можно преобразовать к требуемому виду (например, к форме Бэкуса—Наура или к форме описания с использованием метасимволов). Задача разработчиков заключается в том, чтобы построить рас­познаватель для заданного языка, который затем будет основой синтаксического анализатора в компиляторе.

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

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

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

Кроме того, если входная цепочка символов не принадлежит заданному языку — исходная программа содержит ошибку, — разработчику программы не интересно просто узнать сам факт наличия ошибки. В данном случае задача разбора также расширяется: распознаватель в составе компилятора должен не только устано­вить факт присутствия ошибки во входной программе, но и по возможности            оп­ределить тип ошибки и то место в цепочке символов, где она встречается.

Регулярные языки и грамматики

Леволинейные и праволинейные грамматики. Автоматные грамматики

К регулярным, как уже было сказано, относятся два типа грамматик: леволинейные и праволинейные.

Леволинейные грамматики G(VT,VN,P,S), V = VNuVT могут иметь правила дву видов: А-»Ву или А-»у, где A,BeVN, yeVT*.

В свою очередь, праволинейные грамматики G(VT,VN,P,S), V - VNuVT могу иметь правила также двух видов: А-»уВ или А-»у, где A.BeVN, yeVT*.

Доказано, что эти два класса грамматик эквивалентны. Для любого регулярног языка, заданного праволинейной грамматикой, может быть построена левол* нейная грамматика, определяющая эквивалентный язык; и наоборот — для лк бого регулярного языка, заданного леволинейной грамматикой, может быть ш строена праволинейная грамматика, задающая эквивалентный язык.

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

Среди всех регулярных грамматик можно выделить отдельный класс — автома ные грамматики. Они также могут быть леволинейными и праволинейными.

Леволинейные автоматные грамматики G(VT,VN,P,S), V - VNuVT могут имс правила двух видов: A-»Bt или A-»t, где A.BeVN, teVT.

Праволинейные автоматные грамматики G(VT,VN,P,S), V - VNuVT могут име правила двух видов: A-»tB или A-»t, где A.BeVN, teVT.

Разница между автоматными грамматиками и обычными регулярными rpai матиками заключается в следующем: там, где в правилах обычных регулярньграмматик может присутствовать цепочка терминальных символов, в автомат­ных грамматиках может присутствовать только один терминальный символ. Лю­бая автоматная грамматика является регулярной, но не наоборот — не всякая регулярная грамматика является автоматной.

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

Чтобы классы автоматных и регулярных грамматик были полностью эквивалент­ны, в автоматных грамматиках разрешается дополнительное правило вида S->^., где S — целевой символ грамматики. При этом символ S не должен встречаться в правых частях других правил грамматики. Тогда язык, заданный автоматной грамматикой G может включать в себя пустую цепочку: >.eL(G). В таком случае автоматные леволинейные и праволинейные грамматики, так же как обычные леволинейные и праволинейные грамматики, задают регулярные языки. Поскольку реально используемые языки, как правило не содержат пустую цепочку симво­лов, разница на пустую цепочку между этими двумя типами грамматик значения не имеет и правила вида S->X далее рассматриваться не будут.

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

Алгоритм преобразования регулярной грамматики к автоматному виду

Имеется регулярная грамматика G(VT,VN,P,S), необходимо преобразовать ее в почти эквивалентную автоматную грамматику G'(VT,VN',P',S'). Для опреде­ленности будем рассматривать леволинейные грамматики, как уже было сказано выше (для праволинейных грамматик можно легко построить аналогичный ал­горитм).

Алгоритм преобразования прост и заключается он в следующей последователь­ности действий:

Шаг 1. Все нетерминальные символы из множества VN грамматики G перено­сятся во множество VN' грамматики G'.

Шаг 2. Необходимо просматривать все множество правил Р грамматики G.

Если встречаются правила вида А->Ва!, A.BeVN, ateVT или вида А-^, AeVN, aieVT, то они переносятся во множество Р' правил грамматики G' без измене­ний.

Если встречаются правила вида A->Baia2...a„, n> 1, A,BeVN, Vn>i>0: а^УТ, то во множество нетерминальных символов VN' грамматики G' добавляются

символы Ai,A2. Ап_ь а во множество правил Р' грамматики G' добавляются

правила:

A—> An_!an An-i-> An_2an_i

A2—> Aja2 A^Ba!

Если встречаются правила вида A-^a^.-.a,,, n > 1, AeVN, Vn > i > 0: а;еVT, то во множество нетерминальных символов VN' грамматики G' добавляются символы AtA^-A,,-!, а во множество правил Р' грамматики G' добавляются правила:

А—> Ап_!ап An-i-* An.^n-j

А2-> А,а2

Если встречаются правила вида А-»В или вида А->Х., то они переносятся во мно­жество правил Р' грамматики G' без изменений.

Шаг 3. Просматривается множество правил Р' грамматики G'. В нем ищутся пра­вила вида А->В или вида А-»А,.

Если находится правило вида А->В, то просматривается множество правил Р' грамматики G'. Если в нем присутствует правила вида В-»С, В->Са, В-»а или В-»Х,, то в него добавляются правила вида А-»С, А->Са, А->а и А->Х соответст­венно, VA,B,CeVN\ VaeVT' (при этом следует учитывать, что в грамматике не должно быть совпадающих правил, и если какое-то правило уже присутствует в грамматике G', то повторно его туда добавлять не следует). Правило А->В уда­ляется из множества правил Р'.

Если находится правило вида А->\, то просматривается множество правил Р' грамматики G'. Если в нем присутствует правило вида В->А или В->Аа, то в него добавляются правила вида В-»А, и В-»а соответственно, VA.BeVN', VaeVT' (при этом следует учитывать, что в грамматике не должно быть совпадающих правил, и если какое-то правило уже присутствует в грамматике G', то повторно его туда добавлять не следует). Правило А-»Х, удаляется из множества правил Р'. Шаг 4. Если на шаге 3 было найдено хотя бы одно правило вида А->В или А-»Х во множестве правил Р' грамматики G', то надо повторить шаг 3, иначе перейти к шагу 5.

Шаг 5. Целевым символом S' грамматики G' становится символ S. Шаги 3 и 4 алгоритма в принципе можно не выполнять, если грамматика не со­держит правил вида А-»В (такие правила называются цепными) или вида А-»> (такие правила называются ^-правилами). Реальные регулярные грамматики обыч­но не содержат правил такого вида. Тогда алгоритм преобразования грамматик* к автоматному виду существенно упрощается. Кроме того, эти правила можн( было бы устранить предварительно с помощью специальных алгоритмов преоб разования (они рассмотрены дальше, в главе, посвященной КС-грамматикам, не также применимы и к регулярным грамматикам).

 

Пример преобразования регулярной грамматики к автоматному виду

Рассмотрим в качестве примера следующую простейшую регулярную граммати­ку: G({"a". "(","*",")","{"."}"}. {S.CK}, Р, 5)(символыа. (, *, ), {, } из мно­жества терминальных символов грамматики взяты в кавычки, чтобы выделить их среди фигурных скобок, обозначающих само множество):

Р:

S -> С*)  | К}

С -* (* | Са | С{ | С} | С( | С* | С)

К -► {  | Ка | К(  | К* | К) | К{

Если предположить, что а здесь — это любой алфавитно-цифровой символ, кро­ме символов (, *. ), {, }, то эта грамматика описывает два типа комментариев, допустимых в языке программирования Borland Pascal. Преобразуем ее в авто­матный вид.

Шаг 1. Построим множество VN' = {S,C,K}.

Шаг 2. Начинаем просматривать множество правил Р грамматики G.

Для правила S ->• С*) во множество VN' включаем символ Si, а само правило разбиваем на два: S -> St) и Si -» С*; включаем эти правила во множество пра­вил Р'.

Правило S -» К} переносим во множество правил Р' без изменений.

Для правила С -> (* во множество VN' включаем символ Сь а само правило раз­биваем на два: С -> Ct* и С! -> (; включаем эти два правила во множество пра­вил Р'.

Правила С -» Са | С{ | С} | С( | С* | С) переносим во множество правил Р' без изменений.

Правила К -» { | Ка | К( | К* | К) | К{ переносим во множество правил Р' без из­менений.

Шаг 3. Правил вида А->В или А-»Х, во множестве правил Р' не содержится.

Шаг 4. Переходим к шагу 5.

Шаг 5. Целевым символом грамматики G' становится символ S.

В итоге получаем автоматную грамматику:

G'({"a"."("."*".")"."{"."}"}■  {S S[ c Ci|K^ р._ S).

Р':

$% ЭД  | К}

S, -+ с*

С -> d* | Са | С{ | С} | С( | С* | С)

t, -> (

К -» {  | Ка  | К(  | К* | К)  | К{

Эта грамматика, так же как и рассмотренная выше, описывает два типа коммен­тариев, допустимых в языке программирования Borland Pascal.

 

Конечные автоматы

Определение конечного автомата

Конечным автоматом (КА) называют пятерку следующего вида: M(Q,V,8,qo,F),

где

□     Q, — конечное множество состояний автомата;

□     V — конечное множество допустимых входных символов (алфавит автомата);

□     5 — функция переходов, отображающая VxQ (декартово произведение мно­жеств) в множество подмножеств Q: R(Q), то есть 8(a,q) = R, ае V, qeQ, RcOj

□     q0 — начальное состояние автомата Q, q0eOj

□     F — непустое множество конечных состояний автомата, FcQ, F*0.

КА называют полностью определенным, если в каждом его состоянии сущест­вует функция перехода для всех возможных входных символов, то есть VaeV, VqeQ38(a,q) = R, RcQ.

Работа конечного автомата представляет собой последовательность шагов (или тактов). На каждом шаге работы автомат находится в одном из своих состояний Q (в текущем состоянии), на следующем шаге он может перейти в другое состоя­ние или остаться в текущем состоянии. То, в какое состояние автомат перейдет на следующем шаге работы, определяет функция переходов 8. Она зависит не только от текущего состояния, но и от символа из алфавита V, поданного на вход автомата. Когда функция перехода допускает несколько следующих состояний автомата, то КА может перейти в любое из этих состояний. В начале работы ав­томат всегда находится в начальном состоянии q0. Работа КА продолжается до тех пор, пока на его вход поступают символы из входной цепочки coeV+.

Видно, что конфигурацию КА на каждом шаге работы можно определить в виде (q,co,n), где q — текущее состояние автомата, qeQj со — цепочка входных симво­лов, соеV+; n — положение указателя в цепочке символов, neNu{0}, п < |co| (N — множество натуральных чисел). Конфигурация автомата на следующем шаге — это (q',co,n+l), если q'e8(a,q) и символ aeV находится в позиции п+1 цепочки со. Начальная конфигурация автомата: (q0,co,0); заключительная конфигурация ав­томата: (f,co,n), feQ,, n = |со|, она является конечной конфигурацией, если feF.

КА M(Q,V,S,qo,F) принимает цепочку символов coeV4, если, получив на вход эту цепочку, он из начального состояния q0 может перейти в одно из конечных со­стояний feF. В противном случае КА не принимает цепочку символов.

Язык ЦМ), заданный КА М(О,У,8^0,Р), — это множество всех цепочек симво­лов, которые принимаются этим автоматом. Два КА эквивалентны, если они за­дают один и тот же язык.

Таким образом, КА является распознавателем для формальных языков. Далее будет показано, что КА — это распознаватели для регулярных языков.

КА часто представляют в виде диаграммы или графа переходов автомата.

Граф переходов КА — это направленный помеченный граф, с символами состоя­ний КА в вершинах, в котором есть дуга (p,q) p,qeQ, помеченная символом aeV, если в КА определена 5(а,р) и qe8(a,p). Начальное и конечные состояния авто­мата на графе состояний помечаются специальным образом (в данном пособии начальное состояние — дополнительной пунктирной линией, конечное состоя­ние — дополнительной сплошной линией).

Рассмотрим конечный автомат: M({H,A,B,S}.{a,b},8,H,{S}); 8: 8(H,b) = В, 8(В,а) = А, 8(A,b) = {B,S}. Ниже на рис. 10.1 приведен пример графа состояний для этого КА.

"   b         а            ь^=^

р

Рис. 10.1. Граф переходов недетерминированного конечного автомата

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

Если преобразовать подобным образом рассмотренный выше автомат М, то по­лучим полностью определенный автомат: M({H,A,B,E,S},{a,b},8,H,{S}); 8: 8(Н,а) = Е, 8(H,b) = B, 8(B,a) = A, 8(B,b) = E, 8(A,a) = {E}, 8(A,b) = {B,S}, 8(E,a) = {Е}, 8(E,b) = {E}, 8(S,a) = {E}, 8(S,b) = {Е}. Состояние Е как раз соответствует состоянию «ошиб­ка». Граф переходов этого КА представлен на рис. 10.2.

,_.. Ь        а              Ь

а__

а,Ь

*а-

Рис. 10.2. Граф переходов полностью определенного недетерминированного конечного автомата

Детерминированные и недетерминированные конечные автоматы

Конечный автомат M(Q,V,8,q0,F) называют детерминированным конечным авто­матом (ДКА), если в каждом из его состояний для любого входного символа функ­ция перехода содержит не более одного состояния: VaeV, VqeQ; либо S(a,q) = {г}, reQ либо 8(a,q) = 0.

В противном случае конечный автомат называют недетерминированным. ДКА может быть задан в виде пятерки:

M(Q,V,5,q0,F),

где Q — конечное множество состояний автомата; V — конечное множество до­пустимых входных символов; 8 — функция переходов, отображающая VxQ e множество Q: S(a,q) = г, aeV, q,reQ; q0 — начальное состояние автомата Q q0eQ; F — непустое множество конечных состояний автомата, FcQ F*0.

Если функция переходов ДКА определена для каждого состояния автомата, тс автомат называется полностью определенным ДКА: VaeV, VqeQ: либо 38(a,q) = r reQ.

Моделировать работу ДКА существенно проще, чем работу произвольного ДКА.

Доказано, что для любого ДКА можно построить эквивалентный ему ДКА. По­этому используемый произвольный ДКА А стремятся преобразовать в ДКА. При построении компиляторов чаще всего используют полностью определеный ДКА.

Преобразование конечного автомата к детерминированному виду

Алгоритм преобразования произвольного ДКА M(Q)V,8,q0,F) в эквивалентный ему ДКА M'(Q',V,S',q'0,F') заключается в следующем:

1.  Множество состояний Q' автомата М' строится из комбинаций всех состоя­
ний множества Q автомата М. Если qi,q2        qn, n > 0 — состояния автомата М

V0<i<n qjeQ, то всего будет 2п-1 состояний автомата М'. Обозначим ю так: [q,,q2,...,qm], 0<m<n.

2.        Функция переходов 8' автомата М' строится так: 8'(a,[q1,q2,...,qm]) = [г^г^л-Л] где V0 < i < m Э0 < j < k так, что 8(а^) = г,;

3.        Обозначим q'0 = [q0];

4.        Пусть f^.-jfi, 1 > 0 — конечные состояния автомата М, V0 < i < 1 f^eF, тогдг множество конечных состояний F' автомата М' строится из всех состояний имеющих вид [...,1,,...], fjeF.

Доказано, что описанный выше алгоритм строит ДКА, эквивалентный заданно­му произвольному КА.

После построения из нового ДКА необходимо удалить все недостижимые со­стояния.

Состояние qeQ в КА M(QV,S,q0,F) называется недостижимым, если ни при ка­кой входной цепочке юе V+ невозможен переход автомата из начального состоя­ния q0 в состояние q. Иначе состояние называется достижимым.

Для работы алгоритма удаления недостижимых состояний используются двг множества: множество достижимых состояний R и множество текущих актив­ных состояний на каждом шаге алгоритма Рг Результатом работы алгоритма яв­ляется полное множество достижимых состояний R. Рассмотрим работу алгоритма по шагам:

1.        R:={q0}; i:=0; P0:={q0};

2.        Pi+1:=0;

3.         VaeV, VqePj: Pi+1:-Pi+1u8(a,q);

4.          Если Pi+i-R = 0, то выполнение алгоритма закончено, иначе R:=RuPi+1, i:=i+l и перейти к шагу 3.

После выполнения данного алгоритма из КА можно исключить все состояния, не входящие в построенное множество R.

Рассмотрим работу алгоритма преобразования произвольного КА в ДКА на при­мере автомата M({H,A,B,S},{a.b},8,H,{S}); 5: 8(H,b) «- В, 8(В,а) = А, 5(А,Ь) = {B.S}. Видно, что это недетерминированный КА (из состояния А возможны два раз­личных перехода по символу Ь). Граф переходов для этого автомата был изобра­жен выше на рис. 10.1.

Построим множество состояний эквивалентного ДКА:

Q'={[H].[A],[B].[S].[HA],[HB].[HS].[AB],[AS],[BS].[HAB].[HAS].[HBS]. [ABS].[HABS]}.

Построим функцию переходов эквивалентного ДКА:

 

8'([Н],Ь)

=   [B]

8'([А],Ь)

H   [BS]

8'([В],а)

-   [A]

8Х[НА],Ь)

=   [BS]

8'([НВ],а)

=   [A]

8'([НВ],Ь)

=   [B]

5'([HS],b)

=   [B]

8'([АВ],а)

=   [A]

8Х[АВ],Ь)

=   [BS]

8'([AS],b)

=   [BS]

S'([BS],a)

-   [A]

8'([НАВ],а)

=   [A]

8X[HAB],b)

-   [BS]

8X[HAS],b)

=   [BS]

8X[HBS],b)

- [B]

8X[HBS],a)

=   [A]

8X[ABS],b)

=   [BS]

8X[ABS],a)

=   [A]

SX[HABS],a)

=   [A]

SX[HABS],b)

-   [BS]

Начальное состояние эквивалентного ДКА:

Qo' = [Н] Множество конечных состояний эквивалентного ДКА:

F' - {[S].[HS].[AS].[BS].[HAS].[HBS].[ABS].[HABS]}

После построения ДКА исключим недостижимые состояния. Множество дости­жимых состояний ДКА будет следующим R = {[H],[B],[A],[BS]}. В итоге, ис­ключив все недостижимые состояния, получим ДКА:

M4{[H].[B].[A].[BS]}.{a.b}.[H].{[BS]}).

S([H].b)=[B]. 5([B].a)-[A]. 8([A],b)=[BS]. 5([BS].a)=[A].

Ничего не изменяя, переобозначим состояния ДКА. Получим:

M'({H.B.A.S}.{a.b}.H.{S}).

5(H.b)=B. 6(B.a)=A. 8(A.b)=S. 5(S,a)-A.

Граф переходов полученного ДКА изображен на рис. 10.3.

Рис. 10.3. Граф переходов детерминированного конечного автомата

Этот автомат можно преобразовать к полностью определенному виду. Получим граф состояний, изображенный на рис. 10.4 (состояние Е — это состояние «ошиб­ка»).

Рис. 10.4. Граф переходов полностью определенного детерминированного конечного автомата

При построении распознавателей к вопросу о необходимости преобразования К/ в ДКА надо подходить, основываясь на принципе разумной достаточности. Мо делировать работу ДКА существенно проще, чем произвольного КА, но при вы полнении преобразования число состояний автомата может существенно возрас ти и, в худшем случае, составит 2п-1, где п — количество состояний исходноп КА. В этом случае затраты на моделирование ДКА окажутся больше, чем на      моделирование исходного КА. Поэтому не всегда выполнение преобразования ав томата к детерминированному виду является обязательным.

Минимизация конечных автоматов

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

Для минимизации автомата используется алгоритм построения эквивалентны состояний КА. Два различных состояния в конечном автомате M(Q,V,5,q0,F

qeQ,и q'eQ. называются п-эквивалентными (n-неразличимыми), п > О neNu{0}, если, находясь в одном из этих состояний и получив на вход любую цепочку символов со: <oeV* |co| < п, автомат может перейти в одно и то же множество конеч­ных состояний. Очевидно, что эквивалентными состояниями автомата M(Q,V, 5,q0,F) являются два множества его состояний: F и Q-F. Множества эквивалент­ных состояний автомата называют классами эквивалентности, а всю их совокуп­ность — множеством классов эквивалентности R(n) причем R(0)={F,Q,-F}.

Рассмотрим работу алгоритма построения эквивалентных состояний по шагам:

1.         На первом шаге п:=0 строим R(0).

2.         На втором шаге п:=п+1 строим R(n) на основе R(n-l): R(n) = {Г((п): {qjjeQj VaeV 8(a,qjj)cij(n-l)} VijeN}. To есть в классы эквивалентности на шаге п входят те состояния, которые по одинаковым символам переходят в п-1 эк­вивалентные состояния.

3.         Если R(n) = R(n-l), то работа алгоритма закончена, иначе необходимо вер­нуться к шагу 2.

Доказано, что алгоритм построения множества классов эквивалентности завер­шится максимум для n = m-2, где т — общее количество состояний автомата.

Алгоритм минимизации КА заключается в следующем:

1.  Из автомата исключаются все недостижимые состояния.

2.          Строятся классы эквивалентности автомата.

3.          Классы эквивалентности состояний исходного КА становятся состояниями ре­зультирующего минимизированного КА.

4.          Функция переходов результирующего КА очевидным образом строится на ос­нове функции переходов исходного КА.

Для этого алгоритма доказано, во-первых, что он строит минимизированный КА, эквивалентный заданному; во-вторых, что он строит КА с минимально возмож­ным числом состояний (минимальный КА).

Рассмотрим пример: задан автомат M({A,B,C,D,E,F,G},{0,1},5,A,{D,E}), 5(A,0) = {В}, 5(А,1) = {С}, 8(В,1) = {D}, 5(С,1) = {Е}. 5CD.0) = {С}, 5(0,1) = {Е}, 5(Е,0) = {В}, 5(E.l) = {D}, 5(F,0) = {D}, 5(F.l) = {G}, 5(G,0) = {F}, 5(G,1) = {F}; необходимо построить эквивалентный ему минимальный КА.

Рис. 10.5. Граф переходов конечного автомата до его минимизации

 

 

 

Состояния F и G являются недостижимыми, они будут исключены на первом шаге алгоритма. Построим классы эквивалентности автомата:

R(0)={{A,B,C},{D,E}}, n=0;

R(1)={{A},{B.C},{D,E}}, n=l;

R(2)={{A},{B,C},{D,E}}, n=2.

Обозначим соответствующим образом состояния полученного минимального КА и построим автомат: M({A.BC,DE},{0,1},5',A,{DE}), 5'(А,0) = {ВС}, 5'(А,1) = {ВС} 5ЧВС.1) = {DE}, 54DE.0) = {ВС}, 54DE.1) = {DE}.

Граф переходов минимального КА приведен на рис. 10.6.

Рис. 10.6. Граф переходов конечного автомата после его минимизации

Минимизация конечных автоматов позволяет при построении распознавателей получить автомат с минимально возможным числом состояний и тем самым г дальнейшим упростить функционирование распознавателя.

Регулярные множества и регулярные выражения

Определение регулярного множества

Определим над множествами цепочек символов из алфавита V операции конка­тенации и итерации следующим образом:

PQ - конкатенация PeV* и QeV*: PQ = {pq VpeP, VqeQJ; P* - итерация PeV*: P* = {pn VpeP, VneN}.

Тогда для алфавита V регулярные множества определяются рекурсивно:

1.  0 — регулярное множество.

2.         {к} — регулярное множество.

3.         {а} — регулярное множество VaeV.

4.         Если Р и Q. — произвольные регулярные множества, то множества PuQ, PC и Р* также являются регулярными множествами.

5.         Ничто другое не является регулярным множеством.

Фактически регулярные множества — это множества цепочек символов над за­данным алфавитом, построенные определенным образом (с использованием опе­раций объединения, конкатенации и итерации).

Все регулярные языки представляют собой регулярные множества.

Регулярные выражения. Свойства регулярных выражений

Регулярные множества можно обозначать с помощью регулярных выражений. Эти обозначения вводятся следующим образом:

1.  0 — регулярное выражение, обозначающее 0.

2.         X — регулярное выражение, обозначающее {X}.

3.         а — регулярное выражение, обозначающее {a} VaeV.

4.         Если р и q — регулярные выражения, обозначающие регулярные множества Р и Q, то p+q, pq, p* — регулярные выражения, обозначающие регулярные мно­жества PuQ, PQ и Р* соответственно.

Два регулярных выражения а и (3 равны, а = Р, если они обозначают одно и то же множество.

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

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

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

 

1.

^+а<х* г А.+а*а = а*

2.

а+Р = р+аЗ.

3.

а+(Р+у) = (а+р)+у

4.

а(Р+У) ? оф+ау

5.

(Р+у)а = Ра+уа

6.

а(Ру) = (ар)у

7.

а+а = а

8.

а+а* *■ а*

9.

Х+а' = а*+Х - а*

10.

0' = Х

П.

0а=а0~0

12.

0+а = а+0"а

13.

tax = аХ = а

14.

(а*)* - а*

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

Уравнения с регулярными коэффициентами

На основе регулярных выражений можно построить уравнения с регулярными коэффициентами [32]. Простейшие уравнения с регулярными коэффициентами будут выглядеть следующим образом:

X = аХ + р,

Х= Ха + р,

где a,PeV* — регулярные выражения над алфавитом V, а переменная XgV.

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

Решением первого уравнения является множество, обозначенное регулярным вы­ражением а*р. Проверим это решение, подставив его в уравнение вместо пере­менной X:

aX+p = a(a*p)+P =6 (aa*)P+P =13 (aa*)p+ty3 =5 (aa*+?,)p -i a*p = X

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

Решением второго уравнения является множество, обозначенное регулярным выражением pa*.

Xa+p = (pa*)a+p =6 p(a*a)+p =13 P(a*a)+pb =4 |3(a'a+X.) ** Pa* = X

Указанные решения уравнений не всегда являются единственными. Например, если регулярное выражение а в первом уравнении обозначает множество, кото­рое содержит пустую цепочку, то решением уравнения может быть любое мно­жество, обозначенное выражением X = а*(Р+у), где у — выражение, обозначаю­щее произвольное множество над алфавитом V (причем это множество даже может не быть регулярным). Однако доказано, что X = а'Р и X = Ра* — это наи­меньшие из возможных решений для данных двух уравнений. Эти решения на­зываются наименьшей подвижной точкой.

Из уравнений с регулярными коэффициентами можно формировать систему уравнений с регулярными коэффициентами. Система уравнений с регулярными коэффициентами имеет вид (правосторонняя запись):

Xt = а10 + a.nXi + а12Х2 + ... + а1пХп Х2 = а20 + a21Xt + а22Х2 + ... + а2пХп

Xj = ai0 + auXi + ai2X2 + ... + ainXn

Xn = an0 + anlXj + a12X2 + ... + annXn или (левосторонняя запись):

X, = a10 + Xjan + X2a12 + ... + Xnaln X2 = a20 + Хха21 + X2a22 + ... + Xna2n

Xj = ai0 + XjOit + X2ai2 + ... + Xnain

Xn = an0 + Xtanl + X2a12 + ... + Xnann

В системе уравнений с регулярными коэффициентами все коэффициенты а^ яв­ляются регулярными выражениями над алфавитом V, а переменные не входят в алфавит V: Vi Xjg V. Оба варианта записи равноправны, но в общем случае могут иметь различные решения при одинаковых коэффициентах при переменных. Чтобы решить систему уравнений с регулярными коэффициентами, надо найти такие регулярные множества Xj, при подстановке которых в систему все уравне­ния превращаются в тождества множеств. Иными словами, решением системы является некоторое отображение f(X) множества переменных уравнения Л={Х|: n > i > 0} на множество языков над алфавитом V*.

Системы уравнений с регулярными коэффициентами решаются методом после­довательных подстановок. Рассмотрим метод решения для правосторонней запи­си. Алгоритм решения работает с переменной номера шага i и состоит из следую­щих шагов.

Шаг 1. Положить i := 1.

Шаг 2. Если i = п, то перейти к шагу 4, иначе записать i-e уравнение в виде: Xj = ajXi+Pi, где a; = aii7 Pi = рю + РИ-цХ1+1 + ... + pinXn. Решить уравнение и полу­чить Xj = ocj'pj. Затем для всех уравнений с переменными Xi+1,...,Xn подставить в них найденное решение вместо Xj.

Шаг 3. Увеличить i на 1 (i := i+1) и вернуться к шагу 2.

Шаг 4. После всех подстановок уравнение для Хп будет иметь вид Xn = anXn+p, где an = ann. Причем р будет регулярным выражением над алфавитом V* (не со­держит в своем составе переменных системы уравнений Xj). Тогда можно найти окончательное решение для Xn: Xn r an*p. Перейти к шагу 5. Шаг 5. Уменьшить i на 1 (i := i-1). Если i = 0, то алгоритм завершен, иначе перей­ти к шагу 6.

Шаг 6. Берем найденное решение для Xj = cxjXj+Pj, где оц = aii; р( = pi0 + Pii+iXi+i +
+ ... + pinXn> и подставляем в него окончательные решения для переменных
Xj+i... Хп. Получаем окончательное решение для Х;. Перейти к шагу 5.

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

Система уравнений с регулярными коэффициентами всегда имеет решение, но это решение не всегда единственное. Для рассмотренного алгоритма решения системы уравнений с регулярными коэффициентами доказано, что он всегда на­ходит решение f(X) (отображение f: Vi Xj->V"), которое является наименьшей неподвижной точкой системы уравнений. То есть если существует любое другое решение g(X), то всегда f(X)cg(X).

В качестве примера рассмотрим систему уравнений с регулярными коэффици­ентами над алфавитом V = {"-", "+", ".", О, 1, 2, 3, 4, 5, 6, 7, 8, 9} (для ясности за­писи символы -, + и . взяты в кавычки, чтобы не путать их со знаками опера­ций):

Xj = ("-" + "+" + X)

Х2 = Х1"."(0+1+2+3+4+5+6+7+8+9) + Х3"." + Х2(0+1+2+3+4+5+6+7+8+9)

Х3 - Х1(0+1+2+3+4+5+6+7+8+9) + Х3(0+1+2+3+4+5+6+7+8+9)

х4 = х2 + х3

Обозначим регулярное выражение (0+1+2+3+4+5+6+7+8+9) через а для крат­кости записи: a = (0+1+2+3+4+5+6+7+8+9). Получим:

Xl = ("-" + "+;; + х)

Х2 - X,"."a + Х3"." + Х2а

Х3 = XjCt + Х3а

х4 = х2 + х3

Решим эту систему уравнений. Шаг 1. i := 1.

Шаг 2. Имеем i = 1 < 4. Берем уравнение для i = 1. Имеем Х1 = ("-" + "+" + X). Это уже и есть решение для Xj. Подставляем его в другие уравнения. Получаем:

Х2 = ("-" + "+" + ху."а + Х3"." + Х2а Х3 = ("-" + "+" + А.)а + Х3а

х4 = х2 + х3

Шаг 3. i:- i + 1 - 2.

Возвращаемся к шагу 2.

Шаг 2. Имеем i = 2 < 4. Берем уравнение для i = 2. Имеем

Х2 = ("-" + "+" + Х)"."а + Х3"." + Х2а. Преобразуем уравнение к виду:

Х2 = Х2а + (("-" + "+" + Х)"."а + Х3"."). Тогда а2 = а, р2 = ("-" + "+" + Х)""а + Х3".". Решением для Х2 будет:

Х2 = р2а2* - (("-" + "+" + Х)"."а + Х3".")а* = ("-" + "+" + Х)"."аа' + Х3"."а*.

Подставим его в другие уравнения. Получаем:

Х3 = ("-" + "+" + ^)а + Х3а

Х4 - ("-" + "+" + ^)"."аа* + Х3"."а* + Х3

Шаг 3. i:- i + 1 = 3.

Возвращаемся к шагу 2.

Шаг 2. Имеем i = 3 < 4. Берем уравнение для i = 3. Имеем

Х3 - ("-" + "+" + Х)а + Х3а. Преобразуем уравнение к виду

Х3 = Х3а + ("-" + "+" + Х)а. Тогда а3 = а, р3 = ("-" + "+" + Х)а. Решением для Х3 будет: Х3 = (33а3* = ("-" + "+" + ^)аа*. Подставим его в другие уравнения. Получаем:

Х4 - ("-" + "+" + b)"."aa* + ("-" + "+" + A,)aa*"."a* + ("-" + "+" + X,)aa*.

Шаг 3. i:- i + 1 = 4.

Возвращаемся к шагу 2.

Шаг 2. Имеем i = 4 = 4. Переходим к шагу 4.

Шаг 4. Уравнение для Х4 теперь имеет вид

Х4 = ("-" + "+" + ^)"."aa* + ("-" + "+" + ^)aa*"."a* + ("-" + "+" + я,)аа*. Оно не нуждается в преобразованиях и содержит окончательное решение для Х4. Переходим к шагу 5. Шаг 5. i := i - 1 - 3 > 0. Переходим к шагу 6.

Шаг 6. Уравнение для Х3 имеет вид Х3 = ("-" + "+" + X,)aa*. Оно уже содержит окончательное решение для Х3. Переходим к шагу 5.

Шаг 5. i:- i - 1 = 2 > 0. Переходим к шагу 6.

Шаг 6. Уравнение для Х2 имеет вид Х2 = ("-" + "+" + X,)"."aa* + X3"."a*. Подста­вим в него окончательное решение для Х3. Получим окончательное решение для Х2: Х2 = ("-" + "+" + X.)"."aa* + ("-" + "+" + Я.)аа*"."а*. Переходим к шагу 5.

Шаг 5. i:- i - 1 = 1 > 0. Переходим к шагу 6.

Шаг 6. Уравнение для Xt имеет вид Xt = ("-" + "+" + X). Оно уже содержит окон­чательное решение для Х\. Переходим к шагу 5. Шаг 5. i :=. i - 1 - 0'- 0. Алгоритм завершен. В итоге получили решение:

Xj = ("-" + "+" + X)

Х2 - ("-" + "+" + Х)"."аа + ("-" + "+" + >.)aa*"."a* Х3 = ("-" + "+" + ^)аа

Х4 = ("-" + "+" + %)".Ш' + ("-" + "+" + ^)aa*".V + ("-" + "+" + A.)aa*

Выполнив несложные преобразования, это же решение можно представить в бо­лее простом виде:

Х1 = ("-" + "+" + X)

Х2 = ("_" + "+" + Х)("."а + aa*".")a*

Х3 - ("-" + "+" + ^)aa*

Х4 = ("-" + "+" + Х)("."а + aa*"." + a)a*

Если подставить вместо обозначения а соответствующее ему регулярное выра­жение a = (0+1+2+3+4+5+6+7+8+9), то можно заметит, что регулярное выраже­ние для Х4 описывает язык десятичных чисел с плавающей точкой.

Способы задания регулярных языков

Три способа задания регулярных языков

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

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

Утверждение 2.1. Язык является регулярным множеством тогда и только тогда, когда он задан леволинейной (праволинейной) грамматикой.

Утверждение 2.2. Язык может быть задан леволинейной (праволинейной) грам­матикой тогда и только тогда, когда он является регулярным множеством.

Утверждение 2.3. Язык является регулярным множеством тогда и только тогда, когда он задан с помощью конечного автомата.

Утверждение 2.4. Язык распознается с помощью конечного автомата тогда и только тогда, когда он является регулярным множеством.

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

Связь регулярных выражений и регулярных грамматик

Регулярные выражения и регулярные грамматики связаны между собой следую­щим образом:

□     для любого регулярного языка, заданного регулярным выражением, можно по­строить регулярную грамматику, определяющую тот же язык;

□     для любого регулярного языка, заданного регулярной грамматикой, можно по­лучить регулярное выражение, определяющее тот же язык.

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

Построение леволинейной грамматики для языка, заданного регулярным выражением

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

1.        Для регулярного выражения 0 построим леволинеиную грамматику G(V, {S},0,S), которая будет определять язык, заданный этим выражением (грам­матика, в которой нет ни одного правила).

2.        Для регулярного выражения X построим леволинеиную грамматику G(V,{S}, {S—>A.},S), которая будет определять язык, заданный этим выражением.

3.        Для регулярного выражения aeV построим леволинеиную грамматику G(V, (S},{S-»a},S), которая будет определять язык, заданный этим выражением.

4.   Имеем регулярные выражения аир, заданные ими языки Ц и L2, а также со­
ответствующие им леволинейные грамматики G^V.VNt.Pj.S!) и G2(V,VN2,
P2,S2): Ц = L(G4) и L2 = L(G2). Необходимо на основе этих данных построить
леволинейные грамматики для языков, заданных выражениями а+р (L3 =
= Lj и L2), ар (L4 = L,L2) и а* (L5 = Ц*):
О для языка, заданного выражением а+р, строим грамматику G3(V,VN3,P3,S3):

VN3 = VNi u VN2 u {S3} (алфавит нетерминальных символов G3 строится на основе алфавитов нетерминальных символов Gj и G2 с добавлением но-' вого символа S3), P3 = Pt u Р2 и {S3-»S2|Si} (множество правил G3 строит­ся на основе множеств правил G] и G2 с добавлением двух новых правил S3—>S2lSt), целевым символом грамматики G3 становится символ S3; О для языка, заданного выражением ар, строим грамматику G4(V,VN4,P4,S2): VN3 r VNj u VN2 (алфавит нетерминальных символов G3 строится на ос­нове алфавитов нетерминальных символов Gt и G2), множество правил Р4 строится на основе множеств правил Pt и Р2 следующим образом: все правила из множества Р4 переносятся в Р4,

если правило из множества Р2 имеет вид А-»Ву, A,BeVN2, yeV, то оно г реносится в Р4 без изменений,

если правило из множества Р2 имеет вид А->у, Ае VN2, ye V", то в Р4 доба ляется правило A-^S1y,

целевым символом грамматики G4 становится целевой символ граммат ки G2 - S2;

-   для языка, заданного выражением а*, строим грамматику G5(V,VN5,P5,S VN3 = VNj U {S5} (алфавит нетерминальных символов G3 строится на с нове алфавита нетерминальных символов Gj с добавлением нового симв ла S5), множество правил Р5 строится на основе множеств правил ', следующим образом:

если правило из множества Pt имеет вид А-»Ву, А,ВеVN1; yeV*, то оно б реносится в Р5 без изменений,

если правило из множества Pi имеет вид А-»у, АеVN2, yeV*, то в Р5 доба ляются два правила A—>S1y|y,

дополнительно в Р5 добавляются два новых правила S5—>S1|A., целевым си волом грамматики G3 становится символ S5.

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

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

Построение регулярного выражения для языка, заданного леволинейной грамматикой

Имеем леволинеиную грамматику G(VT,VN,P,S), необходимо найти регуляр» выражение над алфавитом VT, определяющее язык L(G), заданный этой грамм тикой.

В данном случае преобразование не столь элементарно. Выполняется оно следующим образом:

1.  Обозначим символы алфавита нетерминальных символов VN следующим о разом: VN = {Xt, X2, ..., Х„}. Тогда все правила грамматики будут иметь ви X,—»Х/у или X,—>у X;,X;eVN, yeVT*; целевому символу грамматики S буд соответствовать некоторое обозначение X*.

2.         Построим систему уравнений с регулярными коэффициентами на основе п ременных Х1;Х2,...,Х„:

Xi = a0i + Xjttj, + Х2а21 + ... + Х„а„!

Х2 = а02 + Х1ОЧ2 + Х2а22 + ... + Хпап2

Хп = а0п + Хдац, + Х2а2п + ... + Xnann;

коэффициенты a0i, a02,..., а0п выбираются следующим образом: a0i = (Yi + Y2 + + - + Ут)> если во множестве правил Р грамматики G существуют правила Х4—>Y1ly2l...JYm' и aoi= 0> если правил такого вида не существует; коэффициенты а^, сы, ..., ajn для некоторого j выбираются следующим обра­зом: otji = (yt + у2 + ... + Ym)>если в0 множестве правил Р грамматики G сущест­вуют правила Xj—>XjYi|XjY2|...lXjym, и о^ = 0, если правил такого вида не суще­ствует.

3. Находим решение построенной системы уравнений.

Доказано, что решение для Хк (которое обозначает целевой символ S граммати­ки G) будет представлять собой искомое регулярное выражение, обозначающее язык, заданный грамматикой G. Остальные решения системы будут представ­лять собой регулярные выражения, обозначающие понятия грамматики, соответ­ствующие ее нетерминальным символам. В принципе для поиска регулярного выражения, обозначающего весь язык, не нужно искать все решения — достаточ­но найти решение для Хк, если выражения для понятий грамматики не представ­ляют отдельного интереса.

Например, рассмотрим леволинейную грамматику, определяющую язык деся­тичных чисел с плавающей точкой G({".", "-". "+", "О", "1", "2". "3", "4", "5", "6", "7", "8", "9"}, {<знак>, <дробное>, <целое>, <число>},Р,<число>):

Р:

<знак> -> -' | +\'%

<дробное> -> <знак>.0 | <знак>.1 | <знак>.2 | <знак>.3 | <знак>.4 | <знак>,5 | <знак>.6 | <знак>.7 | <знак>.8 | <знак>.9 | <целое>. | <дробное>0 | <дробное>1 | <дробное>2 | <дробное>3 | <дробное>4 | <дробное>5 | <дробное>6 | <дробное>7 | <дробное>8 | <дробное>9 <целое> -> <знак>0 | <знак>1 | <знак>2 | <знак>3 | <знак>4 | <знак>5 | <знак>6 | <знак>7 | <знак>8 | <знак>9 | <целое>0 | <целое>1 | <целое>2 | <целое>3 | <целое>4 | <целое>5 | <целое>6 | <целое>7 | <целое>8 | <целое>9 <число> -» <дробное> | <целое> Обозначим символы множества VN = {<знак>, <дробное>, <целое>, <число>} соот­ветствующими переменными Хр получим: VN = {Xl Х2, Х3, Х4}. Построим систему уравнений на основе правил грамматики G:

Xj = ("-•• + "+" + X)

Х2 = Xj"."(0+1+2+3+4+5+6+7+8+9) + Х3"." + Х2(0+1+2+3+4+5+6+7+8+9)

Х3 « X t(0+1+2+3+4+5+6+7+8+9) + Х3(0+1+2+3+4+5+6+7+8+9)

Х4 = Х2 + Х3 Эта система уравнений уже была решена выше. В данном случае нас интересует только решение для Х4, которое соответствует целевому символу грамматики G <число>. Решение для Х4 может быть записано в виде: Х4 = ("-" + "+" + X) ("."(0+1+2+3+4+5+6+7+8+9) + (0+1+2+3+4+5+6+7+8+9) (O+l+2+3-t +4+5+6+7+8+9)*"." + (0+1+2+3+4+5+6+7+8+9)) (0+1+2+3+4+5+6+7+8+9)*

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

Связь регулярных выражений и конечных автоматов

Регулярные выражения и конечные автоматы связаны между собой следующим образом:

□     для любого регулярного языка, заданного регулярным выражением, можнс построить конечный автомат, определяющий тот же язык;

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

Ниже будет рассмотрен алгоритм, реализующий построение конечного автомате по регулярному выражению. Алгоритм построения регулярного выражения пс конечному автомату здесь не рассматривается — он не представляет интереса поскольку, как будет показано ниже, проще построить грамматику, эквивалент­ную заданному конечному автомату, а потом уже найти регулярное выражение для заданного грамматикой языка (по алгоритму, который уже был выше рас­смотрен) [5, 6, т. 1, 12, 26].

Построение конечного автомата для языка, заданного регулярным выражением

Регулярные множества (и обозначающие их регулярные выражения) заданы ( помощью рекурсивного определения. Будем строить КА для регулярного выра­жения над алфавитом V, следуя шагам этого определения.

1.        Для регулярного выражения 0 построим КА M(Q,= {H,F},V,5,H,{F}), у кото рого функция переходов VqeQ, VaeV имеет вид 5(q,a) = 0.

2.   Для регулярного выражения X построим КА M(Q= {F},V,5,F,{F}), у которой функция переходов VaeV имеет вид 8(F,a) = 0, а множество конечных со­стояний содержит только начальное состояние.

3.   Для регулярного выражения asV построим КА M(Q= {H,F},V,8,H,{F}), с функ цией переходов 8(Н,а) = {F}.

4.   Имеем регулярные выражения аир, заданные ими языки Lt и L2, а также со ответствующие им КА M^Qj.V.SLq^F,) и M2(Q2,V,52,q2,F2): L{ = L(Mi) 1 L2 = L(M2). Необходимо на основе этих данных построить КА для языков, за данных выражениями а+р (L3 = Lj u L2), ар (L4 = L(L2) и а* (L5 - L/).

О для языка, заданного выражением а+р, строим КА M3(Q3,V,53,q3,F3): Оз г Qi u Q2 Ч {Яз} (множество состояний М3 строится из множеств со стояний М( и М2 с добавлением нового состояния q3),

§з(Яз>а) = S^qj.a) u 52(q2,a) VaeV, 53(q,a) = 5,(q,a) VaeV VqeQ,,

83(q,a) = 52(q,a) VaeV VqeQa,

F3 = Ft О F2 О {q3}, если a+p содержит X, или F3 = Ft и F2, если a+p не со­держит X, начальным состоянием КА М3 становится состояние q3;

-    для языка, заданного выражением ар, строим КА M4(Q4,V,84,qi,F4):

Q4 = Qi V Q2 (множество состояний М4 строится из множеств состояний

Mj и М2),

54(q,a) = ЩЩк) VaeV ЧЩ%/*д\

54(q,a) = 8!(q,a) и 82(q2,a) VaeV VqeFt,

84(q,a) = 82(q,a) VaeV VqeQ,,

F4 = F2, если q2gF2 или F4 = Щ и F2, если q2eF2,

начальным состоянием  К А М3 становится начальное состояние К A Mt — q(; О для языка, заданного выражением а*, строим КА M5(Q5,V,85,q5,F5):

Q5 = Q.! u {qs} (множество состояний М5 строится из множества состояний

Mt с добавлением нового состояния q5),

55(q,a) - 8,(q,a) VaeV Vqe(Q1/F1),

85(q,a) = 8i(q,a) u S^q^a) VaeV VqeFt,

85(q5.a) Г 8i(q!,a) VaeV,

F5 = Fi О {q5},                                                                                             >m

начальным состоянием КА М5 становится состояние q5. Используя указанные построения в качестве базиса индукции, на основе матема­тической индукции можно доказать, что для любого регулярного языка, заданно­го регулярным выражением, можно построить определяющий этот язык КА. Построение КА на основе регулярного выражения выполняется аналогично по­строению леволинейной грамматики.

Связь регулярных грамматик и конечных автоматов

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

Это очень важное утверждение, поскольку регулярные грамматики используют­ся для определения лексических конструкций языков программирования. Соз­дав автомат на основе известной грамматики, мы получаем распознаватель для лексических конструкций данного языка. Таким образом, удается решить задачу разбора для лексических конструкций языка, заданных произвольной регуляр­ной грамматикой. Обратное утверждение также полезно, поскольку позволяет узнать грамматику, цепочки языка которой допускает заданный автомат. Для построения конечного автомата на основании известной грамматики и для построения грамматики на основании данного конечного автомата используются достаточно простые алгоритмы. Все языки программирования определяют нотацию записи «слева направо». В той же нотации работают и компиляторы. Поэтому далее рассмотрены алгоритмы для леволинейных грамматик.

Построение конечного автомата на основе леволинейной грамматики

Имеется леволинейная грамматика G(VT,VN,P,S), необходимо построить экви­валентный ей конечный автомат M(Q,V,5,q0,F).

Прежде всего для построения автомата исходную грамматику G необходимо привести к автоматному виду. Известно, что такое преобразование можно вы­полнить для любой регулярной грамматики. Алгоритм преобразования к авто­матному виду был рассмотрен выше, поэтому здесь на данном вопросе останав­ливаться нет смысла. Можно считать, что исходная грамматика G уже является леволинейной автоматной грамматикой.

Тогда построение конечного автомата M(Q,V,8,q0,F) на основе грамматики G(VT, VN,P,S) выполняется по следующему алгоритму.

Шаг 1. Строим множество состояний автомата 0\ Состояния автомата строятся таким образом, чтобы каждому нетерминальному символу из множества VN грам­матики G соответствовало одно состояние из множества Q автомата М. Кроме того, во множество состояний автомата добавляется еще одно дополнительное состояние, которое будем обозначать Н. Сохраняя обозначения нетерминальных символов грамматики G, для множества состояний автомата М можно записать: Q = VNu{H}.

Шаг 2. Входным алфавитом автомата М является множество терминальных сим­волов грамматики G: V = VT.

Шаг 3. Просматриваем все множество правил исходной грамматики. Если встречается правило вида A->teP, где AeVN, teVT, то в функцию перехо­дов 8(H,t) автомата М добавляем состояние A: AeS(H,t).

Если встречается правило вида A-»BteP, где A.BeVN, teVT, то в функцию пе­реходов 8(B,t) автомата М добавляем состояние A: Ae8(B,t).

Шаг 4. Начальным состоянием автомата М является состояние Н: q0 = Н.

Шаг 5- Множество конечных состояний автомата М состоит из одного состоя­ния. Этим состоянием является состояние, соответствующее целевому символу грамматики G: F = {S}.

На этом построение автомата заканчивается.

Построение леволинейной грамматики на основе конечного автомата

Имеется конечный автомат M(Q,V,8,q0,F), необходимо построить эквивалент­ную ему леволинейную грамматику G(VT,VN,P,S). Построение выполняется по следующему алгоритму. Шаг 1. Множество терминальных символов грамматики G строится из алфавита входных символов автомата М: VT = V.

Шаг 2. Множество нетерминальных символов грамматики G строится на основа­нии множества состояний автомата М таким образом, чтобы каждому состоянию автомата, за исключением начального состояния, соответствовал один нетерми­нальный символ грамматики: VN = Q\{qo}.

Шаг 3. Просматриваем функцию переходов автомата М для всех возможных со­стояний из множества Одля всех возможных входных символов из множества V. Если имеем 8(A,t) = 0, то ничего не выполняем.

Если имеем 8(A,t) = {В^Вг^.Д,}, п >0, где AeQ, Vn>i>0: B;eQ, teV, тогда для всех состояний Bj выполняем следующее:

□     добавляем правило Bs—>t во множество Р правил грамматики G, если А = q0;

□     добавляем правило B^At во множество Р правил грамматики G, если A*q0. Шаг 4. Если множество конечных состояний F автомата М содержит только одно состояние F = {F0}, то целевым символом S грамматики G становится символ мно­жества VN, соответствующий этому состоянию: S = F0; иначе, если множество конечных состояний F автомата М содержит более одного состояния F = {¥и F2,...,Fn}, п>1, тогда во множество нетерминальных символов VN грамматики G добавляется новый нетерминальный символ S: VN = VNu{S}, а во множество пра­вил Р грамматики G добавляются правила: S—»Fi|F2|...|Fn.

На этом построение грамматики заканчивается.

Пример построения конечного автомата на основе заданной грамматики

Рассмотрим грамматику 6({"а","(","*".")"."{"'"}"}• {S.C.K}, P. S) (символы а, (, *, ), {, } из множества терминальных символов грамматики взяты в кавычки, чтобы выделить их среди фигурных скобок, обозначающих само множество):

Р:

S -> С*)  | К}

С -» (* | Са | С{  | С}  | С(  | С* | С)

К -» {  | Ка | К(  | К* | К) | К{ Это леволинейная регулярная грамматика. Как было показано выше, ее можно преобразовать к автоматному виду.

Получим леволинейную автоматную грамматику следующего вида: G'({"a","(", "*".")","{"."}"}. {S.SlCCl^.P'.S):

Р':

S -> S,)  | К}

S! -» С*

С -> С,* | Са | С{  | С}  | С(  | С* | С)

С, -» С

К -> {  | Ка  | К(  | К* | К)  | К{

Для удобства переобозначим нетерминальные символы Q и S4 символами D и Е. Получим грамматику G'({"a","С."*",")","{",'■}"}. {S.E.C.D.K}, P\ S):

Р':

S ->   Е)  | К}

Е ->  С*

С -> D* | Са | С{  | С}  | С(  | С* | С)

О -> (

К -»   {  | Ка | К(  | К* | К)  | К{

Построим конечный автомат M(Q,V,8,q0,F), эквивалентный указанной грамма­тике.

Шаг 1. Строим множество состояний автомата. Получаем: Q=VNu{H} = = {S,E,C,D,K,H}.

Шаг 2. В качестве алфавита входных символов автомата берем множество тер­минальных символов грамматики. Получаем: V = {"а","(","*",")","{ ">"}"}•

Шаг 3. Рассматриваем множество правил грамматики.

Для правил S -> Е) | К} имеем 5(Е,")") = {S}: 5(К,"}") = {S}.

Для правила Е ->• С* имеем 8(С,"*") = {Е}.

Для правил С -» D* | Са | С{ | С} | С( | С* | С) имеем 5(D,"*") = {С}: 5(С."а") = {С}; 5(С,"{") = {С}: 5(С,"}") = {С}; 5(С."(") = {С}: 8(С,"*") = {Е.С}; 8(С,"Г) = {С}.

Для правила D -> ( имеем 5(Н,"(") = {D}.

Для правил К -+ { | Ка | К( | К* | К) | К{ имеем 5(Н,"{") = {К}: 5(К,"а") = {К}: 5(К,"(") = {К}; 8(К,"*") = {К}; 5(К,")") = {К}: 8(К."{") = {К}.

Шаг 4. Начальным состоянием автомата является состояние q0 = Н.

Шаг 5. Множеством конечных состояний автомата является множество F = {S}.

Выполнение алгоритма закончено.

В итоге получаем автомат M({S.E.CD,К,Н}, {"а","(","*",")","{"."}"}. 8, Н, {S}) с функцией переходов:

 

8(Н.'

{

') " {<}

5(Н.'

(

') = {0}

5(К,'

а

') = {<}

6(К.'

(

') = {К}

5(К,'

*

') - {к}

5(К.'

)

') = (к}

5СК.'

{

') - {к}

5(К.'

}

') - {S}

5(D.'

*

') ■ (С}

8(С

а

') - {С}

6(С

{

') ■ {С}

8(С.'

}

') - {С}

8(С

(

') - {С}

8(С.'

*

') = {Е.С}

 

5(С.")") 5(1,"О")

{С} {S}

Граф переходов этого автомата изображен на рис. 10.7.

а, (,*,)ДЛ

Рис. 10.7. Недетерминированный КА для языка комментариев в Borland Pascal

Это недетерминированный конечный автомат, поскольку существует состояние, в котором множество, получаемое с помощью функции переходов по одному и тому же символу, имеет более одного следующего состояния. Это состояние С и функция 8(0,"*") - {Е,С}.

Моделировать поведение недетерминированного КА — непростая задача, поэто­му можно построить эквивалентный ему детерминированный КА. Полученный таким путем КА можно затем минимизировать.

В результате всех преобразований получаем детерминированный конечный ав­томат M'({S.E, CD. К, Н},{"а", ■•(»,•'*",")","{". "}"}.5',H.{S}) с функцией переходов:

Граф переходов этого автомата изображен на рис. 10.8.

а,(,Ш Рис. 10.8. Детерминированный КАдля языка комментариев в Borland Pascal

На основании этого автомата можно легко построить распознаватель. В данном случае мы можем получить распознаватель для двух типов комментариев языка программирования Borland Pascal, если учесть, что а может означать любой ал­фавитно-цифровой символ, кроме символов (, *, ), {, }.

Свойства регулярных языков

Свойства регулярных языков

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

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

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

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

□     пересечения;

□     объединения;

□     дополнения;

□     итерации;

□     конкатенации;

□     гомоморфизма (изменения имен символов и подстановки цепочек вместо сим­волов).

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

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

Проблема эквивалентности. Даны два регулярных языка Lt(V) и L2(V). Необхо­димо проверить, являются ли эти два языка эквивалентными. Проблема принадлежности цепочки языку. Дан регулярный язык L(V) и цепочка символов cteV*. Необходимо проверить, принадлежит ли цепочка данному языку. Проблема пустоты языка. Дан регулярный язык L(V). Необходимо проверить, является ли этот язык пустым, то есть найти хотя бы одну цепочку а^Х, такую что aeL(V).

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

Для регулярных грамматик также разрешима проблема однозначности — доказа­но, что для любой регулярной грамматики можно построить эквивалентную ей однозначную регулярную грамматику. Это очевидно, поскольку для любой регу­лярной грамматики можно однозначно построить регулярное выражение, опре­деляющее заданный этой грамматикой язык.

Лемма о разрастании для регулярных языков

Иногда бывает необходимо доказать, является или нет некоторый язык регуляр­ным. Конечно, можно пойти путем поиска определения для цепочек заданного языка через один из рассмотренных выше способов (регулярные грамматики, ко­нечные автоматы и регулярные выражения). Если для этого языка хотя бы один из способов будет определен, следовательно, язык является регулярным (и на основании одного найденного способа определения языка можно найти осталь­ные). Но если не удается построить определение языка ни одним из этих спосо­бов, то остается неизвестным: то ли язык не является регулярным, то ли просто не удалось найти определение для него.

Однако существует простой метод проверки, является или нет заданный язык регулярным. Этот метод основан на проверке так называемой леммы о разраста­нии языка. Доказано, что если для некоторого заданного языка выполняется лемма о разрастании регулярного языка, то этот язык является регулярным; если же лемма не выполняется, то и язык регулярным не является [6, т. 1]. Лемма о разрастании для регулярных языков формулируется следующим обра­зом: если дан регулярный язык и достаточно длинная цепочка символов, при­надлежащая этому языку, то в этой цепочке можно найти непустую подцепочку, которую можно повторить сколь угодно много раз, и все полученные таким спо­собом новые цепочки будут принадлежать тому же регулярному языку2.

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

2Если найденную подцепочку повторять несколько раз, то исходная цепочка как бы «раз­
растается» - отсюда и название «лемма о разрастании языков». Формально эту лемму можно записать так: если дан язык L, то 3 константа р > О, такая, что если asL и |а|>р, то цепочку а можно записать в виде а = 8ре, где О < |р| < р, и тогда а' = 8р!е, a'eL Vi > 0.

Используя лемму о разрастании регулярных языков, докажем, что язык L = {апЬл | п > 0} не является регулярным.

Предположим, что этот язык регулярный, тогда для него должна выполняться лемма о разрастании. Возьмем некоторую цепочку этого языка a = anbn и запи­шем ее в виде a = 5рБ. Если Реа+ или Peb+, то тогда для i = 0 цепочка 5р°е = 8е не принадлежит языку L, что противоречит условиям леммы; если же Реа+Ь+, то­гда для i = 2 цепочка 5p2s = 5рре не принадлежит языку L. Таким образом, язык L не может быть регулярным языком.

 

 

 

 

Контекстно-свободные языки

Распознаватели КС-языков. Автоматы с магазинной памятью

Определение МП-автомата

Контекстно-свободными (КС) называются языки, определяемые грамматиками типа G(VT,VN,P,S), в которых правила Р имеют вид: А-»р, где AeVN и peV, V=VTuVN.

Распознавателями КС-языков служат автоматы с магазинной памятью (МП-ав­томаты). В общем виде МП-автомат можно определить следующим образом:

RtaV.ZAqo.Zo.F), где Q, — множество состояний автомата; V — алфавит входных символов автома­та; Z — специальный конечный алфавит магазинных символов автомата (обычно он включает в себя алфавиты терминальных и нетерминальных символов грам­матики), VcZ; 8 — функция переходов автомата, которая отображает множество Qx(Vu{?i})xZ на конечное множество подмножеств P(QxZ'); qoeQ. — начальное состояние автомата; z0eZ — начальный символ магазина; FcQ, — множество ко­нечных состояний.

МП-автомат в отличие от обычного КА имеет стек (магазин), в который можно помещать специальные «магазинные» символы (обычно это терминальные и не­терминальные символы грамматики языка). Переход из одного состояния в дру­гое зависит не только от входного символа, но и от одного или нескольких верхних символов стека. Таким образом, конфигурация автомата определяется тремя

Конфигурация МП-автомата описывается в виде тройки (q,a,eo)eQxV*xZ*, кот< рая определяет текущее состояние автомата q, цепочку еще непрочитанных сил волов а на входе автомата и содержимое магазина (стека) со. Вместо а в конф! гурации можно указать пару (Р,п), где PeV* — вся цепочка входных символо а neNu{0}, п > 0 — положение считывающего указателя в цепочке.

Тогда один такт работы автомата можно описать в виде (q,aa,zco) -s- (q',a,yco), есл (q',y)e8(q,a,z), где q.q'eQ, aeVu{^}, aeV, zeZu{A.}, y,coeZ*. При выполнени такта (перехода) из стека удаляется верхний символ, соответствующий услови перехода, и добавляется цепочка, соответствующая правилу перехода. Первы символ цепочки становится верхушкой стека. Допускаются переходы, при коп рых входной