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

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

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

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

Контекстно-свободной грамматикой называется система  G=<V_T, V_N, R, s> , где  V_T и  V_N - конечные множества терминальных и нетерминальных символов соответственно, такие что  V_T \cap V_N =  \emptyset , а  s \in V_N - стартовая аксиома. Символом R обозначено конечное множество правил вывода (или правил подстановки), обозначаемых следующим образом:  r_i : A_i \rightarrow \beta , где  A_i \in  V_N , а  \beta \in (V_T \cup V_N)^{*} .

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

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

Вероятностная (стохастическая) контекстно-свободная грамматика, - это система вида G = (N, \Sigma, R_S, S ), где R_S - конечное множество правил вывода. Множество правил  R_S можно представить в виде объединения:  R_S =  \cup_{i=1}^{k}R_i , где  k = |V_N| и  R_i = \{ r_{i,1}, \ldots, r_{i,n_i} \} .

Каждое правило имеет вид:  r_{ij} : A_i \xrightarrow{p_{ij}} \beta_{ij}, j=1,\ldots,n_{i} ,

где  A_i \in V_N ,  \beta_{ij} \in (V_T \cup V_N)^{*} и  p_{ij} - вероятность применения правила  r_{ij}, которая удовлетворяет следующим условиям:  0 < p_{ij} \leq 1 и  \sum\limits_{j=1}^{n_i}p_{ij}=1 .

КС-язык

Для  \alpha, \gamma \in ( V_N \cup B_T)^{*} будем говорить, что \gamma непосредственно выводимо из \alpha (обозначается как \alpha \Rightarrow \gamma, если существуют  \alpha_1 \alpha_2 \in (V_N \cup V_T)^{*}, для которых  \alpha = \alpha_1 A_i \alpha_2, \gamma = \alpha_1 \beta_{ij} \alpha_2 и в грамматике имеется правило  A_i  \xrightarrow{p_{ij}} \beta_{ij}.

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

Множество слов  \{ \alpha : s \Rightarrow_{*} \alpha, \alpha \in V_T^{*}\} называется КС-языком. Таким образом, КС-язык - это множество слов, порождаемых контекстно-свободной грамматикой.

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

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

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

  • Корень дерева помечается аксиомой грамматики  s .
  • Пусть при выводе слова на очередном шаге в процессе вывода применяется правило  A \xrightarrow{p_{ij}} b_{i,1}b_{i,2}\ldots b_{i,m}, где  b_{i_l} \in V_N \cup V_T (l = 1,\ldots ,m) . Тогда из самой левой вершины-листа дерева, помеченной символом  A (при обходе листьев дерева слева направо), проводится  m дуг, которые помечаются слева направо символами  b_{i,1}b_{i,2}\ldots b_{i,m} соответственно.
  • После построения дуг и вершин для всех правил грамматики в выводе слова, все листья помечаются терминальными символами (элементами множества  V_T ) и результирующее слово получается при обходе листьев дерева слева направо.

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

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

Пусть  \omega(\alpha) = r_{i_{1}j_{1}}r_{i_{2}j_{2}}\ldots r_{i_{n}j_{n}} - некоторый вывод слова  \alpha \in L и  d_{\alpha} - сопутствующее ему дерево вывода. Вероятность  p(d_{\alpha}) определяется как произведение вероятностей правил, образующих  \omega(\alpha) : p(d_{\alpha})= p_{i_{1}j_{1}}p_{i_{2}j_{2}}\ldots p_{i_{n}j_{n}} . Вероятность слова \alpha определяется как  p (\alpha) = \sum p (d_{\alpha}) - то есть, как сумма вероятностей всех деревьев вывода, соответствующих данному слову.

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

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

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

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

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

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

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

 G = < V_T, V_N, R, s>, где 
 V_T = \{ a_1, b_1, a_2, b_2, \ldots, a_n, b_n \} 
 V_N = \{ S \} , s = S 
 R = \{ R_0, R_1, R_2, \ldots, R_n \} 
Продукционные правила грамматики: 
 R_0 : S \rightarrow  \varepsilon 
 R_1 : S \rightarrow  a_1 S b_1 S 
 R_2 : S \rightarrow  a_2 S b_2 S 
 R_3 : S \rightarrow  a_3 S b_3 S 
 \ldots 
 R_n : S \rightarrow a_n S b_n S 

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

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

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

 G = < V_T, V_N, R, s> , где:
 V_T = \{0,1,\ldots, 9, +,-,*,/ \}
 V_N = \{E\}, s = E 
 R = \cup R_i 
 R_1 : E \rightarrow  number  (где  number  - произвольное число)
 R_2 : E  \rightarrow  ( E ) 
 R_3 : E  \rightarrow  E + E 
 R_4 : E  \rightarrow  E - E 
 R_5 : E  \rightarrow  E * E 
 R_6 : E  \rightarrow  E / E 

Например, выражение  (3 + 12 ) / ( 2*4 - 3) получается в результате последовательного выполнения правил: R_6, R_2, R_2, R_3, R_4, R_5, R_1, R_1, R_1, R_1, R_1:

* E \xrightarrow{R_6} E / E \xrightarrow{R_2} (E) / E \xrightarrow{R_2} ( E ) / ( E ) \xrightarrow{R_3} ( E + E ) / ( E ) \xrightarrow{R_4} ( E + E ) / (E - E) \xrightarrow{R_5} ( E + E ) / ( E * E + E ) 
*  ( E + E ) / ( E * E + E ) \xrightarrow{R_1} (3 + 12) / ( 2 * 4 - 3 ) 


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

Пример

Пусть задана контекстно-свободная грамматика G = ((\text{S}, \text{NP}, \text{VP}), (\text{D}, \text{N}, \text{V}), R, \text{S}) c правилами R:

  • p(\text{S} \rightarrow \text{NP}\mbox{ }\text{VP}) = 0.8
  • p(\text{NP} \rightarrow \text{D}\mbox{ }\text{N}) = 0.5
  • p(\text{VP} \rightarrow \text{V}) = 1.0
  • p(\text{D} \rightarrow \textit{the}) = 0.3
  • p(\text{N} \rightarrow \textit{man}) = 1.0
  • p(\text{V} \rightarrow \textit{walks}) = 1.0

Предложение the man walks будет представлено в виде выражения: (\text{S} (\text{NP} (\text{D}\mbox{ }the) (\text{N}\mbox{ }man)) (\text{VP} (\text{V}\mbox{ }walks))). Вероятность такого дерева разбора равна ((0.3 \times 1.0 \times 0.5) \times (1.0 \times 1.0)) \times 0.8 = 0.06, однако на практике удобно использовать суммы логарифмов вероятностей, чем произведения вероятностей.

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

Грамматика связей - это грамматическая система для классификации естественных языков указывающая связи между последовательностями слов. Вместо использования 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. Фу К. Структурные методы в распознавании образов. М.: Мир. 1977
  2. Ахо А., Ульман Дж. - Теория синтаксического анализа, перевода и компиляции. Том 1. М.: Мир, 1978