Исторически первой попыткой формализовать язык и автоматизировать его разбор были регулярные выражения, придуманные С.К. Клейни в 1951. Регулярное выражение составляется из символов языка ("терминалов"), и трёх операций: конкатенация, чередование и замыкание. Для разбора регулярных выражений достаточно ДКА без памяти: разборщик знает, в каком состоянии он находится сейчас, но не помнит ничего о своих прошлых состояниях. Это значит, что языки, допускающие вложенные конструкции например, язык вложенных скобок (n)n и язык самих регулярных выражений невозможно описать регулярными выражениями. Естественные языки тоже допускают конструкции неограниченной вложенности ("Вот два петуха, которые будят того пастуха, который бранится скоровницей строгою, которая доит корову безрогую, лягнувшую старого пса без хвоста, который зашиворот треплет кота, который пугает иловит синицу, которая часто ворует пшеницу, которая втёмном чулане хранится вдоме, который построил Джек."), поэтому для описания естественных языков регулярные выражения недостаточно выразительны.
Более выразительный способ описания языков формальные грамматики предложил Н. Чомски в 1956. Предложения на английском довольно неплохо поддаются такому описанию:
S NP VPNP N' | Det N'N' N | Adj N | N PP | N' CPVP V | V NP | V PPPP P NPCP VnP | C VP | C SVnP Vn | Adv VnP | VnP Conj VnN This | rooster | morn | judge | man | maiden | cow | horn | dog | cat | rat | malt | house | JackV is | crowed | woke | married | kissed | milked | tossed | worried | killed | ate | lay | builtVn shaven | shorn | tattered | torn | forlornAdj crumpled Adv allP in | with Det theC thatConj 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 |
lnd |
hlfe |
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,YP 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)
Облачные серверы от Маклауд быстрые и безопасные.
Зарегистрируйтесь по ссылке выше и получите 10% скидку на первый месяц аренды сервера любой конфигурации!
