Глава 1. Языки и грамматики. Обозначения, определения и классификация

Е.И.ЧИГАРИНА, М.А.ШАМАШОВ

ТЕОРИЯ КОНЕЧНЫХ

АВТОМАТОВ

И ФОРМАЛЬНЫХ ЯЗЫКОВ

Допущено учебно-методическим советом по прикладной математике и информатике УМО по классическому университетскому образованию в качестве учебного пособия для студентов высших учебных заведений, обучающихся по специальности и направлению «Прикладная математика и информатика» и по направлению «Информационные технологии»

С А М А Р А

Издательство СГАУ

2007

УДК 004.43(075)

ББК 32.973

Ч586

Инновационная образовательная программа
"Развитие центра компетенции и подготовка
специалистов мирового уровня в области аэрокосмических и геоинформационных технологий"

Рецензенты: д-р техн. наук, проф. А.А.Калентьев,

д-р техн. наук, проф. М.А.Кораблин

Ч586 Чигарина Е.И.Теория конечных автоматов и формальных языков: учеб. пособие / Е.И. Чигарина, М.А.Шамашов. – Самара:
Изд-во Самар. гос. аэрокосм. ун-та, 2007. – 96 с. : ил.

ISBN 978-5-7883-0506-6

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

Пособие ориентировано на студентов очной и заочной форм обучения, изучающих информатику и компьютерные науки, и специалистов, связанных с задачами проектирования системного и прикладного программного обеспечения автоматизированных систем самой различной ориентации. Рекомендуется в качестве учебного пособия для студентов высших учебных заведений, обучающихся по специальностям: 010500 – Прикладная математика и информатика, 010400 – Информационные технологии по курсам «Языки программирования и методы трансляции», «Теория конечных автоматов и формальных языков». и в лаборатории “Открытые системы”

Утверждено редакционно-издательским советом университета в качестве учебного пособия

ISBN 978-5-7883-0506-6© Чигарина Е.И.,Шамашов М.А., 2007

© Самарский государственный

аэрокосмический университет, 2007

Оглавление

Введение. 4

Глава 1. Языки и грамматики. Обозначения, определения и классификация. 6

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

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

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

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

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

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

Упражнения к первой главе. 25

Глава 2. Распознаватели и автоматы.. 27

Глава 3. Автоматные грамматики и конечные автоматы.. 30

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

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

Упражнения к третьей главе. 35

Глава 4. Эквивалентные преобразования контекстно-свободных и автоматных грамматик 37

4.1. Декомпозиция правил грамматики. 37

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

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

форме. 42

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

Упражнения к четвертой главе. 47

Глава 5. Свойства автоматных и контекстно-свободных языков. 48

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

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

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

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

5.2.3. Операции над контекстными языками. 59

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

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

Упражнения к пятой главе. 63

Глава 6. Синтаксический анализ КС-языков. 64

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

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

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

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

Упражнения к шестой главе. 71

Глава 7. Введение в семантику. 72

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

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

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

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

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

Упражнения к седьмой главе. 83

Глава 8. Основные фазы компиляции. 84

Заключение. 87

Приложение. 88

Список рекомендуемой литературы.. 94

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Глава 1. Языки и грамматики. Обозначения, определения и классификация

Поиск по сайту: