![]() КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
LL(1) - грамматикиНаиболее просто данный анализатор строится для LL(1) грамматики. Таблица анализа для данной грамматики не имеет множественных записей. L – просмотр входного потока слева направо, L – левое порождение (вывод), (1) – просмотр одного символа из входного потока на каждом шаге для принятия решения о дальнейшем действие. Примечание: имеются грамматики, которые нельзя привести к LL(1). Пример: Построим анализатор, работающий с грамматикой LL(1). Имеется грамматика и цепочка: Конфигурация, описывающая состояние анализатора в общем виде:
1) Из S порождаем цепочку. Так как первым в 2) В вершине магазина находится терменальный символ a. Так как он совпадает с первым символом 3) Текущий символ входной цепочки – c. В вершине магазина - A, поэтому выбираем правило 3). Таким образом получим: Дальнейший анализ заполнен в таблице:
КС – грамматика без Введем ряд определений: FIRST (A) – это множество терменальных символов, которыми начинаются цепочки, выводимые из терминала A: FOLLOW (A) – это множество терменальных символов, которые могут встретиться непосредственно справа от нетерменала A в некоторой цепочке:
Пример:
SELECT – это множество выбора правил. Оно определяется: 1) eсли 2) если LL(k) – грамматика. КС – грамматика является LL(1), тогда и только тогда, когда для двух различных правил A→β, А→γ Мощности LL(1)-грамматик недостаточно, чтобы описать синтаксис любых языков программы. Естественным обобщением LL(1)-грамматик является LL(k) – грамматика. Для этого введем обобщение множеств FIRST(α) множество LL(k) применяются на практике редко из-за сложности.
|