    10. Компиляция и интерпретация. Реализация простейшего компилятора  с 
языка арифметических формул 

    Мы уже составляли по формуле соответствующую программу для Стекового 
калькулятора (разд. 1). Теперь напишем программу, которая делает это для любой 
формулы автоматически. Такая программа -называется компилятором (переводчиком) 
с языка арифметических формул на язык программ для Стекового калькулятора. 
Однако прежде всего мы уточним, что таксе «язык» и что такое «компилятор», 
Язык и грамматика. 
    Определения. Пусть А—некоторый алфавит, т. е. произч вольное непустое 
множество. Элементы этого множества мы будем называть символами. Произвольная 
конечная последовательность символов алфавита (в том числе и пустая) 
называется цепочкой. Произвольное подмножество LA множества всех возможных 
цепочек называется языком над А\ 
    Над одним и тем~*жё алфавитом можно определить много разных языков. Пусть, 
например, А = {0, 1} — алфавит из двух сим-волов 0 и 1. Мы можем рассмотреть 
язык всех возможных цело-. чек над А; язык непустых цепочек; язык непустых 
цепочек, начинающихся с 1; язык цепочек, состоящих только из 1, и т. д. За< 

    10. КОМПИЛЯЦИЯ И ИНТЕРПРЕТАЦИЯ 151 

    метьте, что здесь мы описываем множество цепочек языка неформально, 
считая, что никаких двусмысленностей или неясностей не возникает. Такое 
словесное задание языка, однако, удобно лишь для простейших случаев. 
Рассмотрим, например, язык LA правильных арифметических формул над алфавитом 
А, состоящим из 26 строчных латинских букв, двух скобок и четырех знаков 
арифметических действий: 
    A = {a,b,c,d,   ... z, (,), + ,-,*,/}. 
    Для простоты ограничимся случаем, когда в формуле фигурируют только 
односимвольные переменные а, Ь, с, d, . . . , z и запрещено использование 
унарных операций, Таким образом, цепочки 
    а 
    b — а * с 
    ((a + b)»(c + d)-a)/(e + f) 
    инляютси правильными формулами, т. е, принадлежат языку LA, а цепочки 
    ))) + а** 
    аа + b 
    * а 
    праиилышмн формулами не являются, т. е. языку LA не принадлежат. Заметьте, 
что в данном случае мы ие описали все множе-стпо цепочек языка, а 
проапеллировали к некоторому интуитивному пргдстаилепию о том, что такое 
«правильная формула без унарных иш-раций». Являются ли в нашем понимании 
правильными формулами цепочки 
    Л     (т. «. пусти и цепочка, по содержащая символов) 
    и -М- Ь) 
    уже не очень ясно. Поэтому обычно такие достаточно сложные языки задаются 
не словесно, а формально, с тем чтобы принадлежность цепочки языку можно было 
доказать или опровергнуть, исходя из определения. Одним из наиболее 
распространенных способов задания языка является его задание с помощью 
грамматики. Определение. Пусть А — некоторый алфавит, М — метаал~ фавит, т, е. 
какой-то другой алфавит, не пересекающийся с А (АПМ = 0). Элементы 
метаалфавита М называются метасимволами. Грамматикой называется система правил 
(т. е. конечная гю-следовательность строк) вида „а ,-*• цепочка над (МуА), 

    152	ГЛ. 2. НЕСКОЛЬКО   ПРИМЕРОВ   ПРОГРШМ 

    где а е М — какой-то метасимвол, в которой для каждого осеМ встречается 
хотя бы одна строка с а в левой части (до стрелочки) и в которой выделен один 
метасимвол, называемый главным. 
    Пример. Пусть А -алфавит, над которым мы рассматрива-ли язык правильных 
арифметических формул, М={а,Рл}. « -~ главный метасимвол, а грамматика такова: 
    а -> сгуа 
    р->а В->Ь 
    Y+ + 
    ?->   — if -> * 
    Содержательно каждое правило грамматики имеет смысл подстановки.  
Например,  строка v 
    или 
    а 
    ! I 
    означает возможность за-, мены метасимвола а на цепочку ftYet 'Начав с 
главного метасимвола и пользуясь различными правилами грамматики (т.е. 
многократно выполняя подстановки), мы можем получать различные цепочки, 
состоящие из символов и метасимволов. Например, цепочку (х + у) можно получить 
так (над стрелками указаны те правила грамматики, т. е. те подстановки, с 
помощью которых получены соответствующие цепочки): 

    Рис.   10.1.  Деревья  вывода  для (х + У)    и   z 

    А цепочку, состоящую из единственного символа z, так: 

    10. КОМПИЛЯЦИЯ И ИНТЕРПРЕТАЦИЯ 153 

    Обычно такие последовательности подстановок и их результаты записывают 
более компактно в виде так называемого дерева вывода или дерева разбора (рис. 10.1). 
    Заметим, что если в .цепочке встречается метасимвол, то ез можно 
преобразовать дальше, применив одно из правил грамма» тики с этим метасимволом 
в левой части. Если же метасимволов в цепочке не осталось, то процесс ее 
преобразования закопчен и больше с цепочкой ничего сделать нельзя. По этой 
причине обычные символы часто также называют терминалами («конечными» 
символами), а метасимволы — нетерминалами. 
    Определение. Все множество цепочек над А (т. е. цепочек без метасимволов), 
которые можно получить таким образом, называется языком, порожденным данной 
грамматикой, или языком, заданным с помощью данной грамматики. 
    До сих пор мы рассуждали па чисто символическом уровне. Как правило, 
однако, метасимволы (нетерминалы) имеют некоторый смысл. Например, в 
приведенной выше грамматике а означает правильную формулу, р — имя переменной, 
а у — знак операции. В этом смысле метасимволы можно понимать как имена 
понятий, которые вводятся для формального описания того или иного ялики. 
Ilo'jroMy обычно для их обозначения используют сами попиши, IUMTIJC и угловые 
скобки, например <формула>, <имя пе-ргмсшюй), <знак операции). Грамматика при 
этом примет вид 
    <формула)->- «формула» <формула)-»-<имя переменной) 
<формула)->-<формула)<знак операции)(формула) 
    и т, д. 
    Кромм того, пришит грлмм.тгнкм с одним и тем же нетерминалом и лгиоП чист 
объединяют, используя вместо стрелочки знак ?:-•• (чипнпся «это есть») и 
разделяя варианты вертикальной чер-'Ю(1 (читается «либо»): 
    (формула): :«= ({формула}) ](имя переменной)! 
    (формула) (знак операции) (формула) (имя переменной): : = a|b|c|d| ... |z 
(знак операции):: = +1 — | * |/ 
    (*) 
    Такую запись правил грамматики принято называть нормальной формулой Бэкуса 
— Наура или сокращенно НФБН. В настоящее иремя НФБН и ее незначительные 
модификации широко используются в программистской литературе для описания тех 
или иных языков программирования. 
    Один  и  тот. же язык можно описать при  помощи  разных  наборов  понятий  
и,  значит,  задать   с  помощью  разных  грамматик. 

    154 ГЛ. 2. НЕСКОЛЬКО  ПРИМЕРОВ   ПРОГРАММ 

    Например, грамматика 
    (формула): : = (терм)](терм) + (формула) | (терм) — (формула) (терм): : = 
(множитель) | (множитель) * (терм)	/    , 
    | (множитель)/(терм) 
    (множитель): : = ((формула)) | (имя переменной) (имя переменной):: = а | b 
1 с |d | ... |z 
    задает тот же язык, что и грамматика (*)   (докажите это!)'. 
    Выбор той или иной грамматики (того или иного набора понятий) для описания 
языка зависит от приложений. Например, если мы только проверяем правильность 
формулы, то удобно использовать простую грамматику (*). Если же, кроме того, 
нас интересует старшинство операций при вычислении по формуле, то удобнее 
грамматика (**), понятия которой это старшинство отражают. 
    Компиляция. Компиляцией (или трансляцией) называется преобразование текста 
(конкретной цепочки символов) с одного языка (А) в семантически эквивалентный 
текст на другом языке (В). Например, с языка правильных арифметических формул 
на язык правильных программ для Стекового калькулятора (рис. 10.2), (Мы 

    СК.начать раеоту СК.Доьавить  <а> в стек СК.доБавить <;ь> » стек СК,сложить 
    СК.лркаэать результат СК.кончить работу 
    а+Ь 
    | Компиляция 

    Рис.   102 

    будем рассматривать только такие программы для Стекового калькулятора, в 
которых в качестве входных параметров фигурируют лишь односимвольные имена 
переменных от а до z.) 
    Компилятором называется исполнитель (или программа), который автоматически 
осуществляет такое преобразование текста с одного языка на другой. 
    Рекурсивная реализация компилятора правильных формул. Будем для 
определенности считать, что язык правильных формул задается грамматикой (**), 
и попробуем реализовать компилятор в соответствии с этой грамматикой: 
    исполнитель Компилятор правильных формул 
    . СП; 
    ,      1. компилировать формулу •*- обработать формулу 
    ,         — обработать терн 


    V	10. КОМПИЛЯЦИЯ И ИНТЕРПРЕТАЦИЯ                           155 


    —обработать множитель 
    .         — обработать имя переменной 
    . идеи реализации: 
    .   Правильная формула задается грамматикой с 4 метасимволами: 
    .	(формула) ::= (терм)! (терм) + (формула) ! (терм) — (формула) 
    .	(терм) ::= (множитель) ! (множитель) * (терм)! (множитель)/(тсрм) 
    .	(множитель) ::= ((формула)) I(имя переменной) 
    .	(имя переменной) ::= a!b!cl ...lylz 
    Для каждого метасимвола пишется отдельная программа. .    Например, 
программа «обработать терм» находит в начале .    непрочитанной части 
последовательности   Р   терм   максимальной .    длины, читает его и печатает 
соответствующий фрагмент про-.    граммы для Стекового калькулятора. 
    .   используемые исполнители: 
    Р: последовательность элементов типа символ конец описаний 
    программа компилировать формулу 
    .   дано        :   Р : последовательность  элементов типа символ 
    .	| Р содержит правильную арифметическую формулу . получить: | содержимое 
Р откомпилировано, т. е. напечатана .                    [соответствующая 
программа для Стекового кальку* ,                    |лятора 
    .    Р.истать в начало последовательности .    лсчапггь ("СК.начать 
работу") .    обработать формулу 
    утв:Р.нет непрочитанных элементов .    печатать ("СК.показать результат") 
.   печатать ("СК.кончить работу") конец программы 
    Здесь нам впервые встречается операция «печатать» Универсального 
Выполнителя, которая печатает на бумаге строку, указанную в угловых скобках в 
качестве параметров. Например, при выполнении строки 
    печатать ("СК. начать работу") 
    будет напечатано СК.начать работу 

    156 ГЛ. 2. НЕСКОЛЬКО   ПРИМЕРОВ   ПРОГРАММ 

    У операции «печатать» может быть несколько параметров, тогда они 
печатаются друг за другом. Если в качестве параметра указан некоторый текст в 
кавычках, то печатается сам этот текст, а если указано имя объекта, то 
печатается значение объекта. Например, если объект х типа символ имеет 
значение "а", то при выполнении строки 
    печатать ("СК.добавить (",х,") в стек") 
    будет напечатано 
    СК.добавить (а) в стек 
    В используемой нами грамматике понятие (формула) определяется через 
понятия (терм) и (формула): 
    (формула) ::= (терм) | (терм) + (формула) | (терм) — (формула) 
    Естественно поэтому попытаться реализовать обработку формулы рекурсивно. 
(Напомним, что рекурсия — это ситуация или програм-мистский прием, состоящий 
в'том, что программа непосредственно или через другие программы обращается к 
себе как к подпрограмме.) 
    В соответствии с определением формулы при ее компиляции можно сначала 
найти и компилировать терм: либо этот терм должен совпадать со всей формулой, 
либо за ним должен следовать знак + или —. Например, для формулы а * b * с -f- 
d нужно сначала компилировать терм а*Ь*с (но не а*Ы), а для формулы (а + b * 
с)—терм (a-f-b*c), совпадающий со всей формулой. Таким образом, после 
компиляции терма возможны три ситуации) 1) в формуле больше символов нет; 2) 
далее идет знак +, а за ним формула; 3) далее идет знак —, а за ним формула. 
Соответственно в целом обработку (компиляцию) формулы можно записать так: 
    программа   обработать формулу 
    „ дано        :   Р: последовательность элементов типа символ .	| 
непрочная часть Р начинается с правильной 
    | арифметической формулы . получить: | из непрочитанной части Р прочитана правильная 
    | формула максимальной длины. Напечатан соответ-.	| ствующий фрагмент 
программы для   Стекового  каль
    [кулятора 
    обработать терм 
    выбор 
    .   при Р.нет непрочитанных элементов => ничего не делать 
    .   при Р.очередной элемент ~"-^-"=f


    10. КОМПИЛЯЦИЯ И ИНТЕРПРЕТАЦИЯ	15/ 


    .   .	Р.пропустить очередной элемент 
    .    •	обработать формулу 
    .    .	печатать ("СК-сложить") 
    .    .   при Р.очередной элемент ="—"=>• 
    .   .	Р.пропустить очередной элемент    ......••• 
    .    .	обработать формулу 
    печатать ("СК.вычесть") .    .   иначе =Ф- ничего не делать .    конец 
выбора конец программы 
    Обратите внимание, что в программе «обработать формулу» мы обрабатываем 
непрочитанную часть Р не до конца последователь-ности, а лишь до конца 
правильной формулы. Это связано о тем, что далее при обработке множителя в 
соответствии с правилом 
    (множитель) :: = «формула» | (имя переменной) мы будем  вызывать программу 
«обработать формулу» для комли-ляции   выражения  внутри  скобок,  а  такая 
обработка должна заканчиваться при достижении закрывающей скобки. 
    Наконец, коль скоро мы воспользовались рекурсией, мы обя< заны 
гарантировать, что программа «обработать формулу» не будет пычыпать себя 
бесконечно. В данном случае убедиться в этом дополыю легко — поскольку перед 
каждым новым вызовом программы «обработать формулу» непрочитанная часть Р 
уменьшается, и последовательность Р конечна, то и вызовов может быть лишь 
конечное число. Следовательно, рано или поздно обработка формулы закончится. 
Аналогичным образом в соответствии с грамматикой реализуются программы 
«обработать терм», «обработать множитель» и «обработать имя переменной»: 
    П|)0| рНММП   Об|11|Ги>Т1ГГ|>   ТСрМ 
    . дни о         : |и начале  непрочитанной   части  исполнителя  Р—терм . 
получить: | из непрочитанной части Р прочитан   терм   максималь-.	| ной 
длины. Напечатан соответствующий фрагмент I программы для Стекового калькулятора 
    ничего не делать 
    обработать множитель 
    выбор 
    . при Р.нет непрочитанных элементов 
    . при Р.очередной элемент = "*" о
    Р.пропустить очередной элемент .	обработать терм 
    печатать ("СК.умножить") 
    . при Р.очередной элемент ="/"=*• . 
    •    Р.пропустить очередной элемент 

    158	ГЛ, Ч. НЕСКОЛЬКО   ПРИМЕРОВ   ПРОГРАММ 

    ,   .	обработать терм 
    .   .	печатать ("СК.. разделить ^> 
    .   .   иначе •=$- ничего не делать 
    .    конец выбора 
    конец программы 

    программа обработать множитель 
    . дано        : | в начале непрочитанной части Р — множитель . получить: | 
из непрочитанной части Р прочитан множитель макск-| мальной длины. Напечатан 
соответствующий фрагмент | программы для Стекового калькулятора 

    если Р, очередной элемент =^="(" то обработать  имя переменной 
    т. с. пропустить ")" 
    .	. иначе 
    .	,  Р. пропустить очередной элемент | т. е. пропустить "(' 
    .	.   отработать формулу 
    .	.    у та-: Р. очередной элемент = ")'" 
    .	.  Р . пропустить очередной элемент 
    .	конец если 
    конец программы 

    программа обработать имя переменной 
    . дано        :   "а" ^ Р, очередной элемент ^."г" 
    . получить: | очередной элемент Р (имя переменной) прочитай. 
    .	| Напечатана соответствующая строка программы для 
    .	1 Стекового калькулятора 
    .    печатать ("СК..добавить (",  Р.очередной элемент,"} в стек") .    
Р.пропустить очередной элемент конец программы 
    конец исполнителя [=== = = «. = = = = =, ==„ ==.,»,. ==., = = .= «..., = =. 

    Откомпилируйте в соответствии с написанной выше программой правильную 
формулу а — b — с. Обратите внимание, что полу» ченная в результате компиляции 
программа для Стекового калькулятора соответствует формуле а—(Ь — с), т. е. в 
этой ситуации наш компилятор работает неверно. Почему так получилось? Чтобы 
разобраться в этом вопросе, давайте построим дерево вывода формулы а —Ь —с в 
грамматике (**) (рис. 10.3). Если мы теперь вместо а, Ь и с подставим числа и 
начнем подниматься вверх, по дереву вывода, вычисляя значения нетерминалов, то 
величина Ь — с будет сначала вычислена, а потом вычтена из а. Наш компилятор 
работает точно так же. Таким образом, операции одинакового старшинства 
выполняются справа налево не из-за ошибок в компиляторе, а иЗ'За TQrOj что 
грамматика (**) языка арифметически* 

    10. КОМПИЛЯЦИЯ И ИНТЕРПРЕТАЦИЯ 159 

    формул не соответствует принятому в арифметике порядку выпол-.. нения 
действий одинакового старшинства, 
    ^формула'. 
    <имя переменной> * 
    Л	—                             Ь                                 —        
                        С 

    Рис.   10.3. Дерево  иынода формулы  а —Ь —с в грамматике (* *) 

    Грамматику   (**)   легко  преобразовать к  виду   (***),  соответ* 
ствующему правильному порядку выполнения действий: 
    (формула): : •= (терм) | (формула) + (терм) | (формула) — (терм) (терм): : 
= (множитель) | (терм) * (множитель) 
    | (терм)/(множитель) 
    (множитель): : = ((формула)) | (имя переменной) (имя переменной): : = а | 
Ь | с | d | ... |z 
    (*«*) 
    Однако рекурсиопо реализовать соответствующий этой грамматике компилятор 
тпк, как это было сделано выше, нельзя. Невозможно, нппримгр, при 
i)dp;i6oii<i: формулы по очередному элементу по слсдоиатслыюсти определить, 
надо ли обрабатывать терм или формулу. Но даже если бы это оказалось 
возможным, мы бы не имели права в программе обработки формулц рекурсивно 
обратиться к себе, так «ак в этот момент непрочитанная часть 
последовательности еще не изменилась и, следовательно, в этом месте программа 
бы обращалась к себе до бесконечности. 
    Приведенную выше реализацию компилятора правильных арифметических формул 
можно подправить так, чтобы операции выполнялись в нужном порядке. Заметим, 
однако, что при этом основное достоинство рекурсивной реализации — простая 
связь грамматики и программы — будет потеряно. Поэтому мы сначала изменим 
форму описания языка и лишь потом переделаем компилятор в соответствии с новым 
описанием языка правильных арифметических формул, 

    160	ГЛ. 2. НЕСКОЛЬКО   ПРИМЕРОВ   ПРОГРАММ 

    Прежде всего заметил?, что в соответствии с грамматикой (**) формула 
состоит из одного или нескольких термов, соединенных знаками -|- или —, а терм 
состоит из одного или нескольких мяо< жителей, соединенных знаками * или /, 
Введем новые понятия '.(метасимволы) 
    (аддитивная операция) ::= + | — (мультипликативная операция) ::="*[/ 
    и зададим понятия <формула) и (терм) в новой форме: 
    (формула) ::= (терм) {(аддитивная операция) (терм)} 
    (терм) ::= (множитель) {(мультипликативная операция)  (множитель)} 
    где фигурные скобки означают повторение содержимого нуль или более раз. 
Остальные понятия грамматики (**) оставим без изме« нений. При реализации 
компилятора в соответствии с новым описанием языка паре фигурных скобок будет 
соответствовать цикл. Программа «обработать формулу», например, примет вид: 

    программа обработать формулу 
    . дано        :    Р:последовательность элементов типа символ 
    | непрочитанная часть исполнителя Р начинается с 
    | правильной арифметической формулы 
    . получить: | из непрочитанной части Р прочитана правильная .	| формула 
максимальной длины.   Напечатан   соответст
    ] вующий фрагмент программы для Стекового 
    I калькулятора 
    выход из цикла 
    .	обработать терм 
    .	цикл выполнять 
    .	.     выбор 
    .	.      .   при Р. нет непрочитанных элементов 
    .	.      .   при Р. очередной элемент =» "+"=*" 
    .	.      .                                   Р. пропустить очередной элемент 
    .	,     ,                                 обработать терм 
    .	.     .                                 печатать ("СК- сложить") 
    .	.     .   при Р. очередной элемент = " — "=»• 
    .	.     .                               Р. пропустить очередной элемент 
    .	.     .                                 обработать терм 
    .	.     .                                 печатать ("СК. вычесть") 
    .	.  . иначе =*• выход из цикла 
    .	.  конец выбора                      
    .	конец цикла 
    конец программы 


    10. КОМПИЛЯЦИЯ И ИНТЕРПРЕТАЦИЯ	1с! 

    Аналогичным образом модифицируется программа «обработать терм». Заметим, 
что, хотя теперь программа «обработать формулу» явно к себе не обращается, 
неявная рекурсия осталась: программа «обработать формулу» вызывает программу 
«обработать терм», которая вызывает программу «обработать множитель», которая 
вызывает исходную программу «обработать формулу». 
    При компиляции по повой программе формула а — b — с будет обработана 
правильно. Действительно, эта формула состоит из трех термов: а, Ь и с. 
Вначале будет обработан первый из них, а потом в цикле два других. 
Соответственно до цикла будет напечатано 

    СК.добавить (а) в стек 
    # А в цикле сначала будет напечатано 
    СК.добавить (Ь) в стек СК.пычость 
    а потом 
    СК.добавить (с) в стек СК. вычесть 

    Компиляция и интерпретация. Компилятор •- это переводчик, который 
переводит текст с одного языка на другой. Результатом рэботы компилятора 
формул является текст программы, а не результат ее выполнения. Мы могли бы, 
однако, поступить по-другому: вместо того чтобы печатать программу для 
Стекового калькулятора, можно было выполнять соотвег» ствующие предписания по 
мере их появления, т. е. вместо строк вида 

    печатать <"СК.начать работу") 
    печатать ("СК.сложить") 
    написать соответственно СК.начать работу СК.сложим» 

    П этом глучлс результатом работы программы был бы не текст, л горя' щая на 
табло Стекового калькулятора величина, вычисленная в соответстнии г заданной 
формулой. Такие программы называются интерпретаторами, а процесс их выполнения 
— интерпретацией. В процессе интерпретайии правильной арифметической формулы 
интерпретатор читает формулу, разбирает ее и по мере разбора выполняет нужные действия. 
    II компиляция, и интерпретация формулы имеют и преимущества, я недостатки. 
Например, если нам нужно много раз считать по одной и то* же формуле с разными 
числовыми данными, то выгодно эту формул/ заранее откомпилировать, а затем 
считать по готовой программе. Бели жо нам нужно посчитать по формуле всего 
один раз, то выгоднее сразу начать ее интерпретировать — при этом не 
понадобится получать и хранить программу для Стекового калькулятора. Это, 
конечно, весьма грубое описание. Более подробно на достоинствах и недостатках 
компиляции и ин« терпретацин мы остановимся D разд. 20. 
    Реализация компилятора с языка арифметических формул с Но* мощью стека. 
Будем рассматривать результат компиляции — про

    6    А.  Г. Кушниреико.  Г, В. Лебедев 
    162	ГЛ. 2. НЕСКОЛЬКО   ПРИМЕРОВ   ПРОГРАММ 

    грамму для Стекового калькулятора — как функцию на пространстве 
последовательностей символов. Поскольку мы имеем дело о функцией на 
пространстве последовательностей, попробуем вычислить ее индуктивно за один проход. 
    Прежде всего заметим, что любую правильную формулу можно 
    скомпилировать так, что 
    а) строки с именами переменных (предписания «добавить в стек») в программе 
будут идти в том же порядке, что н имена переменных в формуле;, 
    б) все операции (сложить/вычесть/умножить/разделить) в программе будут 
расположены позже соответствующих знаков опера-: ций в формуле. 
    Этот факт легко доказывается индукцией по числу знаков операций а формуле. 
Для формулы без знаков операций это, очевидно, так. Предположим, что это верно 
для любой формулы, и которой не больше п. аиакон операций. Докажем, что тогда 
это верно и для формулы с п + 1 знаками операций. Действительно, выделим в 
такой формуле тот знак операции^ который при вычислении по этой формуле 
выполняется последним (если таких енпкоп несколько, то возьмем любой из них, 
например самый правый). Воз. можны две ситуации: 
    (правильная формула х><знак) (правильная формула у)   . 
    (...«правильная формула х> <знак> (правильная формула у>)...). 
    В любом случае формулы х и у содержат не более п знаков операций и по 
предположению индукции могут быть скомпилированы во фрагменты программы X и Y, 
удовлетворяющие условиям а) и б). Записав фрагмент программы X, затем фрагмент 
Y, а за ними операцию Стекового калькулятор;), соответствующую знаку, мы 
получим фрагмент программы, удовленю-ряющий условиям а) и С), для формулы в целом. 
    Таким образом, формулу можно компилировать так: встретив имя переменной, 
немедленно печатать соответствующую строку программы, а встретив знак операции 
или скобку, печатать те из предыдущих, уже прочитанных, но еще невыполненных 
операции (будем их называть отложенными), которые выполнимы в этот момент, 
после чего «откладывать» и новый знак г. Поскольку среди оставшихся отложенных 
операций нет таких, которые выполнимы до z, то для хранения отложенных 
операций можно воспользоваться стеком (назовем его стеком операций]. Этот стек 
и есть та информация, которая необходима для индуктивной компиляции формулы. 
    исполнитель Компилятор формул . СП: 
    1, компилировать правильную формулу (вх : Р) 
    — обработать символ {вх : с : символ) ,    —обработать отложенные операции 
(DX : с : символ) 


    10. КОМПИЛЯЦИЯ И ИНТЕРПРЕТАЦИЯ 163 

    типы: 
    вид = перечисление (имя, лазая скобка, правая скобка, знак) . объекты: 
    стек операций : стек элементов типа символ используемые исполнители: 
    Справки ксшец описаний | ____---__-__.________— ___________ 
    программа компилировать правильную формулу (вх:Р) 
    . дано        :     Р : последовательность элементов типа символ 
    | Р содержит правильную формулу 
    . получать: | Р откомпилирована, т. е. напечатана соответствующая | 
программа для Стекового калькулятора 
    .   печатать ("СК-начать работу") .    стек операций.начать работу 

    В стеке операций в каждый момент времени мы будем хра« лить отложенные и 
не выполненные к этому моменту операции. В момент окончания формулы все эти 
отложенные операции надо иыполнить. Аналогично в момент прочтения правой 
скобки надо выполнить все операции, которые были отложены с момента по* 
явления соответствующей левой скобки. Чтобы не разбирать окон» чанпе формулы 
особо, мы возьмем всю формулу в скобки (точнее^ проимитируем такое «взятие в скобки»): 

    . обработать символ {вх: "(") 
    . Р.встать в начало последовательности 
    . цикл для каждого с из непрочитанной частч Р выаолаять 
    . .    обработать символ (вх : с) 
    . конец цикла 
    . обработай, символ (их : ")") 
    утв: стек операций.стек пуст . стек операций.кончить работу . печатать 
("СК- показать результат") . печатать ("СК- кончить работу") конец программы 
    программа обработать символ (вх : с: символ) . дано        : . получить: 
    . вид: = Справки.вид символа (с) 
    . выбор 
    . .   при вид = имя =*• печатать ("СК-Добавить (", С, "} В ртек") 
    . .  при вид = левая скобка =г-стек операций,добавить (с) 
    6» 


    164 ГЛ. 2. НЕСКОЛЬКО   ПРИМЕРОВ   ПРОГРАММ 

    . .   при вид = знак =>• обработать отложенные операции (с) 
    стек операций.добавить (с) . .   при вид = правая скобка => 
    обработать отложенные операции (с) . . 
    утв: стек операций.вершина = "(" 
    стек операций .-удалить вершину стека . конец выбора конец программы 
    программа обработать отложенные операции {вх : с : символ) . дано        : 
    (Справки.вид символа {с) = знак или 
    Справки.вид символа (с)= правая скобка) и стек операций.стек не пуст | 
там,  как минимум,  "(* . получить: j операции   из   стека операций, которые 
можно выпол-| нить до "с", выполнены. 
    . цикл пока Справки.(стек операций.вершина) выполнима до (с; . .   выполнять 
    .  .     стек операций.взять элемент из стека в (вых: х) . .     выбор 
    . .     .   при х = " + " =*-печатать ("СК. сложить") . .     .   при х = 
" — "<=>• печатать ("СК.вычесть") . .      .   при х = "*"=>• печатать 
("СК.умножить") .   при х. = "/"=> печатать {"СК.разделить") . .     .   иначе 
=>• отказ . .     конец выбора . конец цикла конец программы 
    конец исполнителя 
    исполнитель Справки СП: 
    1. вид символа {вх: с : символ) 
    2. (вх : cl : символ) выполнима до (вх : с2 : символ) — вес (вх : с : символ) 
    вид 
    да/нег 
    1..2 
    . типы: 
    вид = перечисление (имя, левая скобка, правая скобка, знак) конец описаний 
1-- — - ——— — -- —————— — -- — ---~—i 
    программа вид символа (вх : с : символ): вид 
    . дано        : | с ~ символ из правильной формулы 
    . получить: 
    10. КОМПИЛЯЦИЯ И ИНТЕРПРЕТАЦИЯ 165 
    . выбор . .     при 
    "+" или с = "—" или с = "*" или с =•"/" 
    Е> ответ :=знак "("	=Ф-ответ := левая скобка 
    tl\fr 
    =>- ответ := правая скобка г" =*• ответ := имя 
    . .     при с . .      при с = ")л . .      при "а" < с < . .      иначе 
=>• отказ . конец выбора конец программы 
    программа (вх: cl: символ) выполнима до (вх : с2): да/нет 
    . дано        : (вид символа (с!) = знак или 
    .	вид символа (cl) = левая скобка) и             • 
    .	(вид символа (с2) = знак или 
    .	вид символа (с2) — правая скобка) 
    . получить: 
    . выбор 
    . .     при вид символа (cl) = левая   скобкам-ответ:= нет 
    . .     при вид символа (с2) == правая скобка =»- ответ := да 
    . .     иначе **• ответ := (вес (cl) ^ вес (с2)) 
    . конец выбора 
    конец программы 
    программа вес (вх: с : символ): 1. .2 . дано        : вид символа (с) = 
знак . получить: 
    .    выбор 
    . . при с «•*+*•»• ответ := 1 при с = "—"«=>- ответ := I . . при с = "*" 
=*"0твет:=2 . . при с=>"/" =*-ответ:=2 . конец выбора конец программы 
    конец исполнителя [ = === === = 
    Заметьте, насколько наша новая реализация сложнее рекур» снвной. Однако в 
отличие от рекурсивной, где простейшие изменения требуют существенных 
творческих усилий или даже переписывания всей программы целиком, здесь у нас 
изменение порядка операций с обычного на «справа налево» требует замены всего 
од« ного знака — в программе «выполнима до» надо в место ?s написать >, Даже 
более сложная задача ^= переделать компилятор так, 

    166 ГЛ. 2. НЕСКОЛЬКО   ПРИМЕРОВ   ПРОГРАММ 

    чтобы сложение выполнялось справа палево, а вычитание — слева направо, — 
требует добавления лишь одной строки без какого-либо изменения структуры всей реализации. 
    В заключение отметим, что мы компилировали только правильные формулы. В 
реальной жизни от компилятора требуется, чтобы он обрабатывал не только 
цепочки языка, но и любые другие (не принадлежащие языку) последовательности 
символов, сообщая, почему эти последовательности не принадлежат языку 

    \   a+(b+c»*d\     |       Компиляция        )>    \ нарушен Баланс  смоеокЧ 

    Рис.   10.4.   а)   последовательность   символов,   б)   результат   компиляции 

    (рис. 10.4) (в данном случае под символом понимается предопределенный тип 
нашего языка программирования, а не элемент алфавита языка арифметических 
формул). Анализ правильности формулы может быть проведен так, как это было 
сделано в разд. 8, 

    ЗАДАЧИ И УПРАЖНЕНИЯ	' 

    1. Задайте с помощью грамматики язык 
    а) десятичных целых чисел со знаком, 
    б) правильных программ для Стекового калькулятора (т. е, язык всех 
программ, которые получаются при компиляции всех правильных формул; символами 
алфавита в данном случае следует считать отдельные строчки программы). 
    2. Докажите, что цепочка (a *(b + c)+ d)/(a + d) является правильной 
арифметической формулой 
    а) в грамматике (*), 
    б) в грамматике (**) 
    (доказательство   состоит   в   придумывании   дерева   или   
последовательности вывода). 
    Задачи 3—5 относятся к реализации компилятора с помощью стека. 
    3. Нарисуйте последовательные состояния стека операций при компилировании 
формулы (а *(Ь + с) — d)/(a + d). 
    4. Измените Компилятор формул так, чтобы сложение сыпол-пялюсь справа 
налево, а остальные операции — слева направо. 
    5. Измените Компилятор формул так, чтобы в формуле в произвольных местах 
могло стоять произвольное количество пробелов н чтобы эти пробелы полностью 
игнорировались при компиляции. 

    11. ПРОЕКТ «ПОСТРОЕНИЕ ИЗОБРАЖЕНИЯ ПОЛИЭДРА»	167 