Кук Д., Бейз Г. - Компьютерная математика (1048841), страница 40
Текст из файла (страница 40)
Рассмотрим, что случится, если мы имеем «функцию» 1, которая замещает строку ху строкой рхх при условии, что первая строка является подстрокой в операнде. Тогда Нтхр)-Ир *. Однако неясно, чтб является результатом ~(хйрху). Возможны два случая — уххрхр или хрррхх. Аналогично получается, если мы применяем ~ несколько раа. Тогда Я(хурхр)-рххррхх, однако, применяя ~ к ххрр, получаем у(ххур) хрхху, ут(ххуу) рххххр или хухухх. Таким образом, «функцияз является не полностью определенной, и мы не можем поправить дело, потребовав, 260 чтобы операция изменяла все подстроки, поскольку они могут частично перекрываться.
Ситуация еще более усложняется, если применяются несколько замещающих функций. Необходимы средства выбора определенной подстроки всякий раз, когда воани- кает такой выбор; в частности, иы будем рассматривать подстроку, встречающуюся первой при чтепнн слева на- право. Для формализации рассуждений будем использовать порядковые свойства целых чисел н сами целые числа, соответствующие длинам строк. Предположим, что а и б — строки над А, !и!* 1!>! и и является подстрокой 1>. Предположим, что а в !! встречается «> различными спо- собами и что 1()1 — 1и1 я. Тогда мы можем записать ртп различными способами: '(>аб> "(»пб» ° " Т аб„, где (ь б< «з А», 1 «ь $ < «> и л> < я+ 1 (если а р, то я 0; поэтому существует только одна возмонгность). Бу- дем говорить, что т>, ..., "(„сяецифициру>от различные вхон«пения и в !) и что (> дает первое вхождение, а вхож- дение а непосредственно за (> является яереым вхож деиием.
Приме р 1А. Пусть у — функция А» - А» такая, что (х, у, р, д) ыА, и у заменяет первое вхождение ху в строке на ухх. Тогда а(руху)- руухх, а(хур у)- у рху, йт(хурху) уххрухх, Заметим также, что у'(хУ) - а'( ух'у)- а'(у 'у) - а'(у 'ух')- ут(ух»ух') у(ухух«) у»х«, (у»хз)» в. поэтому у~(хтут) - ут(хту») -... 7 Перед тем яак продолжить изложение, отметим, что существует альтернативный набор терминов для буквы, алфавита и слава; это — слово, словарь и предложение соответственно.
В некоторых контекстах эти термины бо лее разумны, однако в этом случае необходимо проявлять особую тщательность в использовании термина «слово», поскольку оно имеет два смысла. 1.2. Языки. Совокупность строк (или предложений) называется языком. Формально леыл Ь над алфавитом 261 А — это множество строк в А»; поэтому Ь ы А».
Следова. тельно, операции над строками индуцируют операции на языках. Отсюда получаем >,+ (транзитивное замыкание Ь) и Ь» (реЯлексивное замыкание Ь) следующим образом: а) ьо- 1Л); б) если Ь< и Е> — языки, то Л<Ь> [ху: выЬ<, уыЦ; в) Г Ь" <Ь, в<вг); г) ь+ 0,)<ь"; д) ь =)>. ь". Сейчас обратим внимание на то, как слова могут составляться в предложения, а мнов<ество всех предложений, имеющих смысл, образует язык. Нас будут в основном интересовать искусственные языки, такие как языки программирования илн языки, описывающие правильные математические выражения, однако вначале будет полезно рассмотреть случай английского языка.
Это даст возмо>квость сформулировать некоторые определения таким образом, что мы сможем сделать первые шаги в теорию языка. Возьмем предложение »ТЬе <)оя Ь11 шеэ. Это предложение можно рассматривать двумя способамн. Во-первых, изучать его как простую совокупность слов, каждое из которых является упорядоченной совокупностью букв; в этом случае предложение рассматривается синтаксически.
Во-вторых, интерпретировать предло>кение, считая, что мы понимаем значения слов и их внутренние связи; тогда мы получаем семантику — значение предло>кения. В дополнение заметим, что если мы произносим предло>кение, то оно влияет на нас своим воздействием — прагматизмом. В совокупности зги три области образуют семиотику языка. Пример 1.5. В языках программирования Фортран и Кобол утверждения А В+ С, АВВ В ТО С О!71ЯО А имеют одинаковый семантический смысл понятий сложения и присваивания, однако у них разный синтаксис. Прагматически они могут быть представлены на некоторой машине как результат выполнения кода ЬОАП В А110 С ЗТОВЕ А.
Х Основным объектом нашего рассмотрения будет область синтаксиса. Чтобы проиллюстрировать класс структур, которые мы будем изучать, рассмотрим диаграмму на рис. 8Л. Цоиав3шмльное 1 шоу оИ Фэв Рве. В.1 На самом деле ета диаграмма означает, что <предложение> может быть построено путем слияния <подлежащего>, <сказуемого> и <дополнения>, хотя зто требует формального определения.
Подлежащее состоит из <артпкля> с <существительным>, и окончательно получаем <артвкль> «гЬе», <существительное>»боя», ..., что дает нам предложение»<Ье боя ЬИ ше». Перед тем как ввести терминологию и обозначения, необходимые для уточнения общих понятий в конкретной ситуации, изображенной ва рис. 8.1, мы установим основные цели теории языков и сделаем обзор оставшейся части главы.
Напомним, что для заданного алфавита А язык т' является произвольным подмножеством множества А», однако произвольные подмножества представляют очень незначительный интерес. Мы хотим сосредоточить внимание на специальных языках, содержащих строки, которые благодаря ввешпей информации об их семантике счита ются осмысленными или хорошо сконструированными. Наиболее интересные языки бесконечны и, следова. тельно, не могут быть выписаны явно. В этих случаях на до придумать способы порождения языка; грамматика б может рассматриваться как такая порождающая система, Сформулируем две основные задачи формальной теории языков: а) Как по заданной грамматике б (и связанным с ней языком Е) порождать предложения ох п ж»'"г б) Как по заданным А <А» и аж А» устанавливать, принадлежит ли а ж г.?, 363 Для того чтобы проверить, входят ли эти строки в Е, надо знать, как Ь порождается грамматиков О.
В $2 и 3 мы опишем общие принципы грамматик с фразовой структурой, а затем подробнее рассмотрим некоторый подкласс, имеющий большов практическое значение. Обоаначим через Ь(О) язык, порожденный грамматикой 6. Тогда алгоритм проверки вхождения ажЬ(6) называется грамматическим раабором; он использует сз и 6. Часто первоначальная грамматика не подходит для определенной техники разбора, однако она может быть преобразована к эквивалентному, более подходящему виду. Вопросы, относящиеся к грамматическому разбору илп модификации грамматики, будут рассматриваться в $4. Проводя далее идею манипулирования грамматикой 6, в некоторых весьма специальных (по обычных) ситуациях можно перенести почти все (а иногда и все) трудности грамматического разбора в аиалиа грамматики и, следовательно, намного упростить апалиа конкретных строк. Спецификация ограничений, которым должны удовлетворять эти грамматики, является более сложной.
Изучению этих проблем посвящен $5. Упражнение 3.1.1. Предположим, что А и  — не- пустые алфавиты такие, что (А(-р, )В~-у, и ~р: А Хт, ~у: В - Х, — биекцпп. Пусть ун А» - Х определено как т; аг... а„~р, ~р(а;)зр и — 1) $ 1 а )(г: Вз - Х определено как ь у,: 5,...5,-3 $(5;).дп-". 1 1 Доказать, что т,'*Х, является биекцпей строк, и пока- вать, как применяется это отображение. Для этого надо найти прямые и обратные образы строк х'ухг в А* и 145332 в Вз, где А (х, у, г), В (1, 2, 3, 4, 5). $2. Грамматики с фразовой структурой 2Л, Основные определения.
О предел е н и е. Грамматикой с фразоаой структурой (ГФС) 6 называется алгебраическая структура, состоящая из упорядоченной четверки ()у, Т, Р, Б), где; 364 а) )ч' и Т вЂ” иепустые конечные алфавиты нетврминальных и терминальных символов") соответственно таких, что Й П Т И; б) Р— конечное множество нродукций, Р ы У+ >< У», где У Ж 0 Т называется словарем 6; в) Бш )у называется начальным символом или источником.
р Предполагая, что символ - не содержится в У, соотношение (а, р) «вР обычно записывают в виде а- Понятие продукции, которую также называют правилом нреобрааования, должно давать взамен«ность заменять одну строку символов другой. Терминальные символы обычно рассматриваются как неизменяемые символы. Поэтому, возмон«но, определение продукции в ГФС является чрезмерно общим. На практике соответствующие ограничения будут вводиться так, чтобы не нарушать постоянства терминальных св»толов, однако сейчас этого определения достаточно. В качестве первого шага рассмотрим рис. 8Л и по.
пытаемся повять, как он связан со следующими примерами. Пример 2Л. Предложение на английском языке, приведенное ранее в качестве иллюстрации, может быть определено в грамматике 6 =(У, Т, Р, Я), где Ф (<предложение>, <подлежащее>, <артикль>, <сущестзительное>, <сказуемое>, <дополнение>); Т- (йе, йоя, ЬИ, шеК Р ° ((<предложение>, <существительное>, <сказуемое>, <дополнение>), (<существительное>, <артикль>, <подлежащее>), (<артикль> »Ье), (<подлежащее> йой)', (<сказуемое> ЬИ), (<дополнение> ше)); Я ° <предлон«ение>.
Эта частная система порождает только одно предложение «йе йоя ЬИ ше» и, следовательно, может быть заменена на Ж = (<предложение>), Р ((<предложение> йе йой ЬИ ше)) нли даже на Ь = (йе йой ЬИ ше). Однако если мы в данном случае захотим расширить язык, чтобы включить в него все предложения, начинающиеся со слов, скажем, «1Ье 1юп», «»Ье гас», ейе Мйег», ») Этв символы будут называться также нетермввалаии в терминал»мв соответственно,— Примеч, ред. 265 со сказуемыми «аЬ» и «а««азией» и дополнениями «уоп» и «Харо1еоп» (тогда Ь будет иметь более 35 элементов), то это может быть сделано добавлением только семи дополнительных элементов к каждому из мяон«еств Т и Р. В этом примере размер языка составляет 4 ~ 3 «3, в то время как размер множества Р примерно равен 4+ 3+ 3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
