ВЫРажение EXPRession

ОСТаток ВЫРажения REST of EXPRession

СЛАГаемое ADDitive term

ОСТаток СЛАГаемого REST of ADDitive term

МНОЖитель MULTiplier

procedure ReadSymb (c: Symbol);

| b := (Next = c);

| if b then begin Move; end;

End;

Procedure ReadExpr;

| ReadAdd;

| if b then begin ReadRestExpr; end;

End;

Procedure ReadRestExpr;

| if Next = '+' then begin

| | ReadSymb ('+');

| | if b then begin ReadExpr; end;

| end else begin

| | b := true;

| end;

End;

Procedure ReadAdd;

| ReadMult;

| if b then begin ReadRestAdd; end;

End;

Procedure ReadRestAdd;

| if Next = '*' then begin

| | ReadSymb ('*');

| | if b then begin ReadAdd; end;

| end else begin

| | b := true;

| end;

End;

Procedure ReadMult;

| if Next = 'x' then begin

| | ReadSymb ('x');

| end else if Next = '(' then begin

| | ReadSymb ('(');

| | if b then begin ReadExpr; end;

| | if b then begin ReadSymb (')'); end;

| end else begin

| | b := false;

| end;

End;

Осталось обсудить проблемы, связанные с взаимной рекурсивностью этих процедур (одна использует другую и наоборот). В паскале это допускается, только требуется дать предварительное описание процедур (»). Как всегда для рекурсивных процедур, помимо доказательства того, что каждая процедура работает правильно в предположении, что используемые в ней вызовы процедур работают правильно, надо доказать отдельно, что работа завершается. (Это не очевидно: если бы в грамматике было правило K -> KK, то из K ничего не выводится, Посл(K) и Нач(K) пусты, но написанная по нашим канонам процедура