Основные идеи нисходящего разбора

Как уже было сказано, задача синтаксического анализа применительно к ФГ состоит в построении синтаксического дерева, соответствующего входному предложению языка. В нисходящем синтаксическом анализе дерево строится «сверху -вниз» от предка к потомкам, что соответствует замене нетерминала левой части на правую часть. Рассмотрим этот процесс подробнее.

1. Дерево строится «сверху-вниз» и «справа-налево», т.е. на каждом шаге выбирается очередная, самая левая «незакрытая» нетерминальная вершина, для которой строится поддерево.

2. Каждому шагу соответствует замена нетерминального символа, соответствующего левой части правила, на его правую часть.

3. Единственная «свобода выбора» и сущность алгоритма нисходящего распознавания заключается в выборе для группы правил с одинаковой левой частью соответствующей правой части.

4. Появляющиеся в процессе построения терминальные вершины «закрывают» соответствующие символы входного предложения (в каждый момент имеет место «незакрытая» часть входного предложения).

5. Единственным основанием для выбора, обозначенного в п.3, является очередной «незакрытый» символ входного предложения (в общем случае это может быть k символов от начала незакрытой части.

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

Перечисленные идеи нисходящего разбора соответствуют классу грамматик, именуемому LL(k), т.е. идеи эти «работают» на грамматиках соответствующего класса:

· Первая L обозначает принцип просмотра входного предложения (цепочки) в направлений слева-направо (left) c последовательным «закрытием» символов терминальными вершинами дерева;

· k – обозначает глубину просмотра «незакрытой» части цепочки для принятия решения о выборе одной из правых частей правила, соответствующего очередному нетерминалу. Обычно k=1;

· Вторая L соответствуют термину «левосторонний вывод» (left), т.е. нисходящий разбор с заменой левой части правила на правую.

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