Тема 14

Практическое занятие № 14

Тема: Алгоритм разбора для LL(1)- грамматик

План:

1. «1-предсказывающий» алгоритм

2. Конфигурация «1-предсказывающего» алгоритма разбора

3. Организация работы алгоритма в зависимости от элемента управляющей таблицы

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

Разбор для LL(1) - грамматики можно осуществить с помощью так называемого «1-предсказывающего» (один-предсказывающего) алгоритма разбора, который использует входную ленту, магазин и выходную ленту (рис. 41). Единица в названии алгоритма означает, что при чтении анализируемой цепочки, находящейся на входной ленте, входная головка может заглядывать вперед на один символ.

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

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

Обозначим алфавит магазинных символов (без символа ()) как Vp*

Работой алгоритма управляет управляющая таблица М, задающая отображение множества в множестве, состоящее из следующих элементов:

1. (β,i), где - правая часть правила вывода с номером i.

2. ВЫБРОС

3. ДОПУСК

4. ОШИБКА

Алгоритм анализирует входную цепочку, выполняя последовательность тактов, похожих на такты ДМП-преобразователя. Такты алгоритма будем описывать в терминах отношения , определенного на множестве конфигураций.

Пусть FIRST(x)={a}. Тогда работа алгоритма в зависимости от элемента управляющей таблицы М(Х,а) определяется следующим образом:

1. (х, Хα, π) (х, βα, πi), если М(Х, а)= (β, i). В этом случае верхний символ магазина Х заменяется на цепочку , и в выходную цепочку дописывается номер правила i. Входная головка при этом не сдвигается.

2. (ах,аα,π) (х,α,π), если М(а,а)=ВЫБРОС. Это означает, что , если верхний символ магазина совпадает с текущим входным символом, он выбрасывается из магазина, и входная головка сдвигается на один символ вправо.

3. Если алгоритм достигает конфигурации (ε,,π), что соответсвует элементу управляющей таблицы М(,ε)=ДОПУСК, то его работа прекращается, и выходная цепочка π является левым разборои входной цепочки.

4. Если алгоритм достигает конфигурации (х,Хα,π) и М(Х,а)=ОШИБКА, то разбор прекращается и выдается сообщение о ошибке.

Конфигурация (w. S, ε), где - начальный символ магазина (начальный символ грамматики), называется начальной конфигурацией.

Если то π называется выходом алгоритма для входа w.

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

Шаг 1. Алгоритм находиться в начальной конфигурации (i+i*i,E,ε)

Определив значение управляющей таблицы для верхнего символа магазина Е и текущего символа i, получим М(Е,i)=(TE’,1). Это означает, что нужно выполнить следующие действия:

□ Заменить верхний символ магазина Е цепочкой ТЕ’

□ Не сдвигать читающую головку

□ На выходную ленту поместить номер использованного правила 1

Алгоритм переходит в конфигурацию (i+i*i,TE’,1)

Шаг 2. Выполняя действия, аналогичные описанным для шага 1, пройдем следующие конфигурации:

Шаг 3. Алгоритм находится в конфигурации (i+i*i,iT’E’,148). Значение управляющей таблицы М(i,i)= ВЫБРОС. Выполняем следующие действия:

□ Удаляем верхний символ магазина

□ Сдвигаем читающую головку на один символ вправо

□ При этом выходная лента не изменяется

Алгоритм переходит в конфигурацию (+i*i,T’E’,148).

Щаг 4. Выполняя шаги 1 и 2, алгоритм произведет следующие действия:

Шаг 5. Алгоритм находится в конфигурации (ε,,14862485863)

Так как значение М(, ε) = ДОПУСК, то цепочка i+i*i принадлежит языку, и последовательность номеров правил 14862485863 на выходной ленте – это ее разбор.

«1-предсказывающий» алгоритм разбора может быть использован для анализа любого входного языка, синтаксис которого описывается LL(1)- грамматикой. Этот алгоритм можно промоделировать с помощью ДМП-преобразователя с одним состоянием, входная лента которого имеет концевой маркер.

Рассмотрим, как можно построить управляющую таблицу для заданной LL(1)- грамматики.

LL(k) – грамматики

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

Множество FIRSTk(α) является обобщенным множество FIRST(α) и представляет собой множество терминальных префиксов длины k терминальных цепочек, выводимых из α (или меньшей длины, если из цепочки α выводится терминальная цепочка длины, меньшей k).

Таким образом определение LL(k) – грамматик можно сформулировать следующим образом:

Разбор для LL(k) – грамматик выполняется значительно сложнее, чем для LL(1) – грамматик. Связано это с двумя проблемами:

□ Применение алгоритма 7.1 требует использования аванцепочек длиной до k символов, что существенно увеличивает размеры управляющей таблицы

□ Для некоторых LL(k) – грамматик (k>1) верхний символ магазина и аванцепочка длиной k (или меньше) символов не всегда однозначно определяют правило, которое должно быть применено при разборе

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

Обобщение этого утверждения на LL(k) – грамматики приводит к дополнительным ограничениям:

Алгоритм 7.1 позволяет построить корректную управляющую таблицу только для сильно LL(k) – грамматики. В [3] приведен пример LL(2) – грамматики, не являющейся сильно LL(k) – грамматикой.

Сложности построения синтаксического анализатора и их неэффективность не позволяют использовать LL(k) – грамматик ( для k>1) в практике построения компиляторов.

LL(k) – грамматики

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

Множество FIRSTk(α) является обобщенным множество FIRST(α) и представляет собой множество терминальных префиксов длины k терминальных цепочек, выводимых из α (или меньшей длины, если из цепочки α выводится терминальная цепочка длины, меньшей k).

Таким образом определение LL(k) – грамматик можно сформулировать следующим образом:

Разбор для LL(k) – грамматик выполняется значительно сложнее, чем для LL(1) – грамматик. Связано это с двумя проблемами:

□ Применение алгоритма 7.1 требует использования аванцепочек длиной до k символов, что существенно увеличивает размеры управляющей таблицы

□ Для некоторых LL(k) – грамматик (k>1) верхний символ магазина и аванцепочка длиной k (или меньше) символов не всегда однозначно определяют правило, которое должно быть применено при разборе

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

Обобщение этого утверждения на LL(k) – грамматики приводит к дополнительным ограничениям:

Алгоритм 7.1 позволяет построить корректную управляющую таблицу только для сильно LL(k) – грамматики. В [3] приведен пример LL(2) – грамматики, не являющейся сильно LL(k) – грамматикой.

Сложности построения синтаксического анализатора и их неэффективность не позволяют использовать LL(k) – грамматик ( для k>1) в практике построения компиляторов.