Составить грамматику порождающую формальный язык

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

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

Порождающая грамматика состоит из четырех компонент: Г = (V, W, J, R), где V и W — непересекающиеся конечные множества, называющиеся основным и вспомогательным алфавитами (или словарями); элементы этих множеств называются соответственно основными (или терминальными) и вспомогательными (или нетерминальными) символами; J — выделенный вспомогательный символ, называемый начальным символом; R — конечный набор правил вывода, имеющих вид j ® y, где j и y — цепочки, состоящие из основных и вспомогательных символов.

Основные символы — слова языка,

вспомогательные — как имена классов слов и словосочетаний,

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

Правила вывода описывают связи между частями предложения. Применение правила j ® y к цепочке, имеющей вид bja, означает преобразование ее в цепочку bya (здесь a и b — цепочки, одна из которых или обе могут быть пустыми).

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

Цепочка b непосредственно выводима из цепочки a в грамматике G (ÞaGb), если a=dxg, b = dhg и h®x — правило G.

Цепочка b выводима из a, если существует последовательность e0 = a, e1, e2, …, en = b, такая, что для всех i = 0, …, n –1 eii + 1. Эта последовательность называется выводом b из a, a n (число ее элементов, отличных от a) — длиной вывода.

Выводимость b из a обозначается Þanb или Þa*b.

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

73. Классификация грамматик и порождаемых ими языков.

Грамматика типа 0 — это грамматика произвольного вида, без ограничений на правила вывода.

Грамматика типа 1, или контекстная грамматика — это грамматика, все правила которой имеют вид aAbwa®b, где Îw(VÈW)+. Цепочки a и b — это контекст правила. Они не изменяются при его применении.

Грамматика типа 2, или контекстно-свободная (КС-) грамматика, — грамматика, все правила которой имеют вид Aa®, где Îa(VÈW)*

Грамматика типа 3, или регулярная грамматика, — грамматика, все правила которой имеют вид либо A®aB, либо A®a.

Язык L называется языком типа i (i = 0, 1, 2, 3), если существует порождающая его грамматика типа i.

Пример : Язык <аnbn> является КС-языком (языком типа 2), поскольку он порождается КС-грамматикой с двумя правилами вывода:

    Людмила Волынская 3 лет назад Просмотров:

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

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

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

Читайте также:  Фрактальный рисунок и его расшифровка

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:, где цепочка не содержит двух рядом стоящих символов :

Небольшое предисловие

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

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

Определение порождающей грамматики

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

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

Читайте также:  Чем склеить акриловую ванну

Порождающая грамматика Хомского задается как множество «правил порождения» (продукций). Каждое правило является просто парой цепочек (w’, w”) и задает возможность замены левой цепочки на правую при генерации цепочек языка, задаваемого грамматикой. По этой причине, правила обычно записывают в виде w’ –> w” , указывая конкретно, что на что можно заменять. Множество правил в грамматике должно быть непустым и конечным, и обычно обозначается латинской P.

Цепочки в правилах грамматики могут быть составлены из символов двух алфавитов: алфавита терминальных символов (терминалов) и алфавита нетерминальных символов (нетерминалов). Алфавит терминалов обозначают через T. Этот алфавит на самом деле совпадает с алфавитом того формального языка, который задает данная грамматика. Смысл термина «терминальный» состоит в том, что в правилах грамматики в левой части не может быть цепочек, которые составлены только из терминальных символов. Поэтому, если такая цепочка получилась в результате подстановки, то следующая процесс порождения цепочки остановится (terminate). Нетерминальные символы используются в промежуточных порождениях цепочек. Смысл нетерминала в задании алгоритма порождения цепочки может быть самый разный и обычно зависит от типа грамматики, в которой этот символ используется. Различные примеры использования нетерминальных символов будут рассмотрены ниже.

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

Итак, порождающая грамматика Хомского — это четверка G = , где

  • N — конечный алфавит нетерминальных символов.
  • T — конечный алфавит терминальных символов (совпадает с алфавитом языка, задаваемого грамматикой).
  • P — конечное множество правил порождения.
  • S — начальный нетерминал грамматики G .

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

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

Шаг порождения w’ alpha w” => w’ beta w” состоит в замене подцепочки alpha на подцепочку beta в соответствии с правилом порождения alpha –> beta . При этом, очевидно, из цепочки w’ alpha w” получается цепочка w’ beta w” . Иначе говоря, если имеется некоторая цепочка и некоторая ее подцепочка является левой частью какого-то правила грамматики, то мы имеем полное право заменить эту левую часть правила на правую. Конечная последовательность шагов порождений называется порождением. Нуль или более порождений будет обозначать знаком =>* . Обозначение alpha =>* beta говорит о том, что цепочка beta получена из цепочки alpha конечным числом подстановок на основе правил порождения. В этом обозначении может быть так, что подстановка (порождение) не была применена ни разу, в этом случае цепочка alpha совпадает с beta .

Итак, язык порождающей грамматики G = — это множество цепочек, составленных из терминальных символов и порожденных из начального символа грамматики. Математическая формула такова: L = * w> .

Для иллюстрации приведем два простых примера.

Пример очень простого языка

Следует заметить, что для этого языка можно было бы ввести еще один нетерминальный символ, скажем, символ A , а также правила S –> A и A –> a . Тогда единственным порождением было бы следующее: S => A => a . Так как алфавит нетерминалов грамматики мы выбираем произвольно, становится понятно, что даже для такого простого языка имеется бесконечное множество порождающих грамматик, задающих данный язык.

Язык простых арифметических выражений

Рассмотрим язык A = . Цепочки этого языка представляют собой последовательности символов a , разделенных символами + . Как задать правила порождения этого языка? Заметим, что каждая цепочка языка начинается с символа a за которым идет одна или более цепочек +a . Соответственно, возникает мысль сначала породить символ a , а затем каждая цепочка языка будет получаться присоединением к этому символу справа одной или более цепочек +a . Чтобы отделить эти две стадии порождения друг от друга, введем нетерминальный символ A . Тогда, получим грамматику со следующими правилами: S –> aA, A –> +aA, A –> +a .

Рассмотрим, например, как можно породить цепочку a+a+a . S => aA => a+aA => a+a+a . В этом порождении последовательно были применены все три правила: S –> aA, A –> +aA, A –> +a .

Язык A содержит бесконечное число цепочек, значит, ограничения на длину цепочки в этом языке нет. Единственный способ порождать цепочки неограниченной длины, это использовать рекурсивные правила порождения, т.е. правила, в которых в правой части правила содержится его левая часть. В примере выше это правило A –> +aA . Левая часть — это цепочка из единственного символа A , который также содержится и в правой части. Такая рекурсия позволяет последовательно применять в подстановке одно и то же правила, увеличивая, сколько необходимо, длину порождаемой цепочки. Рекурсия может быть и опосредованной, через промежуточные правила. Например, правила A –> aBc, B –> deA задают опосредованную рекурсию цепочки A .

Классы грамматик

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

Грамматики типа 3

Этот класс грамматик задает алгоритм порождения цепочек присоединением некоторого количества терминальных символов с правого или левого края порождаемой цепочки. Очевидно, что правила для такого метода порождения должны иметь вид A –> alpha B или A –> B alpha , где alpha — цепочка, состоящая из терминальных символов. В этом случае, если имеется промежуточная (в процессе порождения) цепочка X1..Xn A , то замена в соответствии с правилом A –> alpha B даст цепочку X1..Xn alpha B . Например, для правил S –> aaaA , A –> abcA и A –> bbb можно задать порождение S => aaaA => aaaabcA => aaaabcbbb .

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

Для математической строгости строку терминальных символов в правилах грамматик типа 3 разбивают на несколько правил с одним терминальным символом в правой части. Например, если имеется правило A –> abcB , то его можно заменить на следующие правила, применение которых в результате порождает ту же цепочку: A –> a A1 , A1 –> b A2 , A2 –> cB . Иначе говоря, подстановка A => abcB эквивалентна последовательности подстановок A => a A1 => a b A2 => abcB . Такие грамматики, где нетерминальный символ стоит справа в правой части правила, называют праволинейными грамматиками, если в правой части нетерминальный символ стоит слева от терминала, то грамматику называют леволинейной.

Зададим, например леволинейную грамматику для языка A = . Правила грамматики типа 3, как было рассмотрено выше, это: S –> aA, A –> +aA, A –> +a . Здесь цепочки порождаются присоединением пары символов справа. Изменим грамматику так, чтобы символы присоединялись слева, а также добавим нетерминальные символы, чтобы каждый раз добавлять только по одному символу. Получим грамматику:
S –> Aa
A –> B+
B –> Aa
B –> a
Вот как выглядит порождение цепочки a+a+a : S => Aa => B+a => Aa+a => B+a+a => a+a+a .

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

Контекстно-свободные грамматики

Контекстно-свободные грамматики имеют правила вида: A –> alpha . В левой части правила должен стоять один символ (конечно, нетерминальный), а справа может быть любая цепочка из терминальных и нетерминальных символов (в том числе и пустая).

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

Читайте также:  Стабилизатор на боинге 737

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

Ввиду того, что КС-грамматика является порождающей, она задает алгоритм (строго говоря, не алгоритм, но исчисление — многовариантный алгоритм) порождения цепочек языка. Порождение здесь задается не только присоединением цепочек справа или слева имеющейся цепочки, но и вставкой цепочки куда-нибудь внутрь имеющейся. Вставка производится заменой нетерминального символа в цепочке на цепочку, которая стоит в правой части некоторого правила, в левой части которого находится этот нетерминал. Скажем, цепочку aabBBACbbb можно преобразовать в цепочку aabBBaaaCbbb , если есть правило A –> aaa . В этом смысле, порождаемая цепочка растет не равномерно с какого-то края, но как-бы «пухнет» изнутри.

Проиллюстрируем сказанное на примере. Рассмотрим язык L = . Выражение a^n здесь означает повторение n раз символа a . Таким образом, язык L состоит из цепочке вида ab, aabb, aaabbb и т.д. Зададим КС-грамматику для этого языка. Для этого заметим, что из цепочки языка можно получить другую цепочку языка, присоединяя к первой слева символ a , а справа символ b . Скажем, если имеется цепочка aabb , то из нее можно получить цепочку aaabbb . Это замечание дает правило порождения S –> aSb (напомним, что цепочки языка порождаются из начального нетерминала грамматики и, значит, могут быть обозначены этим символом). Есть еще специальный случай цепочки, которая не дробится на более мелкие — это цепочка ab . Введем для ее порождения правило S –> ab . Итак, грамматика языка имеет правила: S –> aSb и S –> ab . Зададим порождение цепочки aaabbb : S => aSb => aaSbb => aaabbb .

Контекстно-зависимые грамматики и грамматики без ограничений

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

Контекстно-зависимая грамматика имеет правила вида w’ A w” –> w’ alpha w” . Здесь w’ и w” — цепочки (может быть пустые), составленные из терминальных и нетерминальных символов грамматики, alpha — непустая цепочка из тех же символов. Иначе говоря, нетерминальный символ A заменяется на цепочку alpha в контексте цепочек w’ и w” .

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

Зачем так необходимо выделять класс языков, задаваемых неукорачивающими грамматиками? Дело в том, что для таких языков можно задать распознающий автомат. Распознающая грамматика конструируется следующим образом: получая на вход цепочку, последовательно делаем порождения, упорядочивая их по длине порождаемой цепочки. Т.к. грамматика неукорачивающая, то таких порождений будет конечное множество и, если среди них не нашлось совпадения с данной на вход цепочкой, то напечатать «нет».

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

Действительно ли КЗ-языки образуют собственный класс, не совпадает ли этот класс с классом КС-языков. Иначе говоря, есть ли язык, для которого гарантировано нельзя задать КС-грамматику, но можно задать КЗ-грамматику? Ответ: да, такие языки есть. В качестве примера такого языка можно привести следующий язык L = . Цепочки этого языка составлены из двух повторяющихся цепочек над каким-то алфавитом. Доказывать, что для этого языка нельзя построить КС-грамматики мы здесь не будем. КЗ-грамматику можно задать на основе следующего соображения. Сначала сгенерировать цепочку w и нетерминальный символ, скажем A , т.е. получить цепочку Aw . Затем продвинуть символ A сквозь цепочку w , генерируя по ходу копии символов этой цепочки, после чего продвинуть эти символы направо. Примерно то же, как это будет реализовано в примере ниже.

Рассмотрим пример задания грамматики для языка L = . Цепочки этого языка состоят из символов a , причем число этих символов есть квадрат натурального числа: 1, 4, 9, 25 и т.д. Мы зададим для этого языка грамматику без ограничений. Генерация цепочек будет состоять из следующих этапов:

  1. Генерация n символов для некоторого натурального числа n .
  2. Порождение из этого числа символов n^2 символов.
  3. Преобразование этих символов в символы a .

Для реализации первого этапа добавляем правила
S –> LS’R
S’ –> AS’B
S’ –> AB

Первым правилом оборачиваем порождаемую цепочку в ограничители L и R . Они нам понадобятся в дальнейшем для реализации третьей фазы генерации. Оставшиеся два правила просто генерируют цепочку вида AA. ABB. B , где число символов A и B совпадает.

Теперь необходимо породить n^2 символов на основе цепочке AA. ABB. B . Это делает простым приемом. Двигаем символы B налево и, при каждом переходе через символ A , порождать еще один символ C . Через символы C символ A может свободно проходить направо, а символ B — налево. Правила для этого этапа следующие:
AB –> BAC
AC –> CA
CB –> BC
Когда все символы B дойдут до левого края, перейдя символы A , символов C будет ровно n^2 .

Теперь надо освободиться от символов L , A , B и R , а также преобразовать символы C в символы a . Для этого аннигилируем символ B при его проходе до левого края, т.е. до символа L . Соответственно поступаем и с символом A на правом крае. При реализации такой стратегии останется цепочка вида LCC. CR . Чтобы избавится от символов L и R , начинаем двигать левый ограничитель к правому и, при их соприкосновении, уничтожаем эти символы. Заодно, при прохождении через символы L , преобразуем их в символы a . Приведем правила для этой фазы генерации.
LB –> L
AR –> R
LC –> aL
LR –> epsilon
Здесь epsilon обозначает пустую цепочку.

Приведем в качестве примера порождение цепочки aaaa : S => LS’R => LAS’BR => LAABBR => LABACBR => LBACACBR => LACACBR => LACABCR => LACBACCR => LABCACCR => LBACCACCR => LACCACCR => LCACACCR => LCCAACCR => LCCACACR => LCCACCAR => LCCACCR => LCCCACR => LCCCCAR => LCCCCR => aLCCCR => aaLCCR => aaaLCR => aaaaLR => aaaa

Заключение

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

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

Оцените статью
Добавить комментарий

Adblock
detector