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

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

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

В приводимой ниже процедуре la представляет собой логическое значение, которое определяет, надо ли считывать новый предварительно просматриваемый символ до обработки следующего элемента таблицы разбора. Например, la имеет значение false, когда предварительно просматриваемый символ не является направляющим для какой-либо конкретной правой стороны правила, и требуется исследовать множество направляющих символов, соответствующее другой правой части. Если предварительно просматриваемый символ не содержится в текущем множестве направляющих символов и поле ошибки parsel будет true, то выдается сообщение о синтаксической ошибке. Если поле стека обрабатываемой parsel имеет значение true, то до перехода к адресу, задаваемому полем перехода, в стек помещается адрес следующей parsel.

Вызов процедуры разбора parse (pt) приведет в действие драйвер, где ргос parse = ([ ] parsel pt) bool: begin int i: = 1; push0;

bool la := true; string lookahead;

while if la then lookahead : = lexread fi;

lookahead Ф "±" and i Ф 0

do if lookahead oneof terminals of pt[i]

tben la : = accept of pt [i];

if return of pt [i] then i : = pop

else if stack of pt [i] then push (i + 1) fi;

i: = jump of pt [i]

elif error of pt [i] then syntax error

else i plusab 1; la : = false od;

i = 0 and lookahead = " ±" end «±» - специальный символ, появляющийся после окончания предложения. Процедуры push и pop и оператор oneof определяются следующим образом:

proc push = (int x) void:

begin if Sptr > upb stack then slack plusab 10 fi; ifacfc [Sptr]: = x; Sptr plusab 1 end;

proc pop = int:

begin Sptr minusab 1;

if Sptr < 0 then stack empty fi;

stack [Sptr]

end;

prio oneof=1;

op oneof = (string la, ref list l) bool:

begin bool result: = false; list ll:=l;

while (ll inst nil) and not result

do if la = term of ll

then result: = true

else ll:= next of ll

result

nil обозначает конец списка на Алголе 68, a plusab определяется (помимо его стандартного значения) как:

op plusab = (ref flex [ ] int S, int i) ref flex [ ] int begin [0: upb S + i] int temp; temp[0: upbS] :=S; for j from upb S + 1 to upb temp do temp [j] : = 0 od;

S: = temp end

Кроме того, существуют процедуры обращения с подобными ситуациями -syntax error и stack empty, a lexread выдает строку соответствующ;ую одному символу языка.

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

(1) PROGRAM->begin DECL1ST comma STATEL1ST end

(2)DECLIST->d X

(3)X->semi DECLIST

(4)X->e .

(5)STATELIST->s Y

(6)Y->semi STATELIST

(7)Y->e

Сначала представим грамматику в виде схемы, показанной на рис. 4.2. В скобках слева и справа на рисунке указаны номера соответствующих элементов

таблицы разбора. На основании этой схемы можно построить таблицу разбора (табл. 4.12). 0 появляется в поле перехода, когда оно не имеет отношения к делу. Таблица 4.12