Меню

Построить грамматику порождающую язык решение

ПРИМЕРЫ ПОСТРОЕНИЯ ГРАММАТИК :

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Читайте также:  Как построить торговую площадь

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

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

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

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

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

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

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.

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

Читайте также:  Как построить второй этаж в гараже оформление

Источник

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Читайте также:  Как построить домик в квартире для детей

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

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

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

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

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

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

Приведем в качестве примера порождение цепочки 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