А.С. Герасимов - LR(0)-, SLR(1)-, LR(1)- и LALR(1)-анализ (1134670), страница 2
Текст из файла (страница 2)
Герасимов (СПбАУ РАН)Лекции по теории формальных языков13 мая 2011 г.21 / 30LR(1)-пунктыПусть G = (Σ, Γ, P, S 0 ) — расширенная грамматика.LR(1)-пункт: [A → β1 · β2 , a], гдеII[A → β1 · β2 ] — LR(0)-пункт, называемый ядром этого LR(1)-пункта,a — терминал или символ a.LR(1)-пункт [A → β1 · β2 , a] допустим для активного префиксаαβ1 , если существует (правый) выводS 0 ⇒∗ αAw ⇒ αβ1 β2 w ⇒∗ uwи цепочка w a начинается символом a.Автоматом LR(1)-пунктов грамматики G назовём ε-НКА(1)IG = (Q, Σ ∪ Γ, δ, {i0 }, Q), гдеIIIQ — множество всех LR(1)-пунктов грамматики G ,i0 = [S 0 → ·S, a],отношение переходов состоит из всех базисных переходов вида([A → β1 · X β2 , a], X , [A → β1 X · β2 , a]) и всех ε-переходов вида([A → β1 · Bβ2 , a], ε, [B → ·β, b]), где b ∈ first(β2 a) и припостроении first(β2 a) мы считаем a терминалом.(1)Для IG верны основная теорема LR-анализа и её следствия.А.
С. Герасимов (СПбАУ РАН)Лекции по теории формальных языков13 мая 2011 г.22 / 30LR(1)-автомат(1)(1)ДКА (неполный) AG , построенный по ε-НКА IG алгоритмом излекции 2, будем называть LR(1)-автоматом грамматики G .Пусть M — произвольное множество LR(1)-пунктов расширеннойграмматики G .Положим, что closure1 (M) есть минимальное по включениюмножество LR(1)-пунктов такое, чтоIIM ⊆ closure1 (M) и[A → β1 · Bβ2 , a] ∈ closure1 (M) влечёт[B → ·γ, b] ∈ closure1 (M) для каждого правила вывода видаB → γ и каждого b ∈ first(β2 a).Пусть X — терминал или нетерминал грамматики G .
Положимgoto1 (M, X ) = closure1 ({[A → β1 X ·β2 , a] | [A → β1 ·X β2 , a] ∈ M}).Алгоритм построения LR(1)-автомата.А. С. Герасимов (СПбАУ РАН)Лекции по теории формальных языков13 мая 2011 г.23 / 30Пример построения LR(1)-автоматаG4 : (0) S 0 → S, (1) S → ac, (2) S → bDc, (3) S → Da, (4) D → a.(1)Переходы в IG4 имеют вид ([A → β1 · X β2 , a], X , [A → β1 X · β2 , a])и ([A → β1 · Bβ2 , a], ε, [B → ·β, b]), где b ∈ first(β2 a).На этом рисунке опущенный второй компонент в LR(1)-пунктах есть a.А. С. Герасимов (СПбАУ РАН)Лекции по теории формальных языков13 мая 2011 г.24 / 30Алгоритм построения LR(1)-анализатора.Определение LR(1)-грамматикиВход.
Расширенная грамматика G = (Σ, Γ, P, S 0 ).Выход. Таблица LR-анализа для грамматики G .(1)1. построить LR(1)-автомат AG = (Q, Σ ∪ Γ, δ, I0 , Q);2. для каждого I ∈ Q3.для каждого i ∈ I4.если (i = [S 0 → S·, a]) action(I, a) := X;5.иначе если (i = [A → α·, a])6.action(I, a) := (⊗номер(A → α));7.иначе если (i = [A → β1 · aβ2 , c])8.action(I, a) := ( δ(I, a));9.иначе (т.
е. i = [A → β1 · Bβ2 , c])10.goto(I, B) := δ(I, B)Грамматика называется LR(1)-грамматикой, если в построеннойэтим алгоритмом таблице action нет конфликтов (т. е. в каждойклетке не более одной записи).А. С. Герасимов (СПбАУ РАН)Лекции по теории формальных языков13 мая 2011 г.25 / 30Пример построения LR(1)-анализатораG4 : (0) S 0 → S, (1) S → ac, (2) S → bDc, (3) S → Da, (4) D → a.aSD1D2a1a2a3bc1c2∇А. С.
Герасимов (СПбАУ РАН)actionbcaXgotoS Dc2a3c1⊗4⊗4⊗3a2D1⊗1⊗2a1bSЛекции по теории формальных языковD213 мая 2011 г.26 / 30План1LR(0)-анализ2SLR(1)-анализ3LR(1)-анализ4LALR(1)-анализА. С. Герасимов (СПбАУ РАН)Лекции по теории формальных языков13 мая 2011 г.27 / 30LARL(1)-анализДля языка программирования Паскаль LR(1)-автомат имеетнесколько тысяч состояний, тогда как LR(0)-автомат — несколькосотен состояний.LALR — Look Ahead LR, LR-анализ с предпросмотром.LALR(1)-автомат грамматики получается из LR(1)-автомата этойграмматики объединением всех состояний, имеющих одно и то жемножество ядер LR(1)-пунктов, в одно состояние.Для LR(1)-грамматики LALR(1)-автомат не имеет конфликтовперенос-свёртка.IIПусть [A → α·, a] и [B → β1 · aβ2 , b] принадлежат одномусостоянию LALR(1)-автомата.Тогда [A → α·, a] и [B → β1 · aβ2 , c] (для некоторого c)принадлежат одному состоянию LR(1)-автомата.(Но конфликты свёртка-свёртка могут появиться.)Грамматика называется LALR(1)-грамматикой, если нетконфликтов в таблице action, построенной алгоритмом наслайде 25, но по LALR(1)-автомату этой грамматики.А.
С. Герасимов (СПбАУ РАН)Лекции по теории формальных языков13 мая 2011 г.28 / 30Пример LR(1)-, но не LALR(1)-грамматикиG5 : S 0 → S, S → aAa|aBb|bAb|bBa, A → c, B → c.c1,2 = c1 ∪ c2 = {[A → c·, a/b], [B → c·, a/b]}.([A → α · β, a/b] — сокращение [A → α · β, a], [A → α · β, b].)А. С. Герасимов (СПбАУ РАН)Лекции по теории формальных языков13 мая 2011 г.29 / 30ЛитератураОсновная литератураЗамятин А.
П., Шур А. М. Языки, грамматики, распознаватели:Учебное пособие. Екатеринбург : Изд-во Урал. ун-та, 2007(электронный вариант книги — на http://elar.usu.ru, поиск).Дополнительная литератураАхо А., Лам М., Сети Р., Ульман Дж. Компиляторы: принципы,технологии и инструментарий. М.: ООО ”И.Д. Вильямс”, 2008.Ахо А., Ульман Дж.
Теория синтаксического анализа, перевода икомпиляции. М.: Мир, 1978.Мартыненко Б. К. Языки и трансляции: Учеб. пособие. СПб.:Издательство С.-Петербургского университета, 2004 (электронныйвариант книги — на http://www.math.spbu.ru/user/mbk).А. С. Герасимов (СПбАУ РАН)Лекции по теории формальных языков13 мая 2011 г.30 / 30.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
