2) Для цикла с предусловием польская запись имеет вид:
2. м1: Условие УПнет(м2) Посл-ть блоков БПУ(м1) м2:
3) Для оператора присваивания польская запись имеет вид:
3. Идентификатор Выражение Присвоить
Здесь использованы следующие обозначения:
- УПнет(м1) - условный переход на метку м1, если условие не выполняется;
- БПУ(м1) - бесусловная передача управления на метку м1;
- м1 и м2 метки перехода.
Транслятор будет строится на основе упрощенной модели компилятора, описанной в разделе 7, за исключением того, что в нем будет отсутствовать блок генератора кода.
8.4.1. Построение лексического блока на основе конечного автомата
Лексический блок будет строиться на основе конечного автомата.
Рассмотрим некоторые проблемы, связанные с реализацией этого конечного автомата как программы для вычислительной машины [3-5].
При процедуре чтения символов исходной программы может возникнуть проблема кодировки входного множества лексического блока. Если множество символов исходной программы непосредственно служит входом для лексического блока, содержащего много состояний, то этот блок имеет огромную таблицу переходов из-за большого числа входных символов. Решение этой проблемы заключается в обработке исходных символов транслитератором перед подачей на вход лексического блока (рис.8.5). Задача транслитератора - сократить входное множество до приемлемых размеров.
Транслитератор преобразует каждый входной символ в символьную лексему, которая состоит из двух частей: класса и значения. Например, символ а преобразуется в лексему БУКВА.а. Транслитератор реализуется как процедура, которая находит в таблице перевод для каждого входного символа.
 |
Для нашего случая транслитератор осуществляет перевод входных символов в символьные лексемы так как показано в таблице 8.2.
Задача лексического блока заключается в распознавании конечного множества слов и создании соответствующей лексемы, которая подается на вход синтаксического блока. Множество лексем, выдаваемых лексическим блоком для выбранного языка, показано в таблице 8.3.
Суть проблемы распознавания состоит в том, что компилятор должен обнаружить появление некоторого слова из заданного множества и затем действовать в зависимости от того какое это слово. Задача такого характера называется проблемой идентификации.
Существуют проблемы идентификации, которые, строго говоря, не могут быть решены с помощью конечного автомата. Например, для языков, где число допустимых идентификаторов бесконечно или практически бесконечно, невозможно отвести место в памяти или элемент таблицы имен для каждого возможного идентификатора. Эта проблема решается с помощью расширяющегося конечного автомата. При считывании
Таблица 8.2.
|
Входной символ транслитератора |
символьная лексема |
|
|
класс |
Значение |
|
|
A-Z 0-9 + * = < > ( ) : EOF |
БУКВА ЦИФРА ОПЕРАЦИЯ ОПЕРАЦИЯ ОТНОШЕНИЕ ОТНОШЕНИЕ ОТНОШЕНИЕ ЛЕВ.СКОБКА ПРАВ.СКОБКА ДВОЕТОЧИЕ ПРОБЕЛ КОН.ФАЙЛА |
1 -26 0-9 1 2 1 2 3 - - - |
Таблица 8.3.
|
ЛЕКСЕМА |
|
|
КЛАСС |
ЗНАЧЕНИЕ |
|
КОНСТ ИДЕНТ ОПЕРАЦИЯ ОТНОШЕНИЕ ПРИСВ IF THEN ENDIF WHILE DO ENDWHILE BEGIN END ОШИБКА |
указатель на таблицу имен указатель на таблицу имен номер операции номер отношения Нет Нет Нет Нет нет нет нет нет нет нет |
входной цепочки этот автомат отводит для идентификатора необходимое место в памяти и элемент в таблице, как только тот впервые встречается в программе.
Несмотря на то, что в рассматриваемой задаче число идентификаторов не так велико, будем строить лексический блок на основе расширяющегося конечного автомата.
Состояние автомата может быть представлено явно и неявно. В первом случае в некоторой ячейке памяти запоминается номер, соответствующий текущему состоянию. При неявном представлении для каждого состояния имеется отдельная часть программы. Для решаемой задачи выбираем неявное представление состояний.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.