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

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

Более выразительный способ описания языков — формальные грамматики — предложил Н. Чомски в 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

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

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

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

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

В 1987 в Осакском университете разработали ещё более выразительный способ описания языков — множественные CFG (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)

Стрелка влево обозначает дизъюнкт Хорна. В левой части каждого правила вывода описывается составление аргументов нетерминала-предиката из терминалов и переменных; в правой перечисляются предикаты, которым переменные должны удовлетворять. Порядок записи предикатов в правой части не имеет значения. Каждая переменная, использованная в левой части, должна быть ограничена предикатом в правой части; повторное использование одной переменной не допускается. Если в левой части нет переменных, то правая часть может быть пустой — это значит, что никаких дополнительных условий, кроме совпадения терминалов, не накладывается. Способ записи 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% скидку на первый месяц аренды сервера любой конфигурации!