Установочные эксперименты

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

Вариант 1 A(S)={2,3,4}.

Вариант 2 A(S)={1,3,4}.

Вариант 3 A(S)={1,3,5}

5. Формальные грамматики

5.1. Языки и порождающие их грамматики

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

Большинство искусственных языком используют при построении предложений формальные, т.е. независимые от смысла, правила. Такие языки называются формальными.

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

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

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

например, русского. В естественных языках многие слова сложились в ходе длительного исторического развития и сложно указать правила, по которым они построены (например, согласно каким правилам слово шли – слово языка, а лши - нет).

Таким образом, формальные языки имеют следующие особенности:

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

• строгость правил и отсутствие исключений;

• конечное число правил.

Формальные языки, как и естественные, могут со временем изменяться. В отличие от естественных языков эти изменения происходят не постепенно, а путём появления новых версий. Различные версии могут рассматриваться как различные языки.

Пример 1. Рассмотрим язык, содержащий всевозможные десятичные целые числа. Для него алфавитом будет множество V = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, -, +}.

Пример 2. Пусть язык содержит всевозможные идентификаторы языка Паскаль. Его алфавитом будет множество V = {0,1,  , 9, a, b, c, , Z}.

Пример 3. Рассмотрим алфавит языка, содержащего всевозможные команды языка Паскаль. В его алфавит будут входить идентификаторы Паскаля, имена меток, специальные слова, типа DO, GOTO, IF, ENDIF и т.п.

Система правил, в соответствии с которыми можно строить «правиль-ные» последовательности «букв», представляет собой синтаксис языка.

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

Вторым аспектом является семантика языка. Слово «семантика» происходит от древнегреческих слов «Sema» – «знак, знамение» и «SemanticoS» — «обозначающий».

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

Проверка семантической правильности фразы языка невозможна в рамках грамматики языка, необходимо связать фразы языка с миром, который этот язык описывает. Рассмотрим в качестве примера фразы русского языка с однородными членами предложения. Формально пред-ложения «шел снег» и «шли студенты» можно объединить в одно пред-ложение «шли два студента и снег». Но с точки зрения семантики пред-ложение неверное, так как слово «шел» имеет разный смысл для снега и человека.

Третьим аспектом является прагматика языка. Оно произошло от древнегреческих слов «pragma» — «дело, действие» и «pragmateia» — «деятельность».

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

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

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

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

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

3. указанием способа порождения слов (заданием грамматики языка).

Первый способ на практике не применяется, так как большинство языков содержит бесконечное число слов и перечислить, например, множество всех правильных программ на языке PaScal невозможно. Можно, правда, некоторые простые формальные языки перечислить, прибегая к математическим определениям множеств. Например, запись L={{0, 1}={0n 1n , n≥1}} задает язык, содержащий всевозможные двоичные слова, содержащие одинаковое количество символов 0 и 1. Однако этот способ стоит ближе к третьему способу.

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

Третий способ предполагает описание грамматики языка.

Символы языка будем далее обозначать строчными буквами латинского алфавита, например, V={a,b,c,d}. Рассмотрим, как в формальных языках задаются правила.

Для описания правил вводится множество вспомогательных символов. Эти символы называют ещё нетерминальными. Они образуют вспомогательный (нетерминальный) алфавит языка, который обозначим как N. Если элементы из N записаны как слова (т.е. состоят из более чем одного символа), то их принято заключать в угловые скобки. Обозначим символы нетерминального языка строчными буквами латинского алфа-вита. Например, N={A,B,C}. Ясно, что множества V и N не пересекаются.

Пример 4. Для языка из примера1 в качестве вспомогательных символов могут быть приняты слова {<число>, <знак>, <цифра>, <модуль>}.

Один из нетерминальных символов принят для обозначения того, что является словом языка. Для примера1 это будет слово <число>, для примера 3 –слово <команда>. этот символ принято называть целью языка или его аксиомой. Обозначим его как S.

Объединим два алфавита V и N и обозначим его как U.

Т огда правила формального языка можно описать в виде p: , где  и  некоторые слова из алфавита U, причём слово  содержит хотя бы один символ вспомогательного словаря.

Множество правил обозначим как P={p1, p2, pr}.

Символ стрелка трактуется как "заменить".

Пример 5. Для языка из примеров 1 и 4 правила могут иметь вид. p1: <число> <знак> <модуль>, p2: <знак>+, p3: <знак>-, p4:<модуль><цифра>, p5:<модуль> <цифра><модуль>, p6:<цифра>0, p7:<цифра>1, , p14:<цифра>9.

Для приведённого примера правилу p1 сопоставляется фраза: символ <число> заменить двумя символами - <знак> и <модуль>.

Если слева от стрелки в нескольких правилах стоят одинаковые слова, то эти правила можно объединить. При этом справа слова объединяются через символ  (читается как ИЛИ). Так в последнем примере правила с 6 по 14 можно представить одним правилом

p6: <цифра> 0  1 2 3 4 5 6  7  8  9 . (читается как "нетерминал <цифра > заменить на 1, или 2, или 3, или , или 9").

Иногда в формальных грамматиках для описания правил используют символ «::=», который трактуется как « это есть». Такая запись называется нотацией Бекуса-Наура.

Если записать p2 в виде нотации Бекуса-Наура

p2: <число>::<знак ><модуль>

то этой записи будет соответствовать фраза: «<число> это есть <знак> и <модуль>.

Одним из первых языков программирования высокого уровня, описанным формально через нотации Бекуса-Наура (то есть полно и строго), был АЛГОЛ. Язык ФОРТРАН, который появился немного раньше АЛГОЛА, был описан на естественном (английском) языке, и это описание было не строгим.