Примеры построения грамматик. Формальная грамматика Определение и способы описания формальных грамматик

ВВЕДЕНИЕ………… ………………………………….…………….4

Глава 1. ЯЗЫКИ И ГРАММАТИКИ. ОБОЗНАЧЕНИЯ, ОПРЕДЕЛЕНИЯ И КЛАССИФИКАЦИЯ ………………………………………………………………………………6

1.1. Понятие грамматики языка. Обозначения……………………………………………7

1.2. Классификация грамматик по Хомскому………………………..…………………13

1.3. Техника построения КС- и А- грамматик…………………………………………..16

1.4. Синтаксические деревья вывода в КС-грамматиках. Представление

А-грамматик в виде графа состояний. Неоднозначность грамматик……………..19

1.5. Синтаксический анализ А-языков…………………………………………………..23

Упражнения……………………………………………………………………………….29

Глава 2. РАСПОЗНАВАТЕЛИ И АВТОМАТЫ .……………………………….….…………32

Глава 3. АВТОМАТНЫЕ ГРАММАТИКИ И КОНЕЧНЫЕ АВТОМАТЫ …………….35

3.1. Автоматные грамматики и конечные автоматы…………………………………….35

3.2.Эквивалентность недетерминированных и детерминированных А-грамматик…… 36

Упражнения………………………………………………………………………………… 41

Глава 4. ЭКВИВАЛЕНТНЫЕ ПРЕОБРАЗОВАНИЯ КОНТЕКСТНО-СВОБОДНЫХ

И АВТОМАТНЫХ ГРАММАТИК ………………………………………………..….42

4.2. Исключение тупиковых правил из грамматик………………………………………46

4.3. Обобщенные КС-грамматики и приведение грамматик к удлиняющей форме…….48

4.4. Устранение левой рекурсии и левая факторизация………………………………..…52

Упражнения………………………………………………………………………………….53

Глава 5. СВОЙСТВА АВТОМАТНЫХ И КОНТЕКСТНО-СВОБОДНЫХ ЯЗЫКОВ …55

5.1. Общий вид цепочек А-языков и КС-языков………………………………………..55

5.2. Операции над языками………………………………………………………………….59

5.2.1. Операции над КС-языками………………………………………………………59

5.2.2. Операции над А-языками………………………………………………………62

5.2.3. Операции над К-языками………………………………………………………66

5.3. Выводы для практики…………….………………………………………………….67

5.4. Неоднозначность КС-грамматик и языков…………………………………………71

Упражнения…………………………………………………………………………....…74

Глава 6. СИНТАКСИЧЕСКИЙ АНАЛИЗ КС-языков ……………………………...……...75

6.1. Методы анализа КС-языков. Грамматики предшествования………………….…75

6.2. Грамматики предшествования Вирта……………………………………………...77

Грамматики предшествования Флойда…….……………………………………...79

Функции предшествования…………………………………………………………81

Упражнения………………………………………………………………………………84

Глава 7. ВВЕДЕНИЕ В СЕМАНТИКУ ……………………………………………………….85

7.1. Польская инверсная запись….……………………………………………………...85

7.2. Интерпретация ПОЛИЗа……………………………….………………………..….87

7.3. Генерирование команд по ПОЛИЗу………………………………….…………....89

7.4. Алгоритм Замельсона и Бауэра перевода выражений в ПОЛИЗ………..……….91

7.5. Атрибутные грамматики……………………………………………………………97

Упражнения……………………………………………………………………………..100

Глава 8. ОСНОВНЫЕ ФАЗЫ КОМПИЛЯЦИИ ……………………………………...……100

ЗАКЛЮЧЕНИЕ

ПРИЛОЖЕНИЕ …………………………………………………………………………………105

ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ ……………………………………………………….…….…115

Введение

Лингвистика - наука о языке. Математическая лингвистика - наука, занимающаяся формальными методами построения и изучения языков.

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

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

С проблемами объяснения языка машине сталкиваются многие разработчики программного обеспечения. Человеку свойственно изобретать новые языки. Здесь речь может идти не только о сложных компиляторах для новых алгоритмических языков программирования. Любая автоматизированная система должна понимать некоторый входной язык запросов. Новые информационные технологии предполагают привлечение конечного пользователя (ученого, конструктора, технолога, оператора) - специалиста в конкретной области, а не в области вычислительной техники и технологии программирования, к решению своих задач на ЭВМ. Для качественного решения этой проблемы между пользователем и ЭВМ должен существовать интеллектуальный интерфейс: пользователь должен ставить задачи и получать результаты их решения в терминах известной ему предметной области. То есть, необходима разработка широкого спектра предметно-ориентированных языков. Специалист в области программного обеспечения должен знать, как создаются языки и их программная поддержка.

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

Язык – это множество предложений (фраз), построенных по определенным правилам.

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

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

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

Основными разделами грамматики являются синтаксис и семантика.

Синтаксис - свод правил, определяющих правильность построения предложений языка.

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

Предложение может быть синтаксически верным и семантически неверным.

Синтаксис обычно упрощается тем, что не все фразы языка обязаны иметь смысл. Зачастую трудно понять смысл футуристов или речь некоторых политиков. В этой связи интересен пример академика Л.В.Щербы: «Глокая куздра штеко будланула бокра и кудрячит бокренка». Это фраза на русском языке, так как её можно разобрать по членам предложения, но смысл её неясен.

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

<предложение>

Природу неоднозначности фразы можно объяснить на примере все того же дерева разбора для фразы «Мать любит дочь».

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

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

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

Транскрипт

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

19 :

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

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

22 :

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Эта теория возникла в 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 = а.

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

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

Термины

• Терминал (терминальный символ) - объект, непосредственно присутствующий в словах языка, соответствующего грамматике, и имеющий конкретное, неизменяемое значение (обобщение понятия «буквы»). В формальных языках, используемых на компьютере, в качестве терминалов обычно берут все или часть стандартных символов ASCII - латинские буквы, цифры и спец. символы.
• Нетерминал (нетерминальный символ) - объект, обозначающий какую-либо сущность языка (например: формула, арифметическое выражение, команда) и не имеющий конкретного символьного значения.

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

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

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

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

Вывод

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

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

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

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

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

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

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

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

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

ФОРМУЛА

Вывод :

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

ФОРМУЛА → 3 {\displaystyle {\stackrel {3}{\to }}} (ФОРМУЛА) (ФОРМУЛА ) → 1 {\displaystyle {\stackrel {1}{\to }}} (ФОРМУЛА ЗНАК ФОРМУЛА ) (ФОРМУЛА ЗНАК ФОРМУЛА) → 4 {\displaystyle {\stackrel {4}{\to }}} (ФОРМУЛА + ФОРМУЛА) (ФОРМУЛА + ФОРМУЛА ) (ФОРМУЛА + ЧИСЛО ) (ФОРМУЛА + ЧИСЛО ) (ФОРМУЛА + ЦИФРА ) (ФОРМУЛА + ЦИФРА ) (ФОРМУЛА + 5 ) (ФОРМУЛА + 5) → 2 {\displaystyle {\stackrel {2}{\to }}} (ЧИСЛО + 5) (ЧИСЛО + 5) → 6 {\displaystyle {\stackrel {6}{\to }}} (ЧИСЛО ЦИФРА + 5) (ЧИСЛО ЦИФРА + 5) → 5 {\displaystyle {\stackrel {5}{\to }}} (ЦИФРА ЦИФРА + 5) (ЦИФРА ЦИФРА + 5) → 7 {\displaystyle {\stackrel {7}{\to }}} (1 ЦИФРА + 5) (1 ЦИФРА + 5) → 7 {\displaystyle {\stackrel {7}{\to }}} (1 2 + 5)