Грамматический разбор для естественных языков. Ч.1: Языки описания языков

Исторически первой попыткой формализовать язык и автоматизировать его разбор были регулярные выражения ^[1], придуманные С.К. Клейни в 1951. Регулярное выражение составляется из символов языка ("терминалов"), и трёх операций: конкатенация, чередование и замыкание. Для разбора регулярных выражений достаточно ДКА ^[2] без памяти: разборщик знает, в каком состоянии он находится сейчас, но не помнит ничего о своих прошлых состояниях. Это значит, что языки, допускающие вложенные конструкции — например, язык вложенных скобок (ⁿ)ⁿ и язык самих регулярных выражений — невозможно описать регулярными выражениями. Естественные языки тоже допускают конструкции неограниченной вложенности ("Вот два петуха, которые будят того пастуха, который бранится с коровницей строгою, которая доит корову безрогую, лягнувшую старого пса без хвоста, который за шиворот треплет кота, который пугает и ловит синицу, которая часто ворует пшеницу, которая в тёмном чулане хранится в доме, который построил Джек."), поэтому для описания естественных языков регулярные выражения недостаточно выразительны.

Более выразительный способ описания языков — формальные грамматики ^[3] — предложил Н. Чомски в 1956. Предложения на английском довольно неплохо поддаются такому описанию:

S  → NP VP
NP → N' | Det N'
N' → N | Adj N | N PP | N' CP
VP → V | V NP | V PP
PP → P NP
CP → VnP | C VP | C S
VnP → Vn | Adv VnP | VnP Conj Vn
N  → This | rooster | morn | judge | man | maiden | cow |
     horn | dog | cat | rat | malt | house | Jack
V  → is | crowed | woke | married | kissed | milked |
     tossed | worried | killed | ate | lay | built
Vn → shaven | shorn | tattered | torn | forlorn
Adj → crumpled 
Adv → all
P   → in | with 
Det → the
C   → that
Conj → and

Этой формальной грамматики из пары десятков абстрактных символов ("нетерминалов") и пары десятков правил вывода (не считая лексикона) достаточно, чтобы разобрать вложенные конструкции в том самом предложении про петуха, коровницу, пса и кота:

Для контекстно-свободных ^[4] грамматик (CFG) — когда в левой части каждого правила вывода стоит ровно один нетерминал, как в этом примере — существуют эффективные алгоритмы разбора текста; поэтому почти все языки программирования описываются CFG. В отличие от языков программирования, тексты на естественных языках часто допускают несколько возможных разборов — например, [that woke the judge…]_CP могло бы относиться и к morn_N' — выбор между которыми требует семантического разбора. Однако для естественных языков с более гибким порядком слов, чем в английском, CFG недостаточно: уже для разбора русского стишка понадобились бы и VP → V PP, N' → N Adj ("бранится с коровницей строгою"), и VP → PP V, N' → Adj N ("в тёмном чулане хранится"); чуть ли не для каждого правила вывода в грамматику понадобилось бы добавить его "зеркальное отражение" — и тогда количество возможных разборов текста растёт экспоненциально. Ещё хуже то, что при топикализации ^[5] листья поддерева, соответствующего нетерминалу, могут идти в тексте не подряд: например, в "Я тебя детям просил помочь, [а не родителям]" члены сложного дополнения [детям помочь]_CP разделены сказуемым просил_V. В нескольких языках — исследователи отмечают голландский и швейцарский немецкий — есть не связанные с топикализацией "параллельно-вложенные" конструкции, например ^[6]:

Такую цепочку можно наращивать неограниченно, как в стишке про дом Джека; но глаголы во второй части предложения должны идти в том же порядке, в котором идут их дополнения в первой части предложения. Такие явления — скрэмблинг ^[7] при топикализации и "параллельно-вложенные" конструкции в голландском и швейцарском немецком — формальные грамматики не в состоянии описать.

Более формально можно доказать, что CFG могут описывать вложенные конструкции — в частности, язык вложенных скобок (ⁿ)ⁿ описывается тривиальной грамматикой S → () | (S) – но неиерархические зависимости описанию не поддаются: в частности, CFG не может описать язык aⁿbⁿcⁿ или язык дважды повторённых строк ((a|b)⁺)².

В 1987 в Осакском университете разработали ещё более выразительный способ описания языков — множественные CFG ^[8] (MCFG); одновременно с этим и независимо от осакцев в Университете Пенсильвании разработали линейные контекстно-свободные системы перезаписи (LCFRS), которые отличаются от MCFG только более простой формой записи. В MCFG/LCFRS нетерминалы становятся многоместными предикатами — например, эта LCFRS описывает язык дважды повторённых строк:

S(XY) ← P(X,Y)
P(a,a) ← ε
P(b,b) ← ε
P(XY,ZW) ← P(X,Z),P(Y,W)

Стрелка влево обозначает дизъюнкт Хорна ^[9]. В левой части каждого правила вывода описывается составление аргументов нетерминала-предиката из терминалов и переменных; в правой перечисляются предикаты, которым переменные должны удовлетворять. Порядок записи предикатов в правой части не имеет значения. Каждая переменная, использованная в левой части, должна быть ограничена предикатом в правой части; повторное использование одной переменной не допускается. Если в левой части нет переменных, то правая часть может быть пустой — это значит, что никаких дополнительных условий, кроме совпадения терминалов, не накладывается. Способ записи LCFRS сильно отличается от принятого для CFG — например, грамматику языка дважды повторённых строк можно было бы записать в более прозрачном, хоть на практике и не используемом виде:

S → XY  ⇐ P → X,Y
P → a,a | b,b | XY,ZW  ⇐ P → X,Z ∧ P → Y,W

В отличие от CFG, где каждый узел дерева разбора соответствует подстроке разобранного текста, — при разборе MCFG/LCFRS узел дерева разбора может соответствовать нескольким подстрокам, идущим в тексте не подряд: (толщина линии показывает, сколько подстрок нетерминал получает от дочерних узлов)

Практическая польза MCFG/LCFRS в том, что они позволяют описать "разорванный" член предложения (детям, помочь)_CP:

VP(X,Y) ← NP(X),V(Y)
CP(X,Y) ← VP(X,Y)
VP(X,YZW) ← NP(X),V(Z),CP(Y,W)
S(XYZ) ← NP(X),VP(Y,Z)

Но для практической применимости MCFG/LCFRS нужен ещё и эффективный алгоритм разбора. Этому будет посвящена ч.2.

Облачные серверы от Маклауд ^[10] быстрые и безопасные.

Зарегистрируйтесь по ссылке выше и получите 10% скидку на первый месяц аренды сервера любой конфигурации!

Автор: vildeste

Источник ^[11]