Элементы компиляции программ

Большинство людей считают компьютеры математическими машинами,
разработанными для выполнения численных расчетов. В действительности
же компьютеры представляют собой языковые машины: основа их
могущества заключается в способности манипулировать лингвистическими
знаками — символами, которым приписан некоторый смысл.
Терри Виноград

В процессе изложения материала данного раздела мы получили достаточные знания для того, чтобы с пользой применить их на примере достаточно сложной задачи. Одной из таких задач традиционно считается разработка компилятора (интерпретатора). Тем более что у нас есть для этого повод — необходимость создания препроцессора для новых команд микропроцессоров Pentium Pro/II/IH/IV (см. главу 10). Исходя из этого задачу будем решать поэтапно: на первом этапе разберемся с общими вопросами из теории компиляции, которые будут полезны в контексте решения нашей задачи, а затем, на втором этапе, разработаем сам препроцессор. В соответствии с этими этапами весь материал также будет разбит на две части и рассмотрен в разных главах настоящей книги. Но для того, чтобы все наше строение было логически связанным, мы сформулируем для каждого из этапов свои целевые установки. Цель первого этапа — научиться проводить распознавание и синтаксический разбор одиночных предложений, принадлежащих некоторому языку. Цель второго этапа — применить полученные знания для обработки некоторой программы на языке ассемблера, содержащей новые команды микропроцессоров Pentium Pro/II/III, о которых транслятор ассемблера «не знает». В результате этой обработки новые команды будут замещены эмулирующим кодом. Конечно, кто-то возразит — можно попытаться достать соответствующий «patch» к транслятору, что позволит ему непосредственно поддерживать новые команды. Или выбрать другой путь — использовать набор макрокоманд, предоставляемых фирмой Microsoft (защищенный, кстати, ее авторскими правами). Но, как быть тем, кто привык работать с ассемблерами других фирм? Более того, разработка данной задачи и использование ее результатов в своей практической работе ощутимо поднимает уровень профессиональной подготовки программиста. А это уже достижение одной из целей данной книги.
Теория компиляции разработана очень хорошо. В списке литературы вы сможете найти ссылки на некоторые источники, где приведено ее описание. Наша задача — сформировать некий подход, который бы на хорошем профессиональном уровне позволил вам решать определенный круг задач. Конечно же, мало кому придется разрабатывать свой транслятор, но практически всем приходилось или придется разрабатывать языковой интерфейс своей программы с пользователем. Ну и как ваша программа будет его обрабатывать? На основе каких-то символьных заготовок? Изучив предлагаемый материал, вы, например, самостоятельно сможете производить синтаксический разбор предложений, поступающих
на вход вашей программы, оптимальным образом анализировать содержимое нужных файлов и т. п.

Формальное описание языка программирования

Язык программирования является подмножеством естественного языка и предназначен для поддержки процесса общения человека с компьютером. В общем случае язык — это множество предложений, которые можно записать на нем. Отличие языка программирования от естественного — в его законченности или замкнутости. Под этим понимается, что теоретически можно перечислить все предложения, которые можно на нем составить. Для естественного языка это невозможно. В контексте нашего изложения под языком программирования будем понимать не только языки высокого уровня, но и языки командных процессоров и вообще любые наборы предложений, с помощью которых производится управление работой некоторой программы.
Теория компиляции базируется на том, что любой язык может быть описан формально.
Основа любого естественного языка — его алфавит, то есть множество символов букв. Вспомним, что обучение в школе начинается с букваря, то есть со знакомства с набором символов, из которых в дальнейшем будут строиться слова. Приступая к изучению языка программирования, программист также вначале знакомится с набором символов (букв, цифр, разделительных знаков), из которых строятся слова программы и объединяются затем в предложения программы. Для формального описания языка программирования также необходимо знать алфавит, но в этом случае его понятие отличается от того, к которому мы привыкли. К этому мы вернемся чуть позже. Для написания программы недостаточно знать только лишь один алфавит. Так, в школе после изучения алфавита дети начинают изучать предмет «Русский язык». Можно выделить по крайней мере две цели, которые при этом ставятся: во-первых, на основе алфавита и набора правил научить школьника правильно строить слова языка (которые составляют его лексику); во-вторых, научить его правильно составлять предложения из слов, то есть делать это так, чтобы его могли понимать окружающие. Для построения правильных предложений в любом языке существует набор правил, которые описывают синтаксис этого языка. Каждому правильному предложению языка приписывается некоторый смысл. Описание смысла предложений составляет семантику языка.
Естественный язык многозначен, и часто с его помощью одну и ту же мысль можно выразить несколькими синтаксически разными предложениями. Компьютер — не человек, и общение с ним (во всяком случае, пока) должно быть однозначным, то есть не может быть двух разных по написанию предложений, выполняющих одно действие. Применительно к компьютеру семантика языка программирования представляет собой описание того, как следует исполнять на машине конкретное предложение. Различие синтаксиса и семантики лучше всего иллюстрирует следующий классический пример. Имеются два одинаковых с точки зрения синтаксиса предложения:
Здесь I, J, К — целые, а X, Y, Z — вещественные числа. В машинном представлении для вычисления данных выражений будут использоваться не только разные команды, но и алгоритмы. Если вдруг перед нами будет поставлена задача перевода программы на другой язык программирования, то в той или иной степени будет меняться все — алфавит, лексика, синтаксис, но семантика в идеале должна остаться неизменной.
Таким образом, для формального описания языка необходимы по крайней мере два элемента — алфавит и набор правил (синтаксис) — для построения предложений языка. Существует еще несколько элементов формального описания, которые также важны для процесса однозначного построения и распознавания предложений языка. Знакомство с ними целесообразно вести в рамках такого понятия, как грамматика языка.
Грамматика языка представляет собой механизм порождения предложений языка и определяет форму (синтаксис) допустимых предложений языка. Это важное положение, запомните его. В своем изложении мы постараемся по возможности избежать «формализмов», которыми изобилует теория компиляции, хотя полностью сделать это нам не удастся. В частности, без этого трудно ввести понятие грамматики. Формально грамматику языка G можно определить как совокупность четырех объектов: G-{Vt. Vn. P. Z}
Эти объекты можно описать следующим образом.

• Vt — множество терминальных символов грамматики. Кстати, в этом контексте слово «символ» не означает отдельную литеру. В контексте терминальных и нетерминальных символов символы — это ключевые слова, допустимые имена идентификаторов, знаки операций, разделительные знаки, то есть все отдельные объекты исходного текста программы, имеющие смысл для компилятора. По сути, множество терминальных символов представляет собой набор лексем, которые являются допустимыми словами языка, составляющими его лексику. Таким образом, важно понимать, что исходный текст программы состоит только из терминальных символов.
• Vn — множество нетерминальных символов. Эти символы являются вспомогательными конструкциями, определенными внутри грамматики. К пояснению того, что представляют собой нетерминальные символы, мы вернемся чуть позже. Важно отметить, что множества Vt и Vn не пересекаются. Объединение множеств Vt и Vn составляет алфавит языка. Отметим, что введенное здесь понятие алфавита грамматики (а значит, и языка) отличается от того, что есть в букваре. Не забывайте об этом важном моменте при проведении дальнейших аналогий.
• P- набор правил грамматики, определяющих синтаксис языка. Эти правила называются правилами вывода. Эти правила определяют возможность получения любого предложения языка.
• Z- начальный символ языка. Он входит в множество Vn. Одна из его особенностей состоит в том, что он должен встретиться по крайней мере в левой части одного из синтаксических правил, входящих в множество Р. И именно это правило является первым в процессе вывода любого допустимого предложения языка.

Далее, если не оговорено особо, прописными буквами будем обозначать терминальные символы, а строчными — нетерминальные.
Поясним, как с помощью грамматики задается язык. Начнем с простого примера. Опишем грамматику G1nt языка целых чисел:

Glnt = {Vt=(0.1.2,3.4.5.6.7.8.9). VrH число, цифра). Р. г=(число)}.

Множество правил Р грамматики Gint выглядит так:

число::=цифра
число::=цифра число
цифра::=0
цифра::=1
цифра::=2
цифра::-3
цифра::=4
цифра::=5
цифра::=6
цифра::-7
цифра::-8
цифра::=9

Обычно подобные правила записывают короче:

число::= цифра | цифра число цифра::=0|1|2|3|4|5|6|7|8|9

Здесь символ | означает альтернативу выбора, при этом все элементы, которые он разделяет, равноправны по отношению к нетерминальному символу левой части. Покажем, что эта простая грамматика действительно однозначно определяет язык, с помощью которого можно получить любое целое число. Процесс получения предложения языка, задаваемого грамматикой, называется выводом и определяется правилами вывода, входящими во множество Р. Причем начинать вывод предложения можно не с любого правила, а только с одного из тех, в левой части которых стоит начальный символ языка Z. В нашем случае таким символом является нетерминальный символ число. Видно, что он стоит в левой части двух правил:

число::= цифра (2.9)
число::= цифра число (2.10)

Сам процесс вывода предложения языка итеративный и состоит из одного или нескольких шагов. Например, рассмотрим процесс получения предложения 8745. Согласно сказанному выше, на первом шаге вывода можно использовать правило (2.9) или (2.10). Если использовать правило (2.9), то это означает, что предложение будет состоять из одной цифры. В нашем случае на первом шаге необходимо применить правило (2.10). Производя дальнейшие подстановки, можно получить предложение, состоящее из любого количества цифр. Заметьте, что на последнем шаге вместо правила (2.10) применяется правило (2.9), что в конечном итоге приводит к желаемому результату. Таким образом, предложение 8745 получается использованием правил вывода грамматики в следующей последовательности:

число => цифра число => 8 число => 8 цифра число => 87 число => 87 цифра число => 874 число => 874 цифра => 8745.

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

цифра число, 8 число, 8 цифра число, 87 число, 87 цифра число, 874 число, 874 цифра, 8745.

Предложением языка является только одна из этих сентенциальных форм — строка 8745.
На правила грамматики обычно накладываются определенные ограничения. В зависимости от этих ограничений языки делятся на 4 класса.

• Класс 0. Грамматики без ограничений. Правила этих грамматик имеют форму: u=>w. При этом не накладывается каких-либо ограничений на строки и и v в левой и правой частях правил вывода. Используя языки этого класса, можно моделировать естественный язык.
• Класс 1. Контекстно-чувствительные грамматики. Правила этих грамматик имеют форму: AuB=>AwB. Замена и на v возможна лишь в контексте строк А и В (отсюда и название). При этом: ueVn; we(VnuVt)*; A, Be(VnuVt)+. Символы * и + обозначают множество всех строк, выводимых в рамках данной грамматики, включая ("*") и исключая ("+") пустую строку.
• Класс 2. Контекстно-свободные, или контекст}ю-нечувствительные, грамматики. Их правила имеют форму: u=>w, где ueVn, we(VnuVt)*. Название данного класса грамматик отражает тот факт, что и можно заменить на w, не обращая внимания на контекст. Другая особенность грамматик этого класса в том, что в правой части всех правил грамматики стоит только один нетерминал. Отметим, что языки программирования моделируются с использованием грамматик именно этого класса.
• Класс 3. Регулярные, или автоматные, грамматики. Исходя из вида правил, которые используются в таких грамматиках, их делят на два подкласса.
• Грамматика, выравненная вправо. Ее правила имеют форму: u=>Aw или и=>А, где AeVt, u и weVn.
• Грамматика, выравненная влево. Ее правила имеют форму: u=>\vA или и=>А, где AeVt, u и weVn. Это очень важный класс грамматик, который наряду с грамматикой класса 2 используется для моделирования языков программирования. Заметим, что рассмотренная выше грамматика языка целых чисел как раз и является грамматикой класса 3. Чтобы убедиться в этом, необходимо лишь немного подправить правила:

число: ."¦ цифра
число: :*=0 число |1 число |2 число |3 число |4 число |5 число |б число |7 число
|8 число |9 число иифра::=0|1|2|3|4(5|6|7|8|9

Приведенная выше классификация языков была введена в 1959 году американским ученым-лингвистом Н. Хомским.
Выше, при изложении основ работы с двусвязными списками, мы ввели понятие конечного автомата. Язык, который воспринимает любой конечный автомат, относится к языкам класса 3, то есть является регулярным. Покажем это, сформулировав грамматику для языка вещественных чисел. Напомним соответствующее регулярное выражение: (+| -)dd*.dd*e(+| 0dd*, где d* обозначает цифру 0-9 или пусто.

Grea1-{Vt-(.. + . -. е. 0. 1, 2, 3. 4. 5. 6. 7. 8. 9). VrHreal. s. m, n. k, t). P. Z-(< real >)}.

Множество правил P грамматики Greal:

real=>+s|-s|Ds s=>ds |. m m=>Dn | D n=>Dn | ek k=>+t|-t|Dt|D T=>dT|d

Попробуйте, используя данную грамматику, самостоятельно вывести следующие предложения языка вещественных чисел: 5.5, +0.6е-5. Покажите, что предложение «+.45е4» невыводимо в терминах данной грамматики. При необходимости посмотрите еще раз материал раздела «Сеть» данной главы, где было введено понятие конечного автомата и разработана программа, моделирующая его работу при распознавании строки с вещественным числом.
Анализ правил вывода грамматики Greal показывает, что генерируемый ею язык относится к языкам класса 3, а сама грамматика является грамматикой, выровненной вправо.
Рассмотрим еще одну грамматику для языка идентификаторов Gident.

G1dent-{Vt-(.. +. -. е. 0. 1. 2. 3. 4. 5. 6. 7. 8, 9). VrHreal. S. M. N. К. Т), Р, 2=(< real >)}

Множество правил Р грамматики Gident:

ident=>letter| ident letter | ident figure letter => A|B|C| ... X|Y|Z figure => 0|l|2|...8|9

Видно, что это тоже грамматика языка класса 3.
А теперь приведем пример грамматики, генерирующей язык класса 2. С ее помощью смоделируем псевдоязык, похожий на Pascal, который мы используем в нашей книге для пояснения некоторых алгоритмов:

Vt=(riPOrPAMMA, ПЕРЕМЕННЫЕ, НАЧ_ПРОГ. КОН_ПРОГ, НАЧ_БЛОК. КОН_БЛОК. ".".ID. CHJNT. СН_ REAL. «:».«:». «/». REAL. INTJYTE. INT_WORD. INT_OWORD. «,».«:»». «=».«+».«-».«*». DIV. MOO. «(». «)». «[». «]». «<».«>», «==»,«>=».«=<». ЧИТАТЬ, ПИСАТЬ, ДЛЯ. ДОДЕЛАТЬ. ПОКА. Д08НИЗ, ЕСЛИ. ЕСЛИ. ДО. ТО. ПЕРЕЙТИ_НА. ПОВТОРИТЬ),
Vn»( prog, prog-name, dec-list, stmt-list, dec. id-list, type. var. varjnd. ind. label. go_to. stmt, assign, read, write, until, for. call_func. exp. term, factor, index-exp. body, condition. cond_op). P. Z-(< prog >) }

Множество правил Р грамматики G:

prog => ПРОГРАММА prog-name ПЕРЕМЕННЫЕ dec-list НАЧ_ПРОГ stmt-list КОН_ПРОГ
prog-name => ID
dec-list => dec | dec-list : dec
dec => type id-list
type => INTJYTE | INT_WORD | INT_DWORD | REAL
1d-list=> var | id-list , var
var=> ID | varjnd
var_ind=> ID ind
ind => [ exp ]
stmt-list => stmt | stmt-list ; stmt
stmt => assign | read | write | for | while | until | label | go_to | cond op | call_
func
assign => var :- exp exp => term | exp + term | exp - term
term => factor | term * factor | term DIV factor| term MOD factor factor => var | CH_INT | CH_REAL | ( exp ) read => ЧИТАТЬ (id-list) ~ write => ПИСАТЬ (id-list) for=> ДЛЯ index-exp ДЕЛАТЬ body until => ПОВТОРИТЬ body ПОКА logical_exp call_func => ID (id-list) cond_op=> ЕСЛИ logical_exp TO body while => ПОКА logical_exp ДЕЛАТЬ body label => ID : stmt-list go_to => ПЕРЕЙТИ_НА idjabel idjabel => ID
index-exp => var := exp ДО exp | exp Д0ВНИЗ exp logical_exp => ( condition )
condition => l_exp < l_exp | l_exp <@062> l_exp | l_exp >- l_exp | l_exp =< l_exp | l_exp — l_exp | l_exp ИЛИ l_exp | l_exp И l_exp | l_exp XOR l_exp | HE l_exp l_exp => exp | condition body => stmt | НАЧ_БЛОК stmt-list КОН_БЛОК

Посмотрим внимательно на правило вывода, в левой части которого стоит начальный символ языка prog. Правая часть этого правила представляет собой сентенциальную форму, содержащую все необходимые элементы программы. На примере этой грамматики хорошо видно, что представляет собой алфавит языка программирования. По сути это совокупность лексем, которые программист использует для написания программы и которые в терминах языка являются терминальными символами, а также нетерминалов, которые имеют смысл в рамках грамматики. Более того, к терминальным символам относятся также символы ID (идентификатор), CHINT (целое число) и CHREAL (вещественное число). В программе им соответствуют Совершенно разные сочетания символов букв, цифр и разделительных знаков, например идентификаторы — chl, sab, masl; целые числа — 1, 24, 98584; вещественные числа — +33.5, 0.95е-3. С точки зрения синтаксиса эти разные по написанию объекты являются терминальными символами — идентификатором, целым числом, вещественным числом. Это ключевой момент. Мы
к нему еще вернемся, а пока давайте посмотрим, каким превращениям подвергается исходный текст программы, для того чтобы превратиться в форму, пригодную для машинного исполнения.

Описание процесса трансляции программы

Транслятор представляет собой программу, выполняющую анализ исходного кода на некотором языке программирования и формирующую объектный модуль. Процесс преобразования исходного кода называется трансляцией. Вместо термина «транслятор», часто употребляется слово «компилятор», и соответственно процесс преобразования называется компиляцией. Не вдаваясь в описание лишних подробностей, будем считать эти названия синонимами и в дальнейшем изложении использовать их исходя из своих пристрастий.
Для многих транслятор представляется как некий черный ящик, которому программист много раз на день доверяет выстраданную им программу. При общении программиста с транслятором возможны два варианта исхода: удачный, при котором на выходе транслятора формируется объектный модуль, и неудачный, когда транслятор обнаруживает в программе различные ошибки. Давайте заглянем в черный ящик, именуемый транслятором, и посмотрим, каким образом он работает. Конечно же, нашему взгляду будут доступны только общие принципы его функционирования, но мы их рассмотрим с той степенью детализации, чтобы можно было самим разработать нечто подобное.
Трансляция программы производится в несколько этапов.

1. 1. Лексический анализ.
   2. Синтаксический анализ.
   3. Генерация кода.

На каждом из этих этапов выполняется вполне определенная работа. В общем случае проблема компиляции заключается в поиске соответствия написанных программистом предложений структурам, определенным грамматикой, и генерации соответствующего кода для каждого предложения.
Итак, файл исходной программы подготовлен, после чего мы некоторым образом передаем его транслятору для обработки. Происходить это может двумя способами: посредством командной строки (возможно, с использованием утилиты make.exe) либо в интегрированной среде. По сути, для транслятора оба эти способа одинаковы, так как ядро транслятора для обработки этих файлов будет одно. Единственное отличие в том, что в первом случае программист явно формирует все необходимые ключи и параметры командной строки, а во втором случае он это делает неявно, путем настройки параметров интегрированной среды.

Лексический анализ

Цель лексического анализа — выделение и классификация лексем в тексте исходной программы. Программа, которая выполняет лексический анализ, называется сканером, или лексическим анализатором. Сканер производит посимвольное чтение файла с исходным текстом программы.
Полный набор лексем языка определен множеством терминальных символов в его грамматике. Среди них можно выделить изменяемые и неизменяемые лексемы. Неизменяемые лексемы в любой программе пишутся одинаково. Для грам-
матики псевдоязыка это такие лексемы, как: ПРОГРАММА, ПЕРЕМЕННЫЕ, НАЧ_ПРОГ, КОН_ ПРОГ, НАЧ_БЛОК, КОН_БЛОК, «.», «;», «:», «/», REAL, INTBYTE, INT_WORD, INTDWORD, «,», «:=», «=», «+», «-», «*», DIV, MOD, «(», «)», «[», «]», «<», «>», «==», ЧИТАТЬ, ПИСАТЬ, ДЛЯ, ДОДЕЛАТЬ, ПОКА, ДОВНИЗ, ЕСЛИ, ЕСЛИ, ДО, ТО, ПЕРЕЙТИ_НА, ПОВТОРИТЬ. «За бортом» остались три терминальных символа — ID, CH_INT, CH_REAL. Эти терминальные символы соответствуют идентификаторам, целым и вещественным числам. Естественно, что даже в пределах одной программы они будут различны. Задачей сканера как раз и является распознавание изменяемых и неизменяемых терминальных символов. С позиции логики обработки сканером удобно все терминальные символы отнести к одному из следующих классов (применительно к нашей грамматике псевдоязыка):

• идентификаторы — ID;
• ключевые слова - ПРОГРАММА, ПЕРЕМЕННЫЕ, НАЧПРОГ, КОН_ПРОГ, НАЧБЛОК, КОН_ БЛОК, REAL, INTJYTE, INTWORD, INT_DWORD, DIV, MOD, ЧИТАТЬ, ПИСАТЬ, ДЛЯ, ДОДЕЛАТЬ, ПОКА, ДОВНИЗ, ЕСЛИ, ЕСЛИ, ДО, ТО, ПЕРЕЙТИ_НА, ПОВТОРИТЬ;
• целые числа — CHINT;
• вещественные числа — CH_REAL;
• однолитерные разделители — «.», «,», «;», «:<@187>, «+»,«-», «*»,«/», «(»,«)», «=», «[», «]», «<», «>»;

В двулитерные разделители — «:=», «=», «>=», «=<».
Задача сканера — построить для каждого терминального символа его внутреннее представление. Делается это для того, чтобы убрать лишнюю информацию, подаваемую на вход синтаксического анализатора. Проведем аналогию. Все знают о твердом порядке слов в английском предложении. При этом не оговариваются конкретные слова, которые должны стоять на месте подлежащего, сказуемого, дополнения. Главное, чтобы слово, которое стоит, например, на месте подлежащего, было существительным или местоимением, то есть относилось к определенному классу. Сканер как раз и выполняет классификацию лексем, подаваемых на его вход. Он распознает, например, что очередная лексема является ключевым словом begin, после чего присваивает ей определенное целое значение и передает его далее. Если же сканер распознал на своем входе некоторый идентификатор, то он производит не просто замещение, но и некоторые другие действия. Чтобы подробнее разобраться со всем этим, необходимо понять состав и назначение структур данных, определенных внутри сканера.
Сканер работает с определенным набором таблиц, среди которых есть входные и выходные.
В общем случае сканер должен иметь две входные таблицы — таблицу лексем языка и таблицу классов литер. Таблица лексем языка содержит перечень всех лексем языка и соответствующих им целочисленных значений. Для нашей грамматики таблица может быть следующей:

Таблица классов литер используется только в процессе сканирования и предназначена для выяснения класса литеры, когда она выбирается сканером из входного потока. Лучше всего эту таблицу организовать в виде массива, элементы которого отражены на используемую кодовую таблицу (например, таблицу ASCII). Значение каждого элемента таблицы классов литер определяется классом литеры в кодовой таблице. В общем случае можно определить следующие классы литер:

• d - цифра;
• 1 — буква;
• b — литеры, которые игнорируются, к ним может относится, например, пробел;
• s1 — одиночные разделители: «.», «:», «(«, «)», «*»;
• s2 — особые одиночные разделители: «.», «+», «-»,«:», «=», «<», «>».

Последние разделители отличаются тем, что они могут быть как собственно одиночными разделителями, так и входить в состав литер лексем, состоящих из нескольких литер. Например, разделитель «:» является не только одиночным, но и первой литерой двухлитерного разделителя «:=», а литеры «.», «+» и «-» являются составной частью лексемы «вещественное число».
Количество выходных таблиц может быть различным и определяется сложностью входного языка. В минимальном варианте используют две или три таблицы: таблицу лексической свертки, таблицу идентификаторов и, возможно, таблицу констант. Рассмотрим пример программы на псевдоязыке:

ПРОГРАММА progl (1M14, #progl) ПЕРЕМЕННЫЕ (2)
INTBYTE 1 (6) (14. #i)
НАЧ_ПРОГ (26)
ДЛЯ i := О ТО 9 ДЕЛАТЬ (10Н14, #i)(24)(15. 0)(13)(15. 9Н11) ПИСАТЬ (i) (9)(12)(14, #i)(25)
КОНПРОГ (27)

Приведенная программа выводит на экран целые числа от 0 до 9, хотя в контексте нашего обсуждения это и не важно. После обработки сканером исходный текст программы преобразуется во внутреннее представление, которое показано справа для каждой строки. Становится понятным значение термина «лексическая свертка» — программа как бы сворачивается в некоторую унифицированную форму, теряя при этом свою индивидуальность. Каждая лексема замещена своим кодом. Идентификаторы замещены кортежами, первый элемент которых является кодом лексемы-идентификатора, а второй элемент — ссылкой на элемент таблицы идентификаторов, где содержится более подробная информация о данном идентификаторе. Ссылка может быть адресом элемента в таблице, но может быть удобнее, чтобы это было просто число, представляющее собой индекс в этой таблице. Это же касается и лексемы «целое число». Здесь возможны разные варианты: во-первых, можно организовать таблицу констант, подобную таблице идентификаторов; во-вторых, для простых применений константу можно разместить прямо в кортеже. В нашем примере для констант выбран второй вариант.
Можно предложить несколько способов организации таблицы идентификаторов. Самый простой и неэффективный — в виде массива указателей на списки переменной длины, элементы которого содержат символы идентификатора. Имена идентификаторов нужны лишь на этапе лексической свертки для выделения одинаковых идентификаторов. Важно понимать, что после выделения сканером идентификаторов и присвоения одинаковым из них ссылок на определенный элемент массива (таблицы) идентификаторов сами символьные имена уже не нужны. Если, конечно, не будет производиться формирование диагностических сообщений. Впоследствии эти указатели можно переориентировать для ссылок на ячейки с другой информацией, например с адресом области памяти, которая будет выделена для данного идентификатора на этапе генерации кода. Аналогично можно организовать и таблицы констант, если в этом возникнет необходимость. Это самые простые варианты организации подобных таблиц. Но исходя из опыта, полученного при изучении материала данной книги, можно организовать таблицу символов более эффективно — в виде лексикографического дерева или используя методы хэширования. Если используется лексическое дерево, то каждый узел этого дерева может состоять из следующих полей:

• уникальный номер — номер, который на последующих этапах трансляции
  будет идентифицировать данное символьное имя;
• указатель на список, содержащий символы идентификатора;
• указатель на список с номерами строк, в которых встретился данный идентификатор.

Впоследствии, когда имена идентификаторов не будут нужны, можно на основе этого дерева построить хэш-таблицу, доступ к элементам которой будет осуществляться на основе уникальных номеров. Кстати, для повышения эффек-
тивности процесса распознавания стоит все терминальные символы — ключевые слова языка, разделители и т. п. (за исключением id, chint и ch_rea1) — также свести в отдельное лексикографическое дерево или организовать хеш-таблицу.
Можно поступить по-другому. Этот вариант, который можно использовать для анализа ввода в командной строке и т. д., работает в случае, если сканер вызывается из синтаксического анализатора. Суть его в том, что сканер вызывается из синтаксического анализатора, когда последнему нужна очередная лексема. Сканер выделяет ее во входном потоке и выдает синтаксическому анализатору кортеж из двух элементов: кода лексемы и строки, содержащей саму лексему.
А как организовать сам процесс распознавания лексем входной программы? Для этого попробуем сформулировать некий обобщенный алгоритм построения сканера.

1. 1. Выделить классы лексем.
   2. Определить классы литер.
   3. Определить условия выхода из сканера для каждого класса лексем.
   4. Для каждого класса лексем поставить в соответствие грамматику класса 3.
   5. Для каждой грамматики, построенной на шаге 4, построить конечный автомат, который будет распознавать лексему данного класса.
   6. Выполнить объединение («склеивание») конечных автоматов для всех классов лексем.
   7. Составить матрицу переходов для «склеенного» конечного автомата.
   8. «Навесить» семантику на дуги «склеенного» конечного автомата.
   9. Выбрать коды лексической свертки для терминалов грамматики и формат таблицы идентификаторов.
   10. Разработать программу сканера.

Полностью реализовывать этот алгоритм для сканера транслятора упрощенного языка Паскаль мы не будем. Это не является предметом нашей книги. Нас интересуют прежде всего организация данных и возможности по работе с ними на ассемблере. Поэтому, для того чтобы пояснить подход к подобным задачам, мы остановим свое внимание на шагах 1-8 приведенного алгоритма.

Выделение классов лексем

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

• идентификаторы — ID;
• ключевые слова - ПРОГРАММА, ПЕРЕМЕННЫЕ, НАЧ_ПРОГ, КОНПРОГ, НАЧ_БЛОК, КОН БЛОК, REAL, INTJYTE, INT_WORD, INT_DWORD, DIV, MOD, ЧИТАТЬ, ПИСАТЬ, ДЛЯ, ДОДЕЛАТЬ, ПОКА, ДОВНИЗ, ЕСЛИ, ЕСЛИ, ДО, ТО, ПЕРЕЙТИ_НА, ПОВТОРИТЬ;
• целые числа — CH_INT;

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

Синтаксический анализ

После того как лексемы входного потока распознаны, транслятору необходимо удостовериться, что вся их совокупность является синтаксически правильной. Вопрос: зачем? Заглянем немного вперед и задумаемся о том, каким образом производится генерация кода. Если рассматривать этот вопрос схематично, то можно утверждать, что для каждого нетерминала грамматики существует некий шаблон кода, который подставляется в определенное место выходного кода. Настройка этого шаблона производится значениями лексем, распознанными сканером. Извлечь эту информацию можно, если соответствующая конструкция в исходном коде синтаксически правильна. В конечном итоге мы должны доказать, что вся программа синтаксически правильна.
Цель синтаксического анализа — доказать существование дерева грамматического разбора в контекстно-свободной грамматике G для входной цепочки s, состоящей из терминальных символов.
Существует много различных методов синтаксического анализа программ. Но главное понимать, что все они неявно стремятся доказать одно и тоже — существование синтаксического дерева для транслируемой программы. Ведь применительно к нашей грамматике не может блок описания переменных следовать где-то в середине или конце программы, за операторами, которые эти переменные используют. Кстати, посмотрите сейчас еще раз на правило грамматики, соответствующее начальному символу языка. В этом правиле определена общая структура программы и в ней видно место блока описаний переменных. Вместо списка стоит нетерминал. Можно нарисовать воображаемую дугу к правилу грамматики, соответствующему нетерминалу блока описания переменных, и т. д. То есть мы действительно начали строить грамматическое дерево. И если нам удастся его построить для данной программы, то последняя действительно синтаксически правильна. Если на каком-то шаге построения этого дерева у нас случится ошибка, допустим в том же блоке описания переменных программы вместо идентификатора будет стоять целое число, то дерево мы построить не сможем. То есть программа синтаксически неправильная. Можно формировать соответствующее диагностическое сообщение.
Таким образом, можно утверждать, что если возможно построение дерева трансляции для данного входного потока, то он синтаксически правилен. Понятно, что для другого текста программы дерево трансляции будет другое, но в лю-
бом случае листьями этого дерева будут лексемы программы, а корнем — начальный символ языка. Причем если совершить обход листьев дерева слева направо, то получим вытянутый в строку текст нашей программы.
Если судить по рисунку, то программа синтаксически правильная. Но каким бразом выясняет этот факт транслятор? Как отмечено выше, существует несколько методов выполнения синтаксического анализа. Все они делятся на два класса в зависимости от того, как они движутся по дереву трансляции во время разбора — сверху вниз или снизу вверх. Алгоритмы «сверху вниз» стремятся построить дерево трансляции начиная вывод от начального символа языка к анализируемой цепочке. И наоборот, алгоритмы «снизу вверх» строят дерево трансляции от анализируемой цепочки терминалов к начальному символу языка. Важно подчеркнуть, что на самом деле никакого дерева в памяти нет и не строится. Как показано выше, его структура заложена в правилах грамматики. Используя алгоритм конкретного метода синтаксического разбора и представленные определенным образом в памяти правила грамматики, мы и производим движение по воображаемому дереву трансляции.
На практике не исключены случаи комбинированного применения восходящих и нисходящих методов синтаксического анализа. Например, арифметические выражения удобно разбирать с помощью восходящих методов, а общий разбор программы делать нисходящими методами. В большинстве случаев достаточно одного универсального метода — метода рекурсивного спуска. Для краткости будем называть синтаксический анализатор распознавателем.

Метод рекурсивного спуска

Главное свойство нисходящих методов — их целенаправленность. Метод рекурсивного спуска — наиболее яркий и простой представитель этих методов. Основ ной его недостаток — сильная зависимость от конкретного языка. Программа распознавателя рекурсивного спуска представляет собой, по сути, набор рекурсивных процедур — по одной для каждого из нетерминалов грамматики. Первой получает управление процедура, соответствующая нетерминалу — начальному символу языка. Эта процедура уже знает, что она должна делать. Если первый символ в этом правиле — терминал, то процедура знает об этом и ждет его. Это ожидание заключается в том, что процедура сравнивает код терминала, который должен быть первым, согласно правилу, с кодом первой лексемы из лексической свертки входной строки. Если они совпадают, то процесс разбора идет дальше. Если они не совпадают, то фиксируется ошибка. Если очередным символом правила должен быть нетерминал, то в этом месте вызывается соответствующая ему процедура. Эта процедура тоже построена исходя из правила грамматики для этого нетерминала, поэтому ее действия также уже предопределены. И так будет продолжаться до тех пор, пока разбор не вернется к первому правилу, то есть управление вернется процедуре, соответствующей правилу грамматики для начального символа языка. В нашем случае последним должен быть проанализирован факт того, что последний символ во входной строке — терминал кон_прог.
При реализации метода рекурсивного спуска в чистом виде возможны сложности. Посмотрим на правила грамматики, подобные следующим:

dec-list => dec | dec-list ; dec
id-list=> ID | id-list . ID
term => factor | term * factor | term div factor
strut-list => stmt | stmt-list ; stmt
Видно, что эти правила леворекурсивны. Например, рассмотрим следующее правило:
id-list => ID | ID-LIST , ID

В этом правиле вторая альтернатива начинается с нетерминала ID-LIST, то есть в процессе разбора при обращении к процедуре, соответствующей этому нетерминалу, получится бесконечный цикл. Ее необходимо устранить. Для этого соответствующие правила подправляются следующим образом:

dec-list => dec | dec-list ; dec id-HSts» ID I {. ID}
stmt-list => stmt | {: stmt} exp => term {+ term | - term}
term => factor {* factor | div factor}

Теперь для принятия решения о дальнейшем пути выполнения рекурсивной процедуры необходимо просматривать один символ вперед. Если он совпадает с тем, что в правиле, то процедура рекурсивно вызывается снова. Если этот символ любой другой, то производится возврат из этой процедуры. Таким образом, процесс написания программы неявно представляет собой строительство дерева разбора начиная от его корня — начального символа языка. То есть это действительно нисходящий метод.
Остается заметить еще одно достоинство метода рекурсивного спуска. Если очередная языковая конструкция распознана, то почему бы сразу в соответствующей рекурсивной процедуре не «навесить» семантику, то есть генерацию кода.
Но метод рекурсивного спуска не всегда применим. В сложных случаях, когда имеется скрытая левая рекурсия, необходимо применять более сложные методы для ее устранения или замены правой рекурсией.
После этого обсуждения мы готовы написать распознаватель, но делать этого не будем, так как цель, достижению которой был посвящен материал данного раздела, достигнута. Все остальное — техника программирования. Остается добавить, что разговор о проблемах трансляции мы продолжим в главе 10.