61.Последовательность разбора. Использование просмотра вперед.

Последовательность разбора определяет, каким образом осуществляется формирование фрагмента дерева разбора на каждом шаге подстановки. Эти подстановки могут осуществляться слева направо, справа налево, произвольно.

Последовательность разбора непосредственно сочетается с методом разбора. Так, при нисходящем разборе слева направо, подстановка правил вместо самых левых нетерминалов ведет к тому, что входная цепочка распознается с ее начала. Нисходящий разбор справа налево ведет к первоначальному подтверждению символов с конца цепочки. Наоборот, восходящий разбор слева направо осуществляет замену на нетерминал символов, расположенных в конце цепочки. Замена начальных символов производится при восходящем разборе справа налево. Произвольный разбор не оговаривает последовательность подстановки правил. Это ведет к большему количеству переборов.

Повышение эффективности разбора осуществляется разработкой грамматик, специально поддерживающих согласованные между собой метод и последовательность. Так, например, Грамматики, предназначенные для нисходящего разбора, обычно используются для вывода слева направо. Следовательно, и входная цепочка будет разбираться слева направо. Это позволяет быстрее получать нужные символы, а не ждать конца цепочки и лишь потом осуществлять разбор (можно, конечно, саму цепочку разбирать от конца к началу, но это уже из области симметрии). Грамматики, ориентированные на восходящий разбор, обычно оптимизированы под правый вывод входной цепочки, что позволяет, при синтаксическом разборе, опять-таки осуществлять подстановки нетерминалов слева направо.

Использование просмотра вперед.

Языки (как и другие системы) бывают различными по сложности. Ряд из них практически невозможно описать с помощью простых грамматик. Поэтому, в грамматиках могут встречаться альтернативные правила, начинающиеся с одинаковых цепочек символов. Возникающая неоднозначность может быть разрешена путем предварительного просмотра правила на n символов вперед до той границы, начиная с которой данное правило можно будет отличить от других. В контекстно свободных (КС) грамматиках число, определяющее количество символов, анализируемых перед выбором подстановки (1, 2...), используется для классификации. По этому критерию КС грамматики, задаются следующим образом: КС(1), КС(2),...

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