Карпов - Основы построения трансляторов (2005) (943926), страница 2
Текст из файла (страница 2)
Именно эти идеи и представлены в пособии. Пособие преследует цель не только ознакомить читателя с теоретическими вопросами для понимания принципов работы существующих трансляторов, но и дать ему знания и умения, достаточные для написания им своего транслятора с разработанного им самим простого языка. В то же время такие чисто Предисповие технические вопросы, как оптимизация, распределение памяти, генерация кода для специфических конструкций алгоритмических языков и т. и., здесь не рассматриваются. Не рассматриваются в пособии и технологические вопросы генерации оптимального кода для специфической архитектуры процессоров, погружения оттранслированных программ в ту или иную операционную среду. Поэтому для построения современного транслятора с алгоритмического языка высокого уровня изложенных здесь сведений недостаточно.
Многие руководства по системному программированию и построению трансляторов делают упор именно на эти, не освещенные здесь вопросы. После ознакомления с основными концепциями трансляции, представленными в данном пособии, читатель без труда может пользоваться любой литературой в этой области, посвященной в том числе техническим и технологическим проблемам разработки трансляторов. Для понимания материала читателю необходимы основные сведения из дискретной математики, технологии программирования и теории автоматов в объеме курса технического вуза.
Пособие может быть использовано для студентов вузов, обучающихся по направлениям подготовки специалистов 553000 "Системный анализ и управление" и 552800 "Информатика и вычислительная техника". Введение Разработка трансляторов — чрезвычайно интересная область. Очевидной ее практической целью является построение программных систем специфического назначения — языковых процессоров. Эта область базируется на своем фундаменте — теории формальных языков, и главной целью учебного курса по основам построения трансляторов является представление этого фундамента.
За 50 лет теоретических и практических достижений в этой области основные положения этого теоретического фундамента стали классикой, их использование позволяет студенту построить свой собственный транслятор лаже для нетривиального языка. Любой человек, изучающий информатику, может задаться вопросом: а нужно ли знание теории и практики построения трансляторов лично ему, ведь используемых языков программирования не так много, новые языки высокого уровня появляются редко, и вероятность, что именно он лично в своей практической работе встретится с необходимостью построения компилятора для нового языка, ничтожна.
Ответ на этот вопрос состоит в том, что кроме распространенных алгоритмических языков программирования постоянно возникает необходимость в специализированных языках, часто разрабатываемых для решения конкретных задач передачи и обработки информации в конкретных узких областях приложений информатики. Для работы с этими языками нужны знания по основам трансляции. Формальные специализированные языки существуют во всех сферах деятельности человека. Конечно, можно разработать один универсальный язык, ««а котором можно было бы описать любую проблему ~и в качестве основы якого универсального языка принять естественный язык).
Однако этот универсальный язык в любой конкретной области приложения будет чрезвычай«ю неудобным: двусмысленным, неточным, нсэкономным. Например, попробуйте, используя только естественный язык, описать последовательность операций нахождения корней квадратного уравнения, проведя только с по- Введение мощью рассуждений разложение его на множители.
В то же время, оперируя символами на языке алгебры, сделать это очень просто. Другой пример— преобразование логических формул. Например, только постановка задачи доказательства тавтологичности формулы (р1 ==>р2) ==> ((р2:=~ рЗ) => ~р1 => р3)) на естественном языке выглядела бы так: 'Дсиы три угггвер>гсдеггия, истициых лиоо ложных. Дог'изать, что если ггсг?гиггггосгггь первого угггверждеггггя влечет истинность в??гороно, иго из э??гого с.гесЭуеггг, что если ггсггггигггосг??ь вгг?ороРО угггверждеггггя вчечеггг исгггиllггосгггь 1?грегггье20 иго и3 э??гол) с7есгуегуг что истинносп?ь г?грег??ьего угггверждеггия яв.'иегггся сгедсгггвгге1? ??с?пинг?ости первого".
Сложность доказательства этого утверждения, проведенного только на естественном языке без привлечения специального языка логики, очень велика. Очевидно, что для автоматической обработки формальных записей логических формул необходимо не только представить их на формальном языке, но и формализовать правила "понимания" этих формул. Человек в каждой узкой области своей деятельности использует и постоянно изобретает новые специализированные языки. Химия и вязание, алгебра и логика, шахматы и азбука Морзе — во всех этих ооластях придуманы свои специализированные языки для представления информации. Генная инженерия работает с языком кодирования аминокислот и генов. Станки с числовым программным управлением работают с описаниями деталей„представленными на специальном языке.
Широко развиты и графические языки. Электрические схемы, машиностроительные чертежи, знаки дорожного движения, системы переходов и сгг?ейтчаргггы (ь|а1ес11агЬ) для графического представления алгоритмов поведения сложных систем с конечным числом состояний, представление параллельных алгоритмов в виде сетей Петри — все это примеры графических языков.
Языки описания схем используются для автоматизированного проектирования дискретных устройств. Но конечно, огромное разнообразие специализированных языков имеется в системном программировании: это и языки описания интерфейсов, и командные языки операционных систем, и языки описания протоколов коммуникации в компьютерных сетях. Все системные программисты в своей работе сталкиваются с необходимостью конструирования новых языков. Форматы входных данных любой программы определяют свой язык.
Для большинства программ этот язык тривиален, но часто программные системы на своих интерфейсах характеризуются удобным для коммуникации, но нетривиальным для обработки языком представления информации, которая может включать декларации, инструкции, выра>кения и т. д. Практически всякая большая программная система включает в себя входной язык — от примитивного языка команд до весьма сложного. Примером простого языка может служить язык управления заданиями операционной системы. Более сложные языки — это современные языки программирования. Введение Человечество постоянно изобретает языки, с помощью которых можно точно, недвусмысленно и экономно выразить постановку задачи, правила преобразования, передать информацию в обозримой, удобной, компактной и наглядной форме.
Можно утверждать, что прогресс некоторой области науки существенным образом зависит от удобства, выразительности и степени формализации языка, используемого в этой области для задания и преобразования информации. "Границы моего языка есть границы моего мира," — писал философ Л. Витгенштейн. Таким образом, методы построения трансляторов являются областью знаний, нужных не только разработчикам языков программирования высокого уровня: идеи и методы этой области используются во все возрастающем числе приложений компьютеров.
ГЛАВА 1 Синтаксически-ориентированная трансляция Транслятор — это программа, которая переводит входной текст в некоторый выход. Например. входом транслятора может быть программа, написанная на языке программирования высокого уровня, таком как Паскаль или С, или каком-нибудь специализированном языке. Выходом транслятора может быть целевая программа на языке ассемблера, промежуточном языке или машинном языке, либо просто последовательность некоторых действий, предписанных входным предложением. Основной мыслью, которая вводится в данной главе, является та, что для любых преобразований <вхос)-выхо~)> современные трансляторы используют идею синтаксически-ориентированной трансляции, состоящую в том, что для любого преобразования предложения входного языка транслятор должен использовать структуру этого предложения. Гакой подход является обычным в науке: анализ и понимание сложной сисгемы всегда явно или неявно опираются на структуру этой системы.
1.1. Задача трансляции Задача трансляции формулируется следующим образом. Выполнить перевод, преобразование текста, написанного на некотором входном языке 1., в некоторый выход. Если входной язык — алгоритмический, то входной текст называют входной программой. Схематично транслятор как "черный ящик" представлен на рис. 1.1. Задачей данного пособия является рассмотрение того, как этот "черный ящик" устроен, т.
е. как организован такой перевод, и почему он организован так, а не иначе. Рассматриваемые принципы применимы не только для трансляторов языков программирования, но и для трансляторов искусственных языков любой природы. В традиционных областях применения трансляторов принята своя терминология. Основной такой областью является трансляция входной программы, написанной на языке программирования высокого уровня в эквивалентную Глава г программу на другом языке. В этом случае входной язык называется ггсходны.и (ьоогсе 1ащиаде), а входная программа на этом языке — исходным кодом (юцгсе соде). Язык, на который осуществляется трансляция, называется обьекгггныл| языко1г, результат трансляции — обьекгггиьг,1г кодо и. Компьютер, на котором впоследствии оттранслированная программа будет запущена, называется целевой.иаишгюй ~1агдс$ гпаС1и1е), он не обязательно совпадает с типом машины, на которой работает транслятор.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
