АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

LL(k) ЯЗЫКИ И ГРАММАТИКИ

Читайте также:
  1. I. ИНДОЕВРОПЕЙСКИЕ ЯЗЫКИ
  2. I. ИНДОЕВРОПЕЙСКИЕ ЯЗЫКИ
  3. XX. ИНДЕЙСКИЕ (АМЕРИНДСКИЕ) ЯЗЫКИ
  4. Алтайские языки
  5. Племенные языки и образование родственных языков.
  6. Проблемно-ориентированные языки. Языки представления знаний.
  7. Синтаксис как раздел грамматики
  8. Фаза анализа и перевода грамматики во внутреннее представление
  9. Что такое языки?
  10. ЯЗЫКИ И ГРАММАТИКИ ПРОСТОГО ПРЕДШЕСТВОВАНИЯ
  11. Языки и истолкование

 

 

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

Дадим вначале неформальное определение LL(k) грамматики. Напомним, что в левостороннем анализаторе дерево вывода цепочки abg строится по заданной грамматике, начиная от корня (аксиомы грамматики), сверху вниз. Пусть на каком-то шаге анализа уже построено частичное дерево вывода с кроной aAj (см. рис. 5.1). Для продолжения разбора требуется заменить нетерминал A по одному из правил вида A®b. Если для однозначного выбора этого правила окажется достаточно знать только a и первые k символов цепочки bg, то заданная грамматика является LL(k) –грамматикой.

 

Дадим более строгое определение. Определим два множества цепочек:

FIRST k (a) - множество терминальных цепочек, выводимых из a, укороченных до k символов.

FOLLOW k (A) - множество укороченных до k символов терминальных цепочек, которые могут следовать непосредственно за A в выводимых цепочках.

КС-грамматика называется LL(k) -грамматикой для некоторого фиксированного k, если из существования двух левых выводов

(1) S Þ * wAa Þ wba Þ * wj

и

(2) S Þ * wAa Þ wga Þ * wy,

для которых FIRST k (j) = FIRST k (y), следует, что b=g.

Пример 5.1. Пусть грамматика G1 состоит из правил S ® aASôb, A ® aôbSA. Интуитивно G1 является LL(1) грамматикой, так как если дан самый левый нетерминал C в левовыводимой цепочке и следующий входной символ с, то существует не более одного правила, применимого к C и приводящего к терминальной цепочке, начинающейся символом c. Переходя к определению LL(1) грамматики мы видим, что если
S Þ * wSa Þ wba Þ * wj и S Þ * wSa Þ wga Þ * wy и цепочки j и y начинаются символом a, то в выводе участвует правило S ® aAS и b = g = aAS. Альтернатива
S ® b здесь невозможна. С другой стороны, если j и y начинаются с b, то должно применяться правило S ® b и b = g = b. Заметим, что случай b = g = e здесь невозможен, так как из S не выводится пустая цепочка e.

Когда рассматриваются два других вывода с нетерминалом A, то рассуждение аналогично. Ÿ

Пример 5.2. Рассмотрим более сложный случай - грамматику G2, определяемую правилами S ® eôabA, A ® Saaôb. Это не LL(1) грамматика, так как, пройдя часть левого вывода S Þ abA Þ abSaa для входных цепочек abaa или ababbaa и, имея на входе символ a, не ясно какое правило надо применить: S ® e или S ® abA. Покажем, что G2 – это LL(2) -грамматика.

Допустим, что S Þ * wSa Þ wba Þ * wj и S Þ * wSa Þ wga Þ * wy и первые два символа цепочки j (если они есть)совпадают с первыми двумя символами цепочки y. Нетрудно видеть, что здесь нет иных возможностей, кроме j = y = e, j и y начинается с aa, j и y начинается с ab. В первых двух случаях в обоих выводах применяется правило S ® e и b = g = e. В третьем случае должно применяться S ® abA и
b = g = abA. Ÿ

Пример 5.3. Рассмотрим грамматику G3 = ({S, A, B}, {0, 1, a, b}, P3, S), где P3 состоит из правил:

S ® AôB

A ® aAbô0

B ® aBbbô1

Здесь L(G3) = {an0bnôn ³ 0}È{ an1b2 nôn ³ 0}. G3 не является LL(k) -грамматика ни для какого k. Интуитивно, если мы начинаем с чтения достаточно длиной цепочки, начинающейся с символов a, то не знаем, какое из правил S ® A или S ® B было применено первым, пока не встретим 0 или 1. Обращаясь к точному определению LL(k) -грамматики, положим w = a = e, b = A, g = B, j = ak0bk и y = ak1b2 k. Тогда выводы

 

S Þ0 S Þ A Þ*ak0bk

 

S Þ0 S Þ B Þ*ak1b2 k

 

соответствуют выводам (1) и (2) определения. Первые k символов цепочек j и y совпадают, однако заключение b = g ложно. Так как k здесь выбрано произвольно, то G3 не является LL -грамматикой. Можно показать, что для языка L(G3) вообще не существует LL(k) -грамматики. Ÿ

Из определения LL(k) грамматики может показаться, что для определения нужного правила надо помнить уже всю проанализированную часть входной цепочки w. Но это не так. Рассмотрим теорему, очень важную для понимания LL(k) -грамматик, которая тривиально доказывается исходя из определения LL(k) -грамматики.

Теорема 5.1. КС-грамматика G = (N, S, P, S) является LL(k) -грамматикой тогда и только тогда, когда для двух различных правил A ® b и A ® g из P пересечение FIRSTk(ba) Ç FIRSTk(ga) пусто при всех таких wAa, что S Þ*wAa. €

 

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

 

Пример 5.4. Пусть грамматика G определяется двумя правилами S ® Saôb. Возьмем, как и в теореме 5.1, вывод S Þ i Sa i, где i ³ 0, A = S, a = e, b = Sa и g = b. Тогда для i ³ k

FIRST k (Saa i ) Ç FIRSTk(ba i ) = ba k-1

Таким образом, G не может быть LL(k) -грамматикой ни для какого k. €

 

 

Еще одно следствие теоремы 5.1 состоит в том, что если КС-грамматика G не содержит аннулирующих правил, то она будет LL(1) -грамматикой только в том случае, когда для всех AÎN каждое множество A -правил A ® a1ôa2ô¼ôa n из P таково, что FIRST1(a1), FIRST1(a2), ¼, FIRST1(an) попарно не пересекаются. (Отсутствие
e -пра­вил здесь существенно).

Введенная выше функция FOLLOW k (A) как раз и нужна для грамматик с аннулирующими правилами. Для LL(1) -грамматик справедливо следующее утверждение.

 

Теорема 5.2. КС-грамматика G = (N, S, P, S) является LL(1) -грамматикой тогда и только тогда, когда для двух различных правил A ® b и A ® g пересечение FIRST1(bFOLLOW 1 (A)) Ç FIRST1(gFOLLOW 1 (A)) пусто при всех AÎN. €

 

Другими словами G является LL(1) -грамматикой, если для каждого множества A -правил A ® a1ôa2ô¼ôa n

(1) множества FIRST1(a1), FIRST1(a2), ¼, FIRST1(a n) попарно не пересекаются,

(2) если a i Þ e, то FIRST1(a j) Ç FOLLOW 1 (A) = 0 для 1 £ j £ n, i ¹ j.

 

 

Таким образом, в случае k = 1 для однозначного выбора правила для нетерминала А, достаточно знать только нетерминал A и а – первый символ нерассмотренной части входной цепочки j:

следует выбрать правило A ® b, если а входит в FIRST1(b)

следует выбрать правило A ® e, если а входит в FOLLOW1(A).

 

 

Прежде чем рассмотреть алгоритм разбора для LL(1) -грамматик отметим, что неразрешима проблема распознавания существования LL(k) -грамматики, эквивалентной КС-грамматике G, которая не является LL(k) -грамматикой. Тем не менее существуют ситуации, в которых отдельные преобразования позволяют из не LL(1) -грамматики получить эквивалентную LL(1) -грамматику. Проиллюстрируем два таких преобразования на примерах.

 

Пример 5.5. Пусть G – леворекурсивная грамматика S ® Saôb, которая, как видно из примера 5.4 не является LL -грамматикой. Устраняя левую рекурсию, заменим два эти правила на следующие три:

S ® bS¢

S¢ ® aS¢ôe

получив при этом эквивалентную грамматику . С помощью теоремы 5.2 легко показать, что LL(1) -грамматика. €

 

Пример 5.6. Рассмотрим LL(2) -грамматику G – с двумя правилами S ® aSôa. Проведем левую факторизацию, “вынеся влево за скобку” символ a и, записав правила в виде S ® a(Sôe). Иными словами, мы считаем, что операция конкатенации дистрибутивна относительно операции выбора альтернативы. Заменив эти правила на

S ® aA

A ® Sôe

получим тем самым эквивалентную LL(1) -грамматику. €


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.007 сек.)