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