Синтаксический анализ

Материал из NLPub
Перейти к: навигация, поиск
NLPub-QA.svgЭто уже обсуждалось на NLPub Q&A!
Предмет данной статьи обсуждался на нашем вопрос-ответном сервисе.

Синтаксический анализ (парсинг) — преобразование последовательности символов на естественном или искусственном языке в соответствии с формальной грамматикой. Англоязычный термин parsing образован от латинского pars ōrātiōnis, означающего «часть речи».

SearchDocument.svg Найдите научные статьи по этой теме в трудах российских NLP-конференций.

Контекстно-свободные грамматики

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

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

Вероятностная контекстно-свободная грамматика получается, наложением на множество правил распределения вероятностей.

Вероятностная (стохастическая) контекстно-свободная грамматика, - это система вида , где - конечное множество правил вывода. Множество правил можно представить в виде объединения: , где и .

Каждое правило имеет вид: ,

где , и - вероятность применения правила , которая удовлетворяет следующим условиям: и .

КС-язык

Для будем говорить, что непосредственно выводимо из (обозначается как , если существуют , для которых и в грамматике имеется правило .

Через обозначается рефлексивное транзитивное замыкание отношения .

Множество слов называется КС-языком. Таким образом, КС-язык - это множество слов, порождаемых контекстно-свободной грамматикой.

Дерево вывода

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

Алгоритм построения дерева вывода грамматики выглядит следующим образом.

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

Порядок нумерации ярусов дерева: корень дерева располагается в нулевом ярусе. Вершины дерева, смежные с корнем образуют первый ярус и т.д. Дуги, выходящие из вершин -го яруса, ведут к вершинам яруса.

Высотой дерева называется максимальная длина пути от корня дерева к листу (т.е. номер последнего яруса).

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

Применение контекстно-свободных грамматик

Контекстно-свободные грамматики хорошо зарекомендовали себя в задачах разбора многих западноевропейских языков, таких как английский.

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

Машинный разбор предложения с использованием контекстно-свободных грамматик реализуется при помощи алгоритма Эрли или алгоритма Кока — Янгера — Касами.

Примеры КС-грамматик

  • Язык Дика (последовательность правильных расстановок скобок)

Язык Дика описывается грамматикой следующего вида:

, где 



Продукционные правила грамматики: 






Если интерпретировать как открывающую скобку -го типа, а как закрывающую скобку -го типа, то язык Дика описывает правильную расстановку скобок типов. А именно:

1. Для любой начальной последовательности число открывающих скобок -го типа не меньше числа закрывающих скобок этого же типа
2. Для всей последовательности число вхождений открывающей скобки -го типа равно числу вхождений закрывающей скобки -го типа.
  • Язык арифметических выражений

Пример грамматики, генерирующей строки, представляющие арифметические выражения со следующими операциями: и числами как операндами.

, где:



 (где  - произвольное число)





Например, выражение получается в результате последовательного выполнения правил: :

* 
* 


  • Лямбда-исчисление [1].
  • Грамматики языков программирования (Python [2] , Lua [3] )

Пример

Пусть задана контекстно-свободная грамматика c правилами :

Предложение the man walks будет представлено в виде выражения: . Вероятность такого дерева разбора равна , однако на практике удобно использовать суммы логарифмов вероятностей, чем произведения вероятностей.

Грамматика связей

Грамматика связей - это грамматическая система для классификации естественных языков указывающая связи между последовательностями слов. Вместо использования part-of-speech tags на основе правил для разбора предложений, грамматика связей использует связи для создания синтаксической структуры для языка.

Основная идея

Слова рассматриваются как блоки с выходными разъемами (connectors).

Есть несколько типов разъемов; а также, разъемы могут также указывать вправо, или влево. Раъем указывающий влево соединяется с разъемом, указывающим вправо того же самого типа иного слова. Два разъема вместе формируют "связь" (link).

Разъемы указывающие направо, помечаются знаком "+", указывающие влево - знаком "-".

Слова имеют правила о том, как их разъемы могут быть соединены, т.е. правила о том, что будет составлять корректное использование данного слова. Корректное предложение - это предложение, в котором все представленные слова используются корректно, в соответствии с их правилами и которые также удовлетворяют определенным глобальным правилам. [4]

Правила для слов (word rules)

Обычная запись в словаре выглядит следующим образом:

blah: A+;

Это означает, что если слово "blah" используется в предложении, оно должно формировать связь "A" с другим словом, т.е. должно быть другое слово справа с разъемом (connector) типа "A-". В противном случае, предложение некорректно. Выражение, следующее за двоеточием - это "требования к связям" (linking requirement) для слова.

Слово может иметь более одного раъема. Это будет обозначаться следующим образом:

blah: A+ & B+;

Слово может иметь такие правила, что только один из двух (или один из нескольких) разъемов будет использовано, но один из них обязательно должен быть использован. Это обозначается следующим образом:

blah: A+ or B-;

Это означает что если слово может сделать либо связь типа "А" справа, либо связь типа "B" слева, то его использование в предложении будет корректным, но оно обязано содержать одну из связей и не может сделать обе связи. Эти правила могут быть скомбинированы. Например:

blah : A+ or (B- & C+);

Это означает что слово должно содержать либо связь типа "A" справа, либо связь типа "B" слева и связь типа "С" справа. Другие комбинации будут некорректны.

Также выражения могут быть вложенными без ограничений:

blah: (A+ or B-) & (( C- & A+ & (D- or E-)) or F+);

Некоторые раземы опциональны, для этого используются фигурные скобки. Например:

blah: A+ & {B+};

Это означает что слово должно содержать связь типа "А" справа, и оно может содержать связь типа "В" справа, но не обязано содержать её. Фигурные скобки могут также заключать в себе сложные выражения, например:

blah: (A+ or B+) & {C- & (D+ or E-)};

Эквивалентный способ записи опционального выражения "{X-}" следующий: "(X- or ())".

Слово может также создавать неопределенное число связей одного типа с другими словами. Для этого, используется multi-connector символ "@". Например, в следующем примере слово может создавать любое число связей типа F со словами справа (но не обязано содержать их).

blah: (A+ or B+) & {C- & (D+ E-)} & {@F+};

(Если слово имеет "@A+", без фигурных скобок, то оно обязано содержать как минимум одну связь типа A (справа), остальные опциональны). Порядок элементов в выражении (connector expression) важен. Он диктует относительную близость (relative closeness) слов, которые будут соединены.

blah: A+ & B+;

В этом примере слово "blah" должно образовывать связь типа "А" справа и связь типа "B" справа, и слово, образующее связь типа "А" должно быть ближе, чем слово образующее связь типа "В".

Однако, это относится только к соединениям одной направленности. Для разъемов, указывающих в противоположных направлениях, порядок не важен. Поэтому,

blah: A+ & B-;

означает то же самое, что и:

blah: B- & A+;

В этом отношении:

blah: A- & B+ & C+ & D-;

означает то же самое, что:

blah: B+ & C+ & A- & D-;

Для выражений с оператором "or", таких как "A+ or B+", порядок элементов не важен.

Запись в словаре поэтому содержит слово, последующее двоеточие, а затем выражение связей (connector expression), заканчивающееся точкой с запятой. Словарь содержит серию таких записей. Любое число слов может быть помещено в список, разделенный пробелами, и все они будут обладать требованиями на связи *linking requirement):

blah blee blay: A+;

Имя раъема (connector name) должно содержать одну или несколько заглавных букв (может быть использовано их любое число), с последующими "+" или "-".

Также следует упомять концепцию "разъединителей" (disjunct). Разъединитель - это набор типов разъемов (connector types), образующих корректное использование слова. Выражение в словаре для любого слова может быть представлено как набор разъединителей (set of disjuncts).

Если, например, слово имеет следующее выражение:

blah: {C-} & (A+ or B+);

тогда, оно имеет следующие четыре разъединителя:

C- A+
A+
C- B+
B+

Эти разъединители отображают все корректные использования слова "blah". Использование C- и A+ - корректно для слова, в то время как использование A+ и B+ некорректно. Разделители играют важную роль во внутренней работе парсера связей.

Глобальные правила (Global rules)

Также как и правила слов ("word rules"), которые указаны в словаре, есть два других глобальных правила, которые контролируют, как слова могут быть соединены.

Прежде всего, ссылки не могут пересекаться. Например, следующий способ соединения четырех слов ( соединение "cat" к "dog" и "horse" к "fish") будет неправильным. Парсер просто не найдет таких связей.

       +------------+
 +-----|------+     |
 |     |      |     |
cat   horse  dog  fish

Это правило планарности ("planarity rule" или "crossing-links"). Во вторых, все слова в предложении должны быть косвенно связаны (indirectly connected) с каждым другим словом. Поэтому следующий путь соединения этих четырех слов также будет некорректным:

 +---------+        +-----+
 |         |        |     |
cat      horse     dog   fish

Это правило вовлеченности ("connectivity" rule). Поэтому, корректное предложение - это предлоежение, которое может быть связано следующими связями:

  • все используемые слова предложении, удовлетворяют правилам связей (linking requirements);
  • не нарушаются правила планарности (crossing-links) и вовлеченности (connectivity).


Грамматика связей и её отношения с другими системами

Структура, назначенная предложению грамматикой связей значительно отличается от других грамматических систем (хотя она связана с грамматикой зависимостей). Вместо того, чтобы размышлять в терминах синтаксических функций (как субъект и объект), или составляющих (например, "глагольная составляющая"), необходимо размышлять в терминах взаимоотношений между парами слов. В предложении ниже, например, есть "S"-отношение (субъект) между "dog" и "has"; отношение "PP" (past-participle) между "has" и "gone"; и "D"-отношение (determiner) между "the" и "dog:

 +-----Ds-----+          
 |     +---A--+-Ss-+-PP-+
 |     |      |    |    |
the black.a dog.n has gone

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

Инструменты

Название Метод Языки Лицензия Платформа
АОТ грамматика HPSG русский, английский, немецкий LGPL Linux, Windows
ISPRAS API Texterra машинное обучение русский, английский Бесплатная для исследовательских целей + коммерческая Веб-сервис, Java, Python
MaltParser машинное обучение русский, английский Собственная Java
MSTParser максимизация остовного дерева английский, португальский Apache License Java
Link Grammar Parser грамматика связей русский, английский BSD Linux, Windows
AGFL грамматика аффиксов над конечной решёткой русский[5], английский, французский, испанский, арабский GPL Linux, Windows
NLTK машинное обучение английский Apache License Python
MBSP машинное обучение английский GPL Python
Pattern правила, регулярные выражения английский, испанский, немецкий, французский, итальянский, нидерландский BSD Python
Solarix правила русский, английский Коммерческая Linux, Windows
ABBYY Compreno правила русский Коммерческая Windows
AskNet правила русский, английский Коммерческая Windows
DictaScope правила русский Коммерческая FreeBSD, Windows
ЭТАП-3 правила русский, английский н/д Windows
Синтактико-Семантический Анализ Русского Языка функциональная модель языка русский Коммерческая Веб-сервис
The Stanford Parser машинное обучение английский, немецкий, арабский, китайский, болгарский, итальянский, португальский GPL Java
ZPar машинное обучение английский, китайский, румынский GPL v3 C++
mate-tools машинное обучение английский, немецкий, китайский, испанский GPL v2 Java
zamgi машинное обучение русский некоммерческая .NET on Linux, Windows

См. также

Примечания

Литература

  1. Фу К. Структурные методы в распознавании образов. М.: Мир. 1977
  2. Ахо А., Ульман Дж. - Теория синтаксического анализа, перевода и компиляции. Том 1. М.: Мир, 1978