Синтаксический анализ
Это уже обсуждалось на NLPub Q&A! Предмет данной статьи обсуждался на нашем вопрос-ответном сервисе. |
Синтаксический анализ (парсинг) — преобразование последовательности символов на естественном или искусственном языке в соответствии с формальной грамматикой. Англоязычный термин parsing образован от латинского pars ōrātiōnis, означающего «часть речи».
Содержание
Контекстно-свободные грамматики
Контекстно-свободной грамматикой называется система , где и - конечные множества терминальных и нетерминальных символов соответственно, такие что , а - стартовая аксиома. Символом обозначено конечное множество правил вывода (или правил подстановки), обозначаемых следующим образом: , где , а .
В практических задачах часто используют вероятностные контекстно-свободные грамматики.
Вероятностная контекстно-свободная грамматика получается, наложением на множество правил распределения вероятностей.
Вероятностная (стохастическая) контекстно-свободная грамматика, - это система вида , где - конечное множество правил вывода. Множество правил можно представить в виде объединения: , где и .
Каждое правило имеет вид: ,
где , и - вероятность применения правила , которая удовлетворяет следующим условиям: и .
КС-язык
Для будем говорить, что непосредственно выводимо из (обозначается как , если существуют , для которых и в грамматике имеется правило .
Через обозначается рефлексивное транзитивное замыкание отношения .
Множество слов называется КС-языком. Таким образом, КС-язык - это множество слов, порождаемых контекстно-свободной грамматикой.
Дерево вывода
При выведении из грамматики слов языка существует чрезвычайно полезное представление в виде так называемого дерева вывода. Это дерево наглядно показывает, каким образом происходит процесс порождения слова контекстно-свободного языка.
Алгоритм построения дерева вывода грамматики выглядит следующим образом.
- Корень дерева помечается аксиомой грамматики .
- Пусть при выводе слова на очередном шаге в процессе вывода применяется правило , где . Тогда из самой левой вершины-листа дерева, помеченной символом (при обходе листьев дерева слева направо), проводится дуг, которые помечаются слева направо символами соответственно.
- После построения дуг и вершин для всех правил грамматики в выводе слова, все листья помечаются терминальными символами (элементами множества ) и результирующее слово получается при обходе листьев дерева слева направо.
Порядок нумерации ярусов дерева: корень дерева располагается в нулевом ярусе. Вершины дерева, смежные с корнем образуют первый ярус и т.д. Дуги, выходящие из вершин -го яруса, ведут к вершинам яруса.
Высотой дерева называется максимальная длина пути от корня дерева к листу (т.е. номер последнего яруса).
Пусть - некоторый вывод слова и - сопутствующее ему дерево вывода. Вероятность определяется как произведение вероятностей правил, образующих . Вероятность слова определяется как - то есть, как сумма вероятностей всех деревьев вывода, соответствующих данному слову.
Применение контекстно-свободных грамматик
Контекстно-свободные грамматики хорошо зарекомендовали себя в задачах разбора многих западноевропейских языков, таких как английский.
Также контекстно-свободные грамматики описывают грамматическую структуру большинства языков программирования.
Машинный разбор предложения с использованием контекстно-свободных грамматик реализуется при помощи алгоритма Эрли или алгоритма Кока — Янгера — Касами.
Примеры КС-грамматик
- Язык Дика (последовательность правильных расстановок скобок)
Язык Дика описывается грамматикой следующего вида:
, где Продукционные правила грамматики:
Если интерпретировать как открывающую скобку -го типа, а как закрывающую скобку -го типа, то язык Дика описывает правильную расстановку скобок типов. А именно:
1. Для любой начальной последовательности число открывающих скобок -го типа не меньше числа закрывающих скобок этого же типа 2. Для всей последовательности число вхождений открывающей скобки -го типа равно числу вхождений закрывающей скобки -го типа.
- Язык арифметических выражений
Пример грамматики, генерирующей строки, представляющие арифметические выражения со следующими операциями: и числами как операндами.
, где: (где - произвольное число)
Например, выражение получается в результате последовательного выполнения правил: :
* *
Пример
Пусть задана контекстно-свободная грамматика 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) довольно просто.
См. также
Примечания
- ↑ http://classes.soe.ucsc.edu/cmps112/Spring03/readings/lambdacalculus/syntax.html
- ↑ https://docs.python.org/3.4/reference/grammar.html
- ↑ http://lua-users.org/wiki/LuaGrammar
- ↑ http://www.link.cs.cmu.edu/link/dict/introduction.html
Литература
- Фу К. Структурные методы в распознавании образов. М.: Мир. 1977
- Ахо А., Ульман Дж. - Теория синтаксического анализа, перевода и компиляции. Том 1. М.: Мир, 1978