fl_task11 (1) (1178916), страница 2
Текст из файла (страница 2)
Если, при этом из цепочки β выводимо пустое слово, тоза словом, выводимым из нетерминала X следует слово из множестваFOLLOW(A), поскольку из вывода6S ⇒∗ γAw ⇒ γαXβw ⇒ γ |{z}αX wAследует, что если элемент FIRST(w) лежит в множестве FOLLOW(A),то элемент FIRST(w) лежит так же в множестве FOLLOW(X). Такимобразом, по определению функции FOLLOW, если в грамматике естьправило A → αXβ и при этом из цепочки β выводимо пустое слово,то множество FOLLOW(X) включает в себя множество FOLLOW(A).В частности, возможно что β = ε, поэтому при наличии в грамматикеправила A → αX, справедливо FOLLOW(X) ⊇ FOLLOW(A).В итоге, мета-алгоритм сводится к следующим шагам:• Вычислить множества FIRST для грамматики G;• Для правил A → αXβ добавить FIRST(β) \ {ε} к FOLLOW(X);• Для правил A → αXβ, таких что, ε ∈ FIRST(β) добавить FOLLOW(A)к FOLLOW(X).Упражнение 5.
Доказать корректность данного мета-алгоритма. Тоесть, что все элементы множеств FOLLOW будут найдены и ничего лишнего найдено не будет.Замечание 1. По хорошему, возникает проблема с тем, лежит ли пустоеслово в FOLLOW(X). Эта проблема решается следующим образом: ковсем словам, порождаемым G добавляется маркер конца слова, и еслиэтот маркер оказывается в FOLLOW(X), то пустое слово принадлежитFOLLOW(X). Для этого по грамматике G строится пополненная грамматика G0 , которая содержит правило S 0 → S$, где $ – маркер концаслова. Все остальные правила грамматики G0 взяты из грамматики G.На практике, функция FOLLOW используется в анализаторах, на входкоторым и так подаётся пополненная грамматика, поэтому решать проблему наличия пустого слова в множестве FOLLOW(X) не надо.Теперь опишем сам алгоритм.
Идея алгоритма схожа с индуктивнымвычислением множеств FIRST.7Алгоритм:Шаг 0. Для каждого нетерминала Y положим F0 (Y ) = ∅. Вычислимзначение функции FIRST для грамматики G.Шаг i. Положить множество Fi (X) равным множеству Fi−1 (X).Для каждого правила A → αXβ добавить FIRST(β) \ {ε} к Fi (X);Если ε ∈ FIRST(β) добавить Fi−1 (A) к Fi (X).Остановка. Как только Fi (Y ) = Fi−1 (Y ) для любого Y из N . Положить FIRST(X) = Fi (X).4От FIRST к FIRSTkСначала введём вспомогательную операцию на множествах.
Пусть L1 иL2 некоторые языки. Тогда язык L1 ⊕k L2 состоит из всех таких слов w,что либо в языке L1 есть слово w1 длины не меньшей k и w = w1 [1, k],либо слово x длины не большей k лежит в L1 , слово y лежит в L2 , словоu есть их конкатенация xy и, наконец, w = u[1, k], если |u| > k или простоw = u, если |u| < k. ФормальноL1 ⊕k L2 = {w | ∃x ∈ L1 , ∃y ∈ L2 , u = xy, |u| 6 k ⇒ w = u, |u| > k ⇒ w = u[1, k]}Другой вариант формального определения, чтобы окончательно запутать читателя:L1 ⊕k L2 = {xy | x ∈ L1 , y ∈ L2 , |xy| 6 k}∪{u[1, k] | ∃x ∈ L1 , ∃y ∈ L2 , u = xy, |xy| > k}Из определения операции ⊕k следует, что для X1 , X2 , . .
. Xn ∈ N ∪ TсправедливоFIRSTk (X1 X2 . . . Xn ) = FIRSTk (X1 ) ⊕k FIRSTk (X2 ) ⊕k . . . ⊕k FIRSTk (Xn ).Фактически, когда мы вычисляли функцию FIRST, мы вычислялиеё используя оператор ⊕1 . Перепишем алгоритм вычисления функцииFIRST для вычисления функции FIRSTk .Алгоритм:8Шаг 0. Для каждого терминала σ положим Fi (σ) = σ для любогоi.
Для каждого нетерминала Y , рассмотрим все правила вида Y →xα, где x – слово (быть может пустое!), а цепочка α либо начинаетсяс нетермнинала, либо пуста. Если |x| > k , добавим к множествуF0 (Y ) слово x[1, k]. Иначе, если α = ε, добавим к множеству F0 (Y )слово x.Шаг i. Добавить к множеству Fi (X) множество Fi−1 (X). Для каждого правила X → β = Y1 . . . Ynдобавить к Fi (X) множество Fi−1 (Y1 ) ⊕k .
. . ⊕k Fi−1 (Yn ),вычислить Fi (Yj ), для j = 1..nОстановка. Fi (Y ) = Fi−1 (Y ) для любого Y из N . Положить FIRSTk (X) =Fi (X).Упражнение 6. Доказать корректность работы данного алгоритма.На практике удобно вычислять функцию FIRSTk для всех нетерминалов сразу.5LL(k)-грамматикиМы не будем строить анализаторы для LL(k)-грамматик, где k > 1 всилу нехватки времени. Тем не менее, мы будем работать с определениемLL(k)-грамматики и её свойствами.Вспомним, что грамматика является LL(k)-грамматикой тогда и только тогда, когда она левоанализируема, т.е.
существует детерминированный анализатор (ДМП-автомат с выходом), который реализует СУ перевод w → πl (w).С таким определением не очень удобно работать с точки зрения анализа грамматики, поэтому мы будем также использовать эквивалентныеему определения.Теорема 1. Грамматика является LL(k)-грамматикой тогда и толькотогда, когда для любых двух правил A → β, A → γ, FIRSTk (γα) ∩FIRSTk (βα) = ∅ для таких α, что S ⇒∗l wAα.Не все грамматики, задающие LL-языки являются LL-грамматиками.Но некоторые из них можно преобразовать к LL(k)-грамматике используя приёмов левой факторизации и удаления левой рекурсии. Изучитеэти приёмы по книжке Серебрякова или по Ахо и Ульману.96ЗадачиВ первых двух задачах под грамматикой G понимается грамматика, порождающая арифметические выражения.Задача 1.
Построить дерево вывода, левые и правые разборы для слова((a)) в грамматике G, определённой выше.Задача 2. Построить детерминированный левый анализатор для грамматикиS → 0SS → 1SS→ε(1)(2)(3)3∗. Добавим в грамматику G правило E → ε. Вычислите значение функции F IRST (E).Задача 4. Докажите, что грамматика не является LL(1)-грамматикой,но является LL(2)-грамматикой.
Вычислите функции FIRST2 и FOLLOW2для всех нетерминалов.S → aAaa|bAbaA → b|εЗадача 5. Для грамматики написать эквивалентную LL(1)-грамматикуи вычислить функции FIRST и FOLLOW для каждого нетерминала. Постройте по получившейся грамматике LL(1)-анализатор.S → ba|AA → a|Aab|AbЗадача 6∗.
Докажите, что язык a∗ ∪ an bn не является LL-языком.10.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
