Классическая теория компиляторов
 Скачать 1.25 Mb.
|
|
АЛГОРИТМ ДЕЙКСТРЫ Алгоритм Дейкстры представляет собой менее формализованный вариант метода операторных грамматик. Он интересен нам прежде всего с исторической точки зрения. Пусть имеется следующая грамматика инфиксных арифметических выражений: E E + T | E – T E T T T * F | T / F T F F F ^ P F P P (E) P a Каждой операции ставится в соответствие некоторый приоритет, а именно: +, - 2 *, / 3 ^ 4 Эти приоритеты отражают старшинство операций умножения и деления по сравнению со сложением и вычитанием и старшинство возведения в степень по сравнению со всеми остальными операциями. Алгоритм преобразования основан на использовании стека и состоит в следующем: 53 1. Проверяется очередной символ во входной строке. 2. Если это операнд, то он передается в выходную строку. 3. Если это открывающая скобка, то она заносится в стек с приоритетом нуль. 4. Если это операция, то ее приоритет сравнивается с приоритетом операции, находящейся на вершине стека. Если приоритет новой операции больше, то эта новая операция заносится в стек. В противном случае берется операция с вершины стека и помещается в выходную строку, после этого повторяется сравнение с новыми верхними элементами стека до тех пор, пока на вершине стека не окажется операция с приоритетом, меньшим, чем у текущей операции, или пока стек не станет пустым. После этого текущая операция заносится в стек. 5. Если текущий символ во входной строке является закрывающей скобкой, то операции из стека последовательно переносятся в выходную строку до тех пор, пока на вершине стека не появится открывающая скобка; эта открывающая скобка отбрасывается. 6. Если выражение закончилось, то из стека последовательно переносятся в выходную строку все оставшиеся в нем операции. МАТРИЦЫ ПЕРЕХОДОВ Перейдем теперь от анализа арифметических выражений к более сложным объектам – программам. Пусть у нас есть язык, включающий в себя оператор присваивания, а также условный и циклический операторы. Грамматика такого языка в самом упрощенном виде может выглядеть так: прогр ::= инстр инстр ::= инстр; инстр инстр ::= перем := выр инстр ::= if выр then инстр else инстр end инстр ::= while выр do инстр end выр ::= выр перем | перем перем ::= i Тогда мы сможем писать программы наподобие следующей: d := 10; a := b+c-d; if a then d := 1 else while d do e := e-1 end end 54 Как видно, этот язык, несмотря на свою простоту, позволяет создавать весьма нетривиальные условные и циклические конструкции. Описанные выше способы анализа предложений КС-языков имеют существенный недостаток, связанный с необходимостью реализации процедуры поиска правил или просмотра таблицы для выбора нужной редукции. Далее мы рассмотрим еще один метод анализа подобного рода языков. Это – весьма старый метод, разработанный еще на заре становления теории компиляторов, однако он хорошо зарекомендовал себя и используется в практически неизменном виде и поныне. Этот метод основан на использовании т.н. таблицы решений или матрицы переходов. Для наглядности рассмотрим еще более упрощенный вариант грамматики нашего языка: <прог> ::= <инстр> <инстр> ::= IF <выр> THEN <инстр> <инстр> ::= <перем> := <выр> <выр> ::= <выр> + <перем> | <перем> <перем> ::= i Для реализации матрицы переходов нам, как всегда, понадобится стек, переменная, хранящая текущий считываемый символ, и переменная, в которой будет храниться значение последней приведенной формы. Стек необходим нам для хранения правых частей грамматики, заканчивающихся терминалом. Эта часть называется головой правила. Строки матрицы переходов соответствуют тем головам правых частей правил, которые могут появиться в стеке, а столбцы соотносятся с терминальными символами, включая и ограничитель предложений #. Элементами матрицы будут номера или адреса подпрограмм. # IF THEN := + i # 5 1 0 6 0 1 IF 0 0 9 0 3 1 IF <выр> THEN 7 1 0 6 0 1 <перем> := 8 0 0 0 3 1 <выр> + 4 0 4 0 4 1 i 2 0 2 2 2 0 Итак, распознаватель использует стек S, переменную R, принимающую значение текущего считываемого символа, а также переменную U, которая либо пуста, либо содержит тот символ, к которому была приведена последняя 55 первичная фраза (иными словами, значением переменной является последняя разобранная синтаксическая категория). Структура стека несколько отличается от предыдущих: элементами стека являются не отдельные символы, а цепочки символов – головы правых частей правил. Например, последовательность # IF <выр> THEN IF <выр> THEN <перем> := в стеке будет представлена следующим образом: <перем> := IF <выр> THEN IF <выр> THEN # Итак, в стеке хранятся те последовательности символов, которые должны редуцироваться одновременно. Распознаватель работает следующим образом. На каждом шаге работы верхний элемент стека соответствует некоторой строке матрицы. По входному терминальному символу (это – столбец) определяется элемент матрицы, являющийся номером подпрограммы, которую нужно выполнить. Эта подпрограмма произведет необходимую редукцию или занесет R в стек и будет сканировать следующий исходный символ. При написании подпрограмм будем считать, что функция PUSH(R) помещает в стек символ R, функция SCAN() помещает очередной символ из входной цепочки в R, а функция POP() просто извлекает из стека верхний символ (предполагается, что он нам уже не нужен). Схема рассуждений при формировании подпрограмм выглядит так (рассмотрим, для примера, подпрограмму 9): сначала мы выписываем содержимое верхнего элемента стека (для нашей подпрограммы это будет IF). Далее записываем значение считанного терминала (это THEN) и смотрим, что может находиться между ними (т.е. какая синтаксическая категория U): …IF U THEN… Судя по всему, U должно быть равно <выр>. Значит, первая процедура нашей подпрограммы – это проверка вида if U <выр> then error() Затем смотрим, не получилось ли у нас разобранной синтаксической категории. Ничего путного пока у нас не вышло, поэтому присвоим переменной U пустое значение (U := ''), а в стек занесем полученную голову правила (PUSH('IF <выр> THEN')). Далее надо будет считать следующий входной символ. Итак, подпрограмма номер 9 будет выглядеть так: 9: IF U '<выр>' AND U '<перем>' THEN ERROR(); PUSH('IF <выр> THEN') 56 U := ''; SCAN(). Еще пример. В самом начале в стеке находится символ # и U пусто. В соответствии с нашей грамматикой входным символом должен быть либо IF, либо i. Поскольку с них начинаются правые части, необходимо занести их в стек и продолжить работу. Тогда первой подпрограммой будет такая: 1: IF U '' THEN ERROR(); PUSH(R); SCAN(). Предположим, что i – верхний элемент стека. Определим теперь, какие символы из тех, которые могут оказаться в R, считаются допустимыми. За i могут следовать символы: #, THEN, := или +. В любом из этих случаев необходимо заменить i на <перем>, т.е. выполнить редукцию ...<перем>... => ...i... В подпрограмме 2 именно это и делается: 2: IF U '' THEN ERROR(); POP(); U := '<перем>' Итак, каждый элемент матрицы является номером подпрограммы, которая либо заносит входной символ в стек, либо выполняет редукцию. Приведем все подпрограммы, соответствующие нашей матрице переходов: (1) IF U '' THEN ERROR(1); PUSH(R); SCAN(). (2) IF U '' THEN ERROR(2); POP(); U := '<перем>'. (3) IF U '<выр>' AND U '<перем>' THEN ERROR(3); PUSH('<выр>+') U := ''; SCAN(). (4) IF U '<перем>' THEN ERROR(4); POP(); U := '<выр>'. (5) IF U '<прог>' AND U '<инстр>' THEN ERROR(5); STOP(). (6) IF U '<перем>' THEN ERROR(6); PUSH('<перем>:=') U := ''; SCAN(). (7) IF U '<инстр>' THEN ERROR(7); 57 POP(); U := '<инстр>'. (8) IF U '<выр>' AND U '<перем>' THEN ERROR(8); POP(); U := '<инстр>'. (9) IF U '<выр>' AND U '<перем>' THEN ERROR(9); PUSH('IF <выр> THEN') U := ''; SCAN(). (0) ERROR(10); STOP(). На самом деле мы поступили не совсем корректно, определяя подпрограммы с одинаковыми номерами. Все подпрограммы должны быть уникальными. Дело в том, что каждая подпрограмма выдает свою собственную диагностику ошибок. А это очень важный фактор. То, чем мы занимались до сих пор, касалось лишь задачи анализа. А как же быть с синтезом (например, польской формы)? Процедура синтеза осуществляется тогда, когда происходит редукция формы, т.е. тогда, когда срабатывает какое-либо правило грамматики и переменная U получает значение. К этому моменту нам известно, какие инструкции подлежат редукции и обработке. Способ матриц переходов – это очень быстрый метод обработки, т.к. в нем полностью исключается поиск. Во-вторых, очень эффективна нейтрализация ошибок: каждый нуль в матрице соответствует определенной синтаксической ошибке. Так как нулей, соответствующих частным случаям ошибок, в матрице обычно много, то диагностика получается достаточно полной. По меньшей мере, метод матриц переходов – это наиболее эффективный с точки зрения нейтрализации ошибок способ обработки. Кроме того, матрица переходов достаточно легко может быть отредактирована и/или дополнена новыми элементами по ходу развития представлений разработчика об устройстве создаваемого языка. Вдобавок ко всему, по имеющейся грамматике языка матрица переходов может быть сформирована автоматически. Недостаток метода матрицы переходов заключается в том, что для более сложной грамматики получается матрица очень большого размера, что влечет массу проблем особенно в том случае, если мы пытаемся сформировать ее вручную. 58 На этом мы закончим рассмотрение методов синтаксического анализа. Разберемся теперь с тем, как могут быть представлены результаты этого анализа. ВНУТРЕННИЕ ФОРМЫ ПРЕДСТАВЛЕНИЯ ПРОГРАММЫ Мы уже говорили о том, что внутренняя форма – это промежуточная форма представления исходной программы, пригодная (1) для простой машинной обработки (операторы располагаются в том же порядке, в котором они и будут исполняться); (2) для интерпретации. Рассмотрим, как представимы во внутренней форме некоторые наиболее употребительные операторы. Начнем с польской формы. ПОЛЬСКАЯ ФОРМА Вернемся к вопросу вычисления польской формы записи. При этом модифицируем первоначальный алгоритм так, чтобы операнды выбирались не из входного потока непосредственно, а из специально отведенного для этого стека. Как и раньше, будем хранить в R текущий считываемый символ. (1) Если R является идентификатором или константой, то его значение заносится в стек и осуществляется считывание следующего символа (правило "<операнд>::=идентификатор"). (2) Если R – бинарный оператор, то он применяется к двум верхним операндам в стеке, и затем они меняются на полученный результат (правило "<операнд>::=<операнд><операнд><оператор>"). (3) Если R – унарный оператор, то он применяется к верхнему символу в стеке, который затем заменяется на полученный результат (правило "<операнд>::=<операнд><оператор>"). Упрощенно алгоритм вычисления польской формы (ПФ) выглядит так: R := getchar while R != # do case R of 'идентификатор': push(R) 'бин.оператор': pop(B), pop(A), Tmp := R(A,B), push(Tmp) 'унарн.оператор': pop(A), Tmp := R(A), push(Tmp) endcase R := getchar endwhile Замечание. Следует помнить, что существуют операторы, которые не заносят в стек результаты своей работы. Таким оператором является, к 59 примеру, оператор присваивания языка Паскаль. Однако в языке Си (Си++) оператор присваивания возвращает значение. Польскую форму легко расширять. Рассмотрим включение в ПФ других, отличных от арифметических, операторов и конструкций. Символом $ мы будем предварять имена операторов, чтобы не спутать их с аргументами. Безусловные переходы Безусловный переход на метку (аналог GOTO L) L $BRL (Branch to label) L – имя в таблице символов. Значение его – адрес перехода. Основная проблема при реализации этого оператора – определение адреса перехода. Возможным решением является введение фиктивного оператора, соответствующего метке, на которую будет осуществлен переход с последующим поиском его в массиве польской формы. Безусловный переход на символ C $BR Под символом здесь понимается номер позиции (индекс) в массиве, содержащем польскую форму. Условные переходы <операнд1> <операнд2> $BRxZ|$BRM|$BRP|$BRMZ|$BRPZ| <операнд1> – значение арифметического выражения, <операнд2> – номер или место символа в польской цепочке (адрес). $BRx – код оператора. При этом можно ввести самые разнообразные условия перехода. Например: $BRZ – переход по значению 0, $BRM – переход по значению <0, $BRP – переход по значению >0, $BRMZ – переход по значению <=0, $BRPZ – переход по значению >=0, и т.п. При выполнении условия перехода в качестве следующего символа берется тот символ, адрес которого определяется вторым операндом. В противном случае работа продолжается как обычно. Условные конструкции IF <выражение> THEN <инстр1> ELSE <инстр2> В ПФ мы имеем: <выражение> > $BRZ <инстр 1 > > $BR <инстр 2 > 60 Предполагается, что для любого выражения 0 означает "ложь", а неравенство нулю – "истина". Здесь > – номер символа, с которого начинается <инстр 2 >, > – номер символа, следующего за <инстр 2 >, $BR – оператор безусловного перехода на символ, $BRZ – оператор перехода на символ c 1 , если значение <выражение> равно нулю). Выражение C 1 $BRZ Инстр 1 C 2 $BR Инстр 2 C 1 C 2 Обратите внимание на то, что при выполнении операторов перехода из стека лишь извлекается необходимое количество символов, а обратно ничего не возвращается. Понятно, что применение ПФ для условной конструкции в виде <выр> <инстр1> <инстр2> $IF неприемлемо, ибо к моменту выполнения оператора $IF все три операнда должны быть уже вычислены или выполнены, что, разумеется, неверно. Описание массивов Пусть дано описание массива ARRAY A[L1..U1,...,Lk..Uk] в ПФ оно представляется в виде L1 U1 ... Lk Uk A $ADEC, где $ADEC – оператор объявления массива. Оператор $ADEC имеет переменное количество аргументов, зависящее от числа индексов. Операнд A – адрес в таблице символов. При вычислении $ADEC из этого элемента таблицы извлекается информация о размерности массива A и, следовательно, о количестве операндов $ADEC. Отсюда понятно, почему операнд A должен располагаться непосредственно перед оператором $ADEC. Обращение к элементу массива и вызовы подпрограмм Конструкция A[<выр>,..,<выр>] записывается в виде <выр> .. <выр> A $SUBS Оператор $SUBS, используя элемент A таблицы символов и индексные выражения, вычисляет адрес элемента массива. Затем операнды исключаются из стека и на их место заносится новый операнд, специфицирующий тип элемента массива и его адрес. 61 Методика обращения к элементу массива представляется очень важной для понимания того, как происходит вызов функций и процедур. Дело в том, что при обращении к функции нам также необходимо извлекать откуда-то необходимое количество аргументов. А количество их мы можем определить по содержимому таблицы имен. Поэтому вызов функции вида f(x 1 ,x 2 ) в польской форме записи будет выглядеть как x 1 x 2 f $CALL, где x 1 и x 1 – аргументы, f – имя функции, $CALL – команда передачи управления по адресу, определяемому именем функции. При этом предполагается, что мы заранее занесли в таблицу имен информацию о том, сколько и каких аргументов у функции f, а также ее адрес – индекс начала кода подпрограммы в массиве польской формы. Не случайно поэтому в подавляющем количестве языков программирования имена функций ассоциируются с их адресами. Циклы Реализация циклов также не вызывает сложностей. Во-первых, имея оператор безусловного перехода и условный оператор, можно всегда сконструировать цикл "вручную". Например, цикл вида FOR I=N1 TO N2 DO Operator может быть сконструирован на исходном языке: I := N1; L1: IF I>N2 THEN GOTO L2; Operator; I:=I+1; GOTO L1; L2: Тем не менее, если необходимо реализовать этот цикл как оператор языка, то в польской форме записи он будет выглядеть так: … I N1 := L1 N2 I – L2 $BRM Operator I I 1 + := L1 BR L2 … 62 Рассмотрим фрагмент программы: BEGIN INTEGER K; ARRAY A[1..I-J]; K := 0; L: IF I>J THEN K := K+A[I-J]*6 ELSE BEGIN I := I+1; I := I+1; GOTO L; END END. Добавим еще два оператора без операндов – $BLOCK ("начало блока") и $BLOCKEND ("конец блока"). Эти операторы иногда очень важны – в некоторых языках программирования с их помощью можно вводить локальные, "внутриблоковые" переменные, вызывать автоматически деструкторы и т.п. Кроме того, нам понадобится оператор присваивания ":=", который ничего не заносит обратно в стек. Польская форма нашего фрагмента будет выглядеть так: $BLOCK 1 I J - A $ADEC K 0 := I J - 29 |