Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 49
Текст из файла (страница 49)
242 я их оценк . ценки. Поэтому надо понять способы задания и реалии ежде чем применять к компиляторам критезации перевода, р рии и инженерного проектирования. 3„1. ФОРМАЛИЗМЫ~ ИСПОЛЬЗУЕМЫЕ ДЛЯ ОПРЕДЕЛЕНИЯ ПЕРЕВОДА В этом разделе мы изложим два фундаментальных метода определения п.р-вода. Один нз них — „схема перевода", которая представляет собой грамматику, снабженную механизмом, обечивающим выход для каждой порождаемой цепочки.
В другом методе основную роль играет „преобразователь", т. е. распознватель с выходом, который на каждом такте может выдавать цепочка ь у выходных символов ограниченной длины. начала мы об рассмотрим схемы перевода, основаннйе на контекстно-сво одныхграмматиках, а потом займемся конечными преобразователями и преобразователями с магазинной памятью. 3.1Л. Перевод и семантика В гл. 2 изучались только синтаксические аспекты языков.
Та мы познакомились с несколькими методами определения ам м правильно построенных цепочек, или предложений, языка. пе ь мы хотим исследовать механизмы, связывающие с каждым предложением (цепочкой) языка другу1о цепочку, которая должн Р жна быть выходом, или результатом перевода, этого предложения. Для обозначения этого отношения между предложениями и соответствующими выходными цепочками, определяющими их „смыслы", или „значения", иногда употребляют термин „семантика".
Определение. Пусть Х вЂ” входной'алфавит и А — выходной алфавит. Переводом с языка Е, с= Х' на язык ~, а: — ' Аа назовем отношение Т из Х' в б', для которого ь,— область определения, а 1.э — множество значений. Если (х, у) Е Т, то цепочка у называется выходом для цепочки х. Заметим, что в общем-случае в переводе Т для данной входной цепочки может быть более одной выходной цепочки.
Однако перевод, предназначенный для описания языка программирования, должен быть функцией, т. е. для каждого входа должно быть не более одного выхода. Можно привести много примеров переводов. По-видимому, самый примитивный тип перевода — перевод, задаваемый гомоморфизмом, Пример 3.1. Допустим, что мы хотим перевести каждую греческую букву цепочки из множества Х' в ее английское название Зто можно сделать с помощью такого гомоморфизма 6, что 243 ГЛ. 3.
ТЕОРИЯ ПЕРЕВОДА Таблица зл Греческая буква Греческая буква (!) А(а)=а, если а принадлежит Х, но не является буквой греческого алфавита; (2) А (а) определяется табл. 3.1, если а †греческ буква. Например, переводом предложения а.=-нг' будет цепочка а=р! Г', () Другой пример перевода, полезный при описании одного процесса, часто встречающегося при компиляции,— отображение обычной (инфиксной) записи арифметических выражений в польскую запись, Определение.
Запись обычных (или .инфиксных) арифметических выражений без использования скобок называют польской (бесскобочной) записью'), Пусть 9 — множество знаков бинарных операций (например, (+, «)) и Х вЂ” множество операндов, Определим рекурсивно две формы польской записи, префиксную и лосгпфиксную: (1) Если инфиксное выражение Е является единственным операндом аЕХ, то как префиксная, так и постфиксная поль. ские записи выражения Š— это просто а. (2) Если Е,ОЕ,— инфиксное выражение, где Π— знак операции, а Е, и Š— ннфиксные выражения, операнды для О, то (а) ОЕ;Ек — префиксная польская запись выражения Е,ОЕ, где Е; и Е; — префиксные польские записи выражений Е, и Е, соответственно; а) Этот метод впервые описал польский математик Лукасевнч, фамилию которого произнести труднее, чем слово япольская".
З,1 ЬОРМАЛИЗМЫ, ИСПОЛЬЗРЕМЫЕ ДЛЯ ОПРЕДЕЛЕНИЯ ПЕРЕВОДА (б) Е,"Е;Π— постфиксная польская запись выражения Е,ОЕ„, где Е," и Š— постфиксные польские записи выражений Е, и Е, соответственно. (3) Если (Е) — йнфиксное выражение, то (а). префиксная польская запись выражения (Е) — это префиксная польская запись выражения Е; (б) постфиксная польская запись выражения (Е) — это постфиксиая польская запись выражения Е. Пример 3.2.
Рассмотрим инфиксное выражение (а+Ь) «с. Зто выражение вида Е,«Е„где Е,=(а+Ь) н Е,=с. Тогда с — префиксиая и постфиксная польская запись выражения Е,. Префиксная запись' выражения Е„т. е. выражения а+ Ь, это +аЬ. Таким образом, префиксной зааисью выражения (а+Ь) «с является «+аЬс. Аналогично постфиксной записью выражения а+ Ь будет аЬ+, а постфиксной записью выражения (а+ Ь) «с будет аЬ+ се. 0 От префиксного или постфиксного выражения можно однозначно вернуться к инфиксному выражению.
Зто не совсем очевидно, но можно доказать, используя упр. 3.1.16 н 3.1.17. Рис. 3,1. Древовидное представление выражения (а+Ь) ес. Арифметические выражения удобно представлять с помощью деревьев. Представление выражения (а+Ь) «с в виде дерева показано иа рис.
3.1. В этом дереве каждая внутренняя вершина помечена знаком операции из множества 9, а каждый лист— операндом из Х. Префиксная польская запись — это просто левое скобочное представление дерева, из которого удалены все скобки. Аналогично постфиксная польская запись — это правое скобочное представление дерева, нз которого удалены все скобки. Два важных примера переводов †множест пар ((х у) ! х — внфиксное выражение и у — префиксная (постфиксная) запись выражения х) Зти переводы нельзя задать с помощью гомоморфизмов. Нужны более мощные способы задания переводов, и мы займемся теперь формализмами, позволяющими удобно описывать эти и другие переводы. ГЛ.
3. ТЕОРИЯ ПЕРЕВОДА В П ФОРМАЛИЗМЫ, ИСПОЛЬЗУЕМЫЕ ДЛЯ ОПРЕДЕЛЕНИЯ ПЕРЕВОДА 3.1.2. Схемы синтаксически унраепяемого переео14е Проблема задания бесконечного перевода конечными средствами аналогична проблеме задания бесконечного языка. Известно несколько возможных подходов к определению переводов. Аналогично порождению языка с помощью грамматики можно использовать систему, порождающую пары цепочек, принадлежащие переводу, Можно также воспользоваться распознавателем с двумя лентами, распознающим пары, принадлежащие переводу, нли же определить автомат, который принимает в качестве входа цепочку х и выдает (недетермииированно, если нужно) всецепочки у, явля|ощиеся переводами цепочки х.
Этот список не исчерпывает всех возможностей, но охватывает наиболее распространенные модели. Назовем устройство, которое по данной входной цепочке х вычисляет такую выходную цепочку у, что (х, у) Е Т, транслятором, реализующим перевод Т. Хотелось бы, чтобы определение перевода обладало „хорошими" свойствами, в частности такими: (1) в нем легко разобраться, т.
е. легко установить, какие пары цепочек принадлежат переводу, (2) прямо по определению перевода можно механически построить эффективный транслятор, реализующий этот перевод. Желательные качества трансляторов таковы: (1) эффективность трансляции — время, необходимое для обработки входной цепочки гв длины л линейно зависит от л, (2) небольшой объем, (3).корректность †желатель иметь небольшой конечный тест, такой, что если транслятор прошел через него, то пра- вильность работы транслятора гарантирована на всех входных цепочках.
Одним из формализмов, используемьгх для определения переводов, является схема синтаксически управляемого перевода (трансляции). Интуитивно такая схема представляет собой просто грамматику„в которой к каждому правилу присоединяется элемент перевода. Всякий раз, когда правило участвует в выводе входной цепочки, с помощью элемента перевода вычисляется часть выходной цепочки, соответствующая части входной цепочки, порожденной этим правилом.
Пример 3.3. Рассмотрим схему, определяющую перевод ((х, ха) ( х б (О, 1)') (для каждого входа х выходом служит обращенная цепочка) по правилам, выписанным в табл. 3.2. В переводе, определяемом этой схемой, пару вход — выход можно получить, порождая последовательность вывоуимых лар Таблица З.й Элемент леревола Правила 5 50 5=5! 5 — е ()) 5-- 05 12) 5 г5 (3) 5 — ее 5=50, Пока можно рассматривать этот элемент перевода просто как правило 5 50. Так получается, выводимая пара (05, 50). Снова применяя правило (1) к символу 5 в этой новой паре, получаем (005, 500).
Затем правило (2) дает (0015, Я100). Если здесь применить правило (3), то будет (001, 100). К последней паре никакого правила применить нельзя, и потому она принадлежит переводу, определяемому мой схемой. Схема трансляции Т определяет некоторый перевод т(Т). По схеме Т можно построить транслятор, реализующия перевод т(Т), который работает так. По данной входной цепочке х с помощью правил схемы трансляции транслятор находит (если это возможно) некоторый вывод цепочки х из 5.
Допустим, что Я=а,=>а,:=>ав =>... => а„.=х — такой вывод. Затем транслятор строит вывод (а Ро) ~( () ) =р .. =Ь(а„, ~„) "щий из выводимых пар цепочек, для кото о С ( "' б )=(Х У) И КажДЕЯ ЦЕПОЧКа ()Г ПОЛуЧЗЕтея ИЗ ммр, с помощью элемента перевода, соответствующего правилу, примененному в надлежащем месте при переходе от а,, к Цепочка у служит выходом.для цепочки х. Часто выходную цепочку можно получить за время, необходимое для разбора входной цепочки. Пример 3.4. Рассмотрим схему перевода, отобража~ощую арифметические выРажениЯ из Языка Е(бе) в соответствУющие постФиксные польские записи. Оиа изображена в табл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
