Классификация методов синтаксического разбора

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

a = a₁ a₂ a₃ ... a_n. (8.1)

Естественно, что существует огромное количество путей решения данной задачи, и целью разработчика распознавателя является выделение приемлемых вариантов его реализации. Для того, чтобы понять, что, и каким образом, влияет на принципы функционирования распознавателя, а, следовательно, и на организацию разбора, рассмотрим некоторые возможные варианты. Общая классификация рассматриваемых вариантов построения распознавателя представлена на Рисунке 8.1.

Рисунок 8.1 Классификация методов организации

Синтаксического разбора

На самом верхнем уровне выделяются:

– методы разбора;

– последовательность разбора;

– использование просмотра вперед;

– использование возвратов.

Методы разбора

Выделяются два основных метода синтаксического разбора:

– нисходящий разбор;

– восходящий разбор.

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

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

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

Эти рассуждения иллюстрируются следующим примером. Пусть будет дана грамматика G:

G₈ = ({S}, {a, +, *}, P, S), (8.2)

где Pопределяется как:

1. S (r) a

2. S (r) S + S

3. S (r) S * S

Цепочки, порождаемые данной грамматикой можно интерпретировать как выражения, состоящие из операндов «a», а также операций «+» и «*». Недетерминированность грамматики позволяет порождать одну и ту же терминальную цепочки с использованием различных выводов. Например, выражение «a+a*a+a» можно получить следующими способами:

1. S Þ S+S Þ a+S Þ a+S*S Þ a+ a*S Þ a+a*S+S Þ

a+a*a+S Þ a+a*a+a(8.3)

2. S Þ S+S Þ S+a Þ S*S+a Þ S*a+a Þ S+S*a+a Þ

S+a*a+a Þ a+a*a+a (8.4)

3. S Þ S*S Þ S+S*S Þ S+S*S+S Þ a+ S*S+S Þ

a+a*S+S Þ a+a*S+a Þ a+a*a+a (8.5)

И так далее. В этом примере число вариантов одной и той же произвольной цепочки вывода настолько велико, что не имеет и смысла говорить о практическом применении данной грамматики. Но в данном случае она позволяет показать, каким образом могут порождаться различные деревья при нисходящем разборе. Пошаговое построение различных деревьев показано на Рисунках 8.2, 8.3 и 8.4. Можно отметить, что процесс построения дерева совпадает с последовательностью шагов вывода входной цепочки.

Рисунок 8.2 Нисходящий разбор слева направо

Рисунок 8.2 Нисходящий разбор слева направо (окончание)

Рисунок 8.3 Нисходящий разбор справа налево

Рисунок 8.4 Нисходящий произвольный разбор

С операции умножения

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

Восходящий разбор также непосредственно связан с любым возможным выводом цепочки из начального нетерминала. Однако, эта связь, по сравнению с нисходящим разбором, реализуется с точностью до «наоборот». На Рисунках 8.5, 8.6 и 8.7 приведены примеры построения деревьев разбора для грамматики G₆ и процессов порождения цепочек, представленных выражениями (8.3-8.5). Из рисунков видно, что шаги порождения дерева соответствуют движению по представленным цепочкам вывода справа налево.

Рисунок 8.5 Восходящий разбор слева направо

Рисунок 8.5 Восходящий разбор слева направо (окончание)

Рисунок 8.6 Восходящий разбор справа налево

Рисунок 8.6 Восходящий разбор справа налево (окончание)

Рисунок 8.7 Восходящий произвольный разбор

Рисунок 8.7 Восходящий произвольный разбор (окончание)

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

Рисунок 8.8 Пример комбинированного разбора, когда в роли