Построитель множеств FIRST и FOLLOW

5.2. Построитель множеств FIRST и FOLLOW

Программа – построитель множеств FIRST и FOLLOW для заданного нетерминала грамматики разработана на Java и может выполняться как Java-приложение и как Java-апплет, встроенный в HTML-код (загружается при открытии этой страницы). В последнем случае недоступно единственное действие – загрузка грамматики из текстового файла. В основе программы лежат алгоритмы построения множеств FIRST и FOLLOW, изложенный в п.3.3.

Работа с программой начинается с ввода правил грамматики. К формату представления правил предъявляются те же самые требования, что и в пункте 5.3: разделитель правой и левой частей – одиночный символ ‘:’. Пустые строки, символы пробелов и табуляций не допускаются. Правая часть аннулирующего правила отсутствует. В первом правиле обязателен символ конца предложения ‘#’.

Если программа запущена как обычное Java-приложение, то путем выбора в меню «Управление» (1) пункта «Грамматика» можно открыть диалог, в котором выбирается текстовый файл, содержащий правила грамматики. После чего программой создаются и заполняются поля правил (6). Если программа запущена через сеть как апплет, то единственно возможным способом остается ручное редактирование правил. Для ввода правила нужно выбора в меню «Управление» (1) выбрать пункт «+Правило», по которому программой будут добавлено поле правила (6). Затем необходимо записать правило в созданное поле. Повторяя эти действия, необходимо ввести все правила грамматики.

Перед началом построения множества необходимо в поле «Символ» (2) ввести нетерминальный символ, для которого строится множество. Затем в меню «Управление» выбрать пункт «First» или «Follow» в зависимости от того, какое множество будет строиться. После чего при каждом очередном нажатии кнопки «Шаг» (3) выполняется очередное действие алгоритма (в тексте программы расставлены вызовы функции трассировки с выводом необходимых сообщений). Текущее сообщение о событии в программе выводится в поле (4) и добавляется первой строкой в поле (5) – таким образом, события в поле (5) записаны в обратном порядке – от последнего по времени появления к первому.

Поскольку алгоритм построения множеств рекурсивен, более того, построитель FIRST может завывать FOLLOW, и наоборот, то программа отмечает различными цветами поля правил и нетерминалов, которые в данный момент «задействованы» в вычислении множества:

· отмечаются цветом поля (9) нетерминалов, для которых вычисляются множества FIRST и FOLLOW. По окончании вычисления множества отметка с нетерминала снимается, но устанавливается отметка цветом (10) построенное множество;

· отмечаются цветом поля текущих правил, которые просматриваются алгоритмом вычисления FIRST (8 - красный) и FOLLOW (7-оранжевый).

· зеленым цветом отмечаются правила, просмотр которых отложен при построении множеств на предыдущих шагах рекурсии.

Можно редактировать грамматику по время работы программы. Для этого алгоритм возвращается в исходное состояние при выполнении пункта меню «Сброс». После чего отредактируются поля правил (6) (можно увеличивать их количество, единственное, что невозможно – уменьшать их количество). После этого необходимо повторно запустить построение требуемого множества.