М.Черкашин Шпаргалка для компьютера Курсив: Таблицы очень часто облегчают написание программы В окно : Лексема - любая конструкция языка программирования, далее уже не делимая, например константа, ключевое слово, имя переменной и т.д. Сканер - процедура, считывющая текст программмы и определяющая при каждом обращении к ней очередную лексему; благодаря ему компилятор может работать с минимальными элементами языка - лексемами, а не с символами. Конец окна Предположим, Вам хочется написать небольшой калькулятор, то есть программу, которая способна читать выражение с клавиатуры, вычислять значение выражения и печатать его. Вы можете действовать по следующему алгоритму. В окно: Процедура Вычислить. Достать из стека значений два значения, из стека операций - одну операцию. Применить операцию к значениям и полученный результат поместить в стек операций. Конец процедуры Вычислить. Алгоритм вычисления значения выражения. Поместить в стек операций Прокладку. Пока не встретится конец выражения, считывать лексемы и в зависимости от типа лексемы производить следующие действия. 1. Если считанная лексема есть число, положить его в стек значений. 2. Если считанная лексема есть операция, положить ее в стек операций. Однако : класть операцию с более низким приоритетом на операцию с более высоким приоритетом нельзя. Поэтому в случае если у считанной операции приоритет ниже, чем у лежащей в стеке наверху, применить процедуру Вычислить столько раз, сколько необходимо. 3. Если считанная лексема есть открывающая скобка, то положить в стек операций Прокладку. 4. Если считанная лексема есть закрывающая скобка, то применять процедуру Вычислить, пока на вершине стека операций не появится Прокладка. Когда встретится конец выражения, применять процедуру вычислить, пока не появится Прокладка. Единственное оставшееся в стеке значений число и будет искомым значением выражения. Конец алгоритма. Конец окна Заметим, что у данного алгоритма есть одна особенность. Какими бы ни были операции и приоритеты операций и сколько бы их ни было, алгоритм остается неизменным. Если бы мы пытались реализовать этот алгоритм вручную и не помнили всех операций, мы бы выписали обозначения всех операций и их приоритеты в таблицу и пользовались бы ею по мере необходимости. Когда те же данные хранятся в памяти машины, также говорят, что такая-то информация хранится в таблице. Можно сказать так: структуры, информация в которых не изменяется в течение работы программы, называются таблицами. Программа для этого алгоритма приведена в примере 1. Пример 1. Маленький калькулятор с таблицей procedure OneOperation; var X,Y,Z : integer; op : char; begin X := PopVal; Y := PopVal; op := PopOper; case op of '+': Z := X+Y; '-': Z := X-Y; '*': Z := X*Y; '/': Z := X div Y; end; PushVal (Z); end; Procedure Compute; begin PushOper (Layer); case LexMode of LexNumber: PushVal (LexVal); LexOper : begin while Priority (TopOper) do Compute; PushOper (Chr (LexVal)); end; LexLeft : PushOper (Layer); (*(*) LexRight : begin while TopOper <> Layer do Compute; PopOper; end; end; end; begin (* Scan - это сканер *) while not Eof (T) do begin Scan; Compute; end; (* А теперь берем в стеке значений то, что осталось - *) (* и это и есть результат *) end. Сюрприз Таблицы хранят в себе много сюрпризов для программиста - как приятных, так и неприятных. А вот и один из них. Мы можем записать в таблицах программу, решающую нашу задачу; а программой, интерпретирующей таблицы, будет транслятор. Почему бы и нет? Мы можем даже рассматривать любую нашу программу как таблицы для компьютера. Конечно никто не записывает в таблицы программы на Паскале. Но наш пример говорит о том, что таблицы - это невероятно мощная штука. Вот, например, неслыханный прогресс в искусственном интеллекте, связанный с появлением экспертных систем, связан в основном с тем фактом, что удалось поместить в таблицы (а не в текст программы) почти всю информацию, определяющую функционирование системы. Форма Бэкуса - Наура Для того чтобы таблицы было можно использовать, необходимо выбрать форму представления синтаксиса программы, одинаково понятную как человеку, так и машине. Существуют несколько таких форм представления. Здесь выбрана одна из них - самая, по мнению автора, удобная. Любая программа состоит из конструкций - фрагментов, которые имеют какой-то смысл: операторов, описаний и т.д. Более того обычно бывает, что конструкция каждого из возможных типов - это строго заданная последовательность конструкций других типов, либо другая подобная последовательность и т.д. Пример использования формы Бэкуса-Наура приведен на рис. 1. Было: Стало: <Программа>: <Программа>: program <Описания> <Описания> <Тело> <Тело> <Описания>: <Описания>: var int <Переменная> <Переменная> ,<ХвостПеременных>; ,<ХвостПеременных>; <ХвостПеременных>: <ХвостПеременных>: :integer; ; <ХвостПеременных>: <ХвостПеременных>: <Переменная> <Переменная> ,<ХвостПеременных> ,<ХвостПеременных> <Тело>: <Тело>: begin main (){ <ХвостОператоров>. <ХвостОператоров> <ХвостОператоров>: <ХвостОператоров>: <ХвостОператоров> <ХвостОператоров> <Оператор> <Оператор> <ХвостОператоров>: <ХвостОператоров>: end } <Оператор>: <Оператор>: <Переменная>:= <Переменная>:= <Выражение> <Выражение>; <Выражение>: <Выражение>: <Число> <Число> <Выражение>: <Выражение>: <Переменная> <Переменная> <Операция> <Операция> <Переменная> <Переменная> <Операция>:+ <Операция>:+ <Операция>:- <Операция>:- <Операция>:* <Операция>:* <Операция>:div <Операция>:/ <Оператор>: <Оператор>: if <Переменная> if (<Переменная> =<Переменная> ==<Переменная>) then <Оператор> <Оператор> else <Оператор> else <Оператор> <Оператор>: <Оператор>: while <Переменная> while (<Переменная> =<Переменная> ==<Переменная>) do <Оператор> do <Оператор> <Оператор>: <Оператор>: begin <ХвостОператоров> {<ХвостОператоров> <Оператор>: <Оператор>: writeln printf ("%d", (<Переменная>); <Переменная>); Рис. 1. Схема синтаксически управляемого перевода Символ : означает "определяется как". Обратим внимание, что конструкция <Хвост> - последовательность операторов, заканчивающихся ключевым словом end - определяется через самое себя: <Хвост> это либо ключевое слово end, либо оператор, за которым следует <Хвост>. Но это не должно нас удивлять. Вы же знаете, как образуется очередь? Сначала стоит один человек, который уже в каком-то смысле очередь. Потом к нему подходит второй - и они уже вдвоем образуют очередь, потом еще один. Так и получается, что любая очередь состоит из последнего в этой очереди и очереди, которая стоит перед ним. Синтаксически управляемый перевод С нашей точки зрения любой компилятор осуществляет перевод - с языка, который воспринимается компилятором, на язык, программу на котором мы можем обработать. Это может быть Паскаль (если у нас изначально есть с него компилятор), это может быть язык ассемблера, это может быть машинный язык и т.д. Однако попробуйте описать этот перевод - и у Вас возникнут определенные проблемы. Но если мы вспомним формулы Бэкуса - Наура, все совершенно изменится. В самом деле, они задают нам  _структуру программы .. А это совершенно меняет дело. В этом случае мы уже можем сказать: <Оператор> транслируется в то-то и то-то. Например, если исходная программа есть <Описания> begin <Хвост> . (а так может выглядеть программа на Паскале), то мы должны получить результат - его отныне для краткости будем называть "кодом": скомпилированные <Описания> main () { скомпилированный <Хвост> Таким образом, из программы на Паскале мы получаем программу на Cи. Приведенный только что пример показывает, как конструкция одного языка может быть переведена в конструкцию другого. В самом деле, представим его в виде следующей схемы: Было: Стало: <Программа>: <Программа>: <Описания> <Описания> begin main () { <Хвост>. <Хвост> С помощью формул Бэкуса - Наура можно разложить любую программу на конструкции, их - на составляющие их конструкции и т.д. Если к каждой формуле Бэкуса - Наура мы добавим формулу из части "Стало", то мы полностью зададим таким образом перевод из исходного языка в "код". Такой подход является вполне естественным: мы как бы разбираем программу на части, а потом снова собираем, но уже чуть-чуть по-другому. Такой набор пар правил называется схемой синтаксически управляемого перевода (СУ перевода). В качестве примера можно привести схему для перевода из подмножеств языка Паскаль в подмножество языка Cи (рис. 1). А в виде программы? Схемы синтаксически управляемого перевода были бы ни на что не годны, если бы не тот факт, что их можно интерпретировать совершенно механически - то есть с помощью программы. А раз так, то можно написать программу интерпретации схемы перевода, поместить сами схемы в таблицы (т.е. в оперативную память) - а далее запускай программу и иди обедай. В свете того, что сейчас было сказано, самый естественный алгоритм СУ перевода выглядит так. 1. Разобраться в структуре входного текста. 2. Для каждой конструкции произвести замену в соответствии с нашей схемой. Иными словами, разбить программу на операторы и каждый оператор транслировать. К сожалению, буквально этот способ как правило оказывается неудовлетворительным. Поэтому не будем пытаться справиться совсем уж со всеми схемами СУ переводов, а наложим на них два ограничения. Эти ограничения не очень-то нас стеснят, зато сильно упростят написание программы. Во-первых, разобраться в структуре входного текста не всегда так легко. Мы предполагаем, что во входном языке по первой лексеме конструкции можно определить, что это за конструкция. Так оно обычно и бывает. Тип оператора (условный или цикла или какой-нибудь еще) определяется первым ключевым словом. Описние процедуры и функции также отличается по первому ключевому слову. И так далее. Во-вторых, мы не можем позволить себе роскошь держать в памяти весь текст программы целиком. Поэтому в одном правиле в частях "Было" и "Стало" названия конструкций должны идти в одном и том же порядке - такое наше второе ограничение. Стало быть подобные пары правил просто запрещены: Было: Стало: <Программа>: <Программа>: <Описания> begin begin <Хвост> <Хвост>. where <Описания> И понятно, для чего нам это нужно. Вот считываем мы исходную программу, разбираемся с описаниями и уже готовы переписать их скомпилированными в выходной файл - с глаз долой, из сердца вон - как выясняется, что сначала мы должны записать скомпилированный <Хвост>, а описания должны пока держать не пойми где - то ли в оперативной памяти, то ли на диске. Очень неудобно получается. А теперь посмотрим программу. Основная ее часть - это процедура Разбор. Она осуществляет перевод конструкции, название которой ей дано в качестве параметра. Например, если в качестве параметра ей дано название <Оператор>, то она должна считать из входного файла один оператор и записать в выходной файл соответствующий ему "код". А если в этот оператор в качестве составных частей входят другие конструкции, то эта процедура вызывает самоё себя (рекурсивно) для перевода этих конструкций. И для того чтобы запустить перевод, достаточно вызвать процедуру Разбор с параметром <Программа> - и все! Таблиц в этой программе две. Первая - основная - содержит сами правила СУ перевода (см. рис. 1). Вторая для каждой конструкции и каждого типа лексемы содержит правило. И еще одно. Мы до сих пор так и не упомянули о том, с какого языка и на какой мы транслируем. Но в том-то и дело, что это зависит только от таблиц. В примере мы осуществляем перевод с небольшого подножества языка Паскаль в подмножество языка Cи, но ведь стоит изменить таблицы, мы уже получим нечто другое: то, что нам нужно. Программа (пример 2). Пример 2. Программа синтаксически управляемого перевода type sline = string [32]; procedure Parse (NonTerminal: sline); var i : integer; begin ........ (* Здесь мы определяем, какое из правил для данного нетерминала мы используем: WasRule - Правило "Было" BecomeRule - Правило "Стало" *) while i <= length (WasRule) and Not Error do begin Ch := WasRule [i]; if Ch = '<' then begin (* Нетерминал *) s := ''; Inc (i); while WasRule [i] <> '>' do begin s := s + WasRule [i]; Inc (i); end; while BecomeRule [k] <> '<' do begin Write (OutFile, BecomeRule [k]); Inc (k); end; Inc (k); t := ''; while BecomeRule [k] <> '>' do begin t := t + BecomeRule [k]; Inc (k); end; Inc (k); if s <> t then begin WriteLn ('Ошибка в системе правил'); end; if s = 'Переменная' then begin t := ''; while Ch in ['a'..'z','A'..'Z','0'..'9'] do begin t := t + GetNextChar; end; Write (OutFile, t); end else if s = 'Число' then begin t := ''; while Ch in ['0'..'9'] do begin t := t + GetNextChar; end; Write (OutFile, t); end else begin Parse (t); end; end; Работа над ошибками Вообще существуют два основных принципа написания компиляторов. Придумать третий, по всей видимости, невозможно. Либо "по одной процедуре на каждую конструкцию" - либо "задаем синтаксис в одном месте (например, в таблицах), а сам компилятор - в другом". Используя первый принцип, часто приходится отдельно ловить ошибки в каждом операторе. А это малость муторно. А то есть такое правило работы водолаза: "Если встретил акулу - по морде ее!" Однако инструкцию типа : "Закрутил гайку, посмотри, если есть акула - по морде ее; положил гаечный к инструментам, а если рядом акула..." ни один водолаз читать не будет. А если программа написана таким образом, то ее ни один программист не сможет отладить. На самом деле "ловить" ошибки не сложно. Достаточно лишь действовать по принципу: "Если что-то идет не так - ругайся!" И так поступают все компиляторы - именно поэтому так многочисленны ошибки типа "должно быть двоеточие, оператор, ключевое слово do и т.д." Проблема в ином. Если "не то" все-таки произошло, то нужно проскочить опасное место и сделать вид, что все в порядке (хм, а какое место считать опасным?). Это процедура называется восстановлением. Например, можно дойти до ближайшей точки с запятой и там пытаться транслировать очередной оператор. Если у нас работает схема СУ перевода, то все ошибки сводятся к одной: не удается применить ту или иную формулу Бэкуса - Наура. А с одной-то ошибкой и справиться легче. И наконец... Конечно же, это не все... Например, компиляторы часто еще и сами порождают таблицы, для того чтобы другая программа, отладчик, например, смогла разобраться в коде. Или, например, компиляторы копиляторов - программы, которые по описанию языка сами строят табличный компилятор. Историй про таблицы много - и каждая словно детектив. А эта статья - это только начало. ЛИТЕРАТУРА 1. Грис Д. Проектирование компиляторов для цифровых вычислительных машин. М.:Мир - 2. Ахо А, Ульман Дж. Теория синтаксического анализа, перевода и компиляции. М.:Мир - 3. Вирт Н. Алгоритмы + Структуры данных = Программы. М.:Мир -