Карпов - Основы построения трансляторов (2005) (943926), страница 5
Текст из файла (страница 5)
не согласится ли он нарисовать его жену в обнаженном виде. "'Конечно, — от- ветил муж, — но мне все-таки придется надеть носки, чтобы было куда засовывать кисти". Заказа он не получил" — Ридерз дайджест, июнь 2004, с. 144. (чью жену надо было нарисовать, и кто должен был быть обнаженным'?). ". Постройте структуры и проанализируйте следующие примеры двусмысленных предложений английского языка: » "На!а Ьо11ей с1ис1~еп" (" Половина зажаренного цыпленка" либо "Наполовину за>каренный цыпленок"); ° "Т11еу аге Пуш,~ р!апета" ("Они летят самолетами" либо "Это — летящие самолеты"); ° "'! !1е 6п1е Лакея 1йе агго~" (" Время легит, как стрела" либо "Временные мухи любят стрелу"); » "1 гпас1е 11ег диск" (какие еще два смысла, кроме трех приведенных выше в тексте, может иметь это предложение?); ГЛАВА 2 Языки и грамматики Теория формальных языков изучает методы задания, распознавания и обработки языков.
В данной главе вводятся базовые понятия теории: это понятие языка и понятие грамматики как конечной модели задания языка. Вводится модель порождающей грамматики Хомского, показано, как "работает" порождающая грамматика, т. е. как она порождает язык. Приводятся примеры языков и строятся грамматики, их порождающие. Вводится простой алгоритчический язык Милан и строится порождающая его грамматика. Именно на примере языка Милан далее будут продемонстрированы алгоритмы лексиче-кого и синтаксического анализа, на нем же будут продемонстрированы про1лемы семантических вычислений и генерации промежуточного кода при трансляции. Попутно вводятся понятия и термины, существенные в теории формальных языков: порождение (вывод) цепочки языка в порождающей этот язык грамматике, сентенциальная форма как промежуточная цепочка вывода„канонический вывод, дерево вывода, двусмысленные цепочки и грамматики, синтаксический анализ.
Вводится иерархия порождающих 'рамматик Хомского, показано, что основные структуры языков программирования описываются контекстно-свободными грамматиками, хотя многие ;войства таких языков, в частности согласование типов„соответствие формальных и фактических параметров и т. и., являются контекстно-зависимыми ;«не могут быть выражены контекстно-свободными грамматиками. Описыаются также другие методы спецификации языков: БНФ-нотация, синтакси-«еские диаграммы — они являются эквивалентным, но более удобным спосоом задания контекстно-свободных языков по сравнению с грамматиками ~омского. Показывается, что существуют и другие модели задания языков, ..тличные от порождающих грамматик Хомского.
В качестве альтернативного .«еханизма спецификации языков, не связанного с понятием грамматики '',омского. приводятся сети Петри. Глава 2 2.1. Языки Конечное множество объектов будем называть словарем. Элементы словаря будем называть символами. Цепочкой (символов) над словарем будем называть произвольную конечную последовательность символов словаря.
Символы будем далее обозначап латинскими буквами начала словаря, цепочки малыми греческими буквами, ПРИМЕР 2.1. Пусть à — словарь, содержащии три символа: ~~, Ь, с. Над словарем Г можно построить различные цепочки, например, а = «Ыса, ~3 = сса, у== ~. Подобно тому, как ноль играет важную роль в построении числовой системы, в теории языков важную роль играет пустая цепочка, т. е. цепочка, вообще не содержащая символов. Пустую цепочку не всегда удобно обозначать пустой позицией, для се обозначения введен специальный символ е. Пусть à — словарь.
Множество всех возможных цепочек, составленных из символов словаря Г„включая и пустую цепочку, обозначим Г*. Например, если Г=,'а, Ь~, то Г* = ~ь, а, Ь. аа, аЬ, Ьа, Ы, аЬаЬ, ... ~. Если словарь не пуст, то число возможных цепочек над ним бесконечно, точнее, их количество счетно.
Обозначим а" цепочку из л символов а, причем а = е. Определим на множестве Р' бинарную операцию конкатенации (склеивания) цепочек. Результатом конкатенации цепочек и, ре Г' называется цепочка ар, которая, конечно, также принадлежит Г*. Если а = аЬЬса, Р = сса, то ир = аЫсисса, Очевидно, что операция конкатенации не коммутативна, иД ~ Ра.
Пустая цепочка является единицей операции конкатенации: для любой цепочки ае Р' справедливо: ьа = аь = а. Обозначим Г' = Р' — ~е~. Любая цепочка может быть представлена как конкатенация ее подцепочек и в общем случае не единственным образом. Например, цепочку Астана можно представить как конкатенацию трех цепочек, рДу, где р = ос, Д = аЬа, у = е, или же, как конкатенацию акт.
где гг = Ь, а ст = саЬа„а также бесконечным числом других способов. Другой важной операцией на множестве цепочек является операция подстановки„т. е. замены некоторой части цепочки другой цепочкой. Например, если в цепочке осаЬа вместо подцепочки са подставить цепочку оос, то в результате получим новую цепочку ЫосЬа (заменяемая цепочка выделена нами для удобства). Определение 2 1. Языком над словарем Г называется произвольное мно- жество цепочек над этим словарем ~рис. 2.1). Иными словами, язык над словарем à — это произвольное подмножество множества Г*. Языки и грамматики Рис.
2Л. Графическое представление языка над словарем У Это определение достаточно широко. Язык определяется здесь самым простым образом — как совокупность предложений. Язык — это множество (обычно бесконечное) одномерных последовательностей об.ьектов любой природы и вложенного в них смысла, причем объекты эти берутся из некоторого конечного набора (словаря). Очевидно, что над конечным непустым словарем можно определить бесконечное количество языков, точнее, континуум их (число подмножеств счетного множества имеет мощность континуум).
Поскольку языки — это множества, к ним применимы операции пересечения, объединения, взятия дополнения. Естественно определяется также и операция конкатенации двух языков Е~ и Л2. это множество всех таких цепочек, которые могут быть гюстроены как конкатенация какой-либо цепочки языка 1.1 с какой-либо цепочкой языка Л.: Е~Ь = (и~3 ~ аеЛ~, ~3~=-Е2~. Замыканием Клини (или итерацией) языка А называется язык Л* = Л ~ ~Е ~ ~ 2 ~Е и...
Отсюда как раз следует, что для любого конечного множества Г .имволов множество всех возможных цепочек (включая пустую цепочку ь) , оозначается Г*. Иногда используется также операция позитивного замыка- ~ия Е = Л* — ~к~. ПРИМЕР 2.2. Рассмотрим несколько примеров, показывающих применичость введенного определения к искусственным и естественным языкам.
Р'~ = ~а, Ь~; Л~ = ~ааЬЬ, Ьаа, ааЬа',. Здесь язык составляют три цепочки. Все остальные цепочки множества Г1*не принадлежат языку Е~. Р'- = (а, Ь~; Л = ',а Ь ~ л > О~. Язык Л вЂ” это бесконечное множество таких цепочек, которые начинаются символами а, заканчиваются символами Ь, а количества символов а и символов Ь в цепочках одинаковы. ~'з = (а, Ь, с~„Ез = ~а"Ьс"'~ л, лг > О~. Очевидно, аааЬссе1~, сЬЬаакЕз. Количества символов и в начале цепочек языка и символов с в конце цепочек могут не совпадать. Г~ = ~а, Ь~; 1~ = ~а ~ в цепочке а количества вхождений а и Ь равны~.
Очев идно ааЬЬаЬ я Х4 иаЬ ю Л4. Гпава 2 5. ! ~ = ~ (, ) ~; Е~ — множество правильных скобочных выражений. Очевидно, (( ))( ) еЕ;, ))(( ) Ю Е;. б. К„= ~а, Ь, с~: Е», = ~а"Ь"с" ~ л > О,'. Очевидно, ааЬЬссеЕ;„аЬса~Е»,. 7. Г~ =- Я„), +, —, *,/, г,'; Е7 = арифметические выражения, в которых операнды обозначаются символом ю. Очевидно, ~+ь1(в — Р" ~)еЕ;, с+*к ))( с*яЕ7. 8. Г'~ = ~а. Ь, с'1; Е~ = »иси ~ и е ~а, Ь~*». Цепочки языка Е~ — это две идентичные копии произвольной цепочки из символов а и Ь, разделенные маркером с. Примеры цепочек языка Е~.
ааЬсааЬ, ЬаЬасЬаЬа. 9. Н~ = ~а, Ь, с~; Е = ~и|си. ~ и~, и~ ~=~а, Ь'»; и1~ и ~. Цепочки языка Е9 состоят из двух несовпадающих цепочек над словарем (а, Ь~, разделенных маркером с. Примеры цепочек языка Е9. ааЬаасааЬЬа, ЬЬЬиса. 10. ~"~о = ~словоформы русского языка~; Е~о = русский язык. Например, "молодая красивая студентка мчалась галопом в карете по пыльной доро-' ге" ~Е~О, "от дорогу по телеге к" ЮЕ о. 11. Гп = ~а, Ь, с, ..., О, 1,2, ..., ~,1, ..., Ьерп, »Ы1ог, ~; Еп = язык Паскаль.
2.2. Грамматики Определение языка как подмножества множества всех возможных цепочек над конечным словарем является слишком общим и неконструктивным. Такое определение удобно только в случае конечного языка, например, азбуки Морзе, цепочки которой составлены из двух символов — точек и тире, а число цепочек языка конечно. Сложность работы с языками состоит в том, что язык — это обычно бесконечное множество, а бесконечное множество невозможно задать простым перечислением его элементов. Лишь в некоторых случаях бесконечный язык можно задать с помощью условий (предикатов), определенных на цепочках языка, как в слу иях 2, 3, б примера 2.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
