5.3. Построение синтаксического графа

множества порождающих правил БНФ. Это очень удобная форма, и во многих (если не в большинстве) случаев она предпочтительнее БНФ. Разумеется, граф дает более ясное л точное представление о структуре языка, а также позволяет лучше представить себе процесс грамматического разбора.

Рис. 5.1. Синтаксические графы для синтаксиса прим. 5-

раф является подходящим представлением, которое может \лужить отправной точкой для разработчика языка. Примеры полных определений языков с помощью синтаксических графов даны в разд. 5.7 для ПЛ/0 и в приложении В для Паскаля.

Рис. 5.2. Сводный синтаксический граф, соответствующий прим. 5.

Для того чтобы обеспечить детерминированный граммати-ческий разбор с просмотром вперед на один символ, были установлены ограничения 1 и 2. Как проявляются эти ограничения при графическом представлении синтаксиса? Здесь Особенно наглядно видны удобство и ясность такого представления.

1. Ограничению 1 соответствует требование, чтобы при каж-. дом разветвлении можно было выбрать ветвь, по которой

будет идти дальнейший разбор по очередному символу н-этой ветви. Это означает, что никакие две ветви не должн начинаться с одного и того же символа. 2. Ограничению 2 соответствует требование, чтобы если кой-либо граф А можно пройти, не читая вообще никаких входных символов, то такая нулевая ветвь должна помечаться всеми символами, которые могут следовать за /{ (Это влияет на решение о переходе на эту ветвь.)

Легко проверить, удовлетворяет ли некоторая система графов этим двум ограничениям, не обращаясь к представлению грамматики с помощью БНФ. В качестве вспомогательного шага для каждого графа А определяются множества first (А) и follow (А). Затем непосредственно можно проверить выполненйеогр-анттежиг 1 и 2. Сихтемутрафив, которая удовлетворяет этим двум ограничениям, мы будем называть детерминированным синтаксическим графом.

S.4. ПОСТРОЕНИЕ ПРОГРАММЫ ГРАММАТИЧЕСКОГО РАЗБОРА ДЛЯ ЗАДАННОГО СИНТАКСИСА

Программу, которая распознает какой-либо язык, легко построить на основе его детерминированного синтаксического графа (если такой граф существует). Этот граф фактически представляет собой блок-схему программы. Но при ее разработке рекомендуется строго следовать правилам преобразования, подобным тем, с помощью которых можно предварительно получить из БНФ графическое представление синтаксиса. Эти правила перечислены ниже. Они применяются в определенном контексте, который предполагает наличие основной программы, содержащей процедуры, которые соответствуют различным подцелям, а также процедуру перехода к очередному символу.

Для простоты мы будем считать, что предложение, которое нужно анализировать, представлено файлом input и что терминальные символы - отдельные значения типа char. Пусть символьная переменная ch: char всегда содержит очередной читаемый символ. Тогда переход к следующему символу выражается оператором

. read(ch)

Основная программа будет состоять из оператора чтения первого символа, за которым следует оператор активаций основной цели грамматического разбора. Отдельные процедуры, соответствующие целям грамматического разбора или графам, получаются по следующим правилам. Пусть оператор, полученный с помощью преобразования графа S, обозначается через Г (5).

Правила преобразования графа в программу:

81. Свести систему графов к как можно меньшему числу ь отдельных графов с помощью соответствующих под-i становок.

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

ВЗ-В7.

83. Последовательность элементов

переводится в составной оператор

begin T{S,); ns,); Т{5 ) end

В4. Выбор элементов

переводится в выбирающий или условный оператор

if ch in Ll then TS) else if cAinI,2thenr(52)eJse

if cAinL then7(5 ) else error

где Li означает множество начальных символов конструкции Si {Li = first{Si)).

Примечание. Если Li состоит из одного символа а, то, разумеется, вместо ch in L, нужно писать ch = а . В5. Цикл вида