Здравствуйте. Это статья об синтаксическом анализе предложений, их представлении. Для разбора предложений будет использоваться пакет NLTK и язык программирования Python (версии 2.7).

Вступление

В моей предыдущей статье мы рассматривали морфологические анализаторы и их использование. Настоятельно рекомендую прочитать её, чтобы лучше понять данную статью. Также там рассматривается установка и настройка пакета NLTK.

Приступим

Что такое синтаксический анализ? Синтаксический анализ – это процесс, который определяет, принадлежит ли некоторая последовательность лексем языку, порождаемому грамматикой. Обычно представляется в виде дерева для удобства понимания.

Рассмотрим некоторые грамматические особенности английского языка:

1. Неограниченные возможности
   Например, интересной особенностью предложений есть то, что они могут вкладываться в большие предложения. Рассмотрим следующие предложения:
   
   • Usain Bolt broke the 100m record
   • The Jamaica Observer reported that Usain Bolt broke the 100m record
   • Andre said The Jamaica Observer reported that Usain Bolt broke the 100m record
   • I think Andre said the Jamaica Observer reported that Usain Bolt broke the 100m record
   
   Если заменить предыдущие предложения на символ S, то следующие предложения строятся за шаблонами Andre said S, I think S. Эти шаблоны и другие подобные (например, S but S или S when S) позволяют на основе одного предложения строить больше предложений.
   
   С помощью подобных шаблонов построено огромное предложение в сказке «Винни-Пух» (Winnie the Pooh story by A.A. Milne, In which Piglet is Entirely Surrounded by Water):
   

   You can imagine Piglet's joy when at last the ship came in sight of him.] In after-years he liked to think that he had been in Very Great Danger during the Terrible Flood, but the only danger he had really been in was the last half-hour of his imprisonment, when Owl, who had just flown up, sat on a branch of his tree to comfort him, and told him a very long story about an aunt who had once laid a seagull's egg by mistake, and the story went on and on, rather like this sentence, until Piglet who was listening out of his window without much hope, went to sleep quietly and naturally, slipping slowly out of the window towards the water until he was only hanging on by his toes, at which moment, luckily, a sudden loud squawk from Owl, which was really part of the story, being what his aunt said, woke the Piglet up and just gave him time to jerk himself back into safety and say, «How interesting, and did she?» when — well, you can imagine his joy when at last he saw the good ship, Brain of Pooh (Captain, C. Robin; 1st Mate, P. Bear) coming over the sea to rescue him...

   Это предложение с простой структурой, на самом деле. В нём используются простые шаблоны, начиная с S but S, S when S. С этого примера можно сделать вывод, что языку присущие конструкции, которые позволяют, кажется, безгранично расширять предложение.
   
2. Двусмысленность в предложениях
   Известный пример двусмысленности с фильма Groucho Marx, «Animal Crackers» (1930):
   

   While hunting in Africa, I shot an elephant in my pajamas. How an elephant got into my pajamas I'll never know.

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

   >>> grammar = nltk.parse_cfg("""
    S -> NP VP
    PP -> P NP
    NP -> Det N | Det N PP | 'I'
    VP -> V NP | VP PP
    Det -> 'an' | 'my'
    N -> 'elephant' | 'pajamas'
    V -> 'shot'
    P -> 'in'
    """)
   >>> sent = ['I', 'shot', 'an', 'elephant', 'in', 'my', 'pajamas']
   >>> parser = nltk.ChartParser(grammar)
   >>> trees = parser.nbest_parse(sent)
   >>> for tree in trees:
        print tree
   
   (S
     (NP I)
     (VP
       (V shot)
       (NP (Det an) (N elephant) (PP (P in) (NP (Det my) (N pajamas))))))
   (S
     (NP I)
     (VP
       (VP (V shot) (NP (Det an) (N elephant)))
       (PP (P in) (NP (Det my) (N pajamas)))))
   

   
   Программа составила две структуры предложений. Это признак неоднозначности.
   

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

1. Простая грамматика
   Рассмотрим простейшую контекстно-свободную грамматику. Согласно определению, первым символом слева в первом правиле грамматики есть специальный символ S и все деревья должны иметь этот символ как корень.
   В следующем листинге приводится пример определения грамматики и использование его для анализа предложения «Mary saw Bob»:
   
   

   >>> grammar1 = nltk.parse_cfg("""
     S -> NP VP
     VP -> V NP | V NP PP
     PP -> P NP
     V -> "saw" | "ate" | "walked"
     NP -> "John" | "Mary" | "Bob" | Det N | Det N PP
     Det -> "a" | "an" | "the" | "my"
     N -> "man" | "dog" | "cat" | "telescope" | "park"
     P -> "in" | "on" | "by" | "with"
     """)
   >>> sent = "Mary saw Bob".split()
   >>> rd_parser = nltk.RecursiveDescentParser(grammar1)
   >>> for tree in rd_parser.nbest_parse(sent):
   	print tree
   	
   (S (NP Mary) (VP (V saw) (NP Bob)))
    

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

   Символ	Значение	Пример
   S	sentence	the man walked
   NP	noun phrase	a dog
   VP	verb phrase	saw a park
   PP	prepositional phrase	with a telescope
   Det	determiner	the
   N	noun	dog
   V	verb	walked
   P	preposition	in

   
   
2. Рекурсия в синтаксических структурах
   Грамматику называют рекурсивной, если категории с левой части ее правил также встречаются в правых частях. В следующем листинге, правило Nom -> Adj Nom содержит прямую рекурсию категории Nom, тогда как прямая рекурсия S возникает из комбинации двух правил S -> NP VP и VP -> V S.
   
   

   grammar2 = nltk.parse_cfg("""
     S  -> NP VP
     NP -> Det Nom | PropN
     Nom -> Adj Nom | N
     VP -> V Adj | V NP | V S | V NP PP
     PP -> P NP
     PropN -> 'Buster' | 'Chatterer' | 'Joe'
     Det -> 'the' | 'a'
     N -> 'bear' | 'squirrel' | 'tree' | 'fish' | 'log'
     Adj  -> 'angry' | 'frightened' |  'little' | 'tall'
     V ->  'chased'  | 'saw' | 'said' | 'thought' | 'was' | 'put'
     P -> 'on'
     """)
   

   
   Рекурсия этой грамматики позволяет строить, например, деревья с вложенными именительных выражениями и вложенными предложениями.
   

Синтаксический анализ на основе контекстно-свободной грамматики

Синтаксический анализатор – это программа, которая обрабатывает входное предложение согласно правилам грамматики и строит одну или несколько синтаксических структур, которые отвечают этой грамматике.

Мы рассмотрим два простых алгоритма синтаксического анализа: алгоритм рекурсивного спуска (стратегия «сверху-вниз») и алгоритм перемещения-сворачивания (стратегия «снизу-вверх»).
Рассмотрим каждый подробнее:

1. Алгоритм рекурсивного спуска.
   Простейший алгоритм анализатора, интерпретирующий грамматику, как спецификацию для превращения элемента высшего уровня не несколько элементов уровня ниже. Например: задача – найти элемент S. Правило S -> NP VP позволяет анализатору заменить этот элемент на два других (сначала найти NP, потом VP). Каждый из этих элементов может быть преобразован в другие элементы на основе правил грамматики. Такой процесс будет продолжаться до тех пор, пока не будет поставлена задача заменить элемент на слово, например telescope. Тогда происходит сравнение этого слова со словом из входной последовательности и если устанавливается соответствие между этими словами, то алгоритм продолжает работу. Если нет, то анализатор возвращается на шаг назад и пытается рассмотреть другие варианты.
   
   Алгоритм рекурсивного спуска осуществляется методом
   
   

   nltk.RecursiveDescentParser(grammar)

   
   Этот метод может иметь ещё необязательный параметр trace. Если значение этого параметра больше нуля, то анализатор будет выводить на экран результаты всех шагов синтаксического анализа.
   
   Давайте рассмотрим его работу. Будем разбирать предложение «Mary saw a dog». Сначала определим грамматику, а потом воспользуемся методом:
   
   

   >>> import nltk
   >>> grammar = nltk.parse_cfg("""
     S -> NP VP
     VP -> V NP | V NP PP
     PP -> P NP
     V -> "saw" | "ate" | "walked"
     NP -> "John" | "Mary" | "Bob" | Det N | Det N PP
     Det -> "a" | "an" | "the" | "my"
     N -> "man" | "dog" | "cat" | "telescope" | "park"
     P -> "in" | "on" | "by" | "with"
     """)
   >>> rd_parser = nltk.RecursiveDescentParser(grammar)
   >>> sent = 'Mary saw a dog'.split()
   >>> for t in rd_parser.nbest_parse(sent):
        print t
        
   (S (NP Mary) (VP (V saw) (NP (Det a) (N dog))))
   

   
   Испытаем метод с определенным параметром trace=2. Полный вывод будет спрятан под спойлер, ибо сильно длинный:
   
   
   Код программы и вывод

   >>> rd_parser = nltk.RecursiveDescentParser(grammar, trace=2)
   >>> sent = 'Mary saw a dog'.split()
   >>> for t in rd_parser.nbest_parse(sent):
        print t
   
   Parsing 'Mary saw a dog'
       [ * S ]
     E [ * NP VP ]
     E [ * 'John' VP ]
     E [ * 'Mary' VP ]
     M [ 'Mary' * VP ]
     E [ 'Mary' * V NP ]
     E [ 'Mary' * 'saw' NP ]
     M [ 'Mary' 'saw' * NP ]
     E [ 'Mary' 'saw' * 'John' ]
     E [ 'Mary' 'saw' * 'Mary' ]
     E [ 'Mary' 'saw' * 'Bob' ]
     E [ 'Mary' 'saw' * Det N ]
     E [ 'Mary' 'saw' * 'a' N ]
     M [ 'Mary' 'saw' 'a' * N ]
     E [ 'Mary' 'saw' 'a' * 'man' ]
     E [ 'Mary' 'saw' 'a' * 'dog' ]
     M [ 'Mary' 'saw' 'a' 'dog' ]
     + [ 'Mary' 'saw' 'a' 'dog' ]
     E [ 'Mary' 'saw' 'a' * 'cat' ]
     E [ 'Mary' 'saw' 'a' * 'telescope' ]
     E [ 'Mary' 'saw' 'a' * 'park' ]
     E [ 'Mary' 'saw' * 'an' N ]
     E [ 'Mary' 'saw' * 'the' N ]
     E [ 'Mary' 'saw' * 'my' N ]
     E [ 'Mary' 'saw' * Det N PP ]
     E [ 'Mary' 'saw' * 'a' N PP ]
     M [ 'Mary' 'saw' 'a' * N PP ]
     E [ 'Mary' 'saw' 'a' * 'man' PP ]
     E [ 'Mary' 'saw' 'a' * 'dog' PP ]
     M [ 'Mary' 'saw' 'a' 'dog' * PP ]
     E [ 'Mary' 'saw' 'a' 'dog' * P NP ]
     E [ 'Mary' 'saw' 'a' 'dog' * 'in' NP ]
     E [ 'Mary' 'saw' 'a' 'dog' * 'on' NP ]
     E [ 'Mary' 'saw' 'a' 'dog' * 'by' NP ]
     E [ 'Mary' 'saw' 'a' 'dog' * 'with' NP ]
     E [ 'Mary' 'saw' 'a' * 'cat' PP ]
     E [ 'Mary' 'saw' 'a' * 'telescope' PP ]
     E [ 'Mary' 'saw' 'a' * 'park' PP ]
     E [ 'Mary' 'saw' * 'an' N PP ]
     E [ 'Mary' 'saw' * 'the' N PP ]
     E [ 'Mary' 'saw' * 'my' N PP ]
     E [ 'Mary' * 'ate' NP ]
     E [ 'Mary' * 'walked' NP ]
     E [ 'Mary' * V NP PP ]
     E [ 'Mary' * 'saw' NP PP ]
     M [ 'Mary' 'saw' * NP PP ]
     E [ 'Mary' 'saw' * 'John' PP ]
     E [ 'Mary' 'saw' * 'Mary' PP ]
     E [ 'Mary' 'saw' * 'Bob' PP ]
     E [ 'Mary' 'saw' * Det N PP ]
     E [ 'Mary' 'saw' * 'a' N PP ]
     M [ 'Mary' 'saw' 'a' * N PP ]
     E [ 'Mary' 'saw' 'a' * 'man' PP ]
     E [ 'Mary' 'saw' 'a' * 'dog' PP ]
     M [ 'Mary' 'saw' 'a' 'dog' * PP ]
     E [ 'Mary' 'saw' 'a' 'dog' * P NP ]
     E [ 'Mary' 'saw' 'a' 'dog' * 'in' NP ]
     E [ 'Mary' 'saw' 'a' 'dog' * 'on' NP ]
     E [ 'Mary' 'saw' 'a' 'dog' * 'by' NP ]
     E [ 'Mary' 'saw' 'a' 'dog' * 'with' NP ]
     E [ 'Mary' 'saw' 'a' * 'cat' PP ]
     E [ 'Mary' 'saw' 'a' * 'telescope' PP ]
     E [ 'Mary' 'saw' 'a' * 'park' PP ]
     E [ 'Mary' 'saw' * 'an' N PP ]
     E [ 'Mary' 'saw' * 'the' N PP ]
     E [ 'Mary' 'saw' * 'my' N PP ]
     E [ 'Mary' 'saw' * Det N PP PP ]
     E [ 'Mary' 'saw' * 'a' N PP PP ]
     M [ 'Mary' 'saw' 'a' * N PP PP ]
     E [ 'Mary' 'saw' 'a' * 'man' PP PP ]
     E [ 'Mary' 'saw' 'a' * 'dog' PP PP ]
     M [ 'Mary' 'saw' 'a' 'dog' * PP PP ]
     E [ 'Mary' 'saw' 'a' 'dog' * P NP PP ]
     E [ 'Mary' 'saw' 'a' 'dog' * 'in' NP PP ]
     E [ 'Mary' 'saw' 'a' 'dog' * 'on' NP PP ]
     E [ 'Mary' 'saw' 'a' 'dog' * 'by' NP PP ]
     E [ 'Mary' 'saw' 'a' 'dog' * 'with' NP PP ]
     E [ 'Mary' 'saw' 'a' * 'cat' PP PP ]
     E [ 'Mary' 'saw' 'a' * 'telescope' PP PP ]
     E [ 'Mary' 'saw' 'a' * 'park' PP PP ]
     E [ 'Mary' 'saw' * 'an' N PP PP ]
     E [ 'Mary' 'saw' * 'the' N PP PP ]
     E [ 'Mary' 'saw' * 'my' N PP PP ]
     E [ 'Mary' * 'ate' NP PP ]
     E [ 'Mary' * 'walked' NP PP ]
     E [ * 'Bob' VP ]
     E [ * Det N VP ]
     E [ * 'a' N VP ]
     E [ * 'an' N VP ]
     E [ * 'the' N VP ]
     E [ * 'my' N VP ]
     E [ * Det N PP VP ]
     E [ * 'a' N PP VP ]
     E [ * 'an' N PP VP ]
     E [ * 'the' N PP VP ]
     E [ * 'my' N PP VP ]
   (S (NP Mary) (VP (V saw) (NP (Det a) (N dog))))
   >>> 
   

   
   
   
   Анализатор рекурсивного спуска имеет три существенных недостатка:
   
   
   • леворекурсивные правила вида NP -> NP PP приводят к бесконечному циклу;
   • при анализе, много времени уходит на рассмотрение слов и структур, которые не соответствуют входному предложению (это видно в листинге с использованием параметра trace=2);
   • процесс перебора с возвращением отбрасывает проанализированные составляющие, а потом снова обязан их строить.
   
   
2. Алгоритм перемещения-сворачивания.
   Это анализатор «снизу-вверх». Как и другие анализаторы, этот пытается найти последовательности слов и словосочетаний, которые отвечают правой части правила грамматики и заменяет их на левую часть правила, пока предложение не «свернется» к символу S.
   Анализатор перемещения-сворачивания неоднократно помещает следующее слово в стек – эта операция называется «перемещение». Если N элементов с вершины стека отвечают N элементам в правой части правила, тогда они удаляются из стека, а элемент с левой части правила перемещается в стек. Эта замена N элементов в вершине стека на один элемент называется «сворачивание». Эта операция совершается только по отношению к вершине стека, сокращения элементов, находящихся глубже должно быть завершено до того, как в вершину поступают новые данные. Анализатор завершает свою работу, когда обработаны все элементы, поступающие ему на вход и когда в стеке остается только один элемент — дерево разбора с элементом S. Кстати, подробно рассмотреть работу анализатора можно в демонстрационном примере nltk.app.srparser().
   
   В NLTK алгоритм перемещения-сворачивания реализован в методе
   
   

   nltk.ShiftReduceParser(grammar)

   
   Давайте сразу же проверим его на знакомом предложении «Mary saw a dog» (грамматику будем использовать тоже из предыдущего примера):
   
   

   >>> sr_parse = nltk.ShiftReduceParser(grammar)
   >>> sent = 'Mary saw a dog'.split()
   >>> print sr_parse.parse(sent)
   (S (NP Mary) (VP (V saw) (NP (Det a) (N dog))))
   

   
   Анализатор перемещения-сворачивания может попадать в тупики, что не позволит получить любые результаты анализа, даже, если входное предложение не противоречит грамматике. Если такое происходит, то нету уже входных слов и стек содержит элементы, которые нельзя свернуть к S. Эти проблемы возникают в результате действий на предыдущих шагах.
   
   Преимуществом данного анализатора над анализатором рекурсивного спуска есть то, что он строит синтаксическую структуру, которая отвечает входной последовательности слов. Кроме этого, он строит каждую подструктуру отдельно. Например, NP(Det(the), N(man)) строится независимо от того, будет ли она использоваться при сворачивании правила VP -> V NP PP, либо NP -> NP PP .
   

Вывод

В данной статье мы рассмотрели синтаксический анализ предложений с помощью пакета NLTK. Также рассмотрели два алгоритма для синтаксического анализа: алгоритм перемещения-сворачивания и алгоритм рекурсивного спуска.
Спасибо за внимание.

Ссылки

1. Сравнение и создание морфологических анализаторов в NLTK
2. NLTK. Документация