Тема 13

Тема: Простые LL(1) – грамматики.

План:

1. LL(1) – грамматики

2. Алгоритм разбора для LL(1) - грамматик

Простые LL(1) – грамматики

Рассмотрим процесс нисходящего анализа цепочек языка на примере.

Рассмотрим разбор входной цепочки accedd, которая принадлежит языку, определяемому заданной грамматикой.

Начнем с начального символа грамматики S и попытаемся породить рассматриваемую цепочку, используя левый вывод и проверяя на равенство начальные терминалы сентенциальной формы с символом цепочки.

На первом шаге порождения можно использовать первое или второе правило грамматики. Учитывая, что входная цепочка начинается с символа а, мы используем первое правило и получаем сентенциальную форму аА.

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

Рассмотрим последовательность шагов работы такого анализатора для входной цепочки accedd, левый вывод которой равен 1334(рис 39)

Конфигурация, описывающая состояние анализатора (ах, α,π), включает в себя содержимое магазина α (вершина слева), необработанную част входной цепочки ах (а – текущий символ) и построенный к анному моменту времени разбор π.

В [28] содержимое магазина анализатора интерпретируется как следующее утверждение о необработанной части цепочки входных символов: вся входная цепочка допустима тогда и только тогда, когда цепочка оставшихся входных символов, включая текущий, выводимая из цепочки символов, находящихся в магазине. Например, если в процессе анализа в магазине оказалось цепочка acAd, то это означает, что вся входная цепочка допустима тогда и только тогда, когда её необработанная часть состоит из символов ас, за которыми идет цепочка, порождаемая нетерминалом А. Завершаться входная цепочка должна символом d.

Анализатор начинает свою работу в конфигурации (accedd,S,ε), состояние магазина которой утверждает, что входная цепочка должна порождаться начальным символом грамматики.

Шаг 1. Выполняется порождение из символа S цепочки символов, начинающейся с символа а. Для этого анализатор может использовать правило грамматики (1) либо (2). Учитывая, что правило (2) порождает цепочку, начинающуюся символом b, выбираем правило (1) и переходим в конфигурацию (accedd,aA,1).

Шаг 2. В вершине магазина находится терминальный символ а. Так как этот символ совпадает с первым символом цепочки, мы можем вычеркнуть его из магазина и продолжить анализ входной цепочки.

Шаг 3. Текущий символ входной цепочки – символ с (второй символ входной цепочки), а в верхушке магазина находится нетерминал А. Для продолжения разбора анализатор может выбрать правило грамматики (3) или (4). Текущий символ требует, чтобы цепочка, порождаемая нетерминалом А, начиналась с символа с, поэтому выбираем правило (3). Анализатор переходит в конфигурацию (ccedd.cAd,13).

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

Определение LL(1)- грамматики

Обобщим определение множества FIRST так, чтобы его можно было применить для правил произвольного вида.

Данное определение означает, что множество FIRST(α) состоит из множества терминальных символов, которыми начинаются цепочки, выводимые из цепочки α.

В определении LL(1)- грамматики утверждается, что выбор правила для замены нетерминала А в цепочке wAα однозначно определяется цепочкой w и следующим за ней входным символом. На самом деле это не так.

В [3] доказано следующее утверждение.

Из этого утверждения следует, что для LL(1)- грамматики правило для замены нетерминала однозначно определяется текущим входным символом. На рис. 7.2 приведено дерево вывода цепочки wxy. Если к настоящему времени было построено дерево с кроной wAα ,то для определения правила, которое должно быть использовано для замены нетерминала А, достаточно рассмотреть текущий символ – первый символ цепочки х.

Можно доказать [3], что КС-грамматика G=(N,∑ ,P,S) является LL(1)- грамматикой тогда и только тогда, когда для двух различных правил А→β и А→γ:

На основании этого утверждения можно дать более конструктивное определение LL(1)- грамматики.

Важным следствием этого определения является то, что леворекурсивная грамматика не может быть LL(1)- грамматикой.

Другое важное свойство LL(1)- грамматики – ее однозначность.

Рассмотренная грамматика относится к классу простых (simple) LL(1) – грамматик.

Для s- грамматик можно сформулировать простые правила построения детерминированного магазинного автомата, выполняющего синтаксический разбор. Из рассмотренного примера видно, что для МП-автомата достаточно определить две операции: замену верхнего символа магазина цепочкой символов (правой частью соответствующего правила) и вычеркивание символа из магазина.

К сожалению, большинство конструкций языков программирования не могут быть описаны при помощи s-грамматик.

Эта грамматика не относится к классу грамматик, т.к. имеет ε-правило. Несмотря на это, попробуем её использовать для разбора цепочки acbb, действуя так же, как и в предыдущем случае

Щаг 1. Анализатор забирает правило (1) грамматики для порождения из символа S цепочки, начинающейся с символа а, и переходит из начальной конфигурации в конфигурацию (acbb,αAS ,1)

Шаг 2. Далее анализатор вычеркивает символ из магазина и читает второй символ входной цепочки, переходя в конфигурацию (cbb,AS ,1)

Шаг 3. Для порождения из верхнего символа магазина цепочки, начинающейся с символа с, анализатор выбирает правило (3) грамматики и после его использования переходит в конфигурацию (cbb,cASS ,13)

Шаг 4. Повторяя шаг, аналогично шагу 2, анализатор переходит в конфигурацию (bb,ASS ,13)

Заметим, что пока действия анализатора такие же, как и в предыдущем примере.

Щаг 5. Продолжая разбор, анализатор должен выбрать правило грамматики, которое позволяет из нетерминала А породить цепочку, начинающуюся с символа b. Применить правило (3), имеющее вид А→cAS, нельзя т.к. оно начинается с символа с, а текущий входной символ – b.

Остается сделать предположение, что требуемая цепочка порождается из А при помощи правила (4) А→ε и она пустая. В этом случае символ b- это начальный символ цепочки, выводимой их символа, находящегося в магазине ниже А т.е. из нетерминала S.

Шаг 6. Применение правила (4) приводит к тому, что анализатор вычеркивает верхний символ (нетерминал А) из магазина, но не изменяет текущий символ, т.е. из конфигурации (bb,ASS ,13) он переходит в конфигурацию (bb,SS ,134)

Оставшиеся действия анализатора не требуют пояснения:

Анализ действий анализатора показывает, что успешное применение ε- правила для некоторого нетерминала возможно в том случае, если цепочка, порождаемая символом, лежащим ниже этого нетерминала, начинается с символа, совпадающего с текущим символом входной цепочки (шаг 5)

Перейдем к процессу анализа грамматики, определив два множества символов.