Исторически первой попыткой формализовать язык и автоматизировать его разбор были регулярные выражения, придуманные С.К. Клейни в 1951. Регулярное выражение составляется из символов языка ("терминалов"), и трёх операций: конкатенация, чередование и замыкание. Для разбора регулярных выражений достаточно ДКА без памяти: разборщик знает, в каком состоянии он находится сейчас, но не помнит ничего о своих прошлых состояниях. Это значит, что языки, допускающие вложенные конструкции — например, язык вложенных скобок (n)n и язык самих регулярных выражений — невозможно описать регулярными выражениями. Естественные языки тоже допускают конструкции неограниченной вложенности ("Вот два петуха, которые будят того пастуха, который бранится с коровницей строгою, которая доит корову безрогую, лягнувшую старого пса без хвоста, который за шиворот треплет кота, который пугает и ловит синицу, которая часто ворует пшеницу, которая в тёмном чулане хранится в доме, который построил Джек."), поэтому для описания естественных языков регулярные выражения недостаточно выразительны.
Более выразительный способ описания языков — формальные грамматики — предложил Н. Чомски в 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 могло бы относиться и к mornN' — выбор между которыми требует семантического разбора. Однако для естественных языков с более гибким порядком слов, чем в английском, CFG недостаточно: уже для разбора русского стишка понадобились бы и VP → V PP, N' → N Adj ("бранится с коровницей строгою"), и VP → PP V, N' → Adj N ("в тёмном чулане хранится"); чуть ли не для каждого правила вывода в грамматику понадобилось бы добавить его "зеркальное отражение" — и тогда количество возможных разборов текста растёт экспоненциально. Ещё хуже то, что при топикализации листья поддерева, соответствующего нетерминалу, могут идти в тексте не подряд: например, в "Я тебя детям просил помочь, [а не родителям]" члены сложного дополнения [детям помочь]CP разделены сказуемым просилV. В нескольких языках — исследователи отмечают голландский и швейцарский немецкий — есть не связанные с топикализацией "параллельно-вложенные" конструкции, например:
|
... das |
mer |
d'chind |
em Hans |
es huus |
lönd |
hälfe |
aastriiche |
|
... что |
мы |
детей |
Гансу |
дом |
просим |
помочь |
покрасить |
|
"... что мы просим детей помочь Гансу покрасить дом" |
|||||||
Такую цепочку можно наращивать неограниченно, как в стишке про дом Джека; но глаголы во второй части предложения должны идти в том же порядке, в котором идут их дополнения в первой части предложения. Такие явления — скрэмблинг при топикализации и "параллельно-вложенные" конструкции в голландском и швейцарском немецком — формальные грамматики не в состоянии описать.
Более формально можно доказать, что CFG могут описывать вложенные конструкции — в частности, язык вложенных скобок (n)n описывается тривиальной грамматикой S → () | (S) – но неиерархические зависимости описанию не поддаются: в частности, CFG не может описать язык anbncn или язык дважды повторённых строк ((a|b)+)2.
В 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% скидку на первый месяц аренды сервера любой конфигурации!
Автор: vildeste
