Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
ІКНІ
Факультет:
Прикладна лінгвістика
Кафедра:
Кафедра систем автоматизованого проектування
Інформація про роботу
Рік:
2011
Тип роботи:
Методичні вказівки до лабораторної роботи
Предмет:
Інформаційні технології
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ
НУ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
ІНСТИТУТ КОМП’ЮТЕРНИХ НАУК ТА ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ
КАФЕДРА СИСТЕМ АВТОМАТИЗОВАНОГО ПРОЕКТУВАННЯ
ВИВЧЕННЯ БІБЛІОТЕКИ ПРИКЛАДНИХ ПРОГРАМ NLTK, ДЛЯ ОПРАЦЮВАННЯ ТЕКСТІВ ПРИРОДНОЮ МОВОЮ.
АВТОМАТИЧНИЙ СИНТАКСИЧНИЙ АНАЛІЗ (частина2).
Методичні вказівки до лабораторної роботи № 11
з дисципліни «Комп’ютерна лінгвістика»
для магістрів за фахом 8. 02030303 «Прикладна лінгвістика» денної та заочної форм навчання
Затверджено на засіданні кафедри
«Системи автоматизованого проектування»
Протокол № 16 від 17.05.2011 р.
Затверджено на засіданні методичної ради ІКНІ
Протокол № 9-10/11 від 18.05.2011 р.
Зареєстровано в НМУ НУ «ЛП»
№ 3516 від 2.06.2011
Львів-2011
ВИВЧЕННЯ БІБЛІОТЕКИ ПРИКЛАДНИХ ПРОГРАМ NLTK, ДЛЯ ОПРАЦЮ ВАННЯ ТЕКСТІВ ПРИРОДНОЮ МОВОЮ. АВТОМАТИЧНИЙ СИНТАКСИЧНИЙ АНАЛІЗ (частина1). Методичні вказівки до лабораторної роботи № 11 з дисципліни «Комп’ютерна лінгвістика» для магістрів за фахом 8.02030303 «Прикладна лінгвістика» денної та заочної форм навчання/Укл. А.Б.Романюк, І.Ю Юрчак. - Львів: Національний університет «Львівська політехніка», 2011. – 16 с.
Укладачі:
Романюк А. Б., канд. техн. наук, доцент
Юрчак І.Ю., канд. техн. наук, доцент
Відповідальна за випуск:
Юрчак І.Ю., канд. техн. наук, доцент
Рецензент:
Теслюк В.М., д.т.н., професор кафедри САПР
МЕТА РОБОТА
Вивчення основ програмування на мові Python.
Ознайомлення з автоматичним синтаксичним аналізом в NLTK.
КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ
1. Вступ.
В попередніх лабораторних роботах основна увага була зосереджена на словах: яким чином їх ідентифікувати, здійснити аналіз їх структури, здійснити їх морфологічний аналіз та дізнатися їх значення. Крім цього розглядалися способи ідентифікації послідовності слів та n-грами. Але ці методи не торкаються дослідження речень, як граматичної конструкції, побудованої з одного чи кількох слів певної мови, яка становить окрему, відносно незалежну думку; це значеннєве, граматичне і інтонаційне ціле, що виражає якусь думку в відношенні її до дійсності (предикативність, створена категоріями модальності, часу й особи) одним словом чи сполукою слів. Потрібно вирішувати задачу обробки необмеженої множини довільних речень. Потрібно розробляти програми аналізу структури речень і дослідження значення цих речень.
Метою цієї та наступної лабораторних відповісти на наступні питання:
Яким чином використовується формальна граматика для представлення структури необмеженого набору речень?
Як представити синтаксичну структуру речення використовуючи дерева?
Яким чином синтаксичний аналізатор здійснює аналіз речення і автоматично будує синтаксичну структуру у вигляді дерева?
Деякі граматичні дилеми
Лінгвістичні дані та необмежені можливості.
При виконанні попередніх лабораторних робіт значна увага приділялася обробці та аналізу текстових корпусів текстів та наголошувалось на проблемах обробки природної мови в зв’язку з лавиноподібною кількість лінгвістичних даних. Припустимо, що можна побудувати корпус, який буде містити все що було сказано чи написано англійською (чи будь-якою іншою мовою) за останні 50 років. Чи справедливо назвати такий корпус – корпусом сучасної англійської мови? Очевидно, що легко знайти багато причин щоб дати негативну відповідь. Якщо здійснити пошук словосполучення «the of» то виявляється можна знайти дуже багато прикладів його вживання, наприклад New man at the of IMG (http://www.telegraph.co.uk/sport/2387900/New-man-at-the-of-IMG.html). (http://www.telegraph.co.uk/sport/2387900/New-man-at-the-of-IMG.html ). Спеціалісти, які володіють англійською мовою назвуть такі приклади помилкою, і скажуть що ці приклади не належать англійській мові. Відповідно, не можна вважати «сучасною англійською» велику кількість послідовностей слів з нашого уявного корпуса. Носії мови можуть розглядати такі послідовності і відкидати деякі з них як такі що не є граматичними (не відповідають граматиці природної мови). Звичайно, можна побудувати нове речення і знайти носіїв мови, які скажуть що це речення належить мові.
Наприклад, цікавою властивістю речень є те що вони можуть вкладатися в більші речення. Розглянемо наступні речення:
(1)
a.
Usain Bolt broke the 100m record
b.
The Jamaica Observer reported that Usain Bolt broke the 100m record
c.
Andre said The Jamaica Observer reported that Usain Bolt broke the 100m record
d.
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 when S. З цього прикладу можна зробити висновок що мові властиві конструкції, які дозволяють, здається, безмежно розширювати речення. Також вражає те що ми можемо зрозуміти речення довільної довжини, які раніше ніколи не чули. Досить легко придумати зовсім нове речення, яке ніколи раніше ніде в даній природній мові не зустрічалося а всі носії мови його зрозуміють.
Мета граматики – дати явний опис природної мови. Щоб описати мову потрібно визначитись що вважати природною мовою та вивчити основні підходи до її представлення.
В лабораторній роботі розглядається формальне представлення породжуючої граматики, згідно якої мова представляється, як множина всіх граматично вірних речень, а граматика це формальна система , яка може бути використана для генерації елементів цієї множини.
Двозначність (неоднозначності в реченнях).
Відомий приклад двозначності з (2), з фільму Groucho Marx , Animal Crackers (1930):
(2)
While hunting in Africa, I shot an elephant in my pajamas. How an elephant got into my pajamas I'll never know.
Розглянемо неоднозначність виразу: I shot an elephant in my pajamas. Спочатку потрібно визначити (розробити ) просту граматику:
>>> groucho_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'
... """)
Наведена вище граматика дозволяє здійснити аналіз речення двома способами в залежності від того чи прийменниковий вираз in my pajamas описує слона чи подію «стріляння».
>>> sent = ['I', 'shot', 'an', 'elephant', 'in', 'my', 'pajamas']
>>> parser = nltk.ChartParser(groucho_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)))))
Програма створює дві структури, які, з врахуванням дужок, можна представити у вигляді дерев.
Виконати самостійно! Чи мають наступні речення два різні варіанти їх інтерпретації. Fighting animals could be dangerous. Visiting relatives can be tiresome. Чи впливають на цю двозначність неоднозначності окремих слів? Якщо ні то яка причина двозначності?
Що дає використання синтаксису?
Beyond n-grams
В одній з попередніх лабораторних робіт було показано, як можна використати біграми (інформацію про частоту слів в біграмах) для генерації тексту. Програма генерує цілковито прийнятний текст з невеликої кількості слів але зі збільшенням слів текст перетворюється на несинітницю. Аналогічно можна побудувати наступні приклади на основі обчислень біграмів на основі дитячої історії, The Adventures of Buster Brown (http://www.gutenberg.org/files/22816/22816.txt):
(4)
a.
He roared with me the pail slip down his back
b.
The worst part and clumsy looking for whoever heard light
Інтуїтивно, відомо що ці послідовності це просто набір слів, але можливо важно визначити що саме за помилки містять ці послідовності. Якщо розглянути послідовність the worst part and clumsy looking то можна зауважити що це два вирази поєднані сполучником координації (and, but, or) . Цю структуру координації , спрощено, згідно синтаксису можна описати як:
Структура координації: якщо v1 та v2 це вирази граматичної категорії X, тоді v1 and v2 це також вираз категорії X.
Декілька прикладів таких структур (5). В першому прикладі, NP (іменниковий вираз) отримано шляхом поєднання двох NPs, в другому, поєднання двох APs (прикметникові вирази) дозволило отримати один AP.
(5)
a.
The book's ending was (NP the worst part and the best part) for me.
b.
On land they are (AP slow and clumsy looking).
Поєднати NP та AP, неможливо бо вираз the worst part and clumsy looking є не граматичним. Для подальшого потрібно зупинитися на понятті структура складників або структура безпосередніх складників.
Поняття структури складників базується на основі того що слова можуть поєднуватися з іншими словами в окремі самостійні одиниці. Визначити, що послідовність слів виступає окремою одиницею можна на основі ознаки – заміщення, коли послідовність слів в «правильному» реченні може бути замінена більш короткою послідовністю і це не вплине на «правильність» речення. Для розуміння цього твердження, розглянемо наступне речення:
(6)
The little bear saw the fine fat trout in the brook.
Оскільки послідовність The little bear можна замінити на He то це вказує нате що The little bear – окрема самостійна одиниця. Навпаки, неможна аналогічним чином замінити little bear saw.
(7)
a.
He saw the fine fat trout in the brook.
b.
*The he the fine fat trout in the brook.
Контекстно-вільна граматика
Проста граматика
Розглянемо просту (найпростішу) контекстно-вільну граматику. Згідно означення, першим символом зліва в першому правилі граматики є спеціальний початковий символ S, і всі дерева повинні мати цей символ , як корінь. В NLTK, контекстно-вільна граматика визначається в модулі nltk.grammar . В наступному прикладі показано яким чином можна визначити граматику та здійснити синтаксичний аналіз простого речення, яке передбачене цією граматикою.
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)))
Граматика з попереднього прикладу містить правила (продукції) , які включать різні синтаксичні категорії з таблиці 1
Таблиця 1. Синтаксичні категорії
Символ
Значення
Приклад
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
Правило подібне до VP -> V NP | V NP PP містить оператор диз’юнкції в правій частині |, і це є скорочений запис двох правил VP -> V NP та VP -> V NP PP.
В результаті синтаксичного аналізу речення The dog saw a man in the park з використанням такої простої граматики отримуємо два.
Оскільки граматика дозволяє побудувати два дерева для цього речення то це речення називають структурно неоднозначним. До неоднозначності приводить двозначність приєднання прийменникового виразу. Прийменниковий вираз PP in the park може бути приєднаний до двох місць в дереві: або це донька VP або донька NP. В залежності від місця приєднання прийменникового виразу міняється не тільки синтаксична структура речення але і його зміст.
Розробка власної граматики
При розробці власної контекстно-вільної граматики її правила можна записувати і редагувати у звичайному текстовому файлі, наприклад mygrammar.cfg і використовуючи NLTK завантажувати цю граматику та використовувати її для синтаксичного аналізу, як показано в наступному прикладі:
>>> grammar1 = nltk.data.load('file:mygrammar.cfg')
>>> sent = "Mary saw Bob".split()
>>> rd_parser = nltk.RecursiveDescentParser(grammar1)
>>> for tree in rd_parser.nbest_parse(sent):
... print tree
Потрібно пересвідчитись, що файл має розширення .cfg і відсутні пробіли в стрічці 'file:mygrammar.cfg'. Якщо після виконання оператора print tree на екран нічого не виводиться то це означає що граматика не передбачає (не допускає) побудову такого речення. В такому випадку можна запустити програму синтаксичного аналізу з параметром trace=2: rd_parser = nltk.RecursiveDescentParser(grammar1, trace=2), для відслідковування процесу роботи програми. Також можна перевірити (переглянути) правила граматики, вивівши їх на екран в циклі for p in grammar1.productions(): print p.
При розробці контекстно-вільної граматики з метою її використання в NLTK, не можна в правій частині правил поєднувати граматичні категорії та лексичні одиниці, наприклад правило PP -> 'of' NP не допускається. Якщо потрібно в правилі використати лексичну одиницю з декількох слів то замість NP -> 'New York', потрібно записати NP -> 'New_York' instead.
Рекурсія в синтаксичних структурах
Граматику називають рекурсивною, якщо категорії з лівої частини її правил також зустрічаються і їх правих частинах, як показано в наступному прикладі. Правило 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'
""")
Рекурсія цієї граматики дозволяє будувати, наприклад, дерева з вкладеними іменниковими виразами та вкладеними реченнями.
Синтаксичний аналіз на основі контексно-вільної граматики.
Синтаксичний аналізатор це програма, яка обробляє вхідне речення згідно правил граматики і будує одну або декілька синтаксичних структур, які відповідають (узгоджуються) цій граматиці. Граматика, це декларативна специфікація певних закономірностей - це насправді стрічка (набір стрічок) а не програма. Аналізатор здійснює процедурну інтерпретації граматики – шукає серед лісу дерев, які може породжувати граматика одне потрібне дерево, яке відповідає вхідному реченню.
В цій лабораторній роботі розглядаються два прості алгоритми синтаксичного аналізу, алгоритм рекурсивного спуску, який належить до стратегії зверху-вниз та алгоритм переміщення-згортання який належить до стратегії знизу-вверх синтаксичного аналізу. Також буде розглядатися більш складний алгоритм аналізу, який передбачає здійснення аналізу зверху-вниз з фільтруванням знизу вверх - алгоритм left-corner parser.
Алгоритм рекурсивного спуску
Найпростіший тип аналізатора інтерпретує граматику як специфікацію (вказівки) для перетворення (поділу) елемента вищого рівня на декілька елементів нижчого рівня. Початкова задача знайти символ (елемент) S. Правило S → NP VP дозволяє аналізатору замінити (перетворити) цей елемент на два інших елементи: знайти спочатку NP а потім VP. Кожен з цих елементів може бути перетворений на інші елементи на основі правил граматики в яких та є в лівих частинах правил NP та VP. Такий процес буде продовжуватися до тих пір поки не буде поставлена задача знайти (замінити елемент на) слово, наприклад telescope. Тоді відбувається порівняння цього слова зі словом зі вхідної послідовності слів і якщо встановлюється відповідність між цими словами то алгоритм продовжує свою роботу. Якщо відповідність не встановлюється то аналізатор повертається на крок назад і пробує розглянути інші варіанти.
Алгоритм рекурсивного спуску синтаксичного аналізу будує дерево розбору згідно описаного вище процесу. Для детального аналізу роботи цього алгоритму доцільно скористатися демонстраційним прикладом (C:\Python26\Lib\site-packages\nltk\app\ rdparser.py або в IDLE nltk.app.rdparser()) .
Під час своєї роботи, аналізатор часто змушений вибирати між двома можливими правилами. Наприклад, при переході від кроку 3 до кроку 4, програма пробує знайти правила з N в лівій частині. Спочатку буде знайдено N → man. Коли це правило використати не вдається відбувається повернення на крок назад і знову здійснюється пошук N правила поки не буде знайдено N → dog, яке відповідає наступному слову в реченні. Набагато пізніше , як показано на кроці 5 відбувається завершення побудови (знаходження) повного дерева. Це дерево повність охоплює вхідне речення без висячих ребер. Як тільки дерево побудовано можна виконувати інші дії – здійснювати додаткові кроки аналізу. Це передбачає повернення на крок назад і дослідження інших альтернативних правил, якщо вони дозволяють так само отримати результати аналізу – побудувати дерево.
В NLTK реалізовано синтаксичний аналізатор рекурсивного спуску і скористатися ним можна наступним способом:
>>> rd_parser = nltk.RecursiveDescentParser(grammar1)
>>> 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))))
RecursiveDescentParser()може мати необов’язковий параметр trace. Якщо значення цього параметру більше нуля то аналізатор виводить на екран результати виконання всіх кроків синтаксичного аналізу тексту.
Аналізатор рекурсивного спуску має три основні недоліки. Перший, ліво рекурсивні правила виду NP -> NP PP приводять безкінечного циклу. Другий, при аналізі багато часу витрачається на розгляд слів та структур (під дерев) , які не відповідають вхідному реченню. Третій, процес перебору з поверненням, відкидає проаналізовані складники , і потім знову змушений їх будувати. Наприклад, при поверненні на крок назад після побудови фрагменту (піддерева) over VP -> V NP піддерево для NP буде втрачено. Якщо аналізатор буде обробляти правило VP -> V NP PP, то піддерево NP знову буде необхідно побудувати.
Алгоритм рекурсивного спуску відповідає стратегії здійснення синтаксичного аналізу зверху-вниз. Згідно цієї стратегії граматика використовується для передбачення того що буде на вході (вхідними даними-речення) перед переглядом цих вхідних даних. Оскільки, вхідне речення є відоме то доцільно починати аналіз з розгляду цього речення. На такому підході базується стратегія знизу-вверх , згідно якої працює алгоритм синтаксичного аналізу переміщення-згортання.
Алгоритм переміщення-згортання
Найпростіший аналізатор знизу-вверх це аналізатор переміщення-згортання. Так як і інші аналізатори знизу-вверх цей аналізатор намагається (пробує) знайти послідовності слів і словосполучень (виразів), які відповідають правій частині правила граматики і замінює їх на ліву частину правила, до тих пір поки речення не «згорнеться» до символу S.
Аналізатор переміщення згортання неодноразово поміщає наступне вхідне слово у стек і ця операція називається – переміщення. Якщо N елементів з вершини стеку відповідають N елементам в правій частині певного правила граматики, тоді вони видаляються зі стеку а елемент з лівої частини правила поміщається в стек. Ця заміна N елементів на вершині стеку на один елемент називається операцією згортання. Ця операція здійснюється тільки по відношенню до вершини стеку, скорочення елементів, які знаходяться глибше в стеку повинне бути завершене до того як на вершину стеку попадають нові елементи. Аналізатор завершує свою роботу коли опрацьовані всі елементи що поступають йому на вхід і коли в стеку міститься тільки один елемент – дерево розбору з коренем S. Аналізатор переміщення згортання будує дерево виводу протягом всього процесу свого виконання. В кожен з моментів вилучення зі стеку N елементів аналізатор компонує з цих елементів часткове дерево виводу і поміщає його у стек. Докладно роботу аналізатора переміщення згортання можна дослідити скориставшись демонстраційним прикладом nltk.app.srparser().
В NLTK реалізовано ShiftReduceParser(), як простий аналізатор переміщення - згортання. Ця програма синтаксичного аналізу не передбачає здійснення операцій повернення на крок назад, що не гарантує побудову дерева розбору для тексту, навіть якщо таке дерево існує. Крім цього будується тільки одне дерево, навіть якщо можливо побудувати декілька дерев. При роботі цієї програми можна використовувати параметр для контролю за роботою аналізатора та відображення результатів аналізу по кроках:
>>> sr_parse = nltk.ShiftReduceParser(grammar1)
>>> 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 .
Алгоритм Left-Corner
Однією з проблем аналізатора рекурсивного спуску є його за циклювання якщо зустрічається правило з лівою рекурсією. Це стається тому що правила граматики застосовуються без розгляду вхідного речення. Аналізатор left-corner це поєднання аналізаторів знизу – вверх та зверху вниз.
Граматика grammar1 дозволяє здійснити аналіз John saw Mary
Ця граматика містить наступні правила для NP:
(12)
a.
NP → dt nom (stale!)
b.
NP → dt nom pp (stale!)
c.
NP → propn (stale!)
Поглянувши на дерево (11), відразу зрозуміло яке з правил аналізатор рекурсивного спуску повинен застосувати в першу чергу - (12c). Чому не має змісту застосовувати (12a) чи (12b)? Ні одне з цих правил не дозволяє отримати послідовність слів де перше John. Тобто зрозуміло, що успішний аналіз John saw Mary, можливий якщо NP відповідає послідовність John α. Більш загально, категорія B є лівим елементом ( left-corner) дерева з коренем A якщо A ⇒* B α.
Аналізатор left-corner parser це аналізатор зверху-вниз з фільтруванням знизу - вверх. На відміну від аналізатора рекурсивного спуску, він не має проблем з ліво рекурсивними правилами. Перед початком роботи аналізатор попередньо опрацьовує контекстно-вільну граматику і будує таблицю де кожен рядок містить дві комірки, в першій зберігаються символи з лівих частин правил а в другій набір можливих лівих елементів в правилах граматикиl. В таблиці 2 показаний результат такої попередньої обробки граматики grammar2.
Таблиця 2 : Left-Corners in grammar2
Category
Left-Corners (pre-terminals)
S
NP
NP
Det, PropN
VP
V
PP
P
Кожен раз коли аналізатор обробляє правило , здійснюється перевірка чи наступне вхідне слово відповідає хоча би одній з pre-terminal категорій з таблиці2.
ПОРЯДОК ВИКОНАННЯ РОБОТИ
Ознайомитися з теоретичними відомостями.
Виконати приклади, які використовуються в теоретичних відомостях.
Виконати наступні вправи.
Здійснити аналіз речення Kim arrived or Dana left and everyone cheered. Знайти частини речення які охоплюють сполучники and та or. Побудувати дерева, які відповідають цим двом інтерпретаціям.
В класі Tree реалізовано різноманітні корисні методи. Переглянути файл допомоги Tree з документації та описати основні з цих методів (import Tree, help(Tree).
Написати програму побудови двох дерев, кожне з яких відповідає виразу old men and women
Перетворити всі дерева , які зустрічаються в методичних вказівка і зображені за допомогою дужок використовуючи nltk.Tree() . Використовувати draw() для побудови графічного зображення дерева.
Написати програму побудови дерев для речення The woman saw a man last Thursday.
Здійснити аналіз речення з твору A.A. Milne , замінюючи всі прості речення символом S. Намалювати дерево. Яке відповідає цій структурі. Які основні синтаксичні конструкції було використано для побудови такого довгого речення?
Використовуючи демонстраційну програму синтаксичного аналізу згідно алгоритму рекурсивного спуску здійснити експерименти змінюючи вхідне речення.
Написати програму для пошуку відповіді на питання. Чи може grammar1 граматика використовуватися для опису речення довжиною більше ніж 20 слів?
Використовуючи ручку і папір, здійснити всі кроки роботи аналізаторів рекурсивного спуску та переміщення згортання для довільного речення використовуючи просту контексно-вільну граматику.
Здійснити аналіз послідовності слів: Buffalo buffalo Buffalo buffalo buffalo buffalo Buffalo buffalo. Оскільки, згідно з http://en.wikipedia.org/wiki/Buffalo_buffalo_Buffalo_buffalo_buffalo_buffalo_Buffalo_buffalo це граматично правильне речення, напишіть контексно-вільну граматику на основі дерева наведеного на цій сторінці з Інтернету. Здійсніть нормалізацію слів (lowercase), для моделювання ситуації коли слухач сприймає це речення на слух. Скільки дерев розбору може мати це дерево в такому випадку?
Здійснити модифікацію граматики в демонстраційній програмі синтаксичного аналізу згідно алгоритму рекурсивного спуску . Змінити перше правило NP -> Det N PP, на NP -> NP PP. Використовуючи Step кнопку спробувати побудувати дерево розбору. Що відбувається?
Написати програму порівняння швидкодії всіх аналізаторів, які згадувалися в методичних. Використовувати timeit функцію для визначення часу синтаксичного аналізу одного і того самого речення різними аналізаторами.
Прочитати про "garden path" речення http://en.wikipedia.org/wiki/Garden_path_sentence. Оцінити обчислювальну складність аналізу таких речень в порівнянні з труднощами аналізу таких речень людиною?
Для порівняння декількох дерев в одному вікні можна використати метод draw_trees() . Побудуйте декілька дерев та спробуйте виконати:
>>> from nltk.draw.tree import draw_trees
>>> draw_trees(tree1, tree2, tree3)
Написати програму знаходження максимально довгих речень серед декількох електронних книжок з проекту Gutenberg. Які синтаксичні конструкції використовувались при побудові цих речень?
Підготувати і оформити звіт.
Варіант
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Номери завдань
1
3
5
6
1
3
5
6
1
3
5
6
1
3
5
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
7
15
11
8
7
15
11
8
7
15
11
8
7
15
11
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
12
12
12
12
12
12
12
12
12
12
12
12
12
12
12
9
13
9
13
9
13
9
13
9
13
9
13
9
13
9
Варіант
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
Номери завдань
6
1
3
5
6
1
3
5
6
1
3
5
6
1
3
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
8
7
15
11
8
7
15
11
8
7
15
11
8
7
15
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
12
12
12
12
12
12
12
12
12
12
12
12
12
12
12
ЗМІСТ ЗВІТУ
5.1 Титульний аркуш.
5.2 Мета роботи.
5.3 Короткі теоретичні відомості.
5.4 Тексти програм на мові Python.
5.5 Висновок.
ЛІТЕРАТУРА
Steven Bird, Ewan Klein, Edward Loper Introduction to Natural Language Processing. 2001-2007 University of Pennsylvania.
Г. Россум, Ф.Л.Дж. Дрейк, Д.С. Откидач, М. Задка, М. Левис, С.Монтаро, Э.С.Реймонд, А.М.Кучлинг, М.-А.Лембург, К.-П.Йи, Д.Ксиллаг, Х.ГПетрилли, Б.А.Варсав, Дж.К.Ахлстром, Дж.Рокинд, Н.Шеменон, С.Мулендер. Язык программирования Python./ 2001 – 452c.
Сузи Р. А. Язык программирования Python.- 206с.
David Mertz Text Processing in Python Addison WesleyBiber, 2003 - 544.
ІНТЕРНЕТ ПОСИЛАННЯ
http://www.nltk.org
http://python.org
Романюк Андрій Богданович, Юрчак Ірина Юріївна
МЕТОДИЧНІ ВКАЗІВКИ
до лабораторної роботи № 11
з дисципліни «Комп’ютерна лінгвістика»
для магістрів за фахом 8
11.04.2013 17:04-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора