Гладкий - Формальные грамматики и языки - 1973 (947381), страница 57
Текст из файла (страница 57)
Мы дадим ' здесь краткое изложение этих способов, а также правил перехода от одного способа к другому. й П!.1. Системы составляющих Пусть х — произвольная непустая цепочка в словаре У. Множество С отрезков цепочки х называется системой составляющих этой цепочки, если оно удовлетворяет следующим двум условиям: 1. С содержит отрезок, состоящий из всех точек цепочки х, и все одноточечные отрезки х. П.
Лю бые два отрезка из С либо не пересекаются, либо один из них содержится в другом. Элементы С мы будем называть с о с т а в л я ющи м и. Одноточечные отрезки будут называться точе ч н ы м и составляющими, отрезок, состоящий из всех точек цепочки,— полной составг!рюшей; полную и точечные составляющие мы будем иногда называть т и- . в и а л ь н ы м и. вать три- . Для наглядного изображения системы составляющих можно пользоваться следующим простым способом: заключать каждую нетривиальную составляющую в скобки, причем левую и правую скобки, отвечающие одной составляющей, помечать одной и той же меткой так,чтобы разные пары скобок были помечены разными метками; в качестве меток можно использовать хотя бы натуральные числа. Можно, впрочем, обойтись и без меток, так как в силу пункта П определения системы составляющих для каждой левой скобки можно однозначно указать соответствующую ей правую и обратно (упражнение П1.1).
Мы будем пользоваться скобочным изображением как с метками, так и без меток — где как удобнее. Пример. Две разные системы составляющих (из многих возможных — см. упражнение П1.2) одной и той же цепочки ЬаЬсайеЬассйабаЬ можно изобразить так (1) (((Ьа) Ь) са(йеЬ) ) ((асс)(й (аЬ) ) (аЬ) ); 123 3 2 4 4156 67 8 879 95 (2) Ь (а (Ь (с (ай (е (Ьа (сс) й) а) ) ) Ьа Ь) ).
1 2 3 4 5 6 7 7 6 543 21 Если цепочка интерпретируется как предложение' естественного языка, то система составляющих может быть использована в качестве способа выражения информации о его синтаксической структуре (или4. как обычно говорят, способа изображения синтаксической структуры предложения).
Именно, такая информация может представлять собой список ел о восо.ч ет а4 н и й, т, е. тех «кусков» предложения, которые в какомто интуитивном смысле являются «синтаксически связными», Эмпирические соображения позволяют сделать допущение, что словосочетания, во-первых, образуют-от4 резки и, во-вторых, не имеют «частичных пересечений», т. е. удовлетворяют пункту П определения системы составляющих. Таким образом, нетривиальные составляющие — это (при подходящем выборе системы составляющих!) как раз словосочетания.
(Тривиальные добавляются для придания системе формальной законченности.) П р и м е р. Предложение (3) Онегин, добрый мой приятель, родился на брегах Невы допускает следующую «естественную» систему сосТд«вляющих; (4) (Онегин, (добрый (мой приятель) ) ), (родился (на (брегах.Невы).)). Я84 СИСТЕМЫ СОСТАВЛЯЮ!ЦИХ И ДЕРЕВЬЯ ПОДЧИНЕНИЯ [П. е пл.п СИСТЕМЫ СОСТАВЛЯЮЩИХ 288 Аналогичную роль играют составляющие в искус ственных формализованных языках, используемых в ма тематике и в программировании. Так, формула логик ' предикатов (5) Чх(Р(х) д ](6 (х) ~/ ] Н (х))) допускает следующую «естественную» систему саста ляющих (мы записываем ее с гомощью квадратных скобок, так как круглые входят здесь в словарь языка) ' [Ух][([Р(х)]ус[ ][([6(х)] ~/ [ ][Н(х)]])]])].
Та же формула в бесскобочной записи (5') Ухдс г"х ] ~l бх ]Нх допускает «естествен!1)ую» систему составляющих [!ух] [г1 [Гх] [ ] [ ~у [6х] [ ][Нх] ] ] ] ]. Среди многочисленных систем составляющих, кото;, рые имеет предложение естественного языка, лишь" весьма немногие «правильны», т.
е. адекватно отражают. синтаксическое строение предложения. При этом поня' тие «правильной» системы составляющих не абсолютно — оно зависит от соглашений лингвистического ха-' рактера, отражающих определенные содержательные представления о синтаксической структуре предложения данного языка. Так, из двух возможных систем со. ставляющих для одного и того же предложения (5) (Все (эти известия) ) (произвели (на меня) (удручающее впечатление) ) н (б') (Все (эти известия)) произвели (на меня) (удручающее впечатление) первая отвечает традиционному представлению о подлежащем и сказуемом как главных членах предложения, вторая — более новому взгляду на подлежащее и дополнения как равноправно подчиненные сказуемому «актанты». Прн фиксированной системе соглашений предложение также может иметь несколько «правильных» систем составляющих.
Нередко эти системы соответствуют различным толкованиям смысла предложения. В лингвистике такое явление — наличие у одного предложения двух или более правильных «синтаксических анализо⻠— известно под названием синтаксической омоним и н '). Например, предложение (!) Геологи и студенты из Тюмени уехали в Москву допускает по меньшей мере три толкования: 1. «Тюменские геологи и тюменские студенты уехали откуда-то (не обязательно из Тюмени) в Москву». 2. «Какие-то (не обязательно тюменские) геологи и тюменские студенты уехали откуда-то (не обязательно из Тюмени) в Москву».
3. «Какие-то (не обязательно тюменские) геологи н какие-то (не обязательно тюменские) студенты уехали нз Тюмени в Москву». Этим толкованиям отвечают соответственно следующие системы составляющих: (8) ((Геологи и студенть!) (из Тюмени) ) (уехали ('в Москву)). (9) (Геологи и (студенты (из Тюлени))) (уехали (в Мосссву)). (10) (Геологи и студенть!) ((из Тюмени) уехали (в Москву)). Заметим, что синтаксическая омонимия нередко встречается и в таких предложениях, которые обычно не кажутся нам двусмысленными, поскольку мы в состоянии однозначно выбрать нужное толкование, опираясь на имеющиеся у нас сведения о действительности.
Однако при автоматическом синтаксическом анализе такие случаи синтаксической омонимии также должны учитываться. Рассмотрим, например, предложения: (11) Гастроли балета на Кавказе проходят успешно и 1!2) Гастроли балета на льду проходят успешно. Если носитель русского языка, научившийся строить системы составляющих и понимающий смысл этих *) с1то касается искусственных формализованных языков, то они обычно строятся так, чтобы синтаксической емонимин не было. системы сОСТАВляющих !пыл Звв СИСТЕМЫ СОСТАВЛЯЮЩИХ И ДЕРЕВЬЯ ПОДЧИНЕНИЯ [П.. предложений, получит задание указать для них «пр вильные» системы составляющих, то он, надо полагат без труда построит следующие системы: (а) ((Гастроли балета) (на Кавказе) ) (проходят успешно), (б') (Гастроли (балета (на льду))) (проходят успешно) .
Однако такой анализ сушественным Образом оп рвется на знание некоторых внеязыковых фактов (имее ся нечто, называемое «балет на льду», но нет ничег называемого «балет на Кавказе»; понятие «гастроли н Кавказе» имеет сгхысл, а «гастроли на льду» — нет).
Ч ловек, не знающий этих фактов, должен будет допусти для первого предложения еше одну систему (а') (Гастроли (балета (на Кавказе))) (проходят успешно), аналогичную (б'), а для второго — систему (б) ((Гастроли балета) (на льду) ) (проходят успешно), аналогичную (а). Так же будет действовать, разумеется, и машин (вернее, алгоритм синтаксического анализа). Наконец, следует заметить, что различные «правил ные» системы составляюших (при фиксированной сист ме лингвистических соглашений) могут и не соответс вовать каким-либо ошутимым различиям в толкованн смысла. Примером могут служить следующие две сист мы составляющих: (13) Мы увидели (древние (стены города)); (14) Мы увидели ((древние стены) города). Введем теперь следующее определение.
Если А и  — составляюШие некоторой системы то выражение «В непосредственно вложен в А» будет означать, что А с: В и в С нет составляюше Вложенной в А, содержащей В и отличной от А и от В Будем писать в этом случае В с: с:А илн А:» ~В. Нетрудно видеть (упражнение П!. 3), что граф (С;:э ~) является деревом, корнем которого служит полная составляющая и висячими узлами — точечные составляющие. Это дерево называется д е р е в о м с ос т а в л я ю ш и х; его графическое изображение может служить еше одним наглядным способом записи системы составляющих. Например, система составляющих (4) предложения (3) представляется следующим деревом: Онегин, добрый мой приятель, родился на брегах Невы ! родился на брегах Невы ! Онегин, добрый мой приятель ! 4 Онегин добрый мой приятель ! Ф ' 4 добрый мой приятель ! 4 4 мой приятель Ф 4 родился на брегах Невы ! 4 4 на брегах Невы ! Ф брегах Невы Рассматривая составляющую как узел дерева составляюших, мы можем определить ее высоту, р а нг и степень, как на стр.
18. Вместо «ширина (высота, степень) дерева (С; ~:з)» будем говорить «ш и р и и а (в ы с о т а, с т е п е н ь) системы С». Систему составляюших, имеющую бинарное дерево, мы также будем называть б и н а р н о й. Заметим, что если ширина системы С равна 1, то длина составляюшей ранга г не превосходит 1'.
Поэтому каждый отрезок цепочки, длина которого больше нли Равна 1', содержит точку, являющуюся левым или правым концом какой-либо составляющей ранга, не меньшего г. При изучении систем составляющих, связанных с грамматиками, оказывается полезной следующая Л е м м В П1.1. Пусть С вЂ” система составляющих Цепочки хух, 1 — ширина С и ! у !)2п 1'". Тогда найдутся точки а, ( ... (а„< бп( ... (8, цепочки хух такие, нто (а„й1),..., [а„, (!и) ЕВС и либо а, « ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
