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

Тип работы:
Реферат
Предмет:
ТЕХНИЧЕСКИЕ НАУКИ


Узнать стоимость

Детальная информация о работе

Выдержка из работы

Лексический анализ и выделение границ предложений с помощью Грамматик, Разбирающих Выражение_
Лексический анализ и выделение границ предложений с помощью Грамматик, Разбирающих Выражение
Килочек Ю. И.
МГТУим. Н. Э. Баумана yuri. kilochek@gmail. com
Аннотация. В данной статье рассматриваются традиционные подходы к лексическому анализу, такие как регулярные выражения, и отмечается, что в них отсутствуют механизмы устранения неоднозначностей во входном тексте. Вместо них, для описания лексической структуры языка, предлагается использовать Грамматику, Разбирающую Выражение (РВ-грамматику, Parsing Expression Grammar, PEG), в которой неоднозначность в принципе невозможна. Далее предлагается расширение PEG стеком синтезированных значений и семантическими действиями, для того чтобы из входного текста можно было синтезировать некоторые результаты. Расширенный PEG парсер был реализован в виде С++ библиотеки со встроенным языком описания грамматик. После чего была составлена грамматика для лексического анализа и выделения границ предложений русского языка, и реализована в терминах этой библиотеки. Для оценки качества получившегося токенизатора были использованы два корпуса, «Открытый Корпус» и «Национальный Корпус Русского Языка». Места корпусов, в которых токенизатор показывал особенно плохие результаты, были тщательно изучены и грамматика модифицирована таким образом, чтобы учитывать обнаруженные в там конструкции. После нескольких таких итераций финальная версия грамматики корректно выделила и корректно пометила как конец предложения 97. 99% токенов в «Открытом» корпусе и 98. 47% в «Национальном». Если учитывать только корректное выделение токенов (без пометки конца предложения), то результат становится 99. 21% и 99. 99% соответственно.
Ключевые слова: обработка естественных языков, лексический анализ, выделение границ предложений, грамматика разбирающая выражение
1 Введение
Лексический анализ и выделение границ предложений, если таковое требуется, часто являются первыми этапами обработки естественного языка. Любые ошибки на этой стадии распространяться через весь конвейер, и потому крайне важно свести их к минимуму.
Существует несколько подходов к лексическому анализу. Самым распространенным, вероятно, являются регулярные выражения, скомпилированные в детерминированный конечный автомат. Это наиболее высокопроизводительный подход, и действительно является лучшим выбором в том случае, если мощи регулярных языков достаточно. Если это не так, то их часто расширяют возможностью заглядывать вперед для определения наилучшего пути разбора и откатываться назад в случае
неудачи. Эти расширения не могут быть выражены в чистых регулярных выражениях и не могут быть скомпилированы в эффективный детерминированный конечный автомат. Если и этого недостаточно, можно обратиться к контекстно-свободным грамматикам и их различным подмножествам, рискуя дальнейшей потерей быстродействия.
По своей природе, естественные языки неоднозначны, даже на уровне лексики. Хотя регулярные выражения и контекстно-свободные грамматики способные распознавать неоднозначности, они не обладают механизмами выбора наиболее предпочтительного варианта разбора из возможных.
В 2004-ом году Брайан Форд ввел грамматику, разбирающую выражение (РВ-грамматику, Parsing Expression Grammar, PEG) [Ford, 2004], способ формального описания языка набором правил распознавания его строк, в отличие от регулярных выражений и контекстно-свободных грамматик, которые описывают язык правилами генерации его строк. РВ-грамматики внешне похожи на контекстно-свободные грамматики, которые дополнены регулярными операторами. Или, альтернативно, набор именованных регулярных выражений, которые ссылающихся друг на друга, разрешая, таким образом, рекурсию. Ключевое отличие от тех и от других в том, что оператор выбора упорядочен, то есть первому варианту отдается предпочтение перед вторым, что дает возможность явно выбирать между возможными вариантами разбора, и избавляет грамматику от неоднозначностей.
2 Грамматика, разбирающая выражение
РВ-грамматика это набор правил следующего вида:
¦ А & lt-- а.
Где, А — нетерминальный символ, а, а — выражение разбора. Одно из правил и его нетерминальный символ являются начальными, т. е. с них начинается разбор.
Выражение разбора это одно из следующего:
¦? — пустая строка
¦ а — терминальный символ
¦ А — нетерминальный символ
¦ а. (3 — последовательность
¦ а / (3 — упорядоченный выбор
¦ а* - повторение ноль или более раз
¦ ! а — предикат «НЕ»
Где, а и |3 — выражения разбора.
Для сокращения записи дополнительно также определяют следующие выражения разбора («=» означает «определено как»):
¦ а.? = а / г — необязательность
¦ а+ = а а* - повторение один или более раз
Лексический анализ и выделение границ предложений с помощью Грамматик, Разбирающих Выражение_
¦ & amp-а= ! ! а — предикат «И»
Где, а — выражение разбора.
Для задания группировки можно использовать скобки.
Парсер РВ-грамматик оперирует состоянием, которое содержит курсор (текущую позицию во входной строке). Выражения разбора выполняются как рекурсивные процедуры. Каждое может, продвинуть курсор вперед (опционально) и вернуть успех, либо вернуть неудача не двигая при этом курсор.
¦ е — всегда возвращает успех (не двигая курсор).
¦ а — если символ под курсором это а, двигает курсор вперед на один символ и возвращает успех. Иначе возвращает неудача.
¦ А — вызывает выражение разбора а, где, А & lt-- а -соответствующее правило грамматики, и возвращает его результат.
¦ а. — сохраняет состояние парсера. Вызывает а. Возвращает неудача, если, а вернуло неудача. Иначе вызывает (3. Если (3 вернуло неудача, то восстанавливает сохраненное состояние и возвращает неудача. Иначе возвращает успех.
¦ а. / (3 — вызывает а. Возвращает успех, если, а вернуло успех. Иначе вызывает (3 и возвращает его результат.
¦ а* - многократно вызывает а. Возвращает успех, как только, а впервые вернуло неудача.
¦ !а — сохраняет состояние парсера. Вызывает а. Возвращает успех, если, а вернуло неудача. Иначе восстанавливает сохраненное состояние и возвращает неудача.
Изначально курсор указывает первый символ во входной строке, и разбор начинается и вызова начального нетерминального символа.
3 Расширение РВ-грамматик стеком синтезированных значений и семантическими действиями
Форд определил РВ-грамматики таким образом, что они могут только распознавать строки, без синтеза каких либо результатов из их содержимого. В данном же случае текст необходимо преобразовать в список токенов с пометкой конца предложения. Этого можно добиться добавлением нового элемента в состояние парсера — стека синтезированных значений, который будет содержать изначальные аргументы, промежуточные величины и результаты вычислений, управляемых процессом разбора. Также необходимо добавить новое выражение разбора — семантическое действие:
@ f — извлекает п значений с вершины стека, где п — арность функции f. Вычисляет f и помещает её результаты на вершину стека. Никогда не двигает курсор и всегда возвращает успех.
Дополнительно нужно переопределить выражения разбора пустой строки и терминального символа так, чтобы они помещали соответствующие значения на вершину стека:
s — помещает пустую строку на вершину стека и возвращает успех, не двигая курсор.
а — если символ под курсором это а, двигает курсор вперёд на один символ, помещает, а на вершину стека и возвращает успех. Иначе возвращает неудача.
Эти расширения, вместе с набором предопределённых функций, позволяют синтезировать произвольные значения из входного текста. Например, для разбора беззнакового десятичного целого числа:
Integer & lt-- @push0 (@push10 (?multiply Digit @add) +
Digit & lt-- (0/½/¾/5/6/7/8/9) @char_to_int
где push0 помещает 0 на вершину стека, push10 помещает 10 на вершину стека, multiply извлекает два целых числа с вершины стека, умножает их и помещает результат обратно и char_to_int извлекает символ цифры с вершины стека, преобразует его в соответствующее число и помещает его обратно.
4 Первая реализация
Парсер РВ-грамматик с указанными расширениями был реализован в виде С++ библиотеки со встроенным языком описания грамматик, которая была названа pegasus (https: //github. com/yuri-kilochek/pegasus).
Затем, с использованием этой библиотеки, вручную была составлена простая грамматика, основанная на предположениях авторов этой статьи о том, какими могут быть токены и когда конкретный токен можно считать концом предложения.
Получившаяся программа-токенизатор, преобразует параграф неразмеченного текста и превращает его в список токенов с пометкой конца предложения. Например, следующий параграф:
Однако, например, роман «Мастер и Маргарита» был опубликован в 1966—1967 годах. В отношении этого произведения действует положение статьи 1281 пункт 3 ГК РФ.
Может быть преобразован в следующий список токенов:
Лексический анализ и выделение границ предложений с помощью Грамматик,
Разбирающих Выражение_
п Однако
п например п ,
п роман
п Мастер п и
п Маргарита п был
п опубликован
п 1966
п 1967 п годах
п отношении п этого
п произведения п действует п положение п статьи п 1281 п пункт п 3 п ГК п РФ
Где «п» обозначает обыкновенный токен, а «е» — оканчивающий предложение.
5 Оценка результатов и итеративное улучшение
Для оценки качества токенизатора были использованы два корпуса «Открытый Корпус» {http: //opencorpora. org) и «Национальный Корпус Русского Языка» (http: //opencorpora. org). С помощью простых скриптов на языке Python были сгенерированы пары из текста параграфа и списка помеченных токенов для каждого параграфа текста в каждом корпусе. Каждая такая пара является тестовыми примером для тестирования токенизатора.
Задача состоит в максимизации доли корректно выделенных и помеченных токенов. Эта величина вычисляется суммированием по всем тестовым примерам длин наибольших общих подпоследовательностей между «истинным» списком токенов из тестового примера и списком токенов полученных токенизатором из соответствующего неразмеченного
параграфа, и последующим делением этой суммы на общее число токенов во всех тестовых примерах. Следует отметить, что, при вычислении доли корректно выделенных и помеченных токенов, при вычислении наибольшей общей подпоследовательности, токены считаются равными тогда и только тогда, когда совпадают составляющие их строки и совпадают их метки конца предложения. При вычислении же доли только корректно выделенных токенов, метки конца предложения игнорируются и токены сравниваются только по строкам. Всё это было реализовано в ещё одном Python скрипте. Как сам токенизатор, так и скрипты для генерации и выполнения тестов и вычисления результатов находятся в открытом доступе (https: //github. com/yuri-kilochek/graphematizer).
Как и ожидалось, первая версия грамматики показала довольно слабый результат, только около 80%. Для его улучшения в скрипт осуществляющий выполнение тестов и вычисление результатов было добавлено вычисление и вывод результатов отдельных тестов. Таким образом, были выявлены тесты, которые показывали особенно плохие результаты. После их изучения грамматика были добавлены правила для распознавания содержащихся в них конструкций, которые не были учтены при изначальном составлении. Повторением этой процедуры несколько раз результат был значительно улучшен. В итоге получилась следующая грамматика:
ws & lt-- ((| п) @рор)+
punctuation & lt-- е — @append_ch @append_tok
е, @append_ch @append_tok e — @append_ch @append_tok @set_last_end ?: @append_ch @append_tok s … @append_ch @append_tok @set_last_end e … @append_3ch @append_tok @set_last_end ?. @append_ch @append_tok @set_last_end e ! @append_ch @append_tok @set_last_end e? @append_ch @append_tok @set_last_end @set_last_end? • @append_ch @append_tok e «@append_ch @append_tok e «@append_ch @append_tok? (@append_ch @append_tok e) @append_ch @append_tok? ] @append_ch @append_tok? / / @append_2ch @append_tok e / @append_ch @append_tok? ° @append_ch @append_tok? + @append_ch @append_tok e % @append_ch @append_tok? & amp- @append_ch @append_tok digit & lt--0|l|2|3|4|5|6|7|8|9 digits & lt-- e (digit @append_ch)+
number & lt-- digits ((. | ,) Sappend ch digits Sappend str)?
Лексический анализ и выделение границ предложений с помощью Грамматик,
Разбирающих Выражение_
@append_tok number_range & lt-- number
s (- I — I -) @append_ch @append_tok number
list_index & lt-- @set_last_end number г (. |)) @append_ch @append_tok
letter_block & lt-- s ((!ws ?punctuation) $ @append_ch)+
@append_tok token & lt-- number_range !(- | -) | list_index | number !(- | -) | punctuation | letter_block
tokens & lt-- @push_empty_list (ws? token)* @set_last_end
Где pop извлекает одно значение с вершины стека, append_ch присоединяет символ к концу строки, append tok присоединяет строку как обычный токен к концу списка токенов, set_last_end помечает последний токен в списке как конец предложения, append_2ch и append_3ch присоединяют два и три символа к концу строки соответственно и push empty list помещает пустую строку на вершину стека. «(», «)», «?», «!», ««, «п» and «$» обозначают терминальные символы «(», «)», «?», «!», пробел, перевод строки и любой символ соответственно.
Следует отметить, что получение конкретно этой грамматики не является целью данной работы, которая состоит в оценке применимости РВ-грамматик к поставленной задаче. Данная грамматика приведена исключительно в качестве примера.
6 Результаты и выводы
Полученная в итоге грамматика корректно выделяет и помечает как концы предложений 97. 99% токенов для «Открытого Корпуса» и 98. 47% для «Национального Корпуса Русского Языка». При рассмотрении только корректного выделения токенов, игнорируя пометки конца предложения, результаты составляют 99. 21% и 99. 99% соответственно. Обратим внимание, что сравнительно высокие результаты, полученные на «Национальном Корпусе Русского Языка», не совсем корректны из-за структуры самого корпуса. Дело в том, что в нём знаки пунктуации совсем не размечены, поэтому решение считать ли сочетания вроде «),», «?!» и «…» одним токеном или разбивать их на отдельные буквы остается за пользователем корпуса. В данной работе было принято решение делать последнее.
На итерации, в которой в грамматику были добавлены правила для разбора диапазонов чисел и нумераций списков, было получено значительное улучшение результата. Предположительно дальнейшее изучение тестов, показывающих плохие результаты и добавление правил
для таких конструкций как URI, телефонные номера, етш'-/-адреса и т. д. если там обнаружены, приведёт к ещё большему улучшению.
Итогом данной работы является заключение, что РВ-грамматики хорошо подходят для лексического анализа естественных языков и определения границ предложений.
Список литературы
[Ford, 2004] Parsing Expression Grammars: A Recognition-Based Syntactic Foundation // http: //pdos. csail. mit. edU/papers/parsing:popl04. pdf

ПоказатьСвернуть
Заполнить форму текущей работой