3.5. Удаление из грамматики бесполезных нетерминалов

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

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

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

Очищенная от бесполезных нетерминалов грамматика называется приведенной. Заметим, что рассмотренный способ удаления бесполезных нетерминалов можно применить не только к А-грамматикам, но и к КС-грамматикам.

3.6. Лексический анализатор

Лексемы языка программирования, которые можно задавать А-грамматикой и которые должен распознавать лексический анализатор:

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

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

3) изображения констант (целых и вещественных чисел, символьных строк и др.);

4) составные символы (:=, <=, >= и др.);

6) одиночные символы языка программирования (. , ; : [ ] + – / и др.);

5) пробелы, символы перевода строк и другие символы редактирования текста;

6) комментарии.

При этом некоторые лексемы (пробелы, комментарии) должны пропускаться, а для остальных лексем должна быть сформирована семантическая информация.

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

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

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

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

Пример 4. Составим грамматику, таблицу переходов ДКА и семантические программы для распознавания следующих лексем:

1) имен и/или служебных слов, вначале будет формироваться имя, а затем проверяться по таблице совпадение его с каким-либо служебным словом, буквы в них – заглавные латинские;

2) целых чисел без знака;

3) составного символа «:=»;

4) строк символов (в кавычках);

5) пробелов;

6) одиночных символов языка;

7) концевого символа _┴ .

Входные символы при этом объединим в следующие группы (в кавычках «» записано обозначение группы в таблице):

– заглавные латинские буквы «б»;

– цифры 0, 1, …, 9 «ц»;

– двоеточие «:»;

– равно «=»;

– кавычка «’»;

– пробел « »;

– другие символы языка (запятая, точка, + и др.) «с»;

– концевой символ «_┴»;

– все другие символы, не являющиеся символами языка, «др».

Среди нетерминалов (состояний ДКА) особо выделим:

S – начальное состояние;

F – правильное заключительное состояние;

О – ошибочное заключительное состояние.

Получившаяся таблица переходов представлена в табл. 4. Благодаря использованию второго заключительного состояния в построенном ДКА нет тупиков – для всех пар (текущее состояние, входной символ) предусмотрены переходы.

Табл. 4

	«б»	«ц»	«:»	«=»	«’»	« »	«c»	«др»	«┴»
S	I	C	A	F	T	S	F	O	F
I	I	I	F	F	F	F	F	F	F
C	D	C	F	F	F	F	F	F	F
A	F	F	F	F	F	F	F	F	F
T	T	T	T	T	F	T	T	T	O
D	D	D	O	O	O	O	O	O	O

В семантических программах будут использоваться следующие переменные:

C – массив символов, содержащий входной текст;

i – номер очередного символа входного текста;

x – распознанное целое число;

st – накопленная строка символов или имя;

typ – тип распознанной лексемы:

0 – концевой символ «_┴»;

1 – имя,

2 – целое число,

3 – строка символов,

11 – символ :=,

40, …, 93 – другие символы языка, указан код ASCII,

101, …, 200 – служебные слова языка,

–1 – ошибка в лексеме.

Таблица номеров семантических программ представлена в табл. 5.

Табл. 5

	«б»	«ц»	«:»	«=»	«’»	« »	«c»	«др»	«┴»
S	1	3	4	5	6	4	5	7	8
I	2	2	9	9	9	9	9	9	9
C	4	11	12	12	12	12	12	12	12
A	13	13	13	14	13	13	13	13	13
K	15	15	15	15	16	15	15	15	10
D	4	4	10	10	10	10	10	10	10

Далее в кратком виде приведены семантические программы с комментариями.

1. st:=C[i]; i:=i+1; //Начало имени или служебного слова.

2. st:=st+C[i]; i:=i+1; //Продолжение имени или служебного слова.

3. x:=ord(C[i])-ord(’0’); i:=i+1; //Начало числа.

4. i:=i+1; //Пропуск символа входной строки.

5. typ:=ord(C[i]); i:=i+1; //Распознан символ языка.

6. st:=’’; i:=i+1; //Начало строки символов.

7. typ:=-1; i:=i+1; //Ошибочный символ входной строки.

8. typ:=0; //Концевой символ входной строки.

9. . . . //Сравнение st с таблицей служебных слов. При совпадении typ содержит номер служебного слова +100, при несовпадении – число 1.

10. typ:=-1; //Ошибка во входной строке.

11. x:=x*10+ord(C[i])-ord(’0’); i:=i+1; //Продолжение числа.

12. typ:=2; //Распознано число.

13. typ:=ord(’:’); //Распознан символ «:».

14. typ:=11; i:=i+1; //Распознан символ «:=».

15. st:=st+C[i]; i:=i+1; //Продолжение строки символов.

16. typ:=3; i:=i+1; //Распознана строка символов.

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

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

Конец примера.

Замечание. Рассмотренный пример не претендует на полноту, он показывает лишь, как можно разработать эффективный лексический анализатор для реального языка программирования.