Элементы компиляции программ
В общем случае сканер должен иметь две входные таблицы – таблицу лексем языка и таблицу классов литер. Таблица лексем языка содержит перечень всех лексем языка и соответствующих им целочисленных значений. Для нашей грамматики таблица может быть следующей:
| Лексема | Внутренний код | Лексема | Внутренний код |
|---|---|---|---|
| ПРОГРАММА | 1 | * | 23 |
| := | 24 | ||
| НАЧ БЛОК | 3 | ) | 25 |
| КОН_БЛОК | 4 | НАЧ_ПРОГ | 26 |
| REAL | 5 | КОН_ПРОГ | 27 |
| INT_BYTE | 6 | / | 28 |
| DIV | 7 | INT_WORD | 29 |
| ЧИТАТЬ | 8 | INT_DWORD | 30 |
| ПИСАТЬ | 9 | = | 31 |
| ДЛЯ | 10 | MOD | 32 |
| ДЕЛАТЬ | 11 | [ | 33 |
| ( | 12 | ] | 3 4 |
| ТО | 13 | < | 35 |
| ID | 14 | > | 36 |
| CHJNT | 15 | == | 37 |
| CH_REAL | 16 | >= | 38 |
| 17 | =< | 39 | |
| > | 18 | до | 40 |
| 1 | 19 | ПОКА | 41 |
| 20 | довниз | 42 | |
| + | 21 | ЕСЛИ | 43 |
| 22 | до | 44 | |
| ПЕРЕЙТИ_НА* |
Таблица классов литер используется только в процессе сканирования и предназначена для выяснения класса литеры, когда она выбирается сканером из входного потока. Лучше всего эту таблицу организовать в виде массива, элементы которого отражены на используемую кодовую таблицу (например, таблицу 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, хотя в контексте нашего обсуждения это и не важно. После обработки сканером исходный текст программы преобразуется во внутреннее представление, которое показано справа для каждой строки. Становится понятным значение термина "лексическая свертка" – программа как бы сворачивается в некоторую унифицированную форму, теряя при этом свою индивидуальность. Каждая лексема замещена своим кодом. Идентификаторы замещены кортежами, первый элемент которых является кодом лексемы-идентификатора, а второй элемент – ссылкой на элемент таблицы идентификаторов, где содержится более подробная информация о данном идентификаторе.
Ссылка может быть адресом элемента в таблице, но может быть удобнее, чтобы это было просто число, представляющее собой индекс в этой таблице. Это же касается и лексемы "целое число". Здесь возможны разные варианты: во-первых, можно организовать таблицу констант, подобную таблице идентификаторов; во-вторых, для простых применений константу можно разместить прямо в кортеже. В нашем примере для констант выбран второй вариант.