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

  • Tutorial

Мотивация

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Способ задания языка называет грамматикой этого языка. Таким образом, грамматикой мы называем любой способ задания языка. Например, грамматика L = {a^nb^n} (здесь n - натуральное число) задает язык L, состоящий из цепочек вида ab, aabb, aaabbb и т.д. Язык L представляет собой бесконечное множество цепочек, но тем не менее, его грамматика (описание) состоит всего из 10 символов, т.е. конечна.

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

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

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

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

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

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

В середине 60-х годов советский математик Юлий Анатольевич Шрейдер предложил простой способ описания синтаксиса языков на основе т.н. окрестностных грамматик. Для каждого символа языка задается конечное число его «окрестностей» - цепочек, содержащих данный символ (центр окрестности) где-то внутри. Набор таких окрестностей для каждого символа алфавита языка называется окрестностной грамматикой. Цепочка считается принадлежащей языку, задаваемому окрестностной грамматикой, если каждый символ этой цепочки входит в нее вместе с некоторой своей окрестностью.

В качестве примера рассмотрим язык 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) окрестностной грамматикой задано быть не может. Но, если визуализировать синтаксические отношения в цепочках языка, то для диаграмм отношений, в которые превращаются такие цепочки, можно придумать окрестностную грамматику.

Грамматика формальная

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

Термины

Порождающие грамматики

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

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

Итак, грамматика определяется следующими характеристиками:

Вывод

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

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

Типы грамматик

Терминальный алфавит:

Σ ={"0","1","2","3","4","5","6","7","8","9","+","-","*","/","(",")"}.

Нетерминальный алфавит:

{ ФОРМУЛА, ЗНАК, ЧИСЛО, ЦИФРА }

1. ФОРМУЛА ФОРМУЛА ЗНАК ФОРМУЛА (формула есть две формулы, соединенные знаком) 2. ФОРМУЛА ЧИСЛО (формула есть число) 3. ФОРМУЛА (ФОРМУЛА) (формула есть формула в скобках) 4. ЗНАК + | - | * | / (знак есть плюс или минус или умножить или разделить) 5. ЧИСЛО ЦИФРА (число есть цифра) 6. ЧИСЛО ЧИСЛО ЦИФРА (число есть число и цифра) 7. ЦИФРА 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 (цифра есть 0 или 1 или... 9)

Начальный нетерминал:

ФОРМУЛА

Вывод :

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

ФОРМУЛА (ФОРМУЛА) (ФОРМУЛА ) (ФОРМУЛА ЗНАК ФОРМУЛА ) (ФОРМУЛА ЗНАК ФОРМУЛА) (ФОРМУЛА + ФОРМУЛА) (ФОРМУЛА + ФОРМУЛА ) (ФОРМУЛА + ЧИСЛО ) (ФОРМУЛА + ЧИСЛО ) (ФОРМУЛА + ЦИФРА ) (ФОРМУЛА + ЦИФРА ) (ФОРМУЛА + 5 ) (ФОРМУЛА + 5) (ЧИСЛО + 5) (ЧИСЛО + 5) (ЧИСЛО ЦИФРА + 5) (ЧИСЛО ЦИФРА + 5) (ЦИФРА ЦИФРА + 5) (ЦИФРА ЦИФРА + 5) (1 ЦИФРА + 5) (1 ЦИФРА + 5) (1 2 + 5)

Аналитические грамматики

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

Источники

  • Гладкий А. В. Формальные грамматики и языки. - М.: Наука, 1973.
  • Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений . - Новосибирск: НГУ. - 1995. - 112 с.
  • Хомский Н., Миллер Дж. Введение в формальный анализ естественных языков // Кибернетический сборник / Под ред. А.А.Ляпунова и О.Б.Лупанова. - М.: Мир, 1965.

Wikimedia Foundation . 2010 .

Смотреть что такое "Грамматика формальная" в других словарях:

    - (в лингвистике) логическая система, или исчисление, задающая некоторое множество («правильных») цепочек (= конечных последовательностей), построенных из символов заданного конечного набора, называемого «алфавитом» или «основным… … Большая советская энциклопедия

    грамматика формальная - В лингвистике: логическая система, или исчисление, задающая некоторое множество (правильных) цепочек (= конечных последовательностей), построенных из символов заданного конечного набора, называемого алфавитом или основным (терминальным)… … Словарь лингвистических терминов Т.В. Жеребило

    Грамматика формальная - В лингвистике: логическая система, или исчисление, задающая некоторое множество («правильных») цепочек (= конечных последовательностей), построенных из символов заданного конечного набора, называемого «алфавитом» или «основным (терминальным)… … Общее языкознание. Социолингвистика: Словарь-справочник

    Грамматика (от греч. γράμμα «запись»), как наука, есть раздел языкознания, изучающий грамматический строй языка, закономерности построения правильных осмысленных речевых отрезков на этом языке (словоформ, синтагм, предложений, текстов). Эти … Википедия

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

    ФОРМАЛЬНАЯ ГРАММАТИКА. Грамматика, последовательно проводящая принцип изучения только форм языка и исключающая из своего состава все явления, не обозначенные формами языка. Ф. Г. противополагается т. н. логической (название неточное) грамматике,… … Литературная энциклопедия

    Генеративная лингвистика … Википедия

    У этого термина существуют и другие значения, см. Грамматика (значения). Грамматика (др. греч. γραμματική от γράμμα «буква») как наука является разделом языкознания, который изучает грамматический строй языка, закономерности построения… … Википедия

    См. грамматика формальная (в статье грамматика) … Словарь лингвистических терминов

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

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

Всякая ли фраза может быть переведена с одного языка на другой при заданном наборе правил и заданном объеме машинной памяти;

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

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

Появление трансляторов сделало проблему перевода центральной в построении общей теории вычислительных систем.

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

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

Независимо и параллельно развивалась общая теория алгоритмов как ветвь современной математики. Была установлена эквивалентность понятий «нормальный алгоритм Маркова», «общерекурсивная функция» и «машина Тьюринга», а тезис Чёрча связал эти три понятия с интуитивным представлением об алгоритме.

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

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

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

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

Эта теория возникла в 50-е годы в работах американского лингвиста

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

Дадим некоторые определения.

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

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

Словоформа или просто слово – это последовательность (цепочка) морфем.

Морфема – это мельчайшая грамматически значимая часть слова.

Например, слово «ведший» состоит из морфем вед+ ш+ий (корень, суффикс, окончание).

Словосочетание или предложение – это цепочка словоформ.

Грамматика языка – это конечное множество правил, определяющих этот язык.

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

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

Семантика языка – толкование этих правил, правила использования синтаксиса.

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

Первым и основным требованием к грамматике является следующее:

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

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

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

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

Классификация грамматик может быть представлена в следующем виде:

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

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

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

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

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

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

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

,

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

или основным словарем G.

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

Конечное непустое множество символов, называемых нетерминальным (вспомогательным) словарем G.

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

Элементы и называются соответственно нетерминальными и терминальными символами.

- словарь грамматики G.

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

Пустая цепочка обозначается , т.о. . Число членов этой цепочки назовём ее длиной и будем обозначать .

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

Операция конкатенации ассоциативна, но не коммутативна.
эквивалентно .

S – начальный символ грамматики .

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

P – правила грамматики или конечное множество цепочек вида j à y, где j и y - слова в словаре V и цепочка j cодержит по крайней мере один символ из словаря Vн.

Конечое двуместное отношение à интерпретируется как “заменить j на y”.

Это отношение несимметрично и нерефлексивно.

Цепочка вида j à y называется правилами грамматики или правилами подстановки, а множество P – схемой грамматики .

Если задана грамматика , то будем говорить:

Цепочка w’ получается непосредственно из цепочки w применением правила j à y, если w=x1jx2 , w"=x1jx2 и {j à y}ÎP.

Последовательность цепочки j=j0, j1, j2 … , jn = y (n³1) ,

где 0 £ i £ n и j - есть вывод цепо чки y, если для каждого i ji+1 следует из ji .

Наличие j - вывода цепочки y будем обозначать: j => y.

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

Цепочка y выводится из цепочки j, если она получается из j примененных некоторых правил грамматики G .

Вывод цепочки y считается законченным , если не следует цепочка, которая следует из j.

Цепочка, состоящая только из терминальных символов, называется терминальной цепочкой .

Множество цепочек, выводимых в грамматике G, называется языком, порожденным этой грамматикой, и обозначается L(G).

Язык L(G) называется терминальным, если L-множество терминальных цепочек грамматики G.

Условимся:

Первыми строчными латинскими буквами a, b, c, … обозначать элементы терминального словаря Vт,

Прописными латинскими буквами A, B, C, … - элементы нетерминального словаря Vн,

Строчными греческими буквами a, b, … - элементы общего словаря V.

Предложения, составные из этих предложений будем обозначать последними буквами этих алфавитов, т. е. x1 , y1 , … - предложения составляемые из элементов Vт, X, Y, … - предложения, составляемые из элементов Vн, w, j, y , … - предложения составляемые из элементов общего словаря V.

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

Рассмотрим пример:

G=(Vт, Vн,P,S), где Vт={a, b}; Vн={A,B,C}; S=C; P={Càab, CàaCb}.

Пусть w=aCb, w"=aaCbb. Цепочка w" непосредственно выводится из w применением одного правила.

j-вывод: aCb, aaCbb, aaaCbbb, aaaabbbb (терминальная).

Длина вывода = 3.

Из примера видно, что порождающая грамматика не является алгоритмом.

Правила подстановки грамматики – это не последовательность предписаний, а совокупность разрешений.

Это означает следующее:

Правило j à y понимается как “ j может быть заменено на y”, а не “должно быть заменено”;

Порядок применения правил произволен, а в алгоритме был бы задан точный порядок.

Две грамматики G1 и G2 называются слабо эквивалентными , если они порождают один и то же язык L(G1)= L(G2), то есть совпадает множество порождаемых ими фраз.

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

Основным объектом применения таких формальных грамматик являются не произвольные грамматики, а грамматики некоторых специальных типов.

Выделение этих типов производится по виду правил.

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

Грамматика называется грамматикой типа 0 в тех случаях, когда не накладывается никаких ограничений на правила j à y, где j и y могут быть любыми цепочками из словаря V.

Грамматика называется грамматикой типа 1 , если в системе Р правила j à y удовлетворяют условию j = j1Аj2 y = j1wj2,

j, y, w - цепочки из словаря V.

Таким образом, нетерминальный символ А переходит в непустую цепочку w в контексте j1 и j2 (j1 и j2 могут быть пустыми цепочками).

Грамматики типа 1 называют контекстными .

Грамматика называется грамматикой типа 2 – бесконтекстной , если в системе правил Р допустимы лишь правила вида:

где А – нетерминальный символ,

w - непустая цепочка из V.

Грамматика называется грамматикой типа 3 , когда допустимы лишь правила вида:

где w = аВ либо w = а.

Веденные классы могут быть разбиты на подклассы, но об этом немного позже

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

10.1. Алфавит

Изучение любого языка человек начинает с азбуки. В формальной грамматике язык определяется вне зависимости от его смысла. Более того, один и тот же язык может формироваться несколькими грамматиками! Это как в школе - не так важен результат (который можно прочитать в конце учебника), как его получение - зафиксированное в тетради решение задачи. Поэтому подойдем к определению алфавита также формально.

О п р е д е л е н и е . Алфавит - это непустое конечное множество элементов.

В "классическом" языке алфавит - это набор литер. В фонетике - набор издаваемых человеком звуков речи. В музыке - это набор нот, и т.д.

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

Всякая конечная последовательность символов алфавита называется словом, или, более профессионально, цепочкой. Цепочками, состоящими из символов {a, b, c}, будут следующие последовательности: a, b, c, aa, ab, bc, ac , bb, abba и другие. Также допускается существование пустой цепочки Л - полное отсутствие символов. Важен также порядок следования символов в цепочке. Так, цепочки ab и ba - разные цепочки. Далее заглавные латинские буквы будут использованы как переменные и символы, а строчные латинские буквы будут обозначать цепочки. Например:

X = SVT Листинг 10.1.

цепочка, состоящая из символов S , V и T , и именно в этом порядке.

О п р е д е л е н и е . Длиной цепочки называется число символов в этой цепочке. Она обозначается как |x| . Например: |Л| = 0, |A| = 1, |BA| = 2, |ABBA| = 4 .

Если x и y являются цепочками, то их конкатенацией будет цепочка xy . От перестановки цепочек при конкатенации результат меняется (как и в теории групп). Если z = xy - цепочка, то x - голова, а y - хвост цепочки. Если нам безразлична голова цепочки, мы будем обозначать:

Z = … x Листинг 10.2.

а если нам безразличен хвост, мы будем писать:

Z = x … Листинг 10.3.

О п р е де л е н и е . Произведение двух множеств цепочек определяется как конкатенация всех цепочек, входящих в эти множества . Например, если множество A = {a, b}, а B = {c,d} , то:

AB = {ac, ad, bc, bd} Листинг 10.4.

В произведении множеств, как и при конкатенации, порядок множителей существенен.

И при конкатенации цепочек, и при перемножении множеств цепочек истинным остается ассоциативный закон, записывающийся как:

Z = (ab)c = a(bc) = abc Листинг 10.5.

D = (AB)C = A(BC) = ABC Листинг 10.6.

И, наконец, определим степень цепочки. Если x - непустая цепочка, то x 0 = {Л}, x 1 = x, x 2 = xx, x n = x(x) (n-1) . То же самое обстоит и со степенью множеств.

10.2. Терминальные и нетерминальные символы

Понятие терминальных и нетерминальных символов тесно связано с понятием правила подстановки (или продукции). Дадим его определение .

О п р е д е л е н и е . Продукцией, или правилом подстановки, называется упорядоченная пара (U, x ), записываемая как:

U::= x Листинг 10.7.

где U - символ, а x - непустая конечная цепочка символов .

Символы, встречающиеся только в правой части, называются терминальными символами . Символы, встречающиеся и в левой, и в правой части правил, называются нетерминальными символами, или синтаксическими единицами языка. Множество нетерминальных символов обозначается как VN, а терминальных символов - VT.

Примечание . Данное определение терминальных и нетерминальных символов истинно для КС- грамматик и A- грамматик (см. раздел 10.4.3).

О п р е д е л е н и е . Грамматикой G[Z] называют конечное, непустое множество правил, содержащее нетерминальный символ Z хотя бы один раз на множестве правил. Символ Z называют начальным символом. Далее мы все нетерминальные символы будем обозначать как <символ>.

[Пример 01]

Грамматика : "число"

<число> ::= <чс> <чс> ::= <цифра> <чс> ::= <чс><цифра> <цифра> ::= 0 <цифра> ::= 1 <цифра> ::= 2 <цифра> ::= 3 <цифра> ::= 4 <цифра> ::= 5 <цифра> ::= 6 <цифра> ::= 7 <цифра> ::= 8 <цифра> ::= 9

Дадим еще определение :

О п р е д е л е н и е . Цепочка v непосредственно порождает цепочку w , если:

V = xy, а w = xuy Листинг 10.8.

где ::= u - правило грамматики . Это обозначается как v => w . Мы также говорим, что цепочка w непосредственно выводима из v . При этом цепочки x и y могут быть пустыми.

О п р е д е л е н и е . Говорят, что v порождает w , или w приводится к v , если существует конечная цепочка выводов u0, u1, …, u[n] (n > 0) , такая, что

V = u0 => u1 => u2 => … => u[n] = w Листинг 10.9.

Эта последовательность называется выводом длиной n , и обозначается v =>+ w . И, наконец, пишут:

V =>* w, если v => w или v =>+ w Листинг 10.10.

10.3. Фразы

О п р е д е л е н и е . Пусть G[Z] - грамматика , x - цепочка. Тогда x называют сентенциальной формой, если =>* x . Предложение - это сентенциальная форма, состоящая только из терминальных символов . Язык - это подмножество множеств всех терминальных цепочек.

О п р е д е л е н и е . Пусть G[Z] - грамматика . И пусть w = xuy - сентенциальная форма. Тогда u называется фразой сентенциальной формы w для нетерминального символа , если:

Z =>* xy и =>+ u Листинг 10.11.

Z =>* xy и => u Листинг 10.12.

то цепочка u называется простой фразой.

Следует быть осторожным с термином "фраза". Тот факт, что =>+ u (цепочка u выводима из ) вовсе не означает, что u является фразой сентенциальной формы xy; необходима также выводимость цепочки xy из начального символа грамматики Z .

В качестве иллюстрации фразы рассмотрим [Пример 01] сентенциальную форму <чс>1 . Значит ли это, что символ <чс> является фразой, если существует правило: <число> ::= <чс> ? Конечно же, нет, поскольку невозможен вывод цепочки: <число><1> - из начального символа: <число> . Какие же фразы сентенциальной формы <чс>1 ? Рассмотрим вывод :

<число> => <чс> => <чс><цифра> => <чс><1> Листинг 10.13.

Таким образом,

<число> =>* <чс> и <чс> =>+ <чс>1 Листинг 10.14.

1. Самостоятельные части речи:

  • существительные (см. морфологические нормы сущ.);
  • глаголы:
    • причастия;
    • деепричастия;
  • прилагательные;
  • числительные;
  • местоимения;
  • наречия;

2. Служебные части речи:

  • предлоги;
  • союзы;
  • частицы;

3. Междометия.

Ни в одну из классификаций (по морфологической системе) русского языка не попадают:

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

Морфологический разбор существительного

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

План морфологического разбора существительного

"Малыш пьет молоко."

Малыш (отвечает на вопрос кто?) – имя существительное;

  • начальная форма – малыш;
  • постоянные морфологические признаки: одушевленное, нарицательное, конкретное, мужского рода, I -го склонения;
  • непостоянные морфологические признаки: именительный падеж, единственное число;
  • при синтаксическом разборе предложения выполняет роль подлежащего.

Морфологический разбор слова «молоко» (отвечает на вопрос кого? Что?).

  • начальная форма – молоко;
  • постоянная морфологическая характеристика слова: среднего рода, неодушевленное, вещественное, нарицательное, II -е склонение;
  • изменяемые признаки морфологические: винительный падеж, единственное число;
  • в предложении прямое дополнение.

Приводим ещё один образец, как сделать морфологический разбор существительного, на основе литературного источника:

"Две дамы подбежали к Лужину и помогли ему встать. Он ладонью стал сбивать пыль с пальто. (пример из: «Защита Лужина», Владимир Набоков)."

Дамы (кто?) - имя существительное;

  • начальная форма - дама;
  • постоянные морфологические признаки: нарицательное, одушевленное, конкретное, женского рода, I склонения;
  • непостоянная морфологическая характеристика существительного: единственное число, родительный падеж;
  • синтаксическая роль: часть подлежащего.

Лужину (кому?) - имя существительное;

  • начальная форма - Лужин;
  • верная морфологическая характеристика слова: имя собственное, одушевленное, конкретное, мужского рода, смешанного склонения;
  • непостоянные морфологические признаки существительного: единственное число, дательного падежа;

Ладонью (чем?) - имя существительное;

  • начальная форма - ладонь;
  • постоянные морфологические признаки: женского рода, неодушевлённое, нарицательное, конкретное, I склонения;
  • непостоянные морфо. признаки: единственного числа, творительного падежа;
  • синтаксическая роль в контексте: дополнение.

Пыль (что?) - имя существительное;

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

(с) Пальто (С чего?) - существительное;

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

Морфологический разбор прилагательного

Имя прилагательное - это знаменательная часть речи. Отвечает на вопросы Какой? Какое? Какая? Какие? и характеризует признаки или качества предмета. Таблица морфологических признаков имени прилагательного:

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

План морфологического разбора прилагательного

Пример предложения:

Полная луна взошла над городом.

Полная (какая?) – имя прилагательное;

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

Вот еще целый литературный отрывок и морфологический разбор имени прилагательного, на примерах:

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

Прекрасна (какова?) - имя прилагательное;

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

Стройная (какая?) - имя прилагательное;

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

Тоненькая (какая?) - имя прилагательное;

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

Голубые (какие?) - имя прилагательное;

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

Изумительных (каких?) - имя прилагательное;

  • начальная форма - изумительный;
  • постоянные признаки по морфологии: относительное, выразительное;
  • непостоянные морфологические признаки: множественное число, родительного падежа;
  • синтаксическая роль в предложении: часть обстоятельства.

Морфологические признаки глагола

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

Морфологические формы глаголов:

  • начальная форма глагола - инфинитив. Ее так же называют неопределенная или неизменяемая форма глагола. Непостоянные морфологические признаки отсутствуют;
  • спрягаемые (личные и безличные) формы;
  • неспрягаемые формы: причастные и деепричастные.

Морфологический разбор глагола

  • начальная форма - инфинитив;
  • постоянные морфологические признаки глагола:
    • переходность:
      • переходный (употребляется с существительными винительного падежа без предлога);
      • непереходный (не употребляется с существительным в винительном падеже без предлога);
    • возвратность:
      • возвратные (есть -ся, -сь);
      • невозвратные (нет -ся, -сь);
      • несовершенный (что делать?);
      • совершенный (что сделать?);
    • спряжение:
      • I спряжение (дела-ешь, дела-ет, дела-ем, дела-ете, дела-ют/ут);
      • II спряжение (сто-ишь, сто-ит, сто-им, сто-ите, сто-ят/ат);
      • разноспрягаемые глаголы (хотеть, бежать);
  • непостоянные морфологические признаки глагола:
    • наклонение:
      • изъявительное: что делал? что сделал? что делает? что сделает?;
      • условное: что делал бы? что сделал бы?;
      • повелительное: делай!;
    • время (в изъявительном наклонении: прошедшее/настоящее/будущее);
    • лицо (в настоящем/будущем времени, изъявительного и повелительного наклонения: 1 лицо: я/мы, 2 лицо: ты/вы, 3 лицо: он/они);
    • род (в прошедшем времени, единственного числа, изъявительного и условного наклонения);
    • число;
  • синтаксическая роль в предложении. Инфинитив может быть любым членом предложения:
    • сказуемым: Быть сегодня празднику;
    • подлежащим:Учиться всегда пригодится;
    • дополнением: Все гости просили ее станцевать;
    • определением: У него возникло непреодолимое желание поесть;
    • обстоятельством: Я вышел пройтись.

Морфологический разбор глагола пример

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

Вороне как-то Бог послал кусочек сыру... (басня, И. Крылов)

Послал (что сделал?) - часть речи глагол;

  • начальная форма - послать;
  • постоянные морфологические признаки: совершенный вид, переходный, 1-е спряжение;
  • непостоянная морфологическая характеристика глагола: изъявительное наклонение, прошедшего времени, мужского рода, единственного числа;

Следующий онлайн образец морфологического разбора глагола в предложении:

Какая тишина, прислушайтесь.

Прислушайтесь (что сделайте?) - глагол;

  • начальная форма - прислушаться;
  • морфологические постоянные признаки: совершенный вид, непереходный, возвратный, 1-го спряжения;
  • непостоянная морфологическая характеристика слова: повелительное наклонение, множественное число, 2-е лицо;
  • синтаксическая роль в предложении: сказуемое.

План морфологического разбора глагола онлайн бесплатно, на основе примера из целого абзаца:

Его нужно предостеречь.

Не надо, пусть знает в другой раз, как нарушать правила.

Что за правила?

Подождите, потом скажу. Вошел! («Золотой телёнок», И. Ильф)

Предостеречь (что сделать?) - глагол;

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

Пусть знает (что делает?) - часть речи глагол;

  • начальная форма - знать;
  • непостоянная морфология глагола: повелительное наклонение, единственного числа, 3-е лицо;
  • синтаксическая роль в предложении: сказуемое.

Нарушать (что делать?) - слово глагол;

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

Подождите (что сделайте?) - часть речи глагол;

  • начальная форма - подождать;
  • постоянные морфологические признаки: совершенный вид, невозвратный, переходный, 1-го спряжения;
  • непостоянная морфологическая характеристика глагола: повелительное наклонение, множественного числа, 2-го лица;
  • синтаксическая роль в предложении: сказуемое.

Вошел (что сделал?) - глагол;

  • начальная форма - войти;
  • постоянные морфологические признаки: совершенный вид, невозвратный, непереходный, 1-го спряжения;
  • непостоянная морфологическая характеристика глагола: прошедшее время, изъявительное наклонение, единственного числа, мужского рода;
  • синтаксическая роль в предложении: сказуемое.