Рекурсивный спуск с возвратами

Итак, для того, чтобы иметь возможность применить метод рекурсивного спуска, мы должны преобразовать грамматику к виду, в котором множества FIRST не пересекаются. Это сложный и неприятный процесс. Поэтому на практике зачастую используется следующий прием, называемый рекурсивным спуском с возвратами.

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

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

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

AST.Stmt stmt_or_decl ()

{

Lexer saved = new Lexer (lexer);

try {

AST.Type t = type_opt ();

if (lexer.Is (Token.Tag.Ident))

return decl_tail (saved.Curr.coor, t);

}

catch (ParseFailed) {

lexer = saved;

AST.Expr expr = this.expr ();

return new AST.Stmt.Expr (compiler,

saved.Curr.coor|lexer.req (Token.Tag.Semicolon).coor, expr);

}

}

В блоке try мы пытаемся разобрать конструкцию, предполагая, что это описание. Если это нам не удалось, то анализатор создает исключение, которое затем отлавливается в блоке catch и приводит к повторному разбору той же конструкции как выражения.