- PVSM.RU - https://www.pvsm.ru -
Здравствуйте. Это статья об синтаксическом анализе предложений, их представлении. Для разбора предложений будет использоваться пакет NLTK и язык программирования Python (версии 2.7).
В моей предыдущей [1] статье мы рассматривали морфологические анализаторы и их использование. Настоятельно рекомендую прочитать её, чтобы лучше понять данную статью. Также там рассматривается установка и настройка пакета NLTK.
Что такое синтаксический анализ? Синтаксический анализ – это процесс, который определяет, принадлежит ли некоторая последовательность лексем языку, порождаемому грамматикой. Обычно представляется в виде дерева для удобства понимания.
Рассмотрим некоторые грамматические особенности английского языка:
Если заменить предыдущие предложения на символ 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. С этого примера можно сделать вывод, что языку присущие конструкции, которые позволяют, кажется, безгранично расширять предложение.
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)))))
Программа составила две структуры предложений. Это признак неоднозначности.
>>> 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 |
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'
""")
Рекурсия этой грамматики позволяет строить, например, деревья с вложенными именительных выражениями и вложенными предложениями.
Синтаксический анализатор – это программа, которая обрабатывает входное предложение согласно правилам грамматики и строит одну или несколько синтаксических структур, которые отвечают этой грамматике.
Мы рассмотрим два простых алгоритма синтаксического анализа: алгоритм рекурсивного спуска (стратегия «сверху-вниз») и алгоритм перемещения-сворачивания (стратегия «снизу-вверх»).
Рассмотрим каждый подробнее:
Алгоритм рекурсивного спуска осуществляется методом
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))))
>>>
Анализатор рекурсивного спуска имеет три существенных недостатка:
В 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. Также рассмотрели два алгоритма для синтаксического анализа: алгоритм перемещения-сворачивания и алгоритм рекурсивного спуска.
Спасибо за внимание.
Автор: Di3go
Источник [3]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/python/266746
Ссылки в тексте:
[1] предыдущей: https://habrahabr.ru/post/340404/
[2] NLTK. Документация: http://www.nltk.org/book/ch08.html
[3] Источник: https://habrahabr.ru/post/340574/
Нажмите здесь для печати.