1. Построение детерминированного конечного автомата по регулярному выражению. Приведем теперь алгоритм построения детерминированного конечного автомата по регулярному выражению [1]. К регулярному выражению (сокращенно РВ) r добавим маркер конца: (r)#. После построения ДКА для расширенного РВ легко построить ДКА для исходного РВ: все состояния ДКА из которых есть переход в конечное с чтением символа "#", можно считать конечными, а символ "#" и соответствующие переходы удалить. Представим РВ в виде дерева, листья которого - терминальные символы, а внутренние вершины - операции "." (конкатенации), "U" (объединение), "*" (итерация). Каждому листу дерева (кроме e-листьев) припишем уникальный номер и ссылаться на него будем, с одной стороны, как на позицию в дереве и, с другой стороны, как на позицию символа, соответствующего листу. Теперь, обходя дерево T сверху-вниз слева-направо, вычислим четыре функции: nullable, firstpos, lastpos и followpos. Функции nullable, firstpos и lastpos определены на узлах дерева, а followpos - на множестве позиций. Значением всех функций, кроме nullable, является множество позиций. Функция followpos вычисляется через три остальные функции. Функция firstpos(n) для каждого узла n синтаксического дерева регулярного выражения дает множество позиций, которые соответствуют первым символам в подцепочках, генерируемых подвыражением с вершиной в n. Аналогично, lastpos(n) дает множество позиций, которым соответствуют последние символы в подцепочках, генерируемых подвыражениями с вершиной n. Для узлов n, поддеревья которых (т.е. дерево, у которого узел n является корнем) могут породить пустое слово, определим nullable(n)=true, а для остальных узлов false. узел n nullable(n) firstpos(n) lastpos(n) --------------------------------------------------------- лист е | true | 0 | 0 --------+-------------+------------------+-------------- лист i | false | {i} | {i} --------+-------------+------------------+-------------- U | nullable(a) | firstpos(a) | lastpos(a) / \ | or | U | U a b | nullable(b) | firstpos(b) | lastpos(b) --------+-------------+------------------+-------------- . | nullable(a) | if nullable(a) |if nullable(b) / \ | and | then firstpos(a) |then lastpos(a) | | U firstpos(b) | U lastpos(b) a b | nullable(b) | else firstpos(a) |else lastpos(b) --------+-------------+------------------+-------------- * | | | | | true | firstpos(a) | lastpos(a) a | | | -------------------------------------------------------- Рис. 2.5 Таблица для вычисления функций nullable и firstpos приведена на рис. 2.5. Вычисление функции lastpos строится аналогично. Если i - позиция, то followpos(i) есть множество позиций j таких, что существует некоторая строка ...cd..., входящая в язык, описываемый РВ, такая, что i - соответствует этому вхождению c, а j - вхождению d. Функция followpos может быть вычислена также за один обход дерева по следующим двум правилам 1. Пусть n - внутренний узел с операцией "." (конкатенация), a,b - его потомки. Тогда для каждой позиции i, входящей в lastpos(a), добавляем к множеству значений followpos(i) множество firstpos(b). 2. Пусть n - внутренний узел с операцией "*" (итерация), a - его потомок. Тогда для каждой позиции i, входящей в lastpos(a), добавляем к множеству значений followpos(i) множество firstpos(а). Функция followpos позволит теперь сразу построить детерминированный конечный автомат с помощью следующего алгоритма. Алгоритм 2.1. Прямое построение ДКА по регулярному выражению. Будем строить множество состояний автомата Dstates и помечать их. Состояния ДКА соответствуют множествам позиций. Начальным состоянием будет состояние firstpos(root), где root - вершина синтаксического дерева регулярного выражения, конечными - все состояния, содержащие позиции, связанные с символом "#". Сначала в Dstates имеется только одно непомеченное состояние firstpos(root). while есть непомеченное состояние T в Dstates do пометить T; for каждого входного символа a<-T do пусть символу a в T соответствуют позиции p1,...,pi, и пусть S=U followpos(pi) i Если S не пусто и S не принадлежит Dstates, то добавить непомеченное состояние S в Dstates (рис. 2.8) Функцию перехода Dtran для T и a определить как Dtran(T,a)=S. end; end; -------------------------------------------------------------- 2. Построение детерминированного конечного автомата с минимальным числом состояний Рассмотрим теперь алгоритм построения ДКА с минимальным числом состояний, эквивалентного данному ДКА [2]. Алгоритм 2.2. Построение ДКА с минимальным числом состояний. Шаг 1. Строим начальное разбиение П множества состояний из двух групп: заключительное состояние и остальные S-F. Шаг 2. Применяем к П следующую процедуру и получаем новое разбиение Пnew (рис. 2.11): for каждой группы G в П do разбиваем G на подгруппы так, чтобы состояния s и t из G оказались в одной группе тогда и только тогда, когда для каждого входного символа a состояния s и t имеют переходы по a в состояния из одной и той же группы в П; заменяем G в Пnew на множество всех полученных подгрупп end; +---+ +-+ +-+ +-----|s,t|-----+ |s| |t| | +---+ | +-+ +-+ |a a| | | | +---+ | v v +---->| |<----+ +-+ +-+ +---+ | | | | +-+ +-+ Рис. 2.11 Шаг 3. Если Пnew=П, полагаем Пres=П и переходим к шагу 4, иначе повторяем шаг 2 с П:=Пnew. Шаг 4. Выберем по одному состоянию из каждой группы в разбиении Пres в качестве представителя для этой группы. Представители будут состояниями приведенного ДКА М'. Пусть s - представитель. Предположим, что на входе a в M существует переход из t. Пусть r - представитель группы t. Тогда М' имеет переход из a в r по a. Пусть начальное состояние М' - представитель группы, содержащей начальное состояние s0 исходного M, и пусть заключительные состояния М' - представители в F. Отметим, что каждая группа Пres либо состоит только из состояний из F, либо не имеет состояний из F. Шаг 5. Если М' имеет мертвое состояние, т.е. состояние d, которое не является допускающим и которое имеет переходы в себя по любому символу, удалим его из М'. Удалим также все состояния, не достижимые из начального. -------------------------------------------------------------- 3. Алгоритм разбора сверху-вниз Основная проблема предсказывающего разбора - определение правила вывода, которое нужно применить к нетерминалу. Процесс предсказывающего разбора (сверху-вниз) с точки зрения построения дерева разбора можно проиллюстрировать рис. 3.1. Фрагменты недостроенного дерева соответствуют сентенциальным формам вывода. Вначале дерево состоит только из одной вершины, соответствующей аксиоме S. В этот момент по первому символу входного потока предсказывающий анализатор должен определить правило S->X1 X2 ..., которое должно быть применено к S. Затем необходимо определить правило, которое должно быть применено к X1, и т.д., до тех пор, пока в процессе такого построения сентенциальной формы, соответствующей левому выводу, не будет применено правило Y->a .... Этот процесс затем применяется для следующего самого левого нетерминального символа сентенциальной формы. S S S / | \ / | \ X1 X2... X1 X2... / / | ........... ............. / / | Y Y | /|\ /|\ Z / ... / ... /|\ a..........$ a...........$ a........b.......$ а) б) в) Рис. 3.1 На рис. 3.2 приведена структура предсказывающего анализатора, который определяет очередное правило из таблицы. Такую таблицу множно построить непосредственно из грамматики. +---------------+ Вход | a | + | b | $ | +---------------+ ^ | +-+ +----------------------+ |X| | Программа предсказы- | Выход Магазин |-|<---| вающего анализатора |---> |Y| +----------------------+ |Z| | |-| v |$| +---------------------+ +-+ | Таблица анализатора | +---------------------+ Рис. 3.2 Таблично-управляемый предсказывающий анализатор имеет входной буфер, таблицу анализа и выход. Входной буфер содержит распознаваемую строку, за которой следует $ - правый концевой маркер, признак конца строки. Магазин содержит последовательность символов грамматики с $ на дне. Вначале магазин содержит начальный символ грамматики на верхушке и $ на дне. Таблица анализа - это двумерный массив M[A,a], где A - нетерминал, и a - терминал или символ $. Анализатор управляется программой, которая работает следующим образом. Она рассматривает X - символ на верхушке магазина и a - текущий входной символ. Эти два символа определяют действие анализатора. Имеются три возможности. 1. Если X=a=$, анализатор останавливается и сообщает об успешном окончании разбора. 2. Если X=a#$, анализатор удаляет X из магазина и продвигает указатель входа на следующий входной символ. 3. Если X - нетерминал, программа заглядывает в таблицу M[X,a]. По этому входу хранится либо правило для X, либо ошибка. Если, например, M[X,a]={X->UVW}, анализатор заменяет X на верхушке магазина на WVU {на верхушке U}. Будем считать, что анализатор в качестве выхода просто печатает использованные правила вывода. Если M[X,a]=error, анализатор обращается к подпрограмме анализа ошибок. Поведение анализатора может быть описано в терминах конфигураций автомата разбора. Алгоритм 3.1. Нерекурсивный предсказывающий анализ. repeat X:=верхний символ магазина; if X - терминал или $ then if X=InSym then удалить X из магазина; InSym:=очередной символ; else error() end else /*X = нетерминал*/ if M[X,InSym]=X->Y1Y2...Yk then удалить X из магазина; поместить Yk,Yk-1,...Y1 в магазин (Y1 на верхушку); вывести правило X->Y1Y2...Yk else error() /*вход таблицы M пуст*/ end end until X=$ /*магазин пуст*/ Вначале анализатор находится в конфигурации, в которой магазин содержит S$, (S - начальный символ грамматики), во входном буфере w$ (w - входная цепочка), переменная InSym содержит первый символ входной строки. Программа, использующая таблицу анализатора M для осуществления разбора, изображена на рис. 3.3. -------------------------------------------------------------- 4. Множества FIRST и FOLLOW. При построении предсказывающего анализатора полезными оказываются две функции, связанные с грамматикой G. Эти функции, FIRST и FOLLOW, позволяют построить таблицу предсказывающего разбора для G, если, конечно, это возможно. Множества, даваемые этими функциями, могут, кроме того, быть использованы при восстановлении после ошибок. Если u - любая строка символов грамматики, положим FIRST(u) - множество терминалов, с которых начинаются строки, выводимые из u. Если u=>*e, то e также принадлежит FIRST(u). Определим FOLLOW(A) для нетерминала A как множество терминалов a, которые могут появиться непосредственно справа от A в некоторой сентенциальной форме, т.е. множество терминалов a таких, что существует вывод вида S=>*uAav для некоторых u и v. Отметим, что между A и a в процессе вывода могут появиться нетерминальные символы, из которых выводится e. Если A может быть самым правым символом некоторой сентенциальной формы, то $ принадлежит FOLLOW(A). Для построения FIRST(X) для всех символов грамматики X применим следующий алгоритм. Алгоритм 3.2. Построение множеств FIRST для символов грамматики. Шаг 1. Если X - терминал, то FIRST(X) - это {X}; если X - нетерминал, полагаем FIRST(X)={}. Шаг 2. Если имеется правило вывода X->e, то добавить e к FIRST(X). Шаг 3. Пока ни к какому множеству FIRST(X) нельзя уже будет добавить новые элементы или e: если X - нетерминал и имеется правило вывода X- >Y1Y2...Yk, то включить a в FIRST(X), если для некоторого i a<-FIRST(Yi) и e принадлежит всем FIRST(Y1),...,FIRST(Yi-1), т.е. Y1...Yi-1=>*e. Если e принадлежит FIRST(Yj) для всех j=1,2,...,k, то добавить e к FIRST(X). Например, все, что принадлежит FIRST(Y1) принадлежит также и FIRST(X). Если из Y1 не выводится e, то ничего больше не добавляем к FIRST(X), но если Y1=>*e, то добавляем FIRST(Y2), и т.д. Теперь FIRST для любой строки X1X2...Xn можно вычислить следующим образом. Шаг 1. Полагаем FIRST(X1X2...Xn)={}. Шаг 2. Добавим к FIRST(X1X2...Xn) все не e символы из FIRST(X1). Добавим также не e символы из FIRST(X2), если e<-FIRST(X1),не e символы из FIRST(X3), если e принадлежит как FIRST(X1), так и FIRST(X2), и т.д. Наконец, добавим e к FIRST(X1X2...Xn), если e<-FIRST(Xi) для всех i. Для вычисления FOLLOW(A) для нетерминала A применим алгоритм 3.3. Алгоритм 3.3. Построение FOLLOW(X) для всех X - нетерминалов грамматики. Шаг 1. Положить FOLLOW(X)={}. Шаг 2. Поместить $ в FOLLOW(S), где S - начальный символ и $ - правый концевой маркер. Шаг 3. Если eсть правило вывода A->uBv, то все из FIRST(v), за исключением e, добавить к FOLLOW(B). Шаг 4. Пока ничего нельзя будет добавить ни к какому множеству FOLLOW(X): eсли есть правило вывода A->uB или A->uBv, где FIRST(v) содержит e (т.е. v=>*e), то все из FOLLOW(A) добавить к FOLLOW(B). -------------------------------------------------------------- 5. Конструирование таблиц предсказывающего анализатора.<4> Для конструирования таблиц предсказывающего анализатора по грамматике G может быть использован алгоритм, основанный на следующей идее. Предположим, что A->u - правило вывода грамматики и a<-FIRST(u). Тогда анализатор делает развертку A по u, если входным символом является a. Трудность возникает, когда u=e или u=>*e. В этом случае нужно развернуть A в u, если текущий входной символ принадлежит FOLLOW(A) или если достигнут $ и $<-FOLLOW(A). Алгоритм 3.4. Построение таблиц предсказывающего анализатора. Для каждого правила вывода A->u грамматики выполнить шаги 1 и 2 Шаг 1. Для каждого терминала a из FIRST(u) добавить A->u к M[A,a]. Шаг 2. Если e<-FIRST(u), добавить A->u к M[A,b] для каждого терминала b из FOLLOW(A). Если e<-FIRST(u) и $<- FOLLOW(A), добавить A->u к M[A,$]. Шаг 3. Положить все неопределенные входы равными error. -------------------------------------------------------------- 6. Удаление левой рекурсии Основная трудность при использовании предсказывающего анализа - это написание такой грамматики для входного языка, чтобы по ней можно было построить предсказывающий анализатор. Иногда с помощью некоторых простых преобразований не LL(1)-грамматику можно привести к LL(1)-виду. Среди этих преобразований наиболее очевидными являются левая факторизация и удаление левой рекурсии. Здесь необходимо сделать два замечания. Во- первых, не всякая грамматика после этих преобразований становится LL(1) и, во-вторых, после удаления левой рекурсии и левой факторизации получающаяся грамматика может стать трудно понимаемой. Грамматика леворекурсивна, если в ней имеется нетерминал A такой, что существует вывод A=>+Au для некоторой строки u. Леворекурсивные грамматики не могут анализироваться методами сверху-вниз, поэтому необходимо удаление левой рекурсии. Непосредственную левую рекурсию, т.е. рекурсию вида A->Au, можно удалить следующим способом. Сначала группируем A- правила: A -> Au1 | Au2 | ... | Aum | v1 | v2 | .... | vn где никакая из строк vi не начинается с A. Затем заменяем A- правила на A -> v1A' | v2A' | .... | vnA' A'-> u1A' | u2A' | .... | umA' | e Нетерминал A порождает те же строки, что и раньше, но теперь нет левой рекурсии. С помощью этой процедуры удаляются все непосредственные левые рекурсии, но не удаляется левая рекурсия, включающая два или более шагов. Приведенный ниже алгоритм 3.5 позволяет удалить все левые рекурсии из грамматики. Алгоритм 3.5. Удаление левой рекурсии. Шаг 1. Упорядочиваем нетерминалы в произвольном порядке. Шаг 2. for i:=1 to n do for j:=1 to i-1 do пусть Aj->v1 | v2 | ... | vk - все текущие правила для Aj; заменить все правила вида Ai->Aju на правила Ai->v1u | v2u | ... | vkU; end; удалить непосредственную левую рекурсию в правилах для Ai; end После (i-1)-й итерации внешнего цикла на шаге 2 для любого правила вида Ak->Alu, где kk. В результате на следующей итерации (по i) внутренний цикл (по j) последовательно увеличивает нижнюю границу по m в любом правиле Ai->Amu, пока не будет m>=i. Затем, удаляя непосредственную левую рекурсию для Ai-правил, делаем m больше i. Алгоритм 3.5 применим, если грамматика не имеет циклов (выводов вида A=>+A) и e-правил (правил вида A->e). Как циклы, так и e-правила могут быть удалены предварительно. Получающаяся грамматика без левой рекурсии может иметь e- правила. -------------------------------------------------------------- 7. Левая факторизация Oсновная идея левой факторизации в том, что, когда неясно, какую из двух альтернатив надо использовать для развертки нетерминала A, нужно переделать A-правила так, чтобы отложить решение до тех пор, пока не будет досточно информации, чтобы принять правильное решение. Если A->uv1 | uv2 - два A-правила и входная строка начинается с непустой строки, выводимой из u, мы не знаем, разворачивать ли по uv1 или по uv2. Однако можно отложить решение, развернув A->uA'. Тогда после анализа того, что выводимо из u, можно развернуть A'->v1 или A'->v2. Левофакторизованные правила принимают вид A -> u A' A' -> v1 | v2 Алгоритм 3.6. Левая факторизация грамматики. Для каждого нетерминала A ищем самый длинный префикс u, общий для двух или более его альтернатив. Если u#e, т.е. существует нетривиальный общий префикс, заменяем все A-правила A->uv1 | uv2 | ... | uvn | z, где z - все альтернативы, не начинающиеся с u, на A -> uA' | z A' -> v1 | v2 | ... | vn Здесь A' - новый нетерминал. Повторно применяем это преобразование, пока никакие две альтернативы не будут иметь общего префикса. -------------------------------------------------------------- 8. Рекурсивный спуск Выше был рассмотрен таблично-управляемый вариант предсказывающего анализа, когда магазин явно использовался в процессе работы анализатора. Можно предложить другой вариант предсказывающего анализатра, когда каждому нетерминалу сопоставляется, вообще говоря, рекурсивная процедура и магазин образуется неявно при вызовах этих процедур. Процедуры рекурсивного спуска могут быть записаны, как это изображено на рис. 3.9. В процедуре N для случая, когда имеется альтернатива N->ui->*e (не может быть более одной альтернативы, из которой выводится e!), приведены два варианта 1.1 и 1.2. В варианте 1.1 делается проверка, принадлежит ли следующий входной символ FOLLOW(N). Если нет - выдается ошибка. Во втором варианте этого не делается, так что анализ ошибки откладывается на процедуру, вызвавшую N. procedure N;{N -> u1 | u2 | ... | uk} begin if InSym<-FIRST(ui) {только одному!} then if parse(ui) then exit(N->ui) else error() end else Вариант 1: если имеется правило N->ui =>* e то Вариант 1.1 : if InSym<-FOLLOW(N) then exit(N->e) else error() end; Вариант 1.2: exit(N->e) Вариант 2: нет правила N->ui =>*e error() end end; procedure parse(u); {из u не выводится e!} begin v:=u; while v#e do {v=Xz} if X-терминал a then if InSym<>a then return(false) end else {X-нетерминал B} B; end; v:=z end; return(true) end; -------------------------------------------------------------- 9. Построение канонического мн-ва LR-ситуаций Для конструирования набора множеств допустимых LR(1)- ситуаций будут применяться пополненная грамматика G' и процедуры-функции closure и goto. Рассмотрим ситуацию вида [A->u.Bv,a] из множества ситуаций, допустимых для некоторого активного префикса z. Тогда существует правосторонний вывод S=>*yAax=>yuBvax, где z=yu. Предположим, что из vax выводится терминальная строка bw. Тогда для некоторого правила вывода вида B->q имеется вывод S=>*zBbw=>zqbw. Таким образом [B->.q,b] допустима для z. Здесь либо b может быть первым терминалом, выводимым из v, либо из v выводится e в выводе vax=>*bw и тогда b равно a. Т.е. b принадлежит FIRST(vax). Построение всех таких ситуаций для данного множества ситуаций, т.е. его замыкание, делает процедура closure. Aлгоритм построения множеств LR(1)-ситуаций приведен ниже. Алгоритм 3.8. Конструирование множеств LR(1)-ситуаций. Алгоритм заключается в выполнении главной программы items, которая вызывает процедуры closure и goto. function closure(I);/*I - множество ситуаций*/ begin repeat для каждой ситуации [A->u.Bv,a] из I, каждого правила вывода B->w из G' и каждого терминала b из FIRST(va), такого, что [B->.w,b] нет в I do добавить [B->.w,b] к I; until к I нельзя добавить новых ситуаций; return I; end; В анализаторах типа LR(0) при построении closure не учитываются терминалы из FIRST(va). Если I - множество ситуаций, допустимых для некоторого активного префикса z, то goto(I,X) - множество ситуаций, допустимых для активного префикса zX. function goto(I,X);/*I - множество ситуаций; X - символ грамматики*/ begin Пусть [A->u.Xv,a] принадлежит I; Рассмотрим J - множество ситуаций [A-uX.v,a]; return closure(J) end; Работа алгоритма построения множества LR(1)-ситуаций начинается с того, что берется C - множество ситуаций {closure({[S'->.S,$]})}. Затем из имеющегося множества с помощью операции goto() строятся новые множества ситуаций. По- существу, goto(I,X) - переход конечного автомата из состояния I по символу X. procedure items(G'); begin C:={closure({[S'->.S,$]})}; repeat для каждого множества ситуаций I из C и каждого символа грамматики X такого, что goto(I,X) не пусто и не принадлежит C do добавить goto(I,X) к C until к C нельзя больше добавить множеств ситуаций end; В каждый момент анализа в магазине находится активный префикс, который соответствует последовательности переходов из начального состояния (I0) в текущее. Свертка - это замена суффикса префикса и переход в новое состояние, т.е. как бы возврат по части пути, соответствующей основе, и замена этой части переходом, соответствующим левой части. -------------------------------------------------------------- 10. Алгоритм разбора снизу вверх loop Пусть S - состояние на верхушке магазина; if action[S,InSym]=shift S' then поместить InSym и затем S' на верхушку магазина; прочитать в InSym следующий входной символ else if action[S,InSym]=reduce N->w then удалить из магазина 2*|w| символов; пусть теперь на верхушке магазина состояние S'; поместить на верхушку магазина N, а затем состояние goto[S',InSym]; вывести правило N->w else if action[S,InSym]=accept then return else error() end end end end; -------------------------------------------------------------- 11. Построение канонических таблиц LR анализатора. Шаг1. Строим набор множеств LR(1)- ситуаций C={I0,I1,...,In} для G'. Шаг 2. Состояние i анализатора строится из Ii. Действия анализатора для состояния i определяются следующим образом: а) если [A->u.av,b] принадлежит Ii и goto(Ii,a)=Ij, то полагаем action[i,a]="shift j". Здесь a - терминал; б) если [A->u.,a] принадлежит Ii, A#S', то полагаем action[i,a]="reduce A->u"; в) если [S'->S.,$] принадлежит Ii, полагаем action[i,$]="accept". Шаг 3. Переходы для состояния i определяются следующим образом: если goto(Ii,A)=Ij, то goto[i,A]=j (здесь A - нетерминал). Шаг 4. Все входы, не определенные шагами 2 и 3, полагаем равными "error". Шаг 5. Начальное состояние анализатора строится из множества, содержащего ситуацию [S'->.S,$]. Если при применении этих правил возникает конфликт, т.е. в одном и том же множестве может быть более одного варианта действий (либо сдвиг/свертка, либо свертка/свертка), говорят, что грамматика не является LR(1), и алгоритм завершается неуспешно. Таблица, получающаяся из функций анализатора action и goto в результате работы Алгоритма 3.10, называется канонической таблицей LR(1)-анализатора. LR-анализатор, работающий по этой таблице, называется каноническим LR-анализатором. Если функция анализатора action не содержит неоднозначно определенных входов, то грамматика называется LR(1)-грамматикой. -------------------------------------------------------------- 12. Синтаксически управляемый перевод Схемой синтаксически управляемого перевода (или трансляции, сокращенно: СУ-схемой) называется пятерка Tr=(N,T,П,R,S), где N - конечное множество нетерминальных символов; T - конечный входной алфавит; П - конечный выходной алфавит; R - конечное множество правил перевода вида A->u, A1=v1, A2=v2, ... , Am=vm, удовлетворяющих следующим условиям: - каждый символ, входящий в v1, ..., vm, либо принадлежит П, либо является Bk для B<-N и B входит в v (здесь k - номер вхождения B в v), - если u имеет более одного вхождения символа B, то каждый символ Bk во всех v соотнесен (верхним индексом) с конкретным вхождением B; S - начальный символ, выделенный нетерминал из N. A->u называют входным правилом вывода, Ai - переводом нетерминала A и Ai=vi - элементом перевода, связанным с этим правилом перевода. Если через P обозначить множество входных правил вывода всех правил перевода, то G=(N,T,P,S) будет входной грамматикой для Tr. Если в СУ-схеме Tr нет двух правил перевода с одинаковым входным правилом вывода, то ее называют семантически однозначной. Выход СУ-схемы определим снизу вверх. С каждой внутренней вершиной n дерева разбора (во входной грамматике), помеченной A, свяжем одну цепочку для каждого Ai. Эта цепочка называется значением (или переводом) символа Ai в вершине n. Каждое значение вычисляется подстановкой значений символов перевода данного элемента перевода Ai=vi, определенных в прямых потомках вершины n. Переводом t(Tr), определяемым СУ-схемой Tr, назовем множество {(x,y)|x имеет дерево разбора во входной грамматике для Tr и y - значение выделенного символа перевода S в корне этого дерева}. Если Tr=(N,T,П,R,S) - СУ-схема, то т(Tr) называется синтаксически управляемым переводом (СУ-переводом). Теорема 5.1. Если число вхождений каждого нетерминала в слове v не превосходит 1, то t(Tr) является КС-языком. Обратное не всегда верно [5]. Теорема 5.2. Для каждого магазинного преобразователя существует эквивалентная СУ-схема [5]. Обратное, вообще говоря, не верно. Определение. Семантически однозначная СУ-схема Tr=(N,T,П,R,S) называется простой, если для каждого правила A->u,v из R соответствующие друг другу вхождения нетерминалов встречаются в u и v в одном и том же порядке. Перевод, определяемый простой СУ-схемой, называется простым синтаксически управляемым переводом (простым СУ-переводом). Теорема 5.3. Пусть Tr=(N,T,П,R,S) - простая СУ-схема. Существует такой МП-преобразователь P, что t(P)=t(Tr) [5]. Таким образом, класс трансляций, определяемых магазинными преобразователями, совпадает с классом простых СУ-переводов. Теорема 5.4. Пусть Tr=(N,T,П,R,S) - семантически однозначная простая СУ-схема, входной грамматикой которой служит LL(k)- грамматика. Тогда перевод {x$,y)|(x,y)<-t(Tr)} можно осуществить детерминированным МП-преобразователем [5]. Существуют семантически однозначные простые СУ-схемы, имеющие в качестве входных грамматик LR(k) грамматики и не реализуемые ни на каком ДМП-преобразователе. Определение. Назовем СУ-схему Tr=(N,T,П,R,S) постфиксной, если каждое правило из R имеет вид A->u,v, где v<-N*П*. Иными словами, каждый элемент перевода представляет собой цепочку из нетерминалов, за которыми следует цепочка выходных символов. Теорема 5.5. Пусть Tr=(N,T,П,R,S) - семантически однозначная простая постфиксная СУ-схема, входной грамматикой которой служит LR(k)-грамматика. Тогда перевод {(x$,y)|(x,y)<-t(Tr)} можно осуществить детерминированным МП-преобразователем [5]. -------------------------------------------------------------- 13. Атрибутные грамматики Среди всех формальных методов описания языков программирования атрибутные грамматики получили, по-видимому, наибольшую известность и распространение. Причиной этого является то, что формализм атрибутных грамматик основывается на дереве разбора программы в КС-грамматике, что сближает его с хорошо разработанной теорией и практикой построения трансляторов. 5.3.1. Определение атрибутных грамматик Пусть G - КС-грамматика: G=(T,N,P,Z), где T, N, P, Z, - соответственно, множество терминальных символов, нетерминальных символов, множество правил вывода и аксиома грамматики. Правила вывода КС-грамматики будем записывать в виде p: X0 -> X1 ... Xn

и будем предполагать, что G - редуцированная КС-грамматика, т.е. в ней нет нетерминальных символов, для которых не существует полного дерева вывода , в которое входит этот нетерминал. С каждым символом X <- N U T свяжем множество A(X) атрибутов символа X.Некоторые из множеств A(x) могут быть пусты. Запись a(X) означает, что a <- A(X). С каждым правилом вывода p <- P свяжем множество F семантических правил, имеющих следующую форму: a0 = fpa0(a1, ... , aj), где ik <- [0,np] - номер символа правила p, а ak - атрибут символа Xik , т.е. ak <- A(Xik). В таком случае будем говорить , что a0 "зависит" от a1,...,aj или что a0 "вычисляется по" a1,...,aj. В частном случае j может быть равно нулю, тогда будем говорить, что атрибут a0 "получает в качестве значения константу". КС-грамматику, каждому символу которой сопоставлено множество атрибутов, а каждому правилу вывода - множество семантических правил, будем называть атрибутной грамматикой (AG). Назовем атрибут a(X0) синтезируемым, если одному из правил вывода p: X0 ->X1 ... Xnp сопоставлено семантическое правило a<0>=fa<0>(...). Назовем атрибут a(Xi) наследуемым, если одному из правил вывода p:X0 -> X1 ... Xi ... Xnp сопоставлено семантическое правило a=fa(...), i <- [1,np]. Множество синтезируемых атрибутов символа X обозначим через S(X), наследуемых атрибутов - через I(X). Будем считать, что значение атрибутов терминальных символов - константы, т.е. их значения определены, но для них нет семантических правил, определеяющих их значения. 5.3.2. Атрибутированное дерево разбора Если дана атрибутная грамматика AG и цепочка, принадлежащая языку, определяемому G, то можно построить дерево разбора этой цепочки в грамматике G. В этом дереве каждая вершина помечена символом грамматики G. Припишем теперь каждой вершине множество атрибутов, сопоставленных символу, которым помечена эта вершина. Атрибуты, сопоставленные вхождениям символов в дерево разбора, будем называть вхождениями атрибутов в дерево разбора, а дерево с сопоставленными каждой вершине атрибутами - атрибутированным деревом разбора. Между вхождениями атрибутов в дерево разбора существуют зависимости, определяемые семантическими правилами, соответствующими примененным синтаксическим правилам. 5.3.3. Язык описания атрибутных грамматик Формализм атрибутных грамматик оказался очень удобным средством для описания семантики языков программирования. Вместе с тем выяснилось, что реализация вычислителей для атрибутных грамматик общего вида сталкивается с большими трудностями. В связи с этим было сделано множество попыток рассматривать те или иные классы атрибутных грамматик, обладающих "хорошими" свойствами. К числу таких свойств относятся прежде всего простота алгоритма проверки атрибутной грамматики на зацикленность и простота алгоритма вычисления атрибутов для атрибутных грамматик данного класса []. Атрибутные грамматики использовались для описания семантики языков программирования и было создано несколько систем автоматизации разработки трансляторов, основанных на формализме атрибутных грамматик. Опыт их использования показал, что "чистый" атрибутный формализм может быть успешно применен для описания семантики языка, но его использование вызывает трудности при создании транслятора. Эти трудности связаны как с самим формализмом, так и с некоторыми технологическими проблемами. К трудностям первого рода можно отнести несоответствие чисто функциональной природы атрибутного вычислителя и связанной с ней неупорядоченностью процесса вычисления атрибутов (что в значительной степени является преимуществом этого формализма) и упорядоченностью элементов программы. Это несоответствие ведет к тому, что приходится идти на искусственные приемы для их сочетания. Технологические трудности связаны с эффективностью трансляторов, генерированных с помощью атрибутных систем. Как правило, качество таких трансляторов довольно низко из-за больших расходов памяти, неэффективности искусственных приемов, о которых было сказано выше. Учитывая это, мы будем вести дальнейшее изложение на языке, сочетающем особенности атрибутного формализма и обычного языка, в котором предполагается возможность управления порядком исполнения операторов. Этот порядок привязывается к обходу атрибутированного дерева разбора сверху вниз слева направо. Все атрибуты должны быть вычислены за один такой обход. Атрибутные грамматики, обладающие таким свойством, называются L-атрибутными. При записи синтаксиса мы будем использовать расширенную БНФ. Элемент правой части синтаксического правила, заключенный в скобки [ ], может отсутствовать. Элемент правой части синтаксического правила, заключенный в скобки ( ), означает возможность повторения один или более раз. Элемент правой части синтаксического правила, заключенный в скобки [()], означает возможность повторения ноль или более раз. В скобках [] или [()] может указываться разделитель конструкций. Ниже дан синтаксис языка описания атрибутных грамматик. Атрибутная грамматика ::= 'ALPHABET' ( ОписаниеНетерминала ) ( Правило ) ОписаниеНетерминала ::= ИмяНетерминала '::' [( ОписаниеАтрибутов / ';')] '.' ОписаниеАтрибутов ::= ( ИмяАтрибута / ',') ':' Тип Правило ::= 'RULE' Синтаксис 'SEMANTICS' Семантика '.' Синтаксис ::= ИмяНетерминала '::=' ПраваяЧасть ПраваяЧасть ::= [( ЭлементовПравойЧасти )] ЭлементПравойЧасти ::= ИмяНетерминала | Терминал | '(' Нетерминал [ '/' Терминал ] ')' | '[' Нетерминал ']' | '[(' Нетерминал [ '/' Терминал ] ')]' Семантика ::= [( ЛокальноеОбъявление ]) [( СемантическоеДействие ]) СемантическоеДействие ::= Присваивание | [ Метка ] Оператор Присваивание ::= Переменная ':=' Выражение Переменная ::= ЛокальнаяПеременная | Атрибут Атрибут ::= ЛокальныйАтрибут | ГлобальныйАтрибут ЛокальныйАтрибут ::= ИмяАтрибута '<' Номер '>' ГлобальныйАтрибут ::= ИмяАтрибута '<' Нетерминал '>' Метка ::= Целое ':' | Целое 'Е' ':' | Целое 'А' ':' Оператор ::= Условный | ОператорПроцедуры | ЦиклПоМножеству | ПростойЦикл | ЦиклСУсловиемОкончания Описание атрибутной грамматики состоит из раздела описания атрибутов и раздела правил. Раздел описания атрибутов определяет состав атрибутов для каждого символа грамматики и тип каждого атрибута. Правила состоят из синтаксической и семантической части. В синтаксической части используется расширенная БНФ. Семантическая часть правила состоит из локальных объявлений и семантических действий. В качестве семантических действий допускаются как атрибутные присваивания, так и составные операторы. Метка в семантической части правила привязывает выполнение оператора к обходу дерева разбора сверху-вниз слева направо. Конструкция "i : оператор" означает, что оператор должен быть выполнен сразу после обхода i-й компоненты правой части. Конструкция "i E : оператор" означает, что оператор должен быть выполнен, только если порождение i-й компоненты правой части пусто. Конструкция "i A : оператор" означает, что оператор должен быть выполнен после разбора каждого повторения i-й компоненты правой части (имеется в виду конструкция повторения). Каждое правило может иметь локальные определения (типов и переменных). В формулах используются как атрибуты символов данного правила (локальные атрибуты) и в этом случае соответствующие символы указываются номерами в правиле (0 для символа левой части, 1 для символа правой части и т.д.), так и атрибуты символов предков левой части правила (глобальные атрибуты). В этом случае соответствующий символ указывается именем нетерминала. Таким образом, на дереве образуются области видимости атрибутов: атрибут символа имеет область видимости, состоящую из правила, в которое символ входит в правую часть, плюс все поддерево, корнем которого является символ, за исключением поддеревьев - потомков того же символа в этом поддереве (рис. 5.4). | ... . N . . / \ . . / \ . . /\ /\ . . / /\ /\ \ . . / -- -- \ . ...N...........N... /\ /\ -- -- Рис. 5.4 Значение терминального символа доступно через атрибут VAL соответствующего типа. -------------------------------------------------------------- 14. Занесение в среду и поиск объектов Поскольку блоки образуют иерархию на дереве разбора программы, при поиске объекта мы можем с помощью атрибута типа "указатель на блок" переходить от блока к охватывающему блоку. Если теперь у каждого блока есть атрибут, указывающий, является ли блок процедурой или модулем, то легко реализовать сочетание блочной структуры со средствами управления видимостью. Кроме того, корень дерева имеет атрибут, соответствующий предопределенной компоненте, так что через этот глобальный атрибут доступны все предопределенные описания (рис. 6.4). Env ^ ^ / \ Env Env ^^ ^^ / \ / \ Env Env Env Env Рис. 6.4 В качестве типов данных атрибутов мы будем использовать множество. Множество может быть упорядоченным или неупорядоченным, ключевым или простым. Элементом ключевого множества может быть запись, одним из полей которой является ключ: SET OF T - простое неупорядоченное множество объектов типа T; KEY K SET OF T - ключевое неупорядоченное множество объектов типа T с ключом K; LIST OF T - простое упорядоченное множество объектов типа T; KEY K LIST OF T - ключевое упорядоченное множество объектов типа T с ключом K; Над объектами типа множества определены следующие операции: Init(S) - создать и проинициализировать переменную S; Include(V,S) - включить объект V в множество S; если множество упорядоченное, то включение осуществляется в качестве последнего элемента; Find(K,S) - выдать указатель на объект с ключом K во множестве S и NIL, если объект с таким ключом не найден. Имеется специальный оператор цикла, пробегающий элементы множества: for V in S do Оператор; Переменная V локализована в теле оператора и пробегает все значения множества. Если множество упорядочено, то элементы пробегаются в этом порядке, если нет - в произвольном порядке. Среда представляет собой ключевое множество с ключом - именем объекта. Каждый локальный модуль имеет атрибут - множество импортируемых объектов и атрибут - множество экспортируемых объектов. Экспортируемые модулем объекты в соответствии с правилами экспорта включаются в компоненту среды, в которую входит сам модуль. -------------------------------------------------------------- 15. Функции расстановки. Много внимания было уделено тому, какой должна быть функция расстановки. Основные требования к ней очевидны: она должна легко вычисляться и распределять равномерно. Один из возможных подходов заключается в следующем. 1. По символам строки s определяем положительное целое H. Преобразование одиночных символов в целые обычно можно сделать средствами языка реализации. В Паскале для этого служит функция ord, в Си при выполнении арифметических операций символьные значения трактуются как целые. 2. Преобразуем H, вычисленное выше, в номер списка, т.е. целое между 0 и m-1, где m - размер таблицы расстановки, например, взятием остатка при делении H на m. Функции расстановки, учитывающие все символы строки, распределяют лучше, чем функции, учитывающие только несколько символов, например в конце или середине строки. Но такие функции требуют больше вычислений. Простейший способ вычисления H - сложение кодов символов строки. Перед сложением с очередным символом можно умножить старое значение H на константу q. Т.е. полагаем H0=0, Hi=q*Hi- 1+ci для 1<=i<=k, k - длина строки. При q=1 получаем простое сложение символов. Вместо сложения можно выполнять сложение ci и q*Hi-1 по модулю 2. Переполнение при выполнении арифметических операций можно игнорировать. Функция Hashpjw, приведенная ниже [1], вычисляется, начиная с H=0. Для каждого символа c сдвигаем биты H на 4 позиции влево и добавляем c. Если какой-нибудь из четырех старших бит H равен 1, сдвигаем эти 4 бита на 24 разряда вправо, затем складываем по модулю 2 с H и устанавливаем в 0 каждый из четырех старших бит, равных 1. -------------------------------------------------------------- 16. Таблицы на деревьях Рассмотрим еще один способ организации таблиц с использованием двоичных деревьев. Будем считать, что на множестве идентификаторов задан некоторый линейный порядок (например, лексикографический), т.е. задано некоторое отношение '<', транзитивное, антисимметричное и антирефлексивное. Каждой вершине двоичного дерева, представляющего таблицу символов, сопоставлен идентификатор. Вершина может иметь нуль, одного (правого или левого) или двух (правого и левого) потомков. Если вершина имеет левого потомка, то идентификатор, сопоставленный левому потомку, меньше идентификатора, сопоставленного самой вершине; если имеет правого потомка, то ее идентификатор больше. Элемент таблицы изображен на рис. 7.6. +---------------+ TP --->| | | -+--->Ident +-/----\--------+ / \ v v Left Right Рис. 7.6 Поиск в такой таблице может быть описан следующей процедурой: function SearchTree(Id,TP):Pointer; begin if Id=TP^.Ident then return(TP) elsif IdTP^Ident then return(Search_tree(Id,TP^.Right)) else return(nil) end end; Занесение в таблицу осуществляется процедурой function Insert_tree(Id,TP):Pointer; function fill(var P):Pointer; begin if P=nil then P:=new(Element); P^.Ident:=include(Id); P^.Left:=nil; P^.Right:=nil; return(P); else return(Insert_tree(Id,P)) end end; begin if Id=TP^.Ident then return(TP) elsif Id| Предыдущий BP |-----+ v +-----------------+ ................. Максимальный адрес Рис. 8.3 Итак, в случае статической цепочки магазин организован, как это изображено на рис. 8.3. Таким образом, на запись текущей процедуры в магазине указывает регистр BP (Base pointer), с которого начинается динамическая цепочка. На статическую цепочку указывает регистр LP (Link Pointer). В качестве регистров BP и LP в различных системах команд могут использоваться универсальные, адресные или специальные регистры. Локальные переменные отсчитываются от регистра BP вверх, фактические параметры - вниз с учетом памяти, занятой точкой возврата и самим сохраненным регистром BP. Вызов подпрограмм различного уровня производится несколько по-разному. При вызове подпрограммы того же статического уровня, что и вызывающая подпрограмма, выполняются следующие команды: Занесение фактических параметров в магазин JSR A Команда JSR A продвигает указатель SP, заносит PC на верхушку магазина и осуществляет переход по адресу A. После выполнения этих команд состояние магазина становится таким, как это изображено на рис. 8.4. Занесение BP, отведение локальных, сохранение регистров делает вызываемая подпрограмма. +---------------+ |Точка возврата |<---SP |---------------| |Факт. параметры| |+---------------+--| |Сохраненные | |регистры | |---------------| LP +--|Предыдущий LP |<------- | |---------------| Предыдущий | |Локальные | статический| | | уровень | |---------------| BP | |Предыдущий BP |<---- v |---------------| |...............| Рис. 8.4 При вызове локальной подпрограммы необходимо установить указатель статического уровня на текущую подпрограмму, а при выходе - восстановить его на старое значение (охватывающей текущую). Для этого исполняются следующие команды: Занесение фактических в магазин MOVE BP,LP SUB Delta,LP JSR A Здесь Delta - размер локальных вызываемой подпрограммы плюс двойная длина слова. Магазин после этого принимает состояние, изображенное на рис. 8.5. +------------------+ | Точка возврата | |------------------| | Факт. параметры | |--+------------------+--| | Сохраненные | | регистры | |------------------| LP +---| Предыдущий LP |<---+ | |------------------| D | Предыдущий | | | e | статический | | Локальные | l | уровень | | | t | | |------------------| a | | | Предыдущий BP |<---+ v |------------------| | ................ | Рис. 8.5 После выхода из подпрограммы в вызывающей подпрограмме выполняется команда MOVE -Delta(BP),LP которая восстанавливает старое значение статической цепочки. Если выход осуществлялся из подпрограммы 1-го уровня, эту команду выполнять не надо, поскольку для 1-го уровня нет статической цепочки. При вызове подпрограммы меньшего, чем вызывающая, уровня выполняются следующие команды: Занесение фактических параметров в магазин MOVE (LP),LP /*столько раз, какова разность уровней вызывающей и вызываемой ПП*/ JSR A Тем самым устанавливается статический уровень вызываемой подпрограммы. После выхода из подпрограммы выполняется команда MOVE -Delta(BP),LP восстанавиливающая статический уровень вызывающей подпрограммы. Тело подпрограммы начинается со следующих команд: LINK BP,-размер локальных MOVEM -(SP) Команда LINK BP,размер локальных эквивалентна трем командам: MOVE BP,-(SP) MOVE SP,BP ADD -размер локальных,SP Команда MOVEM сохраняет в магазине регистры. В результате выполнения этих команд магазин приобретает вид, изображенный на рис. 8.3. Выход из подпрограммы осуществляется следующей последовательностью команд: MOVEM (SP)+,D0-D7,A0-A7 UNLK BP RTD размер фактических Команда MOVEM восстанавливает регистры из магазина. После ее выполнения магазин выглядит, как это изображено на рис. 8.6. +-----------------+<--SP Текущий | Локальные | уровень |-----------------| | Предыдущий BP |<--BP |-----------------| +------------------+ | Точка возврата | | Точка возврата |<---SP |-----------------| |------------------| | Факт. параметры | | Факт. параметры | |-----------------------| +------------------+ ................. .................. Рис. 8.6 Рис. 8.7 После выполнения команды UNLK BP, которая эквивалентна такой последовательности команд: MOVE BP,SP MOVE (SP),BP ADD #4,BP /*4 - размер слова*/ магазин имеет содержимое, изображенное на рис. 8.7. Наконец, после выполнения команды RTD размер_фактических, которая эквивалентна последовательности ADD размер_фактических, SP JMP -размер_фактических(SP) магазин восстанавливается до состояния, которое было до вызова. В зависимости от наличия локальных переменных, фактических параметров и необходимости упрятывания регистров каждая из этих команд может отсутствовать. Организация магазина с дисплеем Рассмотрим теперь организацию магазина с дисплеем. Дисплей - это массив (DISPLAY) фиксированного размера, определяющего ограничение на число статических уровней вложенности процедур. i-й элемент этого массива представляет собой указатель на область активации процедуры i-го статического уровня. Доступ к переменным самой внутренней процедуры осуществляется через регистр BP. При вызове процедуры меньшего статического уровня изменений в дисплее не производится. При вызове локальной процедуры в дисплее отводится элемент для текущей (вызывающей) процедуры. При вызове процедуры того же уровня (i) i-й элемент замещается на указатель области активации текущей процедуры и при выходе восстанавливается. Тем самым DISPLAY[i] всегда указывает на область активации последней вызванной процедуры i-го статического уровня. Минимальный адрес <------+ | Сохраненные | | Область | регистры | | последней |------------------| | вызванной Текущий | Локальные | | процедуры статический |------------------| | уровень +--| Предыдущий BP |<-- BP <-+ | |------------------| | | | | Точка возврата | | | | |------------------| | | | | Факт. параметры | | | | |------------------|<------+ | DISPLAY[i] | | Сохраненные | | ---------+ | | регистры | +------* | | |------------------| ---------+ | | предыдущий | | | DISPLAY[i] | | |------------------| Предыдущий | | Локальные | статический | | | уровень | |------------------| +->| Предыдущий BP | |------------------| |..................| Рис. 8.8 Запоминание и восстановление DISPLAY[i] можно не выполнять, если процедура не имеет локальных переменных и параметров или если из процедуры нет вызовов описанных в ней процедур. Структура магазина при использовании дисплея изображена на рис. 8.8. Дисплей может быть реализован либо через регистры (если их достаточно), либо через массив в памяти. |----------------------|<-------------------------+ | Локальные | Область активации | |----------------| текущей процедуры | | Регистры | | |----------------| BP | +-----| Предыдущий BP |<----- | | |----------------| BP предыдущего статического | | | x---+---------> уровня | | | Дисплей .......| BP 1-го статического уровня | | | x---+---------> | | |----------------| | | | Точка возврата | | | |----------------| | | | Фактические | | | |--+----------------+--|<-------------------------+ | | Локальные | | |----------------| | | Регистры | | |----------------| +---->| Предыдущий BP | |----------------| | Дисплей | |----------------| | Точка возврата | |----------------| |--+ Фактические +--| Рис. 8.9. Иногда используется комбинированная схема - дисплей в магазине (рис 8.9). Дисплей хранится в магазине. При вызове процедуры текущего статического уровня он просто копируется в новую область активации. При вызове процедуры более глубокого статического уровня в дисплей добавляется указатель BP вызывающей процедуры. Отдельного рассмотрения требует вопрос о технике передачи фактических параметров. Конечно, в случае простых параметров (например, чисел) проблем не возникает. Однако передача массивов по значению - операция довольно дорогая, поэтому с точки зрения экономии памяти целесообразнее сначала в подпрограмму передать адрес массива, а затем уже из подпрограммы по адресу передать в магазин сам массив. В связи с передачей параметров следует упомянуть еще одно обстоятельство. Рассмотренная схема организации магазина допустима только для языков со статически известными размерами фактических параметров. Однако, например, в языке Модула-2 по значению может быть передан гибкий массив, и в этом случае нельзя статически распределить память для параметров. Обычно в таких случаях заводят так называемый "паспорт" массива, в котором хранится вся необходимая информация, а сам массив размещается в магазине в рабочей области выше сохраненных регистров. -------------------------------------------------------------- 18. Распределение регистров при вычислении арифметических выражений Одной из важнейших задач при генерации кода является распределение регистров. Рассмотрим хорошо известную технику распределения регистров при трансляции арифметических выражений, называемую алгоритмом Сети-Ульмана. Пусть система команд машины имеет неограниченное число универсальных регистров, в которых выполняются арифметические команды. Рассмотрим, как можно сгенерировать код, используя для данного арифметического выражения минимальное число регистров. | / \ R1 /\ \ -- /\ R2 /\ \ -- /\ Rn /\ \ -- \ /\LR L/\/\R ---- Рис. 8.13 Предположим сначала, что распределение регистров осуществляется по простейшей схеме слева-направо, как изображено на рис. 8.13. Тогда к моменту генерации кода для поддерева LR занято n регистров. Пусть поддерево L требует nl регистров, а поддерево R - nr регистров. Если nl=nr, то при вычислении L будет использовано nl регистров и под результат будет занят n+1-й регистр. Еще nr (=nl) регистров будет использовано при вычислении R. Таким образом, общее число использованных регистров будет равно n+nl+1. Если nl>nr, то при вычислении L будет использовано nl регистров. При вычислении R будет использовано nr=lr Рис. 8.14 Рис. 8.15 2) если вершина имеет прямых потомков с метками l1 и l2, то в качестве метки этой вершины выбираем большее из чисел l1 или l2 либо число l1+1, если l1=l2. Эта разметка позволяет определить, какое из поддеревьев требует большего количества регистров для своего вычисления. Затем осуществляется распределение регистров для результатов операций. Правила распределения регистров: 1) Корню назначается первый регистр. 2) Если метка левого потомка меньше метки правого, то левому потомку назначается регистр на единицу больший, чем предку, а правому - с тем же номером (сначала вычисляется правое поддерево и его результат помещается в регистр R). Если же метка левого потомка больше или равна метке правого потомка, то наоборот, сначала вычисляется левое поддерево и его результат помещается в регистр R (рис. 8.15). После этого формируется код по следующим правилам. Правила генерации кода: 1) если вершина - правый лист с меткой 1, то ей соответствует код LOAD X,R, где R - регистр, назначенный этой вершине, а X - адрес переменной, связанной с вершиной (рис. 8.16.б); 2) если вершина внутренняя и ее левый потомок - лист с меткой 0, то ей соответствует код Код правого поддерева Op X,R где снова R - регистр, назначенный этой вершине, X - адрес переменной, связанной с вершиной, а Op - операция, примененная в вершине (рис. 8.16.а); 3) если непосредственные потомки вершины не листья и метка правой вершины больше метки левой, то вершине соответствует код Код правого поддерева Код левого поддерева Op R+1,R где R - регистр, назначенный внутренней вершине, и операция Op, вообще говоря, не коммутативная (рис. 8.17 б)). R R R R | | | | / \ / \ / \ / \ / \R R / \ R/ \R+1 R+1/ \R X /\ /\ X /\ /\ /\ /\ (0) -- -- (1) -- -- -- -- а) б) а) б) Рис. 8.16 Рис. 8.17 Если метка правой вершины меньше или равна метке левой вершины, то вершине соответствует код Код левого поддерева Код правого поддерева Op R,R+1 MOVE R+1,R Последняя команда генерируется для того, чтобы получить результат в нужном регистре (в случае коммутативной операции операнды операции можно поменять местами и избежать дополнительной пересылки)(рис. 8.17 а)). Команды пересылки требуются для согласования номеров регистров, в которых осуществляется выполнение операции, с регистрами, в которых должен быть выдан результат. Это имеет смысл, когда эти регистры разные. Получиться это может из-за того, что по приведенной схеме результат выполнения операции всегда находится в регистре с номером метки, а метки левого и правого поддеревьев могут совпадать. В приведенных атрибутных схемах предполагалось, что регистров достаточно, чтобы правильно странслировать любое выражение. Если это не так, приходится усложнять схему трансляции и при необходимости сбрасывать содержимое регистров в память (или магазин). -------------------------------------------------------------- 19. Трансляция логических выражений Логические выражения, включающие логическое умножение, логическое сложение и отрицание, можно вычислять как непосредственно, используя таблицы истинности, так и с помощью условных выражений, пользуясь очевидными правилами: A & B эквивалентно if A then B else False, A v B эквивалентно if A then True else B. Если в качестве компонент выражений могут входить функции с побочным эффектом, то, вообще говоря, результат вычисления может зависеть от способа вычисления. В некоторых языках программирования не оговаривается, каким способом должны вычисляться логические выражения (например, в Паскале), в некоторых требуется, чтобы вычисления производились тем или иным способом (например, в Модуле-2 требуется, чтобы выражения вычислялись по приведенным формулам), в некоторых языках есть возможность явно задать способ вычисления (Си, Ада). Вычисление логических выражений непосредственно по таблицам истинности аналогично вычислению арифметических выражений, поэтому мы не будем их рассматривать отдельно. Рассмотрим подробнее способ вычисления с помощью приведенных выше формул (будем называть его "вычисления с условными переходами"). Иногда такой способ рассматривают как оптимизацию вычисления логических выражений. Утверждение 1. Для каждого набора входных данных любого логического выражения программа, полученная в результате обхода дерева этого выражения, завершается со значением логического выражения в обычной интерпретации, т.е. осуществляется переход на True для значения, равного T, и переход на метку False для значения F. Это утверждение является частным случаем следующего. Утверждение 2. В результате интерпретации поддерева с некоторыми значениями атрибутов FalseLab и TrueLab в его корне выполняется команда GOTO TrueLab, если значение выражения истинно, и команда GOTO FalseLab, если значение выражения ложно. Доказательство можно провести индукцией по высоте дерева. Для деревьев высоты 1, соответствующих правилам BoolExpr ::= F и BoolExpr ::= T, утверждение очевидно из правил грамматики. Пусть дерево имеет высоту n>1. Зависимость атрибутов для дизъюнкции и конъюнкции приведена на рис. 8.23 | FalseLab0 | TrueLab0 / \ / & \ FalseLab1=FalseLab0 / \ FalseLab2=FalseLab0 TrueLab1=NodeLab2 / \ TrueLab2=TruLab0 /\ /\ / \ / \ ---- ---- 147 | FalseLab0 | TrueLab0 / \ / V \ FalseLab1=NodeLab2 / \ FalseLab2=FalseLab0 TrueLab1=TruLab0 / \ TrueLab2=TruLab0 /\ /\ / \ / \ ---- ---- Рис. 8.23 Если для конъюнкции значение левого поддерева ложно и по индукции вычисление левого поддерева завершается командой GOTO FalseLab1, то и интерпретация всего дерева завершается командой GOTO FalseLab0 (=FalseLab1). Если значение левого поддерева истинно, то его интерпретация завершается командой GOTO TrueLab1 (=NodeLab2). Если значение правого поддерева ложно, то интерпретация всего дерева завершается командой GOTO FalseLab0 (=FalseLab2). Если же оно истинно, интерпретация всего дерева завершается командой GOTO TrueLab0 (=TrueLab2). Аналогично - для дизъюнкции. Доказательство утверждения 1 следует из того, что метками вершины дерева логического выражения являются TrueLab=True и FalseLab=False. Утверждение 4. В каждой терминальной вершине, метка ближайшего правого для нее поддерева равна значению атрибута FalseLab этой вершины, тогда и только тогда, когда значение атрибута Sign этой вершины равно true, и наоборот, метка ближайшего правого для нее поддерева равна значению атрибута TrueLab этой вершины, тогда и только тогда, когда значение атрибута Sign равно false.