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

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

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

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

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

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

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

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

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

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

КС-язык

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

, где 



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






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

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) довольно просто.

См. также

Примечания

  1. http://classes.soe.ucsc.edu/cmps112/Spring03/readings/lambdacalculus/syntax.html
  2. https://docs.python.org/3.4/reference/grammar.html
  3. http://lua-users.org/wiki/LuaGrammar
  4. http://www.link.cs.cmu.edu/link/dict/introduction.html

Литература

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