• Tutorial

Мотивация

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

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

Формальные языки

Чтобы лучше разобраться в том, как именно изучаются формальные языки, необходимо сначала понять, в чем заключаются особенности математических методов изучения. Согласно Колмогорову и др. (Александров А.Д., Колмогоров А.Н., Лаврентьев М.А. Математика. Ее содержание, методы и значение. Том 1. М.: Издательство Академии Наук СССР, 1956.), математический метод, к чему бы он ни применялся, всегда следует двум основным принципам:

1. Обобщение (абстрагирование). Объекты изучения в математике - это специальные сущности, которые существуют только в математике и предназначены для изучения математиками. Математические объекты образуются путем обобщения реальных объектов. Изучая какой-нибудь объект, математик замечает только некоторые его свойства, а от остальных отвлекается. Так, абстрактный математический объект «число» может в реальности обозначать количество гусей в пруду или количество молекул в капле воды; главное, чтобы о гусях и о молекулах воды можно было
   говорить как о совокупностях. Из такой «идеализации» реальных объектов следует одно важное свойство: математика часто оперирует бесконечными совокупностями, тогда как в реальности таких совокупностей не существует.
2. Строгость рассуждений. В науке принято для выяснения истинности того или иного рассуждения сверять их результаты с тем, что существует в действительности, т.е. проводить эксперименты. В математике этот критерий проверки рассуждения на истинность не работает. Поэтому выводы не проверяются экспериментальным путем, но принято доказывать их справедливость строгими, подчиняющимися определенным правилам, рассуждениями. Эти рассуждения называются доказательствами и доказательства служат единственным способом обоснования верности того или иного утверждения.

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

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

Алфавит представляет собой конечное непустое множество элементов. Эти элементы будем называть символам. Для обозначения алфавита обычно будем использовать латинское V, а для обозначения символов алфавита - начальные строчные буквы латинского алфавита. Например, выражение V = {a,b} обозначает алфавит из двух символов a и b.

Цепочка представляет собой конечную последовательность символов. Например, abc - цепочка из трех символов. Часто при обозначении цепочек в символах используют индексы. Сами цепочки обозначают строчными символами конца греческого алфавита. Например, omega = a1...an - цепочка из n символов. Цепочка может быть пустой, т.е. не содержать ни одного символа. Такие цепочки будем обозначать греческой буквой эпсилон.

Наконец, формальный язык L над алфавитом V - это произвольное множеств цепочек, составленных из символов алфавита V. Произвольность здесь означает тот факт, что язык может быть пустым, т.е. не иметь ни одной цепочки, так и бесконечным, т.е. составленным из бесконечного числа цепочек. Последний факт часто вызывает недоумение: разве имеются реальные языки, которые содержат бесконечное число цепочек? Вообще говоря, в природе все конечно. Но мы здесь используем бесконечность как возможность образования цепочек неограниченной длины. Например, язык, который состоит из возможных имен переменных языка программирования C++, является бесконечным. Ведь имена переменных в C++ не ограничены по длине, поэтому потенциально таких имен может быть бесконечно много. В реальности, конечно, длинные имена переменных не имеют для нас особого смысла т.к. к концу чтения такого имени уже забываешь его начало. Но в качестве потенциальной возможности задавать неограниченные по длине переменные, это свойство выглядит полезным.

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

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

Назначение грамматики - задание языка. Это задание обязательно должно быть конечным, иначе человек не будет в состоянии эту грамматику понять. Но каким образом, конечное задание описывает бесконечные совокупности? Это возможно только в том случае, если строение всех цепочек языка основано на единых принципов, которых конечное число. В примере выше в качестве такого принципа выступает следующий: «каждая цепочка языка начинается с символов a, за которыми идет столько же символов b». Если язык представляет собой бесконечную совокупность случайным образом набранных цепочек, строение которых не подчиняется единым принципам, то очевидно для такого языка нельзя придумать грамматику. И здесь еще вопрос, можно или нет считать такую совокупность языком. В целях математической строгости и единообразия подхода обычно такие совокупности языком считают.

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

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

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

• Распознающие грамматики. Такие грамматики представляют собой устройства (алгоритмы), которым на вход подается цепочка языка, а на выходе устройство печатает «Да», если цепочка принадлежит языку, и «Нет» - в противном случае.
• Порождающие грамматики. Этот вид устройств используется для порождения цепочек языков по требованию. Образно говоря, при нажатии кнопки будет сгенерирована некоторая цепочка языка.
• Перечисляющие грамматики. Такие грамматики печатают одну за другой все цепочки языка. Очевидно, что если язык состоит из бесконечного числа цепочек, то процесс перечисления никогда не остановится. Хотя, конечно его можно остановить принудительно в нужный момент времени, например, когда будет напечатана нужная цепочка.

Окрестностные грамматики

В качестве примера рассмотрим язык A = {a+a, a+a+a, a+a+a+a,...} . Этот язык представляет собой простейшую модель языка арифметических выражений, где роль чисел играет символ «a», а роль операций - символ "+". Составим для этого языка окрестностную грамматику. Зададим окрестности для символа «a». Символ «a» может встречаться в цепочках языка A в трех синтаксических контекстах: вначале, между двумя символами "+" и в конце. Для обозначения начала и конца цепочки введем псевдосимвол "#". Тогда окрестности символа «a» будут следующими: #a+, +a+, +a# . Обычно для выделения центра окрестности этот символ в цепочке подчеркивается (ведь в цепочке могут быть и другие такие символы, которые не являются центром!), здесь этого делать не будем за неимением простой технической возможности. Символ "+" встречается только между двух символов «a», поэтому для него задается одна окрестность, цепочка a+a .

Рассмотрим цепочку a+a+a и проверим, принадлежит ли она языку. Первый символ «a» цепочки входит в нее вместе с окрестностью #a+ . Второй символ "+" входит в цепочку вместе с окрестностью a+a . Подобное вхождение можно проверить и для остальных символов цепочки, т.е. данная цепочка принадлежит языку, как и следовало ожидать. Но, например, цепочка a+aa языку A не принадлежит, поскольку последний и предпоследний символы «a» не имеют окрестностей, с которыми они входят в эту цепочку.

Не всякий язык может быть описан окрестностной грамматикой. Рассмотрим, например, язык B, цепочки которого начинаются либо с символа «0», либо с символа «1». В последнем случае далее в цепочке могут идти символы «a» и «b». Если же цепочка начинается с нуля, то далее могут идти только символы «a». Нетрудно доказать, что для этого языка нельзя придумать никакой окрестностной грамматики. Легитимность вхождения символа «b» в цепочку обусловлена ее первым символом. Для любой окрестностной грамматики, в которой задается связь между символами «b» и «1» можно будет подобрать достаточно длинную цепочку, чтобы всякая окрестность символа «b» не доставала до начала цепочки. Тогда в начало можно будет подставить символ «0» и цепочка будет принадлежать языку A, что не отвечает нашим интуитивным представлениям о синтаксическом строении цепочек этого языка.

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

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

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

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

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

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

Элементарными лексическими единицами большинства языков программирования являются:

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

<служебные слова>: := AND ½ ARRAY ½ BEGIN ½ CASE ½ CONS ½ DIV ½ DOWNTO ½ DO ½ ELSЕ ½ END ½ FILE ½ FOR ½ FUNCTION ½ GOTO ½ IF ½ IN ½ LABEL ½ MOD ½ NIL ½ NOT ½ OF ½ OR ½ PACKED ½ PROCEDURE ½ PROGRAM ½ RECORD ½ REPEAT ½ SET½ THEN ½ TO ½ TYPE ½ UNTIL ½ VAR ½ WHILE ½ WITH ;

<специальные символы>: := + ½ - ½ * ½ / ½ = ½ < ½ > ½ <= ½ >= ½ [ ½ ] ½ (½) ½ _ ½:= ½ " ½ " ½ . ½ , ½: ½ ; ½ ¹ ½# ½$ ;

десятичные числа без знака.

В выражениях и предложениях формального языка, cодержащих лексемы и синтаксические переменные, лексемы всегда заключены в кавычки. Например, "BEGIN", "NOT", AND" и др.

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

Множество V N - счетно и конечно.

Элементарными синтаксическими переменными для языка программирования являются:

<блок > :: = <блок-операторов>½<блок-процедуры>½<блок-функции>½...;

<заголовок > ::= <заголовок-программы>½<заголовок-процедуры>½

<заголовок-функции>½...;

<идентификатор > ::= <идентификатор-программы>½<идентификатор-

переменной>½...;

<оператор > ::= <оператор-присваивания>½<оператор-ЕСЛИ>...;

<операция > ::= <операция-сложения>½<операция-умножения>

½<операция-отношения>½...;

и другие синтаксические переменные.

В языке Паскаль всего около 240 синтаксических переменных.

В выражениях и предложениях формального языка, содержащих синтаксические переменные, их заключают в угловые скобки. Например, "PROGRAM" <идентификатор-программы> ";" "BEGIN" <блок-операторов> "END" и др.

Объединение символов двух множеств V T и V N представляет множество символов формального языка, т.е.

V = V T ÈV N . (2)

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

Если каждый элемент множества V* обозначить строчной буквой греческого алфавита, то множество V* можно описать перечислением его элементов:

V* = { a ; b ; g ;... } (4)

Например,

a:= "PROGRAM"<идентификатор-программы>";"<блок>".";

b:= "CONST" <определение-константы> "; " ;

g:= "(" <идентификатор> { " , " <идентификатор> } ") " ;

где знак ":=" означает: "...присвоить значение...". Цепочка a ÎV* содержит пять символов множества V, цепочка b ÎV* - три символа и цепочка g Î V* - не менее трех символов, т.к. в языках программирования знак "{ .. }" означает многократное повторение выражения, заключенного в фигурные скобки, включая нуль раз.

Конструкция программы на любом языке программирования состоит, как правило, из двух частей: заголовка - <заголовок-программы> и тела программы - <блок>. В заголовке программы, начинающемся служебным словом "PROGRAM", ей присваивается имя (идентификатор), вслед за которым в круглых скобках задается перечень идентификаторов тех файлов, через которые программа взаимодействует с внешним миром. В теле программы должны следовать в определенном порядке разделы меток, констант, типов, переменных, процедур, функций и операторов. Так как разделы, предшествующие разделу операторов, носят описательный характер, то каждый из них может быть пустой цепочкой, а раздел операторов является основным и должен присутствовать в любой программе. Поэтому в последующих объяснениях <блок> содержит только описание операторов, т.е. исполняет функции <блока-операторов>.

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

Продукцию или правило подстановки записывают так:

где a - левая часть правила,

b - правая часть правила.

Если правил несколько,то их необходимо индексировать:

p i: a i::= b i , где i = 1;2;3;... (6)

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

a ÎV* \ e, где e - пустая цепочка. (7)

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

b ÎV * или b ÎV*\ V N . (8)

Пример 3 . Пусть даны несколько правил языка программирования Паскаль:

<программа> ::= <заголовок-программы> " ; "<блок>" . ";

<заголовок-программы> ::= "PROGRAM"<идентификатор-программы>;

<блок> ::= <раздел-операторов> | ...;

<раздел-операторов> ::= "BEGIN" <оператор> " END" ;

<оператор> ::= <оператор-присваивания> |...;

<оператор-присваивания> ::= <переменная> " := " <выражение>;

<выражение> ::= <терм> <операция-сложения> <терм> ;

<терм> ::= <множитель> <операция-умножения> <множитель>;

<множитель> ::= <переменная> ;

<переменная> ::= <идентификатор-переменной> ;

<операция-сложения> ::= " + " | " - " | "OR";

<операция-умножения> ::= " x " | " / " | "DIV" | "MOD" |"AND".

Синтаксической переменной <идентификатор-программы> присвоим какое-либо значение (например, "ALGEBRA"), т.е.

<идентификатор-программы>::= "ALGEBRA".

Cинтаксической переменной <идентификатор-переменной> также присвоим какое-либо значение, начинающееся с буквы (например," i "), т.е.

<идентификатор-переменной> ::= " i ".

Последовательность использования правил подстановки в процессе формирования цепочки терминальных и/или нетерминальных символов называют выводом. Поэтому эти же правила часто называют правилами вывода. Для указания процесса вывода используют знак "=>".

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

Пример 4 . а) Для начального символа <программа> (пример 3) исполнить левосторонний вывод:

<программа> => <заголовок-программы> ";" <блок> "." => "PROGRAM" <идентификатор-программы> ";" <блок> "." => "PROGRAM" "ALGEBRA" ";" <блок> "." => "PROGRAM" "ALGEBRA" ";" <раздел-операторов> "." => <оператор> "END" "." => "PROGRAM" "ALGEBRA" ";" "BEGIN" <оператор-присваивания> "END" "." => ."PROGRAM" "ALGEBRA" ";" "BEGIN" <переменная> ":= " <выражение> "END" "." => "PROGRAM" "ALGEBRA" ";" "BEGIN" <идентификатор-переменной> ":=" <выражение> "END" "." => "PROGRAM" "ALGEBRA" ";" "BEGIN" " i " ":=" <выражение> "END" "." => ..

b) Для начального символа <программа> (пример 3) исполнить правосторонний вывод:

<программа> => <заголовок-программы> ";" <блок> "." => <заголовок-программы> ";" <раздел-операторов> "." => <заголовок-программы> ";" "BEGIN" <оператор> "END" "." => <заголовок-программы> ";" "BEGIN" <оператор-присваивания> "END" "." => <заголовок-программы> ";" "BEGIN" <переменная> ":=" <выражение> "END" "." => ...

Cинтаксической переменной <выражение> может быть любое арифметическое, алгебраическое или логическое выражение. Так как содержание этого выражения не определено, то оба вывода остановились на этой синтаксической переменной. Остальные члены предложения <программа> представлены элементарными лексическими единицами текста программы.,

Пример 5 . Для cинтаксической переменной <выражение> (пример 3) выполнить левосторонний вывод:

<выражение> => <терм><операция-сложения><терм>=> <множитель> <операция-умножения><множитель><операция-сложения><терм> => <переменная><операция-умножения><множитель><операция-сложения> <терм>=> <идентификатор-переменной><операция-умножения> <множитель> <операция-сложения><терм> => "i" <операция-умножения> <множитель><операция-сложения><терм> => "i" "x" <множитель><операция-сложения><терм> => "i" "x" <переменная><операция-сложения><терм> => "i" "x" <идентификатор-переменной><операция-сложения><терм> => "i" "x" "i" <операция-сложения><терм> => "i" "x" "i" "+" <терм> => "i" "x" "i" "+" <множитель><операция-умножения><множитель> => "i" "x" "i" "+" <переменная> <операция-умножения><множитель> => "i" "x" "i" "+" <идентификатор-переменной><операция-умножения> <множитель> => "i" "x" "i" "+" "i" <операция-умножения> <множитель> => "i" "x" "i" "+" "i" "x" <множитель> "i" "x" "i" "+" "i" "x" <переменная> => "i" "x" "i" "+" "i" "x"<идентификатор-переменной> => "i" "x" "i" "+" "i" "x" "I".

Имя начальной синтаксической переменной языка, для которой дано множество правил вывода называют начальным символом и обозначают буквой J. Роль начального символа может исполнять любая синтаксическая переменная. Для текста программы начальной синтаксической переменной является <программа>. Для части текста программы - выражения - начальной синтаксической переменной является <выражение>.

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

G = á V T ; V N ;J ; P ñ , (9)

где V T = { a;b;c;... } - терминальные символы;

V N = { A;B;C;...} - нетерминальные символы;

JÎ Vn - начальный символ;

P = { p i |i = 1; 2; 3; ... } - синтаксические правила.

Множество правильных цепочек терминальных символов представляет выражения и предложения формального языка данной формальной грамматики L(G) :

L (G) = { a , b , g ,...½ a , b , g Î V *\ VN }. (10)

Текст программы, ограниченный разделителем ".", называют предложением, а часть текста, ограниченную разделителем ";" , - выражением.

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

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

Транскрипт

1 ПРИМЕРЫ ПОСТРОЕНИЯ ГРАММАТИК Порождающие грамматики служат для точного, формального задания языков. На практике часто ставится обратная задача: построить грамматику на основе некоторого числа примеров «правильных» цепочек языка и интуитивных представления о правильности некоторых языковых конструкций. Разработка грамматики это неформальная процедура, которой можно научиться на примерах. Рассмотрим задачу построения грамматик для всех языков в примере выше. Пример: ;. Порождающие грамматики разработаны для задания бесконечных языков. Для конечных языков построение порождающих грамматик является простым. Для этого языка грамматика имеет вид: :

2 Пример: ;. 1. Любая цепочка, порождаемая искомой грамматикой, имеет структуру:, где цепочка, состоящая только из символов, цепочка, состоящая только из символов, и количества символов в цепочках и равны. 2. При выводе цепочек удобно одновременно порождать и, и, тогда это требование будет выполнено автоматически. 3. Если одним из правил грамматики будет, то многократным его применением можно построить:

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

4 Пример: ;. 1. Структура любой цепочки языка, где цепочка, состоящая только из символов, цепочка, состоящая только из символов. 2. Поскольку количества символов в начале цепочек языка и в конце цепочек могут не совпадать, отдельные части структуры цепочек можно генерировать независимо. Для языка грамматика имеет вид: :

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

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

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

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

9 Определение: дерево называется деревом вывода (или деревом разбора) в КС-грамматике, если выполнены следующие условия: (1) каждая вершина дерева помечена символом из множества, при этом корень дерева помечен символом; листья - символами из; (2) если вершина дерева помечена символом, а ее непосредственные потомки - символами,..., где каждое, то - правило вывода в этой грамматике; (3) если вершина дерева помечена символом, а ее единственный непосредственный потомок помечен символом, то - правило вывода в этой грамматике.

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

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

12 : Грамматики такого вида называются автоматными грамматиками (А-грамматиками).

13 Определение: грамматики называются эквивалентными, если они порождают один и тот же язык. Грамматики (). и эквивалентные грамматики Утверждение: Любой язык может быть порожден бесконечным числом грамматик.

14 Пример: ; - множество цепочек с одинаковым количеством вхождений символов и. Очевидно, что,. Можно придумать различные грамматики, прождающие этот язык. Очевидно. Что каждая грамматика отражает некоторую глубинную идею порождения цепочек с указанными свойствами.

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

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

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

18 Аналогичные рассуждения по нетерминалу. Окончательно получаем грамматику: : Пример вывода: В этой грамматике возможен и другой вывод той же самой цепочки: Заметим, что грамматика - КС-грамматика.

19 :

20 Еще один пример грамматики, порождающей язык:

21 Пример:, бочных выражений. - множество правильных ско- Структуру скобочных выражений можно представить либо как конкатенацию двух стоящих рядом скобочных выражений, либо как вложенное в скобки, скобочное выражение. «Крайним частным случаем» является просто отсутствие скобок. :

22 :

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

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

25 Утверждение: Если грамматика используется для определения языка программирования, то она должна быть однозначной. В приведенном выше примере разные деревья вывода предполагают соответствие разным. Если договориться, что должно соответствовать ближайшему к нему, и подправить грамматику, то неоднозначность будет устранена: Проблема, порождает ли данная КС-грамматика однозначный язык (т.е. существует ли эквивалентная ей однозначная грамматика), является алгоритмически неразрешимой.

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

27 Пример: ; - арифметические выражения, в которых операнды обозначаются символом. Наиболее простая грамматика рассматривает арифметическое выражение либо как арифметическое выражение, взятое в скобки, либо как пару стоящих рядом арифметических выражений, соединенных знаком операции: : Канонический левый вывод цепочки имеет следующий вид: Представленная грамматика неоднозначна. в

28 Пример: ;. Цепочки языка - это две идентичные копии произвольной цепочки из символов и, разделенные маркером. 1. // Порождаются одновременно как терминал (остающийся на своем месте), так и соответствующий ему нетерминал, который надо перегнать вправо и превратить терминал только сразу после разделителя. В конце концов, можно превратить в разделитель. Если нетерминалы не менять местами при их движении вправо, то они в том же порядке и останутся перед превращением в соответствующие терминалы. 2., // Нетерминал вправо. перегоняется

29 3. 4. // Терминал теперь может стать на свое место сразу после, 5. // Нетерминал вправо. перегоняется // Терминал теперь может стать на свое место сразу после Заметим, что нетерминалы не могут при движении вправо перепрыгнуть друг друга. Только когда нетерминал уже пришел к разделительной границе, он может превратиться в терминал после нее. Вывод цепочки:

31 ПРИМЕРЫ ЯЗЫКОВ Пример: ;. Цепочки языка - состоят из двух несовпадающих цепочек над словарем, разделенных маркером. Примеры цепочек языка: Очевидно, что,. Пример: словоформы русского языка; Цепочки языка - русский язык. Например, «молодая красивая студентка мчалась галопом в карете по пыльной дороге», «от дорогу по телеге к».

32 ПРИМЕРЫ ЯЗЫКОВ Пример: ; - язык Паскаль. Определение языка как подмножества множества всех возможных цепочек над конечным словарем является общим и неконструктивным.

33 Современные языки программирования высокого уровня задаются порождающими грамматиками Хомского. Грамматики эти состоят из нескольких десятков (а иногда и сотен) правил. Существуют различные нотации описания правил грамматики: 1. Хомского, 2. Хомского-Шутценберже, 3. НФБН, 4. РФБН, 5. диаграммы Вирта.

34 ИЕРАРХИЯ ПОРОЖДАЮЩИХ ГРАММАТИК ХОМКОГО Тип Вид правил Название языка Неограниченные грамма- Рекурсивнотики перечислимый Свободные грамматики язык Контекстно-зависимые КЗ-язык грамматики КЗ-грамматики Контекстно-свободные КС-язык грамматики КС-грамматики Автоматные грамматики Автоматный Регулярные грамматики язык А-грамматики Название грамматики

35 В грамматиках типа 0 на левую и правую части правил не накладывается никаких ограничений. Цепочки и в правилах грамматики могут быть любыми. Единственное ограничение - левая часть не может быть пустой цепочкой. Общего алгоритма распознавания для этого типа грамматик не существует - это класс рекурсивноперечислимых языков. В грамматиках типа 1 правила имеют вид. Здесь - некоторый нетерминал, и произвольные цепочки, фактически образующие контекст, в котором нетерминал может быть заменен цепочкой.

36 Рассмотрим грамматику: Кроме правила все остальные продукции удовлетворяют ограничениям грамматик типа 1. Следовательно, в таком виде грамматика является грамматикой типа 0. Но это не значит, что язык является рекурсивно-пречислимым. Оказывается, что вид продукции можно представить тремя продукциями с эквивалентными возможностями:,. Очевидно, что последовательное применение этих продукций приведет к перестановке и. Причем это

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

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

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

40 В грамматиках типа 3 ограничения накладываются на правую часть продукций. Эти ограничения приводят к тому, что порождаемые языки этого типа являются автоматными, и распознающее их автоматическое устройство это конечный автомат. Для языков типа 3 существует очень эффективный (линейный по сложности) алгоритм синтаксического анализа, описывающий работу конечного автомата. Определение: язык L(G) является языком типа k, если его можно описать грамматикой типа k.

41 Соотношения между типами грамматик и языков: (1) каждый регулярный язык является КС-языком, но существуют КС-языки, которые не являются регулярными (например,). (2) каждый КС-язык является КЗ-языком, но существуют КЗ-языки, которые не являются КС-языками (например,). (3)каждый КЗ-язык является языком типа 0.

42 Примеры грамматик и языков. Замечание: если при описании грамматики указаны только правила вывода, то будем считать, что большие латинские буквы обозначают нетерминальные символы, - цель грамматики, все остальные символы - терминальные. 1) Язык типа 0: :) Язык типа 1:

43 :) Язык типа 2: :) Язык типа 3:, где цепочка не содержит двух рядом стоящих символов:

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

КС-грамматики Разбор цепочки - процесс построения вывода цепочки из цели грамматики G = (T, N, P,). Вывод цепочки T* из N в КС-грамматике G = (T, N, P,), называется: - левосторонним, если в нем каждая

Задание 6 Грамматики Ключевые слова 1:язык, регулярный язык, ДКА, НКА, алгебра регулярных выражений, грамматики, уравнения с регулярными коэффициентами. 1 Грамматики Одна из больших проблем науки, которую

Задание 10 LL-анализ Ключевые слова 1:язык, контекстно-свободный язык, магазинный автомат, грамматика, LL(k)-грамматика, LL(1)-анализатор, функции FIRST, FOLLOW. 1 Нисходящий и восходящий разбор Напомним

А. А. Вылиток Алгоритмы преобразования контекстно-свободных грамматик с помощью графов 1. Устранение бесполезных символов Рассмотрим пример контекстно-свободной грамматики c алфавитом терминальных символов

Формальные грамматики Основные понятия Алфавит - это конечное множество символов. Цепочка последовательность символов. Терминальная цепочка последовательность терминальных символов. Язык множество терминальных

Глава 4 КОНТЕКСТНО-СВОБОДНЫЕ ГРАММАТИКИ 4.1. Упрощение контекстно-свободных грамматик В этой главе мы опишем некоторые основные упрощения КС-грамматик и докажем несколько важных теорем о нормальных формах

22 Классификация грамматик и языков по Хомскому грамматики классифицируются по виду их правил вывода Четыре типа грамматик: тип 0, тип 1, тип 2, тип 3 Язык, порождаемый грамматикой типа k (k=0,1,2,3),

Московский государственный университет им. М.В. Ломоносова Факультет вычислительной математики и кибернетики И. А. Волкова, А. А. Вылиток, Т. В. Руденко Формальные грамматики и языки. Элементы теории трансляции

46 Приведенные КС-грамматики Символ x (T N) называется недостижимым в грамматике G=(T, N, P,), если он не появляется ни в одной сентенциальной форме этой грамматики. Символ А N называется бесплодным в

Московский государственный университет им. М. В. Ломоносова Факультет вычислительной математики и кибернетики И.А. Волкова, А.А. Вылиток, Т.В. Руденко Формальные грамматики и языки. Элементы теории трансляции

Теория конечных автоматов и формальных языков Матросов Александр Васильевич Цели и задачи Цель - знакомство слушателей с математическими моделями формальных языков: конечными автоматами и контекстносвободными

Лекция 2 Формальные языки и способы их задания Формальный язык Алфавит непустое конечное множество (символов) Σ = {a, c, f, h} Цепочка (слово) над алфавитом Σ конечная последовательность символов: α =

Глава 2 ГРАММАТИКИ 2.1. Мотивировка Имеется один класс порождающих систем, которые представляют для нас первейший интерес системы, называемые грамматиками. Первоначально понятие грамматики было формализовано

УДК 004.4"413 О структурировании синтаксических диаграмм С. З. Свердлов, А. А. Хивина Доказана теорема структурирования для синтаксических диаграмм, утверждающая, что произвольную синтаксическую диаграмму

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

А. А. Вылиток О регулярных языках Регулярные языки играют важную роль в математических теориях и в приложениях. К наиболее известным формализмам, описывающим регулярные языки, относятся: регулярные выражения,

Лекции по теории формальных языков Лекция 4. Контекстно-свободные грамматики и языки: определения и примеры. Лемма о накачке Александр Сергеевич Герасимов http://gas-teach.narod.ru Кафедра математических

207 - ТЕХНОЛОГИЧЕСКИЙ КОМПЛЕКС РАЗРАБОТКИ ЯЗЫКОВЫХ ПРОЦЕССОРОВ Б.К.Мартыненко Введение Многие проблемы применения ЗВМ для обработки текстовой информации представляются как проблемы спецификации и реализации

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

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

Задание 9 Приложение КС-грамматик для сжатия данных. Преобразования КС-грамматик-1 Ключевые слова 1:язык, контекстно-свободный язык, магазинный автомат, грамматика, морфизм, метод математической индукции.

Найдем критерий применимости РС-метод примени м, если и только если левый вывод (или дерево нисходящим способом) можно построить, начиная с начального символа S, так, что на каждом шаге вывода решение

ТЕОРИЯ АВТОМАТОВ И ФОРМАЛЬНЫХ ЯЗЫКОВ множество (алфавит) из m символов. Операция конкатенации (соединения) из символов получает цепочку символов. Эту операцию можно применить и к цепочкам. Пример: из символов

1 Теория формальных языков лектор: Вылиток Алексей Александрович (кафедра алгоритмических языков) Материалы лекций: http://cmcmsu.no-ip.info/special.courses/ Литература 2 1. Пентус А.Е., Пентус М.Р. Теория

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Государственное образовательное учреждение высшего профессионального образования Ульяновский государственный технический университет Системное программное обеспечение:

ЗАДАЧИ К ЧАСТИ I Задачи к главе I-1 Задача I-1.1. Функция K(i, j) (i j 1)(i j 2) j отображает упорядоченные пары целых 2 на целые. Найти обратные функции I и J с таким свойством, что I(K(i, j)) = i

Глава 5 МАГАЗИННЫЕ АВТОМАТЫ 5.1. Неформальное описание В этой главе мы рассмотрим простое устройство магазинный автомат 7 (pda pushdown automaton), которое адекватно классу КС-языков в том смысле, что

Глава 9 ОПЕРАЦИИ НАД ЯЗЫКАМИ 9.1. Замкнутость относительно элементарных операций В этой главе мы применяем операции объединения, конкатенации, обращения, замыкания и т.д. к языкам разных типов. Интересно

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ

Лекции по теории формальных языков Лекция 3. Автоматы с магазинной памятью. Грамматики Александр Сергеевич Герасимов http://gas-teach.narod.ru Кафедра математических и информационных технологий Санкт-Петербургского

Лекции по теории формальных языков Лекция 14. LR-анализ с неоднозначными грамматиками. Обработка синтаксических ошибок при LR-анализе. LR(k)-грамматики. Итоги Александр Сергеевич Герасимов http://gas-teach.narod.ru

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

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

Лекция 3 Распознавание формальных языков Метасинтаксис: EBNF Extended Backus-Naur Form - синтаксис для записи синтаксиса (КС-грамматики) левая часть = правая часть левая часть::= правая часть Принятые

Часть I: ЯЗЫКИ, ГРАММАТИКИ, АВТОМАТЫ Глава 1 ЯЗЫКИ ИХ ПРЕДСТАВЛЕНИЕ 1.1. Алфавиты и языки Приступая к изучению теории языков, прежде всего следует определить, что мы подразумеваем под термином язык. Энциклопедическое

Часть III Языки, грамматики, автоматы 137 Глава 10 Языки и конечные автоматы 10.1 Язык Дика Как мы знаем, правильные скобочные структуры перечисляются числами Каталана. Выпишем все правильные скобочные

Компьютерные науки и безопасность. 341 О ГЕНЕРАТОРЕ АНАЛИЗАТОРОВ ДЛЯ ГРАММАТИК ОСОБОГО ВИДА Конончук Д.О. e-mail: [email protected] Создание новых компиляторов и текстовых анализаторов является

Восходящий синтаксический анализ Восходящий синтаксический анализ соответствует построению дерева разбора для входной строки, начиная с листьев (снизу) и идя по направлению к корню (вверх) Алгоритм «сдвиг-свертка»

Лабораторная работа 1 Формальные грамматики и их свойства Цель работы: закрепить понятия «алфавит», «цепочка», «формальная грамматика» и «формальный язык», «выводимость цепочек», «эквивалентная грамматика»;

Лекции по теории формальных языков Лекция 6. Преобразования контекстно-свободных грамматик Александр Сергеевич Герасимов http://gas-teach.narod.ru Кафедра математических и информационных технологий Санкт-Петербургского

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

Билет 1 Задача 6A из списка. Задание языка с помощью формальных грамматик. Определение грамматики общего вида: алфавит метасимволов (нетерминалов), начальный метасимвол, правила грамматики, вывод цепочек

Задание 10 КС-языки: замкнутость и LL-анализ Ключевые слова 1:язык, контекстно-свободный язык, магазинный автомат, грамматика, метод математической индукции. 1 Лемма о накачке Одна из целей изучения леммы

Задание 7 Контекстно-свободные языки и магазинные автоматы Ключевые слова 1:язык, контекстно-свободный язык, магазинный автомат, грамматика, метод математической индукции. 1 МП-автоматы 1.1 Определения

Министерство образования и науки Украины Государственное высшее учебное заведение «Приазовский государственный технический университет» В. С. Молчанова, А. Г. Бурса ТЕОРИЯ ПРОГРАММИРОВАНИЯ Учебное пособие

46 Приведенные КС-грамматики Символ x (V T V N) называется недостижимым в грамматике G=(V T, V N, P, S), если он не появляется ни в одной сентенциальной форме этой грамматики. Символ А V N называется

Решения и критерии проверки ноябрьской контрольной по ТРЯП ФУПМ 2016 Разбалловка неуд удовл хорошо отлично 0 Σ 10 11 Σ 15 16 Σ 22 23 Σ 33 1: 1-7, 2: 8-10 3: 11-13, 4: 14-15 5: 16-18, 6: 19-20, 7: 21-22

Глава 7 МАШИНЫ ТЬЮРИНГА: ПРОБЛЕМА ОСТАНОВКИ, ЯЗЫКИ ТИПА 0 7.1. Универсальная машина Тьюринга В этой главе мы покажем, что существует машина Тьюринга U, которая по заданному коду произвольной машины Тьюринга

Лабораторная работа 2 Грамматики и конечные автоматы Цель работы: изучить методы и средства, используемые при построении лексических анализаторов, в основе которых лежат регулярные грамматики. Краткие

Московский физико-технический институт Факультет инноваций и высоких технологий Математическая логика и теория алгоритмов, осень 2017 Семинар 1: язык записи формальных утверждений Алфавитом называется

Http://vmcozet/ Кодирование ВЕ Алексеев Задача оптимального кодирования Побуквенное кодирование Пусть A a a a } и B b b b } два алфавита Побуквенное кодирование состоит в том что в кодируемом тексте слове

РЕГУЛЯРИЗАЦИЯ КОНТЕКСТНО-СВОБОДНЫХ ГРАММАТИК НА ОСНОВЕ ЭКВИВАЛЕНТНЫХ ПРЕОБРАЗОВАНИЙ СИНТАКСИЧЕСКИХ ГРАФ-СХЕМ Федорченко Людмила Николаевна Специальность 05.13.11 Математическое и программное обеспечение

117 Определение: Пусть T 1 и T 2 алфавиты. Формальный перевод это подмножество множества всевозможных пар цепочек в алфавитах T 1 и T 2: (T 1 * T 2 *). Назовем входным языком перевода язык L вх ()=

Лекции по теории формальных языков Лекция 5. Операции над контекстно-свободными языками. Контекстно-свободные языки и автоматы с магазинной памятью. Контекстно-свободные грамматики и языки программирования.

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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «САМАРСКИЙ ГОСУДАРСТВЕННЫЙ АЭРОКОСМИЧЕСКИЙ УНИВЕРСИТЕТ имени академика

Формируемая компетенция ФОНД ОЦЕНОЧНЫХ СРЕДСТВ ДЛЯ ПРОВЕДЕНИЯ ПРОМЕЖУТОЧНОЙ АТТЕСТАЦИИ ОБУЧАЮЩИХСЯ ПО ДИСЦИПЛИНЕ (МОДУЛЮ) Общие сведения 1. Кафедра Математики, физики и информационных технологий 2. Направление

Рабочая программа составлена на основании: 1) Государственного образовательного стандарта высшего профессионального образования по направлению подготовки 657100 (230400) «Прикладная матика» (регистрационный

Теория вычислительных процессов и структур Лекция 2. Стандартные схемы программ Содержание лекции Программа как объект исследования Стандартные схемы Класс стандартных схем Интерпретация схемы Программа

Одной из формальных систем является система подстановок или полусистема Туэ (по имени норвержского математика Акселя Туэ) , определяемая алфавитом А и конечным множеством подстановок вида:

где α i ,β i – слова, возможно и пустые в А, Þ – символ подстановки, ранее понимаемый нами как «влечет», «выводится».

В системе Туэ используются отношения вида:

понимаемые как пары подстановок:

α i Þ β i (левая);

β i Üα i (правая).

В полусистеме Туэ подстановка α i Þβ i интерпретируется как правило вывода R i . Используя эти полусистемы, американский математик Н. Хомский в 50-е годы сформировал и развил теорию так называемых формальных грамматик, являющихся их частным случаем .

Пусть V – непустое множество символов – алфавит (или словарь) и, тем самым, задано множество V * всех конечных слов в алфавите V. Формальный язык L в алфавите V – это произвольное подмножество V * . Так, если V содержит буквы русского языка, знаки препинания, символы пробелов и т.д., то V * – гипотетическое множество, включающее все произведения великой русской литературы (написанные и будущие).

В качестве символов могут также использоваться слова, математические знаки, геометрические образы и т.п.

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

Формальная грамматика – формальная система, исчисление.

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

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

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

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

Рассмотрим класс порождающих формальных грамматик .

Порождающей формальной грамматикой G называют четвёрку

G=,

где Т – конечное непустое множество конечных терминальных (основных) символов;

N – конечное непустое множество нетерминальных (вспомогательных) символов;

Р – конечное непустое множество правил вывода (продукций);

S – начальный символ.

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

N – нетерминальный словарь – набор вспомогательных символов, означающих классы исходных символов.

Конечное множество – есть полный словарь грамматики G.

Правило вывода – конечное непустое множество двухместных отношений вида φÞψ, где φ и ψ – цепочки в словаре V, символ Þ – «заменить на».

Цепочка β непосредственно выводима из цепочки α в грамматике G (обозначение αβ; индекс G опускается, если понятно, о какой грамматике идёт речь), если α=α 1 φα 2 , β=α 1 ψα 2 , {φÞψ}.

Цепочка β выводима из α, если существует последовательность Е 0 =α, Е 1 ,Е 2 ,…,Е n =β, такая, что " i =0,1,...,n-1 Е i =>Е i +1 .

Эта последовательность называется выводом β из α, а n – длиной вывода.

Выводимость β из α обозначается α=> n β (если нужно указать длину вывода).

Языком L(G), порождаемым грамматикой G, называется множество цепочек в терминальном словаре T, выводимых из S, где S – начальный символ, обозначающий класс языковых объектов, для которых предназначена данная грамматика. Начальный символ называют целью грамматики или её аксиомой.

Грамматики G и G 1 эквивалентны, если L(G)=L(G 1).

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

Пример 1 . Пусть грамматика задана следующим образом :

T-{a,b}, N-{S,A,B}, S-S,

P={1. SÞaB; 2.SÞbA; 3. AÞaS; 4. AÞbAA; 5. AÞa; 6.BÞbS; 7. BÞaBB; 8. BÞb}.

Типичные выводы предложений:

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

Граф такой порождающей грамматики изображен на рис. 125.

Рис. 125. Граф порождающей грамматики

Здесь a и b – конечные вершины (терминальные).

Пример 2 . Пусть грамматика задана следующим образом:

Т={<студент>, <прилежный>, <ленивый>, <выполняет>, <не выполняет>, <домашнее задание>};

N={<сказуемое>, <подлежащее>, <определение>, <дополнение>, <группа подлежащего>, <группа сказуемого>, <предложение>};

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

Очевидно, что последняя цепочка вывода является заключительной и представляет собой предложение естественного языка. Аналогично можно вывести цепочку <ленивый> <студент> <не выполняет> <домашнее задание>. Заметим, что в этом примере нетерминальными символами являются синтаксические категории.

Вывод можно также описать так называемым структурным деревом, изображенным на рис. 126.

Рис. 126. Структурное дерево вывода предложения

Грамматика может задаваться и так называемыми синтаксическими диаграммами Вирта – как в языке Паскаль, которые напоминают переключательные схемы, в которых последовательное соединение указывает цепочку, а параллельное – варианты цепочек – вместо символаï.

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

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

Грамматика типа 0 – это грамматика, в которой не накладывается никаких ограничений на правила вывода jÞy, где j и y могут быть любыми цепочками из V. Такая грамматика может быть реализована машиной Тьюринга. При этом состояние машины Тьюринга соответствуют нетерминальным (вспомогательным) символам, а символы на ленте – терминальным. Правила порождения цепочек описываются системой команд.

Грамматика типа 1 – это грамматика, все правила которой имеют вид aАbÞawb, где wÎТUN, А – нетерминальный символ. Цепочки a и b – контекст правил. Они не изменяются при его применении. Таким образом, в грамматиках типа 1 отдельный терминальный символ А переходит в непустую цепочку w (А можно заменить на w) только в контексте a и b. Грамматики типа 1 называют контекстными или контекстно-зависимыми.

Грамматика типа 2 – это грамматика, в которой допустимы лишь правила вида АÞa, где aÎТUN, т.е. a – непустая цепочка из V. Грамматики типа 2 называют бесконтекстными или контекстно-свободными. Современные алгоритмические языки описываются с помощью контекстно-свободных грамматик .

Грамматика типа 3 – имеют правила вида АÞaB, либо AÞb, где А,ВÎN; a,bÎT.

Здесь A,B,a,b – одиночные символы (не цепочки) соответствующих словарей. Языки, которые задаются грамматиками этого типа, называются автоматными или регулярными.

При этом используется язык регулярных выражений (регулярный язык) вида:

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

Рассмотрим пример задания конечным автоматом регулярного языка :

X={0,1} – множество входных символов;

Y={S,A,B,q k } – множество внутренних состояний, q k – конечное состояние, S – начальное состояние.

Иногда рассматривают несколько конечных состояний и объединяют их во множество F. В данном случае F={q k }.

j: функция переходов – недетерминированная:

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

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

Соответствующая порождающая грамматика имеет вид:

Соответствующий регулярный язык L= :

0, 010, 01010,...

Теория формальных грамматик используется при построении компиляторов. Компилятор проводит разбор исходной программы. При этом определяется, является ли заданная цепочка символов правильно построенным предложением, и, если это так, то восстанавливается её вид. Разбор или синтаксический анализ выполняется специальной программой – парсером (to parse – разбирать). Для решения этой задачи разработаны специальные программы, например, LEX и YACC.

В операционной системе UNIX имеются стандартные программы LEX и GREP – они построены на основе теории регулярных языков .

Программа LEX-осуществляет лексический анализ текста – разбивку текста в соответствии с определенным набором регулярных выражений.

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

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

В настоящее время в компьютерах применяются переводчики типа Promt, Magic Gooddy, Socrat Personal. Кроме того, используются и простые словари, типа.Context, Socrat Dictionary, МультиЛекс.

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

В Японии некоторые фирмы уже приступили к продаже бытовых «говорящих» роботов, которые могут общаться с хозяином.

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

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

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

Теоремы Гёделя

В математической логике доказывается, что исчисление предикатов непротиворечиво – т.е. в нем невозможно одновременно вывести , и . Кроме того, в силу теоремы Гёделя о полноте исчисления предикатов общезначимая формула выводима в исчислении предикатов.

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

Итак, множество всех истинных высказываний логики высказываний перечислимо и разрешимо. Множество всех истинных высказываний логики предикатов перечислимо (ввиду его полноты), но неразрешимо (ввиду бесконечности предметной области).

В качестве еще одной формальной теории в математической логике рассматривается так называемая формальная арифметика, предложенная итальянским математиком Джузеппе Пеано (1858-1932 гг.) . Пеано ввел символы и операции Î, U, I и впервые излагал логику как математическую дисциплину. Впервые попытка сведения математики к логике была предпринята немецким математиком и логиком Готтлибом Фреге (1848-1925 гг.). Это он определил множество, как объем понятия. Он писал: «Арифметика есть часть логики и не должна заимствовать ни у опыта, ни у созерцания никаких основ доказательств». Знаменитый парадокс о множестве всех множеств – это противоречие в системе Фреге, выявленное Бертраном Расселом.

Гёдель доказал, что любая формальная теория Т, содержащая формальную арифметику, неполна: в ней существует замкнутая формула F, такая, что истинно, но ни F, ни не выводимы в Т. В соответствии со знаменитой теоремой Гёделя о неполноте, для любой непротиворечивой формальной теории Т, содержащей формальную арифметику, формула, выражающая непротиворечивость Т, недоказуема в Т.

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

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

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

Невозможность полной формализации содержательно определенных теорий – это не недостаток концепции, а объективный факт, неустранимый никакой концепцией.

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

НЕКЛАССИЧЕСКИЕ ЛОГИКИ

Л А Б О Р А Т О Р Н А Я Р А Б О Т А №1

Cоздание формальной грамматики и построение

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

ОСНОВНЫЕ СВЕДЕНИЯ

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

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

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

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

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

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

Синтаксис – внешнее представление предложений языка.

Семантика – смысловое содержание предложений языка.

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

Формальная грамматика – абстрактное обобщение грамматики естественных языков – рассматривает строки (цепочки) символов.

Формальная грамматика есть четверка

G = { V , V , P , S },

где V- алфавит терминальных символов, т.е. символов, которые могут входить в левые части правил (соответствует набору слов и знаков языка);

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

Р - набор порождающих правил вида

где  и  - цепочки терминальных и нетерминальных символов;

S - начальный символ грамматики (соответствует начальному понятию).

Грамматика G для любой цепочки    задает множество выводимых из нее цепочек, определяя их рекурсивно следующим образом: если  содержится в Р, то цепочка r =  непосредственно выводима из  (обозначается r), если  выводима из  и r , то r нетривиально выводима из  (  + r) ; если   + r или =r, то r выводима из  (=*r). Последо­вательность применения правил  1   2 ... r называется выводом цепочки , если  1 = S,  r =  .

Цепочка, выводимая из S, называется сентенциальной формой . Сентенциальная форма не содержащая нетерминальных символов, называется предложением . Множество предложений образует язык , порожденный грамматикой G (L(G)).

Формы Бэкуса-Науэ р а (БНФ)

Широко используемой формой записи правил грамматик являются формы Бэкуса-Науэра (БНФ).

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

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

Характерной особенностью языков программирования, так же как и естественных языков, является то, что в сложные синтаксические конструкции в качестве составных частей входят другие конструкции. Так, программа на языке TurboPascal является обычно блоком, который в свою очередь может включать в себя один или несколько внутренних блоков. Блок также является сложной конструкцией, включающей в себя описания, операторы; последние тоже имеют составные части и т.д. Таким образом, для того, чтобы написать программу, необходимо знать правила написания блоков и других конструкций, входящих в программу в качестве составных частей. Вторым классом объектов, используемых в формах Бэкуса, как раз и являются имена конструкций описываемого языка, или так называемые металингвистические переменные. Значение металингвистических переменных – это цепочки основных символов описываемого языка.

Каждая металингвистическая формула описывает правила построения некоторой конструкции языка и состоит из двух частей. В левой части находится металингвистическая переменная, обозначающая соответствующую конструкцию (нетерминальный (НТ) символ). Далее следует так называемая металингвистическая связка:: =, проставляемая вместо символа  и имеющая смысл глагола «быть». Она соединяет левую и правую части формулы. В правой части формулы указывается один или несколько вариантов построения конструкции, определенной в левой части. Каждый вариант представляет собой цепочку, состоящующую из металингвистических переменных и основных символов (терминальных(Т)). Для того, чтобы построить конструкцию, определяемую формулой, нужно выбрать некоторый вариант построения из правой части формулы и, используя соответствующие формулы вместо каждой металингвистической переменной некоторые цепочки основных символов. Варианты правой части формулы разделяются металингвистической связкой |, имеющей значение «или».

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

Пример формальной грамматики, записанной в формах Бэкуса-Науэра.

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

Грамматика G1 записи числа содержит следующие 13 правил:

(1) число::= чс

(2) чс::= чс цифра

(3) чс::= цифра

(4) цифра::= 0

(5) цифра::= 1

(6) цифра::= 2

(7) цифра::= 3

(8) цифра::= 4

(9) цифра::= 5

(10) цифра::= 6

(11) цифра::= 7

(12) цифра::= 8

(13) цифра::= 9

G1 = {{0,1,2,3,4,5,6,7,8,9}, {цифра, число, чс}, Р, число },

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

второе указанное множество – алфавит нетерминальных символов;

Р - 13 правил, указанных выше;

 число  - начальный символ грамматики.

Поскольку в формах Бэкуса-Науэра вариант “или” записывается знаком «|», то грамматику необходимо записать так:

число::= чс

чс::= чс цифра | цифра

цифра::= 0|1|2|3|4|5|6|7|8|9

Классификация Хомского

Грамматики можно классифицировать по виду их правил.

Существует четыре вида грамматик:

грамматика с фразовой структурой (на ней построены естественные языки);

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

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

   где  V, а  - цепочка в алфавите V V;

автоматные грамматики, где каждое правило имеет вид:

  х В или

  х, где

х  V, {,B}  V.

Язык L называется автоматным, контекстно-свободным, контекстно-зависимым или с фразовой структурой, если существует определяющая его грамматика G соответствующего типа, для которой L = L(G).