Синтаксический анализ «сверху-вниз» и «снизу-вверх»

Синтаксический анализ «сверху-вниз» - просмотр цепочки осуществляется слева-направо, а анализ правил - сверху-вниз.

Пример: цепочка abbac

S®Cc

C®bA|aB

A®a|aC

B®b|bC

Синтаксический анализ «снизу-вверх» (метод обратной волны) - просмотр цепочки осуществляется справа-налево, анализ правил - снизу-вверх.

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

Анализатор LL-грамматики при анализе входной цепочки просматривает не один символ входной цепочки, а на несколько символов больше, и делает очередной шаг разбора на основе того, что видит.

Пример: Построим синтаксические диаграммы для данной грамматики.

S: A:

C:

B:

C:

B:

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

Вопросы и упражнения

1. Как осуществляется просмотр цепочки при синтаксическом анализе «сверху-вниз »?

2. Как осуществляется просмотр цепочки при синтаксическом анализе «снизу-вверх»?

3. Что понимают под LL-грамматикой?