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

while сЛ in £ do Г(5)

где T{S) есть отображение S в соответствии с правилами ВЗ-В7, а L есть множество L = first{S) (с^ предыдущее примечание). Вб. Элемент графа, обозначающий другой граф А

переводится в оператор обращения к процедуре А. ВТЭлемепт графа^,-ебоз№ачающий терминальный символ

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

if сА = X then read(ch) else error

где error - процедура, к которой обращаются при по< явлении неправильной конструкции.

Теперь покажем применение этих правил на примере преобразования редуцированного графа, изображенного на

program parse (input, output); var ch: char; procedure . 4;

begin if СЙ = x then read(ch) else ifcA (then begjhi read(ch); A; while ch = + do begin read(ch); A end;

If ch ) tben read{ch) else error end else error

end ; begin read(ch); A end

Программа 5.1. Грамматический разбор для синтаксиса из прим. 5.

рис. 5.2 (пример 5), в программу грамматического разбора (программа 5.1):

j]pH ЭТОМ преобразовании свободно применялись некоторые дчевидные правила программирования, позволяющие упростить программу. Например, при буквальном переводе четвертая строка имела бы вид

if ей = Vthen

if ch = .х' then read{ch) else error ----else....

CHO, что ее можно сократить, как это сделано в программе. Операторы чтения в пятой и седьмой строках тоже получены с помощью такого же упрощения.

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

©-

4s>

itch = х/then begin reaJ(cA); 7(5,) end els6 if cA = V then begin readich); r(Sj) end else

if ch =. x, then begin readich); T(S ) end else error

>a

. Кроме того, часто встречающуюся конструкцию

readich); T(Sy, . while В do

begin r f(cA); ад end

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

Итак, грамматика, мы предполагаем, что она представлена в виде детерминированного множества синтаксических графов) преобразуется в подходящую структуру данных, а не в структуру программ [5.2]. Естественный способ представить граф - это ввести узел для каждого символа и связать эти узлы с помощью ссылок. Следовательно, таблица - это не просто массив. Правила преобразования очевидны и приведены ниже. Узлы этой структуры представляют собой записи с вариантами, один для терминального, а другой -для нетерминального символа. Первый идентифицируется терминальным символом, который он обозначает, второй - ссылкой на структуру данных, представляющую соответствующий нетерминальный символ. Оба варианта содержат две ссылки: одна указывает на следующий символ, последователь {sue), а дрУ гая связана со списком возможных альтернатив (alt). Описа-чие соответствующего типа данных приведено в (5.9), а графически узел можно изобразить как

МОЖНО, разумеется, выразить короче:

repeat readich); T(S) until В

Мы намеренно не описываем пока процедуру error ( ощик ка ). Поскольку сейчас нас интересует лишь, как определит правильно ли входное предложение, мы можем считать, ц- эта процедура заканчивает работу программы. Конечно, на практике в случае появления неправильных конструкции нужно использовать более тонкие приемы. Они будут рас! сматриваться в разд. 5.9.

S.5. ПОСТРОЕНИЕ ТАБЛИЧНО-УПРАВЛЯЕМОЙ ПРОГРАММЫ ГРАММАТИЧЕСКОГО РАЗБОРА

Вместо того чтобы для каждого языка составлять спе-