ОСНОВЫ ТЕОРИИ ФОРМАЛЬНЫХ ГРАММАТИК

 

 

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ………… ………………………………….…………….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.1. Декомпозиция правил грамматики…………………………………………………. 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

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

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

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

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

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ…………………………………………………………………………………105

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

СПИСОК РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ…………………………………………114

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

Введение

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

Глокая куздра штеко будланула бокра и кудрячит бокренка
<опред.> <подл.> <обст.> <сказ.> <дополн> <союз> <сказ.> <дополн>
                   

<группа подлеж.> <группа сказ.> <группа сказ.> <группа сказ.>

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

 

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

 

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

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

 

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

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

 

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

 

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

 

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

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

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

Упражнения

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

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

Всякая конечная последовательность символов алфавита называется цепочкой. Так a, b, c, ab, aaca - цепочки в алфавите A = {a,b,c}.

Допустим существование пустой цепочкиe, не содержащей ни одного символа.

Важен порядок символов в цепочке. Цепочка ab отличается от ba.

Длина цепочки ½a½ равна количеству символов в цепочке. Так ½a½=1, ½abc½=3, ½ e ½=0.

Если a иb- цепочки, то их конкатенациейab является цепочка, полученная путем дописывания символов цепочки b вслед за символами цепочки a . Например, если a=ab, b=bc, то ab= abbc и ba= bcab. Поскольку e - цепочка, не содержащая символов, то в соответствии с правилами конкатенации для любой цепочки a можно записать:

ea=ae=a.

Обращением цепочки a (обозначается a R) называется цепочка a, записанная в обратном порядке, т.е. если a = a1...an, где все ai- символы, то aR= an... a1. Кроме того, e R=e .

Языком Lв алфавите A называется множество цепочек в A.

Это определение подходит почти для любого языка. Языки Паскаль, С, Модула-2, английский и русский охватываются этим понятием.

Рассмотрим простые примеры языков в алфавите A.

Пустое множество Æ - это язык. Множество {e },содержащее только пустую цепочку, также является языком.

Заметим, что Æ и { e } - это два разных языка.

Обозначим через A* множество, содержащее все цепочки в алфавите A, включая e.

Например, если A бинарный алфавит {0,1}, то

A* = { e , 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, 110, ...}.

Цепочку, состоящую из i символов a, будем обозначать a i, то есть a0=e, a1= a, a2= aa, a3= aaa и т.д.

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

Грамматика языка - четверка объектов: G = <S, VT, VN, R>, где

S- начальный, выделенный символ грамматики (аксиома грамматики);

VТ - множество терминальных символов (терминал – конечный, неделимый символ);

VN- множество нетерминальных символов (понятий);

R - свод правил грамматики.

Обозначения:

Грамматику языка обозначим через G, возможно с индексом, илиG(S). Язык L, определяемый грамматикой G, обозначимL(G).

Терминальные символы обозначаются маленькими латинскими буквами и являются символами алфавита.

Нетерминальные символы обозначаются заглавными латинскими буквами либо текстом, заключенными в угловые скобки: <нетерминал>.

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

V*- множество цепочек, построенных на алфавите языка V.

Правила обычно записывают в виде