Лингвистическое обеспечение автоматизированных систем

ОГЛАВЛЕНИЕ

Ведение 6

1 Лингвистическое обеспечение автоматизированных систем 8

1.1 Основные понятия 8

1.2 Классификация языков проектирования 8

1.3 Требования к языкам проектирования 12

2 Автоматизация процесса компиляции 13

2.1 Программы для обработки языков 13

2.2 Упрощенная модель компилятора 13

2.3 Лексический блок 14

2.4 Синтаксический блок 15

2.5 Генератор кода 16

2.6 Замечания 18

2.7 Блоки и проходы компилятора 18

3 Синтаксически-ориентированный метод трансляции 20

3.1 Структура и значение языка 20

3.2 Словарь. Цепочка над словарем. Язык. 22

3.3 Примеры языков 23

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

4.1 Формальные грамматики. Пример. 24

4.2 Определение грамматики 27

4.3 Выводимость 30

4.4 Продукции 31

4.5 Замечания 33

4.6 Деревья вывода 34

4.7 Примеры грамматик 36

4.8 Иерархия порождающих грамматик Хомского 41

5 Автоматные языки и грамматики 43

5.1 Граф автоматной грамматики 43

5.2 Автомат Мили 45

5.3 Автомат Мура 46

5.4 Связь автоматов Мили и автоматов Мура. 47

5.5 Автоматы Робина-Скотта 48

5.5.1 Пример 48

5.5.2 Определение НРС-автомата 51

5.5.3 Определение детерминированного автомата Робина-Скотта 52

5.6 Задача трансляции автоматных языков 54

6 Недетерминированный автомат 56

6.1 Определение недетерминированного автомата 56

6.2 Алгоритм построения детерминированного автомата из недетерминированного 57

6.3 Минимизация конечных автоматов 58

6.4 Регулярные выражения 60

6.5 Разрешимые алгоритмические проблемы, связанные с автоматными языками 63

6.6 Правила конструирования транслятора по синтаксическим диаграммам 64

7 Лексический анализ 66

7.1 Программирование конечного автомата 66

7.1.1 Представление входных символов 66

7.1.2 Представление состояний 67

7.1.3 Выбор переходов 68

7.2 Идентификация слов: метод автомата 71

7.3 Идентификация слов: метод индексов 73

7.4 Идентификация имен: метод линейного списка 75

8 Контекстно-свободные языки 76

8.1 Проблемы КС языков 76

8.2 Проблема пустоты 77

8.3 Нерелевантные правила 78

8.4 Нормальная форма Хомского 79

8.5 Оценка длины цепочки 80

8.6 Пример языка не являющегося КС-языком 82

8.7 Проблема конечности языка 82

8.8 Проблема принадлежности 84

8.9 Нормальная форма Грейбаха 84

9 Магазинный автомат и LL-грамматики 86

9.1 Недетерминированный магазинный автомат 87

9.2 Эквивалентность магазинных автоматов и КС-грамматик 89

9.3 Синтаксический анализ «сверху-вниз» и «снизу-вверх» 91

10 Синтаксически-управляемый перевод 93

10.1 Транслирующие грамматики 93

10.2 Понятие синтаксически-управляемого перевода 94

10.3 Атрибутные транслирующие грамматики 98

11 Диалоговые языки. Интерфейс пользователя. 102

11.1 Факторы, влияющие на комфорт общения 102

11.2 Критерии оценки интерфейса 103

11.3 Классификация сообщений 104

11.4 Типы диалоговых процессов 105

11.5 Подсказки. Способы реализации. 106

11.6 Диалог «вопрос-ответ» и «меню». 107

12 Обработка естественно языковых конструкций в системах искусственного интеллекта 109

12.1 Теории моделей общения 110

12.2 Обобщенная схема ЕЯ-систем 114

12.2.1 Компонент понимания высказывания 115

12.2.2 Компонент генерации высказываний 121

12.3 Модели и методы обработки естественного языка в автоматизированных системах 123

12.3.1 Обзор систем обработки естественного языка 124

12.3.2 Методы моделирования языковой деятельности 128

12.3.3 Морфологический уровень 131

12.3.4 Синтаксический уровень 133

12.3.5 Семантический уровень 139

13 Информационный поиск и семантический анализ корпуса текстов 157

13.1 Индексирование текстов 169

13.1.1 Сканирование текста, выделение лексем 170

13.1.2 Стемминг, выделение термов 171

13.2 Взвешивание термов 181

13.2.1 Сравнительный анализ существующих методик взвешивания термов 182

13.3 Латентно-семантический анализ корпуса текстов 195

13.3.1 Сравнительный анализ различных методов ЛСИ 197

13.3.2 Проблема выбора варианта ЛСИ 210

13.3.3 Методика применения модификации метода SVD 212

13.3.4 Обновление документов 219

13.3.5 Вероятностная модель для ЛСИ 226

13.3.6 Чувствительность к размеру матриц 228

13.4 Кластеризация и семантический анализ множества текстов 229

13.4.1 Задача кластерного анализа совокупности текстов 232

13.4.2 Понятие сходства в кластерном анализе документов 238

13.4.3 Меры качества кластеров и кластерного разбиения 246

13.4.4 Методы объединения кластеров 251

13.5 Использование методов кластерного анализа для множества текстов 259

13.5.1 Иерархические агломеративные методы кластеризации 262

13.5.2 Дивизивиная иерархическая кластеризация. Графо-ориентированные методы кластерного анализа. 280

13.5.3 Методы инкрементной кластеризации документов 284

13.5.4 Методы маркирования кластеров 289

13.6 Заключительные замечания 293

Литература 297

Приложения 321