Нисходящий разбор

МЕТОДЫ СИНТАКСИЧЕСКОГО АНАЛИЗА

Будем считать, что цепочка w Î L(G) для некоторой КС-грамматики G проанализирована или разобрана, если известно ее дерево вывода в данной грамматике.

Обычно компилятор выполняет синтаксический анализ путем моделирования МП-автомата, анализирующего входные цепочки.

Пусть заданы КС-грамматика G=(N, T, P, S), правила которой пронумерованы целыми числами 1, 2, …, р и цепочка a Î (N È Т). Тогда:

- левым разбором цепочки a называется последовательность правил, примененных при ее левом выводе из S;

- правым разбором цепочки a называется последовательность правил, примененных при ее левом выводе из S;

Рассмотрим выполнение синтаксического анализа КС-грамматик при условии, что анализируемая цепочка рассматривается слева справа (левый анализ).

Стратегия левого нисходящего разбора предполагает заполнять дерево разбора, начиная с корня, и двигаться слева направо, направляясь к кроне.

Известно, что для любой грамматики G можно построить недетерминированный МП-преобразователь, который может быть основой синтаксического анализатора.

Пусть G=(N, T, P, S) - КС-грамматика, в которой правила пронумерованы числами от 1 до р.

Левым анализатором M_l называется недетерминированный МП-преобразователь ({q}, T, NÈ Т, {1, 2, …, p}, d, q, S, {q}), где d определяется следующим образом:

1) Если A®a - правило из Р с номером i, то (q, a, i) Î d(q, e, A)

2) d (q, a, a) ={(q, e, e)} для всех a Î T

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

(1) E®E+T

(2) E®T

(3) T®T*P

(4) T®P

(5) P®I

(6) P®(E)

M_l = ({q}, {i, +, *, (,)}, {i, +, *, (,), E, T, P}, {1, 2, 3, 4, 5, 6}, d, q, E, {q})

Определим функцию d:

1. По правилу (2) определения d (q, a, a) ={(q, e, e)} для всех a Î T

2. Для правила грамматики E®E+T по правилу (1) определения в функцию d(q, e, E) необходимо включить элемент (q, E+T, 1)

3. Повторив аналогичные действия для всех правил грамматики, получим:

1) d(q, e, E)={(q, E+T, 1), (q, T, 2)}

2) d(q, e, T)={(q, T*P, 3), (q, P, 4)}

3) d(q, e, P)={(q, (E), 6), (q, I, 5)}

4) d(q, a, a)={(q, e, e)} для всех a Î{i, +, *, (,)}

Для входной цепочки i + i * i МП-анализатор M_l среди других может выполнить следующую последовательность тактов:

(q, i + i * i, E, e) ├

(q, i + i * i, E+T, 1) ├

(q, i + i * i, T+T, 12) ├

(q, i + i * i, P+T, 124) ├

(q, i + i * i, i+T, 1245) ├

(q, + i * i, +T, 1245) ├

(q, i * i, T, 1245) ├

(q, i * i, T*P, 12453) ├

(q, i * i, P*P, 124534) ├

(q, i * i, i*P, 1245345) ├

(q, * i, *P, 1245345) ├

(q, i, P, 1245345) ├

(q, i, i, 12453455) ├

(q, e, e, 1245345)

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

Нисходящий анализ налагает ограничение на КС-грамматику: она не должна содержать правил с левой рекурсией.

Дата добавления: 2014-01-03