Prolog #7: Построение таблицы символов

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

f a b = + x b;

будет успешен, но, на самом деле должен фейлиться, потому что идентификатор х не является формальным параметром определяемой функции. Для того, чтобы  разобраться с этим типом ошибок мы должны построить таблицу символов, и проверять код на ошибки и синтаксически и на основе содержания данной таблицы.
В разработке парсера мы полагались на представлении правил парсинга в терминах двух списков: входной список и список, содержащий данные еще не распарсенные правилами. Символьная таблица обладает схожей функциональностью в процессе парсинга, за исключением того, что вместо того, чтобы быть снесенной в течении парсинга, она строится в этот момент. Где мы видели построение этого списка прежде? Как насчет предиката separate? Идея была в том, чтобы взять список А и сделать два списка, в одном целые из А,а в другом – идентификаторы из А. Техника применяема при реализации separate состояла в том, чтобы взять входной список и два результирующих списка. Предикат separate был объектом Задачи 6.2 – гляньте на решение и обратите внимание на метод формирования результирующих списков.
Итак, чтобы добавить символьную таблицу к нашей функции парсинга мы можем сделать (в обратном порядке) то, что делали с программным списком в изначальном парсере: для каждого предиката у нас есть таблица входных символов и таблица выходных. Например, parseFnDefList может быть определен как

parseFnDefList(Sin,STin,STout,Sout) :-
parseFnDef(Sin,STin,STout,Sout).

parseFnDefList(Sin,STin,STout,Sout) :-
parseFnDef(Sin,STin,ST,X),
eat(scolon,X,Y),
parseFnDefList(Y,ST,STout,Sout).

Заметьте, что использование точки с запятой не затрагивает таблицу символов, так что предикат парсинга не ссылается на нее. С другой стороны, определение отражает факт, что если parseFnDefList совпало (заматчилось), STout должно отражать добавление символов в STin как результат повторяющихся совпадений (успешных матчингов) предиката parseFnDef.
Может появиться один вопрос. Как интегрировать приведенные выше определения в предикат parse. Изначально parse был определен так:

parse(S) :- parseFnDefList(S, []).
%% parse(S) :- parseFnDefList(S, [eof] – другая возможность

Параметры в parseFnDefList обозначают, что предикат parse будет успешен тогда и только тогда, когда парсинг завершен и весь ввод был обработан – результирующий список пуст. Нам нужно сделать похожую вещь если мы добавляем таблицу символов. Для начала, мы должны распознать необходимость возврата парсером таблицы символов, так чтобы она могла быть использована последующим предикатом интерпретации. Так, мы должны определить parse следующим образом:

parse(S, ST) :- parseFnDefList(S, [], ST, []).

В этом определении второй параметр в parseFnDefList представляет собой начальную таблицу символов в то время как второй представляет результирующую таблицу.

Задача 14

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

parseFnDef(Sin,STin,STout,Sout) :-
eat(id(N),Sin,X), parseParamList(X,[id(N)|STin],STa,Y),
eat(assign,Y,Z),
parseFnExpDef(Z,STa,STout,Sout).

Когда вы запустите запрос

-? tokens(’prog.FP’,S), parse(S, ST).

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

Пример 7 – Поиск в таблице символов

Чтобы увидеть, что идентификатор в области видимости требуется простой предикат поиска. Если мы имеем список идентификаторов следующее должно работать.

inScope(H, [H|Xs).
inScope(H, [Y|Xs]) :- H \== Y, inScope(H, Xs).

[Атом “H \== Y'” показывает, что H отличается от Y.] Но если у нас есть таблица символов как описано выше, тогда мы должны сопоставить больше чем просто идентификатор – мы должны сопоставить пару, чьи первые компоненты идентификаторы. Следующее будет работать:

inScope(H, [(H,A)|Xs).
inScope(H, [(Y,A)|Xs]) :- H \== Y, inScope(H, Xs).

Это делает то, что мы хотим, но решает ли оно проблему? Нет! Запомните, что мы не удаляем записи из таблицы символов когда нет ассоциированных атрибутов – иначе идентификатор бы был вне области видимости если бы он не обладал записью в таблице символов или его запись была с пустым списком атрибутов. Мы не проверяем на это! Вот корректная реализация inScope

inScope(H, [(H,A)|Xs]) :- A \== [].
inScope(H, [(Y,A)|Xs]) :- H \== Y, inScope(H, Xs).

Чтобы избежать ворнинга “singleton variable” мы можем переписать клозы так:

inScope(H, [(H,A)|_]) :- A \== [].
inScope(H, [(Y,_)|Xs]) :- H \== Y, inScope(H, Xs).

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

inScope(H, [(H,[_|_])|_]).
inScope(H, [(Y,_)|Xs]) :- H \== Y, inScope(H, Xs).

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

isFunction(H, [(H, [(function,_,_)|As])|Xs]).
isFunction(H, [(Y,_)|Xs]) :- H \== Y, isFunction(H,Xs).

Заметьте, что аттрибутная()) запись для функции имеет три компоненты: первый для типа, и два других для будущего использования (номер уровня и номера параметров)
Поиск идентификатора определенного типа в таблице символов это задача, которая должна быть решена реализацией таблицы символов. Еще одна задача – обновление этой таблицы. Это может быть сделано тремя способами: добавлением записи в таблицу символов, добавлением новой атрибутной записи в список атрибутов для имеющихся записей, или удалением атрибутных записей которые более не нужны (выходящих из области видимости). Вот пример того, что возможно сделать. (ссылка на дропбокс файл, ибо много писанины) http://dl.dropbox.com/u/3975965/prolog7.txt (Но лучше обратиться к книге, форматирование съезжает, ссылка на первый пост)

Задача 15

Эти предикаты формируют частично полный парсер с символьной таблицей, но есть вещи, которые следует доделать. Что нужно доделать, так это реализации для новых предикатов: fnNotInTable, addFnToTable, defined, и другие.

1. Завершите реализацию не сделанных предикатов. Возможно пригодятся методы использованные в этой главе.
2. Завершите предикаты enterScope и leaveScope. Вам придется ввести в символьную таблицу значение для текущего уровня и уровень каждого атрибутного множества.

Когда вы завершите эту задачу, у вас будет почти готовый парсер за исключением кодогенерации. Как вы предполагаете её реализовать? Мы обсуждали это на уроке, что потребуется для кодогенерации для функции, и все что нужно – это построить список машинных инструкций и хранить их в таблице кодов. Звучит легко. Попробуйте…