Prolog #5.2: Построение парсера #2

Числовой Токен

Давайте предположим следующий конечный автомат для токенов FP. Заметьте, что с тех пор, как фиксированные токены обрабатываются без переходов, только те переходы, которые связаны с числами, идентификаторами, и токенами ошибки представлены в схеме

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

Этот фрагмент кода определяет фичу определения числовых токенов для предиката getToken.

getToken(digits, [C|R], Rest, S, T) :- digit(C), getToken(digits, R, Rest, [C|S], T).
getToken(digits, [C|R], Rest, S, T) :- letter(C), getToken(error, R, Rest, [C|S], T).
getToken(digits, R, R, S, number(N)) :- reverse(S, S1), atom_chars(N, S1).

Вы должны заметить несколько вещей.

1. Количество параметров расширилось до 5. Это потому что нам нужен еще один для унификации с символами в токене.
2. Когда встречается цифра, она передаются вниз на следующий уровень, а не вверх, как мы видели ранее.
3. Когда встречается символ мы движемся от digits состояния к error состоянию. Любой другой символ оканчивает числовой токен.
4. Вам следует попробовать это определение getToken на файле, содержащем только числа (или любые другие токены для которых вы уже определили getToken). Но используйте следующий клоз

getToken(digits,R, R, S, number(S)).

вместо третьего клоза выше. Вы заметите, что результат отображается как ASCII коды. Предикат atom_chars/2 конвертирует список кодов ASCII в формат символов. Если вы вновь добавите ссылку на atom_chars/2, тогда вы заметите, что символы в токене развернуты. Reverse это исправляет.

Задача 7

Теперь, когда у вас перед глазами несколько примеров, реализуйте Prolog версию лексического парсера FP, getToken и протестируйте на индивидуальных токенах.

Теперь, когда у вас есть реализация для getToken обязательно нужно реализовать более высокоуровневый предикат, который использует getToken и возвращающий список, состоящий из токенов, полученных из файла.

Задача 8

Прикинем, что getToken – это предикат, который принимает 3 аргумента, вот так:

getToken(InList, Token, Rest)
%% InList – список входных символов
%% Token – Токен, в начале InList
%% Rest – Остальная часть списка

Идея заключается в том, чтобы реализовать предикат, скажем getTokens, который принимает два параметра: входной список и второй параметр будет унифицироваться со списком токенов, найденных в файле.

Реализуйте getTokens помня о том, что высокоуровневое определение предиката принимает два параметра, более низкоуровневая версия – может принять три. [Это важная подсказка. Если вы подумаете об этом, то поймете, что рекурсивные ссылки на getTokens будут нуждаться в трех параметрах, с еще одним представляющим часть списка, которая следует за распознанным токеном].

Вам придется подождать, прежде чем тестировать этот предикат.

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

whiteSpace(32).
whiteSpace(10).
digit(D) :- 46 < D, D < 59.
letter(L) :- 64 < L, > < 91.
letter(L) :- 96 < L, L < 123.