Способы получения одних цепочек символов из других

1 Это можно сделать непосредственно, т.е. за одну операцию. Условное обозначение Þ.

Например, dÞh означает, что цепочку символов h можно получить из цепочки d за одну операцию.

Пример. Есть цепочка d=aAb и h=anb. Здесь, a,n,b - терминальные символы (обозначены строчными буквами), а А – нетерминальный символ. Пусть среди множества правил Р есть такое: A®nЄР. То есть нетерминальный символ АЄN можно заменить на терминальный n. Таким образом, за одну операцию из d можно получить цепочку h.

2 Одну цепочку из другой можно получить не за одну операцию. Условие обозначения Þ*

Например, a₀ Þ*a_n

Это имеет место, если a₀ = a_n , или существует последовательность непосредственно получаемых цепочек таких, что a₀ Þ a₁ Þ a₂ Þ… a_n-1 Þ a_n

Формальное определение языка

Способы получения цепочек символов необходимы, чтобы формально дать определение языка L(G), описываемое заданной грамматикой G. Язык L(G) – это множество цепочек w терминальных (и только терминальных!) символов, выводимых из начального (стартового, главного) нетерминального символа S. L(G)={w|S Þ*w,w –терминальные цепочки}.

Вертикальная черта после w в выражении означает, что w получены при условии что они выводятся из S. А звездочка означает, что этот вывод может происходить за произвольное количество операций. При этом используется множество P правил, описанное в грамматике G.

Ниже приводятся примеры грамматики и описываемые ими языки.

Пример 1 G=(T,N,P,S)

T={x, y, w, z} – алфавит терминальных символов. Только эти символы можно использовать.

N={S, A, B} – множество нетерминальных символов, из которых S – главный (стартовый) нетерминальный символ. Именно с него должен начинаться вывод цепочек (слов) в соответствии с множеством правил вывода P .

p={S®AB, A®x,A®y, B®w, B®z}.

Эти правила означают, что S можно заменить последовательностью нетерминальных символов AB. A®x, A®y означает, что А можно заменить на x или на y и т.д., осуществляя эти замены, получаем цепочки w из терминальных символов, составляющих формальный язык L(G).

L(G)={xw, yw, xz, yz}.

Только эти четыре цепочки (слова) и составляют язык, описываемый заданной грамматикой G.

Расширенные грамматики

Существуют т.н. расширенные грамматики. Они порождают те же языки, что и рассмотренные выше грамматики, но являются более наглядными.

Расширенные грамматики задаются парами

A_i ® r_i ,

где A_i ЄN – i-й нетерминальный символ,

r_i – i-е регулярное выражение в алфавите N U I.

Нетерминальный символ первой пары является ГЛАВНЫМ (стартовым)для вывода цепочек.

Например, расширенная грамматика, эквивалентная описанной в примере выше, имеет вид:

S®AB ,

A®x|y ,

B®w|z .

Напомним, что вертикальная черта читается как “или”. То есть А может быть заменена на x или y, а В – на w или z.

Пример 2

Алфавит терминальных символов

Т={вино, коньяк, каша, борщ, мясо, кофе, чай}

Алфавит нетерминальных символов

N={ОБЕД, АЛКОГОЛЬ, ЕДА, ПИТЬЕ}

ОБЕД®АЛКОГОЛЬ ЕДА ПИТЬЕ

АЛКОГОЛЬ ® коньяк | вино

ЕДА ® борщ каша | мясо

ПИТЬЕ ® чай | кофе

В первой паре описан главный нетерминальный символ ОБЕД. Он описывается как последовательность из АЛКОГОЛЬ, ЕДА, ПИТЬЕ. В свою очередь, АЛКОГОЛЬ – это или коньяк, или вино.

ЕДА состоит из борща, за которым следует или каша, или мясо.

ПИТЬЕ – это или чай, или кофе.

С помощью упомянутых ранее действий над цепочками можно выразить самые разные варианты для нетерминального символа ОБЕД.

Например, ОБЕД ® АЛКОГОЛЬ * ЕДА ПИТЬЕ означает, что АЛКОГОЛЬ может повторяться в цикле нуль и более раз. После этого идут ЕДА и ПИТЬЕ.

Рассмотрим также другие варианты.

Например, АЛКОГОЛЬ ® КОНЬЯК + вино* означает, что должен быть хотя бы раз выпит коньяк, а затем может циклически приниматься вино. Количество этих циклов от нуля и более раз.

Или еще вариант: ЕДА ® борщ * мясо + каша

Борщ может употребляться от нуля и больше раз. Затем обязательно хотя бы один раз мясо и после этого – каша.

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

Лекция 2

Задачи анализа

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

Например, цепочка [[x]] принадлежит языку L(G₂), описанному грамматикой G₂.

G₂=(T₂, N₂, P₂, A), где

T₂ = {х, +, [, ]}

N₂ ={А,В}

P₂ = {А®х, А®[В], В®А, В®В+А}

Действительно, заданную цепочку можно получить, применив последовательно по одному из правил вывода, заданного в Р₂.

АÞ [В]Þ [А]Þ [[В]]Þ [[А]]Þ [[х]]

Следовательно, цепочка [[х]] принадлежит формальному языку L(G₂).

Различают две стратегии: стратегия анализа сверху вниз и снизу вверх. При анализе сверху вниз для построения вывода заданной цепочки начинают с ГЛАВНОГО нетерминального символа и выбирают правила из заданного множества так, чтобы прийти к заданной цепочке w.

В примере [[х]] в грамматике G₂ главный нетерминальный символ А. Среди заданного множества правил вывода для А есть два: А ® х и А ® [В]. Первое из них не дает возможности вывести [[х]]. Берем А ® [В], то есть А заменяем на [В]. Теперь нужно выбирать из двух правил вывода для В.

В ® А и В ® В+А.

Выбираем В ® А, заменяем в [В] В на А и получаем [А]. Вновь из двух правил вывода для А выбираем А ® [В]. Заменяем в [А] А на [В]. Получаем [[В]]. Вновь из двух правил для вывода В выбираем В ® А и заменяем в [[В]] В на А. Получим [[А]]. И, наконец, из двух правил вывода для А выбираем А ® х. Заменяем в [[А]] А на х и получаем требуемую цепочку [[х]]. Таким образом, доказано, что заданная цепочка действительно принадлежит языку, определяемому грамматикой G₂.

При анализе сверху вниз основная проблема в определении необходимого правила V ® a_i для построения следующего шага вывода цепочки w, когда в найденной части А Þ* nVb известны левый нетерминальный символ V и n правил вывода V ® a₁ , V ®a₂, …V ® a_n с левой частью V. Решение этой проблемы, в частности, возможно с помощью алгоритма LА(1) – анализа, который определяет необходимое правило V ® a_i в зависимости от первого еще не распознанного символа х в цепочке w.

Осуществляется LA(1) – анализ путем создания для нетерминалов процедур анализа. Эти процедуры, как правило, оказываются взаимно рекурсивными и часто неэффективными.

Для многих грамматик LA(1) – анализ в таком виде не используется. Тогда приходят к расширенным грамматикам или к синтаксическим диаграммам (графикам).

Синтаксические диаграммы

Это ориентированный граф с двумя фиксированными вершинами: входной, из которой дуги только выходят, и выходной, в которую дуги только входят.

Дуги этого графа могут быть помечены терминальными и нетерминальными символами. В расширенной диаграмме с терминальным Т и нетерминальным N алфавитами каждому нетерминалу А и его правилу вывода А ® a, где a - регулярное выражение в алфавите T U N, отвечает одна синтаксическая диаграмма. При обозначении дуг, помеченных терминальными символами, условились эти символы писать строчными буквами и заключать в окружность.

Нетерминальные символы условились писать заглавными буквами и размещать в прямоугольнике.

Регулярное выражение будет обозначаться греческими буквами внутри ромба.

На рисунке показаны примеры изображения дуг, помеченных терминальным символом а, нетерминальным А и регулярным выражением a.

Рисунок 1

Алгоритм LА(1) – анализа может быть применен при условиях, что в синтаксических диаграммах нет непомеченных дуг от входной вершины к выходной и в каждом разветвлении ветки начинаются с неодинаковых последующих терминальных символов.

По синтаксической диаграмме строится функция анализа выводимых из нетерминала цепочек символов.

Прохождению дуги, помеченной терминальным символом а, отвечает распознавание этого символа (т.е. а) в предъявленном для анализа слове и сдвиг на следующий символ в этом слове (чтение очередного символа из слова).

Прохождению дуги, помеченной нетерминальным символом А, отвечает вызов функции распознавания цепочек, которые выводятся из А. Перед вызовом этой функции предварительно должен быть прочитан первый терминальный символ х, который выводят из А, т.е. АÞ* х…Функция успешно анализирует цепочку w, выводимую из нетерминала А, если в соответствии с синтаксической диаграммой, прочитав посимвольно всю цепочку w, удается попасть из входной вершины в выходную.

Лекция 3

Введение в компиляцию

Все изложенные выше сведения о грамматиках и формальных языках необходимы для создания трансляторов.

Транслятором называется компьютерная программа, которая осуществляет переход программы на входном языке (например) алгоритмическом) на эквивалентную ей объектную программу.

Если входной язык высокого уровня (алгоритмические языки Паскаль, Си и др.), а выходной – машинные коды или АССЕМБЛЕР (т.е. машинно-ориентированный язык), то такой транслятор называется КОМПИЛЯТОРОМ.

Интерпретатор - разновидность транслятора, который переводит программу на язык простых промежуточных команд и выполняет их.

Препроцессор – транслятор, осуществляющий перевод с одного языка высокого уровня на другой язык тоже высокого уровня.

Итак, обобщая сказанное, можно определить, что транслятор – компьютерная программа, которая читает последовательно символ за символом текст некоторой другой компьютерной программы на каком-то алгоритмическом языке и осуществляет перевод этой программы на другой (выходной) язык. В случае, если транслятором является программа-компилятор, после перевода с алгоритмического языка будет получена компьютерная программа или на АССЕМБЛЕРЕ, или в виде последовательности машинных команд в кодах (объектный модуль). Один или несколько объектных модулей обрабатываются программой - компоновщиком. В результате создается готовая к исполнению программа.

Компилятор осуществляет перевод программы на алгоритмическом языке в программу, состоящую из последовательности некоторых промежуточных команд. Назначение и количество этих команд определяет программист, создающий интерпретатор.

Сразу же после окончания перевода интерпретатор, в отличие от компилятора, выполняет полученную программу.

Структура компилятора

Рисунок 2

На рис. представлена структура компилятора. Здесь:

ЛА – лексический анализ;

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

ГПК – генерация промежуточного кода;

ОК – оптимизация кода;

ГК – генерация кода.

На всех этапах осуществляется обработка ошибок и происходит заполнение различных таблиц.

Рассмотрим более подробно некоторые этапы обработки исходной программы на алгоритмическом языке.

ЛА – лексический анализ.

Лексема – это один или несколько символов, имеющих некоторый самостоятельный смысл.

В процессе лексического анализа считываемые последовательно из программы на входном (алгоритмическом) языке символы объединяются в лексемы.

Конкретно различаются следующие лексемы:

1) служебные слова;

2) идентификаторы;

3) знаки для обозначения операций, а также другие специальные символы;

4) числа;

5) признак конца считываемого файла.

Следует вспомнить, что служебные (зарезервированные) слова нельзя использовать в программе на алгоритмическом языке в качестве идентификаторов для обозначения переменных и функций. Например, для языка Си - это if, do, while, for, return, goto, char, int, float и др. Поэтому программа-транслятор должна “уметь” отличить эти зарезервированные служебные слова.

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

Проходы компилятора

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

Количество проходов определяется особенностями алгоритмического языка и ПЭВМ.

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

Лекция 4

Алгоритмический язык SPL

Используем основные методы компиляции для реализации однопроходного интерпретатора. Этот интерпретатор, написанный на языке Си, должен прочитать, перевести на язык промежуточных команд и выполнить программу, написанную на алгоритмическом языке SPL. SPL (Simple Programming Language) – простой язык программирования. Это учебный язык высокого уровня, который напоминает Паскаль и Си. Ему присущи все особенности алгоритмических языков высокого уровня за исключением того, что работает он только с одним типом данных – с целыми числами.

Язык SPL, как и любой алгоритмический язык , являет собой набор символов и правил для ввода информации в ЭВМ.

Символы

1) Буквы: A¸Z, a¸z (только латинского алфавита);

2) Цифры: Ƹ9 ;

3) Специальные символы: +, -, *, /, %,(, ), ,,=,’\ ‘,’\n’,’\t’ – всего 13 символов.

Из этих символов образуется конструкция языка SPL.

Идентификаторы

Это имена переменных, констант и функций. Идентификатор являет собой последовательность букв или букв и цифр, но первой должна быть буква. Количество символов от 1 до 40, символы пробела (‘\ ‘ ), перехода на новую строку (‘\n’) и табуляции (‘\t’) в идентификаторе недопустимы .

Константы

Только целые числа.

Описание констант предваряется служебным словом const. Затем следует имя константы, знак ‘=‘ (без апострофов) и значение константы (целое число). Одна константа от другой отделяется запятой. В конце описания должна быть точка с запятой.

Пример, сonst a=12, b=4, d=0;

Переменные

Как и константы, переменные только целого типа. Имеются глобальные и локальные переменные. Как и обычно, глобальные переменные могут использоваться всеми функциями, а локальные – только теми функциями, в которых описаны.

Описание переменных имеет вид:

int имя_переменной_1, имя_переменной_2 ;

Пример, int x, y, z, teta;

Выражения

В выражениях применяются знаки +, -, * (умножить), / (деление), % (остаток от деления).

Служебные слова

Напомним, что это зарезервированные слова, которые нельзя использовать в качестве идентификаторов. Это следующие 11 слов: begin, end, read, print, return, if, then, while, do, int, const.

Функции

Как и в языке Си, программа на SPL состоит из одной или нескольких функций. Количество функций и их имена определяет программист, но одна функция должна обязательно называться main, т.к. именно с неё будет начинаться выполнение программы.

Описание программы имеет вид:

Имя_функции (формальные_параметры через запятую )

begin

описание локальных констант и переменных;

операторы

end

В отличие от Паскаля после end в конце программы точка не ставится.

Операторы заканчиваются точкой с запятой. Однако перед end точку с запятой ставить нельзя. Оператор условной передачи управления if имеет вид:

if условие then последовательность операторов end

В качестве условия может быть имя переменной или выражение. Если значение переменной или выражения больше нуля, тогда выполняется последовательность операторов между then и end. Иначе- переход на следующий за if оператор.

Оператор цикла

Имеет вид:

whileусловие do

последовательность операторов

End

Как и для if “условие” может представлять собой переменную или выражение. Если переменная или результат вычисления больше нуля, тогда вычисляется последовательность операторов между словами do и end. После этого вновь проверяется “условие”. Если результатом проверки условия оказалось число £ 0, то происходит выход из цикла.

При использовании функций в языке SPL результаты их работы можно возвращать или с помощью оператора return выражение, или через глобальные переменные, которые описываются в начале программы вне области действия какой-либо из функций. Как и для других языков высокого уровня, в SPL допускаются рекурсии, когда функция может вызывать саму себя.

Ниже приводится пример программы на SPL, в которой, кроме главной функции main( ), также используется функция возведения в степень а^b. Назовем ее exp ( ).

exp (а, b)

begin

int z;

z=1;

while b do

if b %2 then z=z*a end;

a=a*a;

b=b/2

end;

return z

end

main ( )

begin

int x, y;

read x;

read y;

print exp (x, y)

end

В главной функции описаны и введены с клавиатуры две локальные переменные x, y. Затем в строке print exp (x, y) происходит вызов функции exp ( ), в которую вместо формальных параметров a и b подаются соответствующие фактические параметры x и y. Функция exp ( ) с помощью оператора return z возвращает в main ( ) результат, который выводится на экран.

Алгоритм возведения a^b предлагается рассмотреть самостоятельно, например вычисляя 2⁷.

Лекция 5

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

Вначале составим программу на языке Си, которая предназначена только лишь (!) для распознавания лексем в тексте программы на языке SPL, а также для размещения идентификаторов в специальной таблице TNM. Эта таблица представляет собой глобальный одномерный массив

char TNM [400];

В процессе лексического анализа распознаются лексемы:

1) служебные слова;

2) знаки операций и разделители;

3) целые числа;

4) идентификаторы;

5) признак конца файла.

В программе каждой лексеме ставится в соответствие целое число. Знаки операций и разделители закодированы литеральными константами ‘+’, ‘-‘, ‘*’, ‘/’, ‘%’, ‘=’, ‘(‘, ‘)’, ‘,’, ‘;’.

Каждой из них соответствует целое число из таблицы кодов ASCII (М. Уэйт, С. Прата, Д. Мартин Язык Си.- М: “Мир” ,1988 .- С.512).

В таблице кодов ASCII также закодированы целыми числами символы букв и цифр. Обычно в этой таблице приводятся коды 256 символов.

Для служебных слов имена лексем выбирает программист. Предлагается эти лексемы обозначать соответствующими заглавными буквами с буквой L в конце. Например, служебным словом if и while имена лексем соответственно IFL, WHILEL и т.д. А связь с целыми числами определяется с помощью перечисляемых констант целого типа.

enum {BEGINL=257, ENDL, READL, PRITL, RETRL, IFL, THENL, WHILEL, DOL, INTL, CONSTL, NUMB, IDEN };

Здесь NUMB – лексема для целого числа;

IDEN – лексема для идентификатора.

Благодаря применению enum {}, лексема BEGINL получила числовое значение 257, ENDL – 258 и т.д. Таким образом, при написании программы нет необходимости помнить, что лексема BEGINL закодирована числом 257, а ENDL – 258. Везде, где нужно сослаться на эти лексемы, удобнее писать BEGINL, ENDL и т.д., а вместо них будут подставляться числа 257, 258 и т.д.

Кроме перечисленных лексем также используются признак конца файла EOF. В файле stdio.h есть директива препроцессора #define EOF – 1 . Из нее видно, что EOF закодирован – 1.

Текст программы на Си для лексического анализа программы на SPL приведен в виде файла part1.c.

Целесообразно привести некоторые пояснения к этой программе. В ней используются глобальные переменные и приведенные выше в enum {} перечисленные константы.

int lex; //распознанная лексема (целое число)

int lval; // значение лексемы. Для константы это числовое значение, а для идентификатора – адрес в таблице идентификаторов TNM

int nst=0; // номер считываемой строки в программе на языке SPL

char nch=’\n’; // считываемый символ из программы на SPL

char TNM [400]; // таблица идентификаторов

char * ptn=TNM; // указатель на первый свободный элемент в таблице

идентификаторов. В самом начале он стоит на

TNM [0], т.к. имя массива TNM в языке Си

является адресом его самого первого (т.е. нулевого)

элемента.

FILE * PF; // указатель на файл с текстом программы на языке SPL

FILE * padres // указатель на файл, в который будут заносится

адреса идентификаторов в таблице TNM.

В программе part1.c при вызове функции main () используются параметры. Заголовок функции main ( ) имеет вид:

void main (int av, char * av [ ])

Здесь ac – количество параметров (символьных строк);

char* av [ ] – массив указателей. В этот массив заносятся строки символов.

Конкретно, в av [0] автоматически заносятся имя файла с готовой для исполнения программой (например , part1.exe).

В av [1] следует самостоятельно занести имя файла с текстом программы на языке SPL. Например, var2.s

Для этого необходимо, находясь в среде Borland C++ , вызвать в верхнем меню Run/arguments и нажать клавишу “Enter”. Появится диалоговое окно, в которое следует ввести требуемое имя файла. В данном примере это var2.s. После этого вновь нажать “Enter”. Предполагается, что var2.s находится в текущей директории. Если нужно обеспечить обращение к этому файлу при запуске Borland C++ из другой директории, то следует привести полный путь и ввести, например, C:\\USER\\SPL\\var2.s part1.s ¿

Для лучшего понимания работы лексического анализатора part1.c, предлагается рассмотреть блок-схемы отдельных его функций.

Блок-схема функции

void main (int ac, char * av [ ])

Вначале проверяется количество параметров ac. Должно быть не меньше двух строк символов, например, part1.exe в av [0] и var2.s в av [1]. Если параметров меньше двух, происходит остановка работы программы. Иначе открывается файл для чтения с текстом на SPL. В примере это var2.s , и его имя находится в av [1]. Если файл открылся, то происходит вызов функции get ( ), которая является “поставщиком” лексем.

нет

нет

да

да

да

nch = getc (PF)

lex=nch

nch=getc (PF)

nst ++

Блок-схема функции void get ( )

В функции get () блок №1 в интерпретаторе должен быть if(nch==EOF)

{ lex=EOF;

return;

}

Однако программа part1.c предназначена только лишь для того, чтобы прочитать текст программы на SPL, распознать лексемы, а идентификаторы занести в специальную таблицу идентификаторов char TNM [400]. Поэтому в данной программе в функции get ( ) блок №1 являет собой цикл while (nch!=EOF). Он позволяет прочитать весь текст программы на SPL до конца файла. Далее идет цикл while(isspace(nch)), позволяющий пропускать символы пробела, табуляции, перехода на новую строку и на новую страницу.

Если символ nch, прочитанный из файла с помощью функции get (), не является одним из перечисленных выше, то происходит его распознавание с вызовом функции number( ) или word( ).

Если nch является одним из перечисленных специальных символов, например, ‘(’, ‘)’, ‘+’ и т.д., то лексема получает соответствующее значение, считывается новый символ и происходит возврат в цикл (блок №1). В противном случае выдается сообщение о недопустимом символе и происходит выход из программы.

Блок-схема функции void number ()

Блок №1 представляет собой цикл for ( ). В нем значение лексемы lval вначале обнуляется. Затем проверяется, что nch - цифра. Если это так, то происходит вычисление нового значения lval в блоке №2, старое значение lval умножается на 10, к нему прибавляем результат вычитания из кода прочитанной цифры (nch) кода нуля. В таблице кодов ASCII код нуля в “10” системе равен 48, код “1” – 49, код “2” – 50 и т.д. Соответственно в “16”-ричной системе – (30)₁₆, (31)₁₆, (32)₁₆ и т.д.

Таким образом, разница кодов позволяет получить прочитанную цифру.

Предположим, из программы на SPL считывается константа 541.

По первой цифре “5” будет вызвана функция number (). lval=0. nch содержит код цифры “5”, т.е. (35)₁₆. Естественно, что при проверке условия, является ли содержимое nch кодом цифры, ответ будет положительным. В результате происходит переход к блоку №2. В нем вычисляется lval=10*0+(35)₁₆ – (30)₁₆ =5. После этого происходит возврат в цикл и считывается из файла новое значение nch. Это код (34)₁₆ цифры “4”.

Теперь в блоке №2 lval=10*5+(34)₁₆ – (30)₁₆ =54.

После считывания кода цифры “1” lval=10*54+(31)₁₆ – (30)₁₆=541.

После того, как очередной прочитанный символ окажется не цифрой, происходит выход из цикла. Лексема получает значение NUMB, и происходит выход из функции.

Блок-схема функции void word ()

П

Блок №2 реализуется в виде цикла for. В указатель p заносится адрес tx[0]. Затем проверяется условие, что nch буква или цифра. Если это так, то реализуется блок №3. по адресу в указателе p, т.е. в tx[0] заносится символ nch. После этого значение p увеличивается на 1, то есть в р находится адрес tx [1]. Происходит возвращение в цикл. Считывается новое значение nch. Если это буква или цифра, вновь выполняется блок №2. Теперь уже символ nch заносится в tx [1], после чего в р становится адрес tx [2] и т.д. Если прочитанный символ nch не буква и не цифра, происходит выход из цикла. В очередной элемент массива tx заносится ‘\0’ – признак конца строки символов. В tx сформирована некая последовательность букв или букв и цифр. Теперь предстоит проверить, что она собой являет. Это может быть одно из служебных (зарезервированных) слов, перечисленных в массиве char*serv []

Проверка выполняется в цикле (блоки №5 и №6). В случае совпадения строки символов tx и одного из служебных слов переменная lex получает значение соответствующего элемента из массива int cdl [ ].

Например, если в tx находится строка символов end, то она совпадает с элементом “end” из serv[1]. В результате лексема lex=ENDL, т.е. lex=258 (см. enum={BEGINL=257, ENDL…};).

Если содержимое не совпало ни с одним служебным словом, значит это идентификатор переменной или функции. В этом случае lex=IDEN, т.е. 269, и его необходимо занести в таблицу идентификаторов char TNM [400]. Для этого вызывается функция add (tx). Она возвращает указатель char*. Поэтому, чтобы присвоить возвращаемый адрес переменной целого типа int lval, применяется явное преобразование типа lval=(int) add (tx).

Блок-схема функции char*add(char*nm)

При вызове функции add (char*nm) вместо формального параметра nm передается фактический параметр tx (последовательность символов - идентификатор). В блоках №2 и №3 в цикле осуществляется проверка, не было ли ранее занесено в TNM этот идентификатор. Для этого используется указатель char*p. В блоке №2 вначале в p заносится TNM, т.е. адрес TNM [0]. Затем проверяется условие p<ptn. Следует вспомнить, что char*ptn был описан выше в качестве глобального указателя на первый свободный элемент в таблице идентификаторов TNM. Если p<ptn, то выполняется сравнение строк, прочитанных из TNM по адресу в р и переданных в функцию add ( ). В случае совпадения происходит возвращение адреса, где этот идентификатор был ранее записан. При несовпадении происходит изменение адреса на длину строки только что сравниваемого из TNM идентификатора плюс один символ на ‘\0’.

p+=strlen (p) +1.

После этого вновь проверяется условие p<ptn и т.д.

Если условие p<ptn не выполнилось, это означает, что проверены все ранее записанные в TNM идентификаторы. Тогда нужно изменить значение указателя ptn на количество символов заносимого в таблицу идентификатора плюс один.

ptn+=strlen(nm)+1.

Кроме того, нужно проверить, не выйдет ли новое значение ptn за пределы таблицы TNM. Все это оформлено в виде оператора

if ((ptn+=strlen(nm)+1)>TNM+400)

{

puts(“Переполнение таблицы TNM”);

exit (1);

}

return (strcpy(p, nm));

Если переполнения нет, то вызывается функция копирования строк strcpy( ), которая строку nm скопирует в р, и адрес вернет в функцию word( ).

Лекция 6