Главная  Терминология Хоора 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 [ 111 ] 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133

йыясняется, что еще нужен элемент, представляющий пустую оследовательность, символ пусто . Мы обозначим его с по-{[оШью терминального элемента, называемого empty (5.9).

tyfe pointer = ]node; node =

тесогй suc,alt: pointer; case terminal: boolean of true: {tsym: char); false; (nsym: hpointer)

(5.9)

Правила преобразования графов в структуре данных аналогичны правилам В1-В7.

Правила преобразования графов в структурах данных

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

С2. Преобразовать каждый граф в структуру данных согласно правилам СЗ-С5, приведенным ниже.

СЗ. Последовательность элементов (см. рисунок к правилу ВЗ) преобразуется в следующий список узлов:

С4. Список альтернатив (см. рисунок к правилу В4) преобразуется в такую структуру данных:

п



С5. Цикл (см. рисунок к правилу В5) преобразуется в сл дующую структуру:

empty

в качестве примера на рис. 5.3 показана структура, полученная из графа, соответствующего синтаксису примера 5 (рис. 5.2). Структура данных идентифицируется узлом-заго-

г

empty

Рис. 5.3. Структура данных, представляющая граф рис. 5.2.

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

tygehpointer ~ [header; header ~

record entry: pointer; sym: char

Программа, производящая грамматический разбор преД ложения, представленного в виде последовательности символов входного файла, состоит из повторяющегося оператора

(5.10)



лсывающего переход от одного узла к следующему узлу. )na оформлена как процедура, задающая интерпретацию графа; если встречается узел, представляющий нетерминальной символ, то интерпретация графа, на который он ссылается предшествует завершению интерпретации текущего графа- Следовательно, процедура интерпретации вызывается pgnypcueno. Если текущий символ {sym) входного файла создает с символом в текущем узле структуры данных, то процедура переходит к узлу, на который указывает поле sue, иначе - к узлу, на который указывает поле alt:

jftoceimeparse(goal: hpointer; УйГ match: boolean);

yars:-pointer; liegin; :=s goal\.entry; repeat

if s\.terminal tbea

begin if s].tsym > sym then

begin match := true; getsym /g 11 j

end

else match := (sf.tsym = empty} end

еШ parsers].nsym, match); if match then s : = s\.suc else s :- s\.alt vaAVis > nil

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

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

Представление синтаксиса с помощью графа имеет один Существенный недостаток: вычислительные машины не могут Итать графы. Но перед началом грамматического разбора




1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 [ 111 ] 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133