АВТОМАТИЧНИЙ СИНТАКСИЧНИЙ АНАЛІЗ АЛГОРИТМИ АНАЛІЗУ АЛГОРИТМ ЕРЛІ

ЗВЕРХУ-ВНИЗ
ЗА ОДИН ПРОХІД ЗЛІВА-НАПРАВО ПО ВХІДНИХ ДАНИХ ЗАПОВНЮЄТЬСЯ МАСИВ СПИСКІВ

РОЗБОРУ (CHARTS)
МАСИВ МІСТИТЬ N+1 ЕЛЕМЕНТІВ; N – КІЛЬКІСТЬ СЛІВ У РЕЧЕННІ
ЕЛЕМЕНТАМИ СПИСКІВ РОЗБОРУ Є СТАНИ В ЯКИХ ЗБЕРІГАЄТЬСЯ ІНФОРМАЦІЯ ТРЬОХ ТИПІВ
ПРО СФОРМОВАНІ СКЛАДНИКИ ТА ЇХ МІСЦЕЗНАХОДЖЕННЯ
СКЛАДНИКИ В ПРОЦЕСІ ФОРМУВАННЯ
СКЛАДНИКИ, ФОРМУВАННЯ ЯКИХ ОЧІКУЄТЬСЯ

ГРАМАТИКИ ТА ДОДАВАННЯМ КРАПКИ “.”, ЯКА Є ІНДИКАТОРОМ ФОРМУВАННЯ ПІДДЕРЕВА

dotted-rules.
S   VP VP ОЧІКУЄТЬСЯ
NP  Det  Nominal NP В ПРОЦЕСІ ФОРМУВАННЯ
VP  V NP  VP ПОБУДОВАНО

VP [0,0]


NP  Det  Nominal [1,2]



VP  V NP

 [0,3]

VP ОЧІКУЄТЬСЯ НА ПОЧАТКУ РЕЧЕННЯ


NP В ПРОЦЕСІ ФОРМУВАННЯ
Det ОБРОБЛЕНО В ПОЗИЦІЇ [1 , 2]


VP ПОБУДОВАНО ДЛЯ ПОЗИЦІЙ ВХІДНИХ ДАНИХ ВІД 0 ДО 3

ТАБЛИЦІ
ПРИСУТНІСТЬ СТАНУ
S  α  [0,N]
ВКАЗУЄ НА УСПІШНИЙ АНАЛІЗ

(РОЗБІР) РЕЧЕННЯ

CHARTS (СПИСКИ РОЗБОРУ) ВИКОРИСТОВУЮТЬСЯ ОПЕРАЦІЇ:
PREDICTOR
COMPLETER
SCANNER
КОЖНА ОПЕРАЦІЯ ОТРИМУЄ НА ВХОДІ ОДИН

СТАН І БУДУЄ НОВИЙ
СТАНИ ДОДАЮТЬСЯ ДО СПИСКІВ РОЗБОРУ

СТАНИ ДО ПОТОЧНОГО СПИСКУ РОЗБОРУ
ЗАСТОСОВУЄТЬСЯ ДО СТАНІВ ДЕ ПІСЛЯ КРАПКИ

ЙДЕ НЕТЕРМІНАЛЬНИЙ СИМВОЛ , АЛЕ НЕ РОS ТЕГ

З КРАПКОЮ В КІНЦІ ПРАВИЛА

22.12.2009
Комп'ютерна лінгвістика (2009) Романюк А.Б.
АЛГОРИТМ ЕРЛІ

- COMPLETER

ДЕ ПІСЛЯ КРАПКИ ЙДЕ НЕТЕРМІНАЛЬНИЙ СИМВОЛ - РОS ТЕГ

22.12.2009
Комп'ютерна

лінгвістика (2009) Романюк А.Б.

АЛГОРИТМ ЕРЛІ - SCANNER

ВІДПОВІДАЮТЬ ПОЗИЦІЯМ ВІД 0 ДО 3
ВИКОРИСТОВУЄТЬСЯ КОНТЕКСТНО – ВІЛЬНА

ГРАМАТИКА З ПОПЕРЕДНЬОЇ ЛЕКЦІЇ

СТАНИ МІСТЯТЬ ІНФОРМАЦІЮ ТІЛЬКИ ПРО МОЖЛИВІ ПІДДЕРЕВА
ДЛЯ ВІДТВОРЕННЯ ДЕРЕВА ПОТРІБНО

ДОПОВНИТИ КОЖЕН СТАН ІНФОРМАЦІЄЮ ПРО ЗАВЕРШЕНІ СТАНИ ЗГЕНЕРОВАНІ СКЛАДНИКОМ
ДО СТАНІВ, ЯКІ БУДУЮТЬСЯ COMPLETER ДОДАЄТЬСЯ ВКАЗІВНИК НА ПОПЕРЕДНІ СТАНИ , ЯКІ ВІДПОВІДАЮТЬ СКЛАДНИКАМ ЦЬОГО СТАНУ

22.12.2009

Комп'ютерна лінгвістика (2009) Романюк А.Б.

ВІДТВОРЕННЯ ДЕРЕВА

СЛІВ ПОБУДОВАНО ЧОТИРИ CHARTS ТА 36 СТАНІВ
КОРИСНА ІНФОРМАЦІЯ МІСТИТЬСЯ ТІЛЬКИ

В 7 СТАНАХ
БАГАТО СТАНІВ БУДУЮТЬСЯ ДЛЯ ДАНИХ, ЯКІ НЕ Є У ВХІДНІЙ ПОСЛІДОВНОСТІ

ВИРІШУЮТЬ
АЛГОРИТМИ ДОЗВОЛЯЮТЬ ПОБУДУВАТИ НАБОРИ ДЕРЕВ ДЛЯ ЕЛЕМЕНТІВ [0,N]
АЛГОРИТМИ ЕФЕКТИВНО

ЗБЕРІГАЮТЬ ПІДДЕРЕВА, ЯКІ СПІЛЬНО ВИКОРИСТОВУЮТЬСЯ ПРИ АНАЛІЗІ
ПІДДЕРЕВА ВИВОДЯТЬСЯ ТІЛЬКИ ОДИН РАЗ
АЛЕ ВІДПОВІДІ ЧИ ПРАВИЛЬНУ СИНТАКСИЧНУ СТРУКТУРУ МИ ОТРМУЄМО ОТРИМАТИ НЕ МОЖЕМО.

А.Б.
Balcor NNP B-NP
, ,
Owhich WDT B-NP
has VBZ B-VP
interests NNS

B-NP
in IN B-PP
real JJ B-NP
estate NN I-NP
, , Osaid VBD B-VP
the DT B-NP
position NN I-NP
is VBZ B-VP
newly RB I-VP
created VBN I-VP
. . O

Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition

- Second Edition Prentice Hall, 2008 -988. – Розділ,13 ст. 427-458.

НЕОБХІДНО ПРОЧИТАТИ

22.12.2009

Комп'ютерна лінгвістика (2009) Романюк А.Б.