Элементы компиляции программ
Рассмотрим еще одну грамматику для языка идентификаторов Gident.
Gident-{Vt-(.. +. – . е. 0. 1. 2. 3. 4. 5. 6. 7. 8, 9). VrHreal. S. M. N. К. Т), Р, 2=(< real >)}
Множество правил Р грамматики Gident:
Gident › letter| ident letter | ident figure letter › A|B|C|… X|Y|Z figure › 0|l|2|…8|9
Видно, что это тоже грамматика языка класса 3.
А теперь приведем пример грамматики, генерирующей язык класса 2. С ее помощью смоделируем псевдоязык, похожий на Pascal, который мы используем в нашей книге для пояснения некоторых алгоритмов:
Vt=(Программа, ПЕРЕМЕННЫЕ, НАЧ_ПРОГ. КОН_ПРОГ, НАЧ_БЛОК. КОН_БЛОК. "."
.ID. CHJNT. СН_ REAL. ":".":". "/". REAL. INTJYTE. INT_WORD. INT_OWORD.
",".":"". "="."+"."-"."*". DIV. MOO. "(". ")". "[". "]". "<".">", "==",">="."=<".
ЧИТАТЬ, ПИСАТЬ, ДЛЯ. ДОДЕЛАТЬ. ПОКА. ДО.ВНИЗ, ЕСЛИ. ЕСЛИ. ДО. ТО. ПЕРЕЙТИ_НА. ПОВТОРИТЬ).
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. С точки зрения синтаксиса эти разные по написанию объекты являются терминальными символами – идентификатором, целым числом, вещественным числом. Это ключевой момент. Мы к нему еще вернемся, а пока давайте посмотрим, каким превращениям подвергается исходный текст программы, для того чтобы превратиться в форму, пригодную для машинного исполнения.
Описание процесса трансляции программы
Транслятор представляет собой программу, выполняющую анализ исходного кода на некотором языке программирования и формирующую объектный модуль. Процесс преобразования исходного кода называется трансляцией. Вместо термина "транслятор", часто употребляется слово "компилятор", и соответственно процесс преобразования называется компиляцией. Не вдаваясь в описание лишних подробностей, будем считать эти названия синонимами и в дальнейшем изложении использовать их исходя из своих пристрастий.
Для многих транслятор представляется как некий черный ящик, которому программист много раз на день доверяет выстраданную им программу. При общении программиста с транслятором возможны два варианта исхода: удачный, при котором на выходе транслятора формируется объектный модуль, и неудачный, когда транслятор обнаруживает в программе различные ошибки. Давайте заглянем в черный ящик, именуемый транслятором, и посмотрим, каким образом он работает. Конечно же, нашему взгляду будут доступны только общие принципы его функционирования, но мы их рассмотрим с той степенью детализации, чтобы можно было самим разработать нечто подобное.