Содержание к диссертации
Введение
1. Стандартизация естественных языков 15
1.1. Естественные, искусственные, формальные языки 15
1.2. Контролируемые языки и подмножества языка 19
1.2.1. Проекты контролируемых языков 22
1.2.2. Спецификации ASD-STE100 26
1.3. Адаптация спецификаций ASD-STE100 к другим языкам 31
1.4. Определение языковых характеристик, необходимых для автоматического контроля технической документации на русском языке . 35
1.4.1. Анализ психологических аспектов восприятия текстовой информации 35
1.4.2. Сравнительный анализ спецификаций ASD-STE100 и УТР 37
1.5. Постановка задачи лингвистической валидации технической документации 46
1.6. Выводы 47
2. Анализ автоматических методов разбора текста на естественном языке 49
2.1. Цели и задачи прикладной лингвистики 49
2.2. Наука о языке 52
2.2.1. Подходы к автоматическому анализу естественного языка 52
2.2.2. Компоненты грамматики 54
2.3. Автоматический анализ естественного языка 55
2.4. Автоматический морфологический разбор 56
2.4.1. Слова и формы слова 56
2.4.2. Категоризация 58
2.4.3. Анализ автоматических методов распознавания словоформ 59
2.5. Анализ методов автоматического синтаксического разбора 61
2.6. Анализ систем автоматического синтаксического разбора 70
2.7. Определение лексико-синтаксического анализа 78
2.8. Выводы 79
3. Разработка обобщенной модели представления предложения на русском языке и метода лексико-синтаксического анализа 81
3.1. Обобщенный лексико-синтаксический граф 81
3.1.1. Начальный граф предложения 82
3.1.2. Модификация ребер начального графа 85
3.1.3. Модификация вершин начального графа 87
3.1.4. Правила слияния 91
3.2. Поддержка методов описания синтаксической структуры 92
3.3. Разработка метода лексико-синтаксического анализа 95
3.4. Алгоритмы лексико-синтаксического анализа 98
3.5. Оценка вычислительной сложности алгоритмов ЛСА 102
3.6. Выводы 106
4. Программная реализация ЛСА и результаты экспериментальных исследований 107
4.1. Основные требования к программной модели разрабатываемого метода 107
4.2. Программная реализация ЛСА 108
4.2.1. Лексический анализ 109
4.2.2. Правила слияния синтаксических групп 111
4.2.3. Выявление и разрешение синтаксических неоднозначностей 116
4.3. Экспериментальная проверка теоретической оценки вычислительной сложности алгоритмов 128
4.4. Применение модели ЛСГ и метода ЛСА в Системе валидации технической документации 131
4.5. Выводы 137
Заключение 139
Библиографический список 141
Приложение
- Определение языковых характеристик, необходимых для автоматического контроля технической документации на русском языке
- Автоматический анализ естественного языка
- Поддержка методов описания синтаксической структуры
- Экспериментальная проверка теоретической оценки вычислительной сложности алгоритмов
Введение к работе
-з -
Актуальность исследования. В последние годы роль технической документации как информационного ресурса в производственном процессе существенно возросла. Сложность и многофункциональность даже бытовых приборов требует внимательного изучения правил и особенностей их эксплуатации. Важность подробного документирования всех процедур в тех областях, где безопасность является ключевым понятием, например, в авиастроительной промышленности, невозможно переоценить, поскольку надежность работы комплексной системы зависит не только от совершенства технических решений, но и от правильности их эксплуатации и обслуживания в течение всего жизненного цикла. Составление четкой, однозначной и понятной технической документации, а также ее перевод, является сложной и дорогостоящей операцией, требующей привлечения большого количества ресурсов и лингвистических средств.
Для решения этой проблемы создаются проекты контролируемых технических языков - сводов правил, искусственно ограничивающих естественный язык с целью повышения точности и однозначности высказываний. Одним из примеров такого языка, разработанного представителями Ассоциации Европейских Авиалиний (АЕА), является стандарт Упрощенного Технического Английского языка, представленный спецификациями "ASD-STE100". Этот стандарт одобрен Группой Разработки Упрощенного Технического Английского (Simplified Technical English Maintenance Group - STEMG) и обязателен при составлении технической документации крупнейшими зарубежными авиапроизводителями.
В связи с ростом экспорта российской техники за рубеж применение концепции упрощенного языка технической документации для русскоязычной документации становится приоритетной задачей. Хотя отдельные представители российской авиакосмической промышленности уже разрабатывают проекты ограничения технического русского языка, единого и общепринятого стандарта не существует. Кроме того, большие объемы документации требуют создания автоматизированных средств проверки соответствия текстов этим ограничениям.
Таким образом, разработка методов и моделей функционирования автоматического инструмента для проверки текстов на соответствие требованиям упрощенного технического языка является чрезвычайно актуальной задачей и имеет практическое значение.
Цель и основные задачи диссертации. Целью диссертационной работы является исследование и разработка методов и алгоритмов анализа текста на русском языке в контексте его применения в системе лингвистической валидации технической документации (ЛВТД), предназначенной для проверки технической документации на соответствие проекту спецификаций Упрощенного Технического Русского (УТР) языка.
-4-В соответствии с поставленной целью в диссертации решаются следующие основные задачи:
Проводится анализ спецификаций ASD-STE100, УТР и других проектов контролируемых языков, в результате чего определяются языковые характеристики, существенные для контроля процесса составления технической документации на русском языке.
Проводится анализ существующих методов анализа текстов на естественных языках, что позволяет выделить методы, оптимальные для контроля процесса составления технической документации.
Разрабатывается универсальная модель представления предложения на русском языке, позволяющая манипулировать различными вариантами трактовки предложения в рамках единой структуры.
Разрабатываются методы и алгоритмы автоматического анализа текста на русском языке, позволяющие определять и снимать лексические и синтаксические неоднозначности и определять синтаксические функции отдельных слов и словосочетаний.
Объекты исследования. Объектами исследования являются существующие проекты управляемых языков, лингвистические особенности процесса составления технической документации, техническая документация, методы и алгоритмы анализа текстов на естественном языке.
Методы исследований. В процессе работы использовались методы дискретной математики, теории графов, теории компиляторов.
Научная новизна. В процессе работы над диссертацией были получены следующие результаты:
Разработан реестр языковых характеристик, который отличается от англоязычного аналога ASD-STE100 правилами, свойственными русскому языку как языку со свободным порядком слов, и который позволяет реализовать стратегию упрощения русского языка с целью контроля процесса составления технической документации.
Разработана модель представления предложения на русском языке, отличающаяся от известных моделей инвариантностью формы описания синтаксической схемы и позволяющая анализировать множественные варианты трактовки предложения в рамках единой структуры.
Предложен метод и синтезированы алгоритмы автоматического анализа текста на русском языке, отличающиеся от аналогов снятием лексических и синтаксических неоднозначностей, и позволяющие определять синтаксические функции отдельных слов и словосочетаний.
-5-Практическая ценность. Практическая ценность исследования заключается в синтезе метода синтаксического анализа текстов на русском языке для системы лингвистической валидации технической документации, которая позволяет максимально упростить разработку технической документации в соответствии с принципами Упрощенного Технического Русского языка. Результаты исследования использованы компанией АВИАОК Интернейшенел в процессе реализации концепции Упрощенного Технического Русского языка, в ходе которой разрабатывается программный комплекс, регламентирующий процесс разработки документации. Предложенная в работе модель представления текста и результаты экспериментальной программы послужили основой для создания инструмента проверки текста на соответствие спецификациям УТР. Теоретические результаты использованы при составлении проекта спецификаций УТР.
Достоверность и обоснованность научных положений, результатов и выводов, приведенных в работе, обеспечивается корректным использованием математического аппарата, аналитическим и имитационным моделированием.
Положения, выносимые на защиту:
Модель представления многозначного предложения на естественном языке в виде лексико-синтаксического графа (ЛСГ).
Метод и алгоритмы проведения автоматического лексико-синтаксического анализа в рамках модели ЛСГ.
Апробация основных идей и результатов исследований проведена на следующих конференциях и семинарах:
VII Международная научно-практическая конференция "Информационная безопасность", г. Таганрог, ТРТУ, 2005г;
Всероссийская научно-техническая конференция с международным участием посвященная 60-летию Победы "Компьютерные и информационные технологии в науке, инженерии и управлении" г. Таганрог, ТРТУ, 2005г;
заседания кафедры Вычислительной Техники Таганрогского Технологического Института ЮФУ, г. Таганрог, 2006, 2007, 2008г.
Публикации. По материалам работы опубликовано 7 печатных работ, из них 3 в изданиях, рекомендованных Высшей Аттестационной Комиссией.
Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, заключения, библиографического списка, включающего 102 наименования, и приложений. Текст изложен на 202 страницах, содержит 29 рисунков, 7 таблиц.
Определение языковых характеристик, необходимых для автоматического контроля технической документации на русском языке
Цель исследования психологических аспектов восприятия текстовой информации — изучить отношение читателя к одному и тому же высказыванию технического характера, выраженного через различные языковые структуры. Известно, что многие конструкции русского языка параллельны и взаимозаменяемы. Однако при составлении стандарта УТР возникает необходимость введения ограничений синонимичных форм одним вариантом. Данное ограничение упрощает: стандартизацию технических текстов; машинный перевод; перевод текста переводчиками; восприятие текста читателем.
Одним словом, это необходимый компонент в процессе унификации и стандартизации технического языка. Для достижения целей исследования, необходимо провести анализ лексического материала технического характера на предмет выявления параллельных и синонимичных языковых единиц. Выявленные единицы должны быть подвергнуты психолингвистическому прогнозированию, в результате которого одни единицы предполагаются как наименее удачные варианты для выражения данной мысли в техническом тексте, а другие - как наиболее удачные варианты выражения той же мысли.
На дальнейших этапах психолингвистических исследований необходимо: провести эксперимент с применением методики "семантического шкалирования", при которой испытуемый должен разместить предложенные языковые единицы на градуированной шкале, руководствуясь собственными представлениями. Это позволит не просто предположить, а наиболее точно определить самый подходящий вариант из множества имеющихся; сделать машинный перевод выявленных параллельных конструкций и синонимичных единиц. Проанализировать результаты перевода и выявить варианты, упрощающие машинный перевод; исключить использование в стандарте "УТР" вариантов, усложняющих машинный перевод, и использование вариантов, неподдающихся машинному переводу.
Будучи важной составляющей процесса внедрения концепции УТР, психолингвистические исследования не являются частью данной диссертационной работы.
В данном разделе выявляются языковые особенности, необходимые для реализации ограничительных правил, налагаемых на упрощенный технический русский текст. Следует отметить, что, хотя в Российской Федерации отдельными промышленными компаниями уже ведется работа по созданию требований, регламентирующих использование русского языка при создании технической документации, единых и стандартизированных спецификаций не существует [62].
Предметом анализа являются грамматические правила спецификаций ASD-STE100 и проект спецификаций Упрощенного Технического Русского языка (УТР), разработанный лингвистами компании АВИАОК Интернейшенел. Список грамматических правил спецификаций УТР приведен в Приложении А.
В рамках поставленной задачи необходимо определить, какие отношения между словами являются существенными для анализа технического текста. Для решения задачи проведем анализ ограничений, накладываемых на естественный язык с целью его стандартизации.
Основой спецификаций ASD-STE100 является ограниченная терминологическая база. Словарь спецификаций (выпуск 2007 года) насчитывает 939 слов, в число которых входят как разрешенные слова, так и слова, использование которых в технической документации запрещено. В словаре приведены базовые формы слов с указанием части речи. При этом указано, что формы базового слова, формирующие его парадигму,. в соответствии со спецификациями должны наследовать все его свойства. Таким образом, ключевым элементом словаря является базовая форма, имеющая ссылки на все свои словоформы. В русском языке, как и в других, существуют правила для определения базовых форм слова, однако эти правила определяют формы только для большинства слов и имеют свои исключения. Парадигма имени существительного формируется [33,41] из словоформ, образованных по словообразующим грамматическим категориям числа и падежа. 2 значения категории числа и 6 значений категории падежа образуют парадигму из 12 словоформ: винт, винты, винта, винтов, винтам ... Базовой формой существительного является форма в единственном числе, именительном падеже. Однако, некоторые существительные имеют только одно значение категории числа, либо единственное, либо множественное (небо, ножницы). Таким образом, для определения базовой формы любого имени существительного формулируется следующее правило: базовой формой является существительное в именительном падеже, единственного числа, либо множественного числа, если единственного числа не существует. Подобные исключения существуют в русском языке для других частей речи, а так же и в других языках. Поэтому целесообразным представляется для каждой словоформы определить свойство "вид словоформы" со значением "базовая/второстепенная". Данное свойство будет определяться на этапе составления словаря либо автоматически, либо с помощью специалиста.
Автоматический анализ естественного языка
Процесс чтения предложения исходного языка и определения его структуры называется разбором предложения или парсингом (англ. parsing, лат. pars). Программа или, чаще, процедура, осуществляющая грамматический разбор фразы или предложения называется анализатором или парсером. В вычислительной лингвистике парсеры используются для автоматизации процесса анализа языка и выполняют, в базовом варианте, следующие действия: 1. разложение входящей последовательности символов на элементарные компоненты; 2. классификацию компонент; 3. составление классифицированных компонентов в единую синтаксическую структуру.
В приложениях теории вычислительных машин и систем для формальных языков парсеры используются как часть процесса компиляции для перевода кода с одного программного уровня на другой. В случае обработки естественных языков парсеры используются для распознавания словоформ, синтаксического и семантического анализа. Таким образом, парсеры бывают морфологическими, синтаксическими и семантическими.
Морфологические парсеры проводят анализ слов предложения с целью определения их грамматических свойств и выделения базовой формы слова. Синтаксические рассматривают предложение с целью построения его синтаксической структуры, например в термах порождающих грамматик. Семантические парсеры дополняют функционал синтаксических путем выделения семантических свойств анализируемых элементов. Полноценная система анализа текста на естественном языке подразумевает реализацию всех трех типов парсеров, поскольку синтаксические парсеры предполагают наличие автоматически распознанных словоформ, им необходимы морфологические парсеры, а для работы семантических парсеров необходима синтаксическая информация.
Понятие слова в лингвистической теории неразрывно связано с понятием словоформы. Например, слово люк представлено словоформами люк, люка, люку, люком, люке, люки, люков, люкам, люками, люках. В письменности словоформы разделены пробелами и знаками препинания. Таким образом словоформу в графическом понимании можно определить как последовательность числобуквенных символов, ограниченную с обеих сторон пробелами, которая может включать в себя апострофы и дефисы, но не знаки препинания [78]. Для формирования списка словоформ морфология использует следующие механизмы: словоизменение (inflection): образование словоформ той же лексемы, имеющих разные грамматические значения (винт, винт/ам); словообразование (derivation/compounding): образование новых слов путем комбинирования слова с аффиксами (чист/ый, чист/ить, частотно/-амплитудный).
Множество словоформ, образованных из базовой словоформы с помощью механизма словоизменения, называется словарной парадигмой. Это множество можно также использовать для определения слова как абстрактного понятия, проявляющегося, через свои словоформы. Для именования парадигмы используется базовая форма (БФ) слова, которая, как правило, может быть легко определена. В русском языке БФ существительного - имен, пад., ед. ч. (поверхность), глагола — инфинитив (наносить). Каждую словоформу можно представить тремя значениями (SF, SC, SR): написанием, синтаксической категорией и семантическим представлением.
Синтаксическая категория слова является комбинацией его грамматических характеристик, определяющих его как словоформу: СМИ = сущ., мн. ч., им. п. Семантическое представление определяет слово целиком я служит признаком, объединяющим словоформы в парадигму, таблица 2.1.
Традиционно морфологический анализ предполагает разбитие словоформы на элементарные составляющие — морфемы. Морфемы являются минимальными значащими единицами языка. В отличие от слов языка, количество которых неограниченно, множество морфем в языке конечно. Понятие морфемы абстрактно, поскольку морфема представляет собой набор алломорфов, т. е. форм, которые эта морфема может принять. Например, в словах бегу, бежать морфема "бег-" представлена двумя алломорфами (бёг-и беж-). Морфемы, как и слова, могут быть описаны тремя значениями SF, SC, SR.
Полноценный морфологический анализ неизвестного слова состоит из трех этапов. Во-первых, написание словоформы должно быть разбито на морфемы (сегментация). Во-вторых, посредством поиска в хранилище морфем для каждого элемента определяются его грамматические характеристики (лексический поиск). В-третьих, все элементы сцепляются для формирования анализируемого слова и результата его анализа (конкатенация). Несмотря на то, что сегментации подверглось только написание словоформы, сцепление проводится на всех трех уровнях представления словоформы и морфемы: SF, SC, SR, т.е. морфемы сцепляются на семантическом и синтаксическом уровнях для формирования семантического и синтаксического образа словоформы.
Поддержка методов описания синтаксической структуры
1. Для каждой вершины начального графа перебираются связи с соседними слева вершинами. Для каждой такой пары вершин применяются правила слияния. В случае удовлетворения условий правила слияния, образуется новая СГ. Для каждой новой СГ по такой же схеме применяются все ПС. 2. На следующем этапе первым (прямым) проходом обходятся все вершины модифицированного графа от начала предложения по направлению к концу, при этом каждая вершина помечается расстоянием до начала предложения. При подсчете расстояния мощности всех связей считаются равными 1. Некоторые вершины будут обходиться более одного раза. С целью оптимизации менять расстояние нужно, только если новое значение меньше предыдущего. 3. За время второго прохода (обратного) из всех левых связей каждой вершины выбираются те, которые помечены минимальным расстоянием до начала предложения, и помечаются как части найденного решения.
При этом дальнейшее продвижение влево по графу ведется только по ребрам с минимальным расстоянием. Реализация предложения в виде дольного графа позволяет использовать рекурсивные алгоритмы. Т.е. достаточно определить базовый алгоритм применения правил для одной вершины и вызывать его рекурсивно для всех соседей этой вершины. Выполнение остановится, когда единственным соседом вершины окажется либо вершина начала, либо вершина конца предложения. Для реализации процесса применения ПС определим следующий алгоритм, где BASE - вершина, для которой в данный момент выполняется алгоритм, LEFT - текущая вершина слева от BASE. 1. Есть ли у вершины BASE левые связи? 2. Если нет, завершить выполнение. 3. Определить соседнюю вершину слева LEFT. 4. Перебрать все правила слияния для пары вершин BASE-LEFT 5. Если атрибуты вершин BASE-LEFT удовлетворяют условиям ПС, создать новую вершину, установить ее атрибуты в соответствии с множеством SET данного ПС и связать новую вершину слева со всеми левыми соседями вершины LEFT, и справа со всеми правыми вершины BASE 6. Рекурсивно вызвать этот же алгоритм для новой вершины. 7. Рекурсивно вызвать этот же алгоритм для каждой вершины справа от BASE. 8.
Перейти к пункту 2. Если вызвать этот алгоритм для любой вершины из первой доли начального графа, то ко всем вершинам начального графа и ко всем полученным синтаксическим группам будут применены все правила слияния, в результате чего будет получен модифицированный граф предложения. Для реализации прямого прохода определим следующий алгоритм поведения каждой вершины (рис. 3.7), где D — текущее расстояние вершины до начала предложения, DS — регистр для хранения расстояния. Для запуска процедуры пометки всех вершин графа достаточно вызвать этот алгоритм для вершины начала предложения с параметром 0 (нулевое расстояние до вершины). Алгоритм завершит работу, только достигнув конца предложения (выполнившись для каждой вершины графа). Алгоритм для реализации обратного прохода так же может быть организован рекурсивно. Реализация алгоритма представлена на рисунке 3.8. Для инициации процесса необходимо выполнить этот алгоритм на последнем элементе предложения. Рекурсивно вызвав себя для всех соседних слева элементов, алгоритм завершит работу, достигнув вершины начала предложения. Отработка обоих алгоритмов позволяет найти все решения с минимальным количеством вершин. Если в графе есть хоть одна вершина, длина которой равна длине предложения, то она будет являться единственным решением. Если длина всех вершин меньше длины предложения, то алгоритм отыщет все комбинации решений с минимальным количеством вершин.
Пример работы алгоритма показан на рис. 3.9, где серым цветом выделены вершины, формирующие подграфы решений. Отметим, что СГ [1-0 2-1 3-1] может быть образована как слиянием вершин [1-0 2-1] [3-1], так и вершин [1-0] [2-1 3-1]. Для избежания дублирования результатов слияния необходимо определить принцип уникальности синтаксической группы — т.е. механизм, запрещающий создание новой синтаксической группы, если такая уже была создана в результате. Уникальность СГ должна определяться родительскими вершинами и ее атрибутами. В современной теории анализа алгоритмов время выполнения задачи принято выражать некоторой функцией f(n), зависящей от размерности задачи. Если время выполнения анализируемого алгоритма прямо пропорционально размерности задачи, то данный алгоритм имеет сложность порядка f(n) и обозначается как 0f(n). Функция f(n) является сложностью алгоритма и имеет смысл линейной, квадратичной или другими видами зависимости от параметра. Чем ниже степень сложности функции, тем более эффективным является оцениваемый ею алгоритм. По степени сложности оценки эффективности расположены в следующем порядке.
Оценим вычислительную сложность предлагаемых алгоритмов. Для этого необходимо принять некоторые упрощения. Будем считать, что к каждой паре вершин применяются все правила слияния (обозначим их количество через Y), хотя в действующем алгоритме правила слияния могут быть разбиты на категории, например, по частям речи. Таким образом, для узлов, представляющих собой имена существительные, будут применяться только те правила слияния, которые предназначаются только для существительных. Предположим, что предложение S образовано из N слов W; (і: 1..N). При этом каждое слово W; представлено строго определенным количеством словоформ F. Положим F одинаковым для всех слов и условно считающимся средним количеством словоформ.
Экспериментальная проверка теоретической оценки вычислительной сложности алгоритмов
Проверка оценки производительности реализованных алгоритмов проводилась на компьютере с процессором Intel Pentimn 4 3.00GHz под управлением операционной системы MS Windows ХР. Оценка проводилась в двух режимах: симуляционном и достоверном.
В симуляционном режиме правила слияния отсутствуют, при этом каждая вершина автоматически сливается с каждым своим соседом. Данный режим иллюстрирует проблему экспоненциального взрыва, т.е. неконтролируемого роста количества вариантов разбора.
Производительность реализованных алгоритмов соответствует теоретическим оценкам (3.9), полученным в главе 3. В среднем количество словоформ для каждого русского слова колеблется в пределах одной - трех. Случаи с 4 или более словоформами редки. Приняв за среднее количество словоформ 2, подсчитываются временные характеристики обработки предложений с количеством слов от 7 до 30 (14 - 60 словоформ). При этом время обработки самых сложных предложений не превышает 45 секунд.
В достоверном режиме программа оперировала набором из 200 правил слияния, соответствующих синтаксису русского языка. На вход анализатора подавались предложения длиной до 38 слов. Количество словоформ для каждого конкретного слова варьировалось от 1 до 6. При этом количество вершин в модифицированном графе находилось в границах от 30 до -3000. Время разбора большинства слов лежит в рамках 1 секунды. На разбор самого сложного случая потребовалось немногим более 5 секунд (таблица 4.1).
При этом количество вариантов разбора существенно ниже и соответствует теоретической оценке (ЗЛО) при значении q 0.44, что соответствует оценке сверху 0(п"). Время обработки тестовых предложений (до 20 слов) не превышает 1 секунды.
Эти цифры неточно соответствуют формулам, выведенным в разделе, посвященном теоретической оценке вычислительной сложности алгоритмов. Происходит это потому, что распределение словоформ по словам и их отношение к правилам слияния сугубо индивидуально каждому предложение и поддается только приблизительной оценке. Однако характер изменения величин в зависимости от количества слов в предложении согласовывается с теоретическими оценками, что следует из графиков.
График на рисунке 4.9 показывает, как коррелирует время выполнения алгоритмов с количеством вершин в модифицированном графе предложения. Кривая количества вершин в графе являет собой полиноминальную кривую.
График на рисунке 4.10 показывает зависимость количества ребер и счетчика примененных правил алгоритмов от количества вершин в начальном графе предложения.
В данном подразделе покажем, как результаты метода ЛСА используются Системой лингвистической валидации технической документации (СЛВТД), предназначенной для проверки технической документации на соответствие проекту спецификаций Упрощенного Технического Русского (УТР) языка. Структурная схема системы показана на рисунке 4.11
Процесс валидации технической документации начинается и заканчивается в среде разработки документации, наиболее популярными из которых являются Adobe FrameMaker, Arbortext Epic, MS Office Word, Corel XMetal, oXygene.
Текстовое содержимое документа через модуль-адаптер, ответственный за взаимодействие с конкретной средой разработки, попадает в модуль графематического анализа.
Целью графематического анализа является подготовка текста к этапу применения лексического анализа. Для этого входной текст разбивается на параграфы, параграфы на предложения, предложения на слова и знаки препинания. Иными словами цепочка символов на входе анализатора преобразовывается в список элементов, подаваемых на вход модуля лексического анализа. Преобразование симметрично, т.е. по списку элементов можно построить исходную цепочку символов. Для реализации этого процесса был введен формализм таких понятий как параграф, предложение, слово и т.д. и описан следующей КС грамматикой:
Терминальный символ ALPHA представлен одной из строчных букв кириллического алфавита. В общем виде для Unicode строк этот символ может быть представлен как WCHARS - NUM - SPACE_CHAR - CRLF - U , где WCHARS - множество всех символов Unicode.
Анализатор для данной грамматики был реализован в виде конечного детерминированного преобразователя с магазинной памятью. Основной задачей анализатора является определение графематического типа каждого элемента из результирующего списка. Перечень всех графематических типов приведен в таблице 4.3.
