2014-11-14 5 views
5

Я пытаюсь извлечь CNF-грамматические постановки предложения от его синтаксического дерева:Хомских нормальная форма извлечение грамматики из дерева разбора

(ROOT 
    (S 
    (NP (DT the) (NNS kids)) 
    (VP (VBD opened) 
     (NP (DT the) (NN box)) 
     (PP (IN on) 
     (NP (DT the) (NN floor)))))) 

Я положил дерево отверстия в строку с именем S и затем:

tree = Tree.fromstring(S) 
tree.chomsky_normal_form() 
for p in tree.productions(): 
    print p 

выход

(1) NN -> 'box' 
(2) PP -> IN NP 
(3) DT -> 'the' 
(4) ROOT -> S 
(5) NP -> DT NN 
(6) VBD -> 'opened' 
(7) VP|<NP-PP> -> NP PP 
(8) VP -> VBD VP|<NP-PP> 
(9) NP -> DT NNS 
(10) NN -> 'floor' 
(11) IN -> 'on' 
(12) NNS -> 'kids' 
(13) S -> NP VP 

Но некоторые из производств (номер 7 & 8), похоже, не CNF! В чем проблема?

ответ

4

VP|<NP-PP> является один нетерминальный символ. Вертикальная панель не означает множество вариантов в традиционном смысле. Скорее, NLTK ставит его там, чтобы указать, откуда взялось правило, т. Е. «Этот новый нетерминальный символ был получен из комбинации VP и NP-PP». Это новое производственное правило, созданное NLTK для преобразования вашей грамматики в нормальную форму Хомского.

Взгляните на спектаклях дерева, предварительно CNF:

ROOT -> S 
S -> NP VP 
NP -> DT NNS 
DT -> 'the' 
NNS -> 'kids' 
VP -> VBD NP PP *** 
VBD -> 'opened' 
NP -> DT NN 
DT -> 'the' 
NN -> 'box' 
PP -> IN NP 
IN -> 'on' 
NP -> DT NN 
DT -> 'the' 
NN -> 'floor' 

В частности, обратите внимание на правила VP -> VBD NP PP, который не находится в КНФ (Там должно быть ровно два нетерминальные символов на правой части любое производственное правило)

Два правила (7): VP|<NP-PP> -> NP PP и (8): VP -> VBD VP|<NP-PP> в вашем вопросе функционально эквивалентны более общему правилу VP -> VBD NP PP.

Когда VP обнаружен, результаты применения правила в:

VBD VP|<NP-PP>

И, VP|<NP-PP> это LHS правила производства, созданного, в результате чего:

VBD NP PP

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

>>> tree.chomsky_normal_form() 
>>> prod = tree.productions() 
>>> x = prod[7] # VP|<NP-PP> -> NP PP 
>>> x.lhs().symbol() # Singular! 
u'VP|<NP-PP>' 
+0

Итак, как я могу различать стержни, которые означают OR (которые всегда находятся на RHS), с полосками, которые не означают OR и могут возникать как на RHS, так и на LHS (например, тот, который вы упомянули)? – sabzdarsabz

+1

В каком контексте вам нужно «различать» между ними? На самом базовом уровне, подавая нетерминальный символ на LHS, как 'VP | 'будет выдавать ошибку, так как символы не должны содержать пробелов. Также поймите, что спецификация 'A -> B | C' является сокращением для более формальных 'A -> B',' A -> C'. – jayelm

+1

Действительно, NLTK разделяет эти правила на свои составляющие формы, поэтому помимо ввода вручную правил, таких как 'A -> B | C', вы не найдете вхождения в символы '|', что означает «несколько опций» в грамматиках NLTK. Попробуйте 'nltk.CFG.fromstring (« A -> B | C »)', который создает грамматику с двумя производственными правилами. – jayelm