А.С. Герасимов - LR(0)-, SLR(1)-, LR(1)- и LALR(1)-анализ (1134670)
Текст из файла
Лекции по теории формальных языковЛекция 13.LR(0)-, SLR(1)-, LR(1)- и LALR(1)-анализАлександр Сергеевич Герасимовhttp://gas-teach.narod.ruКафедра математических и информационных технологийСанкт-Петербургского академического университетаРоссийской академии наук.Весенний семестр 2010/11 учебного года13 мая 2011 г.А. С. Герасимов (СПбАУ РАН)Лекции по теории формальных языков13 мая 2011 г.1 / 30План1LR(0)-анализ2SLR(1)-анализ3LR(1)-анализ4LALR(1)-анализА. С. Герасимов (СПбАУ РАН)Лекции по теории формальных языков13 мая 2011 г.2 / 30План1LR(0)-анализ2SLR(1)-анализ3LR(1)-анализ4LALR(1)-анализА.
С. Герасимов (СПбАУ РАН)Лекции по теории формальных языков13 мая 2011 г.3 / 30Анализ с помощью LR(0)-автомата:неформальное описаниеПодадим цепочку w на вход LR(0)-автомату AG грамматики G .После каждого такта работы автомата AG кладём новое состояниеавтомата в стек и, анализируя это состояние, до перехода кследующему такту производим описанные ниже действия.Если в состоянии есть пункт [A → α1 · α2 ] и α2 6= ε, то выполняемперенос следующего символа, т. е. переходим к следующему тактуработы автомата AG .Если в состоянии есть пункт [A → α·], то выполняем свёртку поправилу A → α (при этом активный префикс γα в стекезаменяется на активный префикс γA):IIIвыталкиваем из стека |α| состояний;на вершине стека оказывается состояние I после прочтения γ;вернём автомат в состояние I и дадим прочитать ему наследующем такте A.Если таким образом автомат прочитает w и придёт в состояние,содержащее пункт [S 0 → S·], то w ∈ L(G ), иначе w ∈/ L(G ).А.
С. Герасимов (СПбАУ РАН)Лекции по теории формальных языков13 мая 2011 г.4 / 30КонфликтыКонфликт перенос-свёртка: в одном состоянии LR(0)-автоматаимеются пунктыII[A → α1 · α2 ], где α2 6= ε, и[B → β·].Конфликт свёртка-свёртка: в одном состоянии LR(0)-автоматаимеются различные пунктыII[A → α·] и[B → β·].А.
С. Герасимов (СПбАУ РАН)Лекции по теории формальных языков13 мая 2011 г.5 / 30LR(0)-грамматика: определение и примерГрамматика называется LR(0)-грамматикой, если каждоесостояние её LR(0)-автомата, содержащее пункт вида [A → α·],состоит из единственного пункта.Пример. G1 : (0) S 0 → S, (1) S → aDc, (2) D → Db, (3) D → b.А. С. Герасимов (СПбАУ РАН)Лекции по теории формальных языков13 мая 2011 г.6 / 30Алгоритм построения LR(0)-анализатораВход.
Расширенная LR(0)-грамматика G = (Σ, Γ, P, S 0 ).Выход. Таблица LR-анализа для грамматики G .1. построить LR(0)-автомат AG = (Q, Σ ∪ Γ, δ, I0 , Q);2. для каждого I ∈ Q3.для каждого i ∈ I4.если (i = [S 0 → S·]) action(I, a) := X;5.иначе если (i = [A → α·])6.для каждого a ∈ Σ ∪ {a}7.action(I, a) := (⊗номер(A → α));8.иначе если (i = [A → β1 · aβ2 ])9.action(I, a) := ( δ(I, a));10.иначе (т. е. i = [A → β1 · Bβ2 ])11.goto(I, B) := δ(I, B)Почему в каждой клетке построенной таблицы не более одной записи?А. С.
Герасимов (СПбАУ РАН)Лекции по теории формальных языков13 мая 2011 г.7 / 30Пример построения LR(0)-анализатораG1 : (0) S 0 → S, (1) S → aDc, (2) D → Db, (3) D → b.aSDab1b2c∇А. С. Герасимов (СПбАУ РАН)⊗3⊗2⊗1aactionbcb2b1⊗3⊗2⊗1aXgotoS DcD⊗3⊗2⊗1⊗3⊗2⊗1SЛекции по теории формальных языков13 мая 2011 г.8 / 30Предложение о корректности алгоритма построенияLR(0)-анализатораПредложениеLR(0)-анализатор, построенный алгоритмом на слайде 7 пограмматике G , допускает цепочку w тогда и только тогда, когдаw ∈ L(G ).Д о к а з а т е л ь с т в о.Этот анализатор работает как LR(0)-автомат с запуском изнеочередного состояния в случае свёртки и складыванием всостояний стек.Анализатор выполняет свёртку в том и только в том случае, когдаон находится в состоянии I вида {[A → α·]}.Если LR(0)-автомат находится в состоянии I, а в стеке — γ = γ 0 α,то по основной теореме LR-анализа γ является активнымпрефиксом, для которого допустим пункт [A → α·],а α является основой некоторой r -формы, начинающейся с γ.А.
С. Герасимов (СПбАУ РАН)Лекции по теории формальных языков13 мая 2011 г.9 / 30Предложение о корректности алгоритма построенияLR(0)-анализатора: окончание доказательстваВ состоянии I имеется единственный пункт [A → α·], поэтомуα является основой любой r -формы, начинающейся с γ.Таким образом, анализатор выполняет свёртку тогда и толькотогда, когда наверху стека находится основа текущей r -формы.Иначе анализатор пытается осуществить перенос.
Есликонкатенация содержимого стека и необработанного суффиксавходной цепочки является r -формой, то такой перенос возможен,поскольку LR(0)-автомат распознаёт все активные префиксы.Наконец, допуск производится тогда и только тогда, когдавходная цепочка свёрнута в аксиому грамматики.А. С. Герасимов (СПбАУ РАН)Лекции по теории формальных языков13 мая 2011 г.10 / 30Теорема об оценке числа шаговLR(0)-анализатораТеоремаЧисло шагов (переносов и свёрток) LR(0)-анализатора, построенногоалгоритмом на слайде 7, линейно зависит от длины входной цепочки.А.
С. Герасимов (СПбАУ РАН)Лекции по теории формальных языков13 мая 2011 г.11 / 30План1LR(0)-анализ2SLR(1)-анализ3LR(1)-анализ4LALR(1)-анализА. С. Герасимов (СПбАУ РАН)Лекции по теории формальных языков13 мая 2011 г.12 / 30Пример конфликта «свёртка-свёртка»G2 : (0) S 0 → S, (1) S → aDb, (2) D → Db, (3) D → b.Разрешение конфликта:если очередной символ a, то ⊗1;если очередной символ b, то ⊗2.А. С.
Герасимов (СПбАУ РАН)Лекции по теории формальных языков13 мая 2011 г.13 / 30Пример конфликта «перенос-свёртка»G3 : (0) S 0 → S, (1) S → ac, (2) S → aDbc, (3) D → Db, (4) D → ε.S∇ = {[S 0 → ·S], [S → ·ac], [S → ·aDbc]} → S = {[S 0 → S·]}↓aca = {[S → a · c], [S → a · Dbc], [D → ·Db], [D → ·]} → c1 = {[S → ac·]}↓DbcD = {[S → aD · bc], [D → D · b]} → b = {[S → aDb · c], [D → Db·]} →c2 = {[S → aDbc·]}Разрешение конфликтов:если очередной символ c, то перенос;если очередной символ b, то свёртка.А.
С. Герасимов (СПбАУ РАН)Лекции по теории формальных языков13 мая 2011 г.14 / 30Разрешение некоторых конфликтов при помощимножеств follow(A)Свёртка по правилу A → α является правильным действиемLR-анализатора, только если очередной входной символпринадлежит follow(A).Пусть пункт [A → α·] (A 6= S 0 ) принадлежит состоянию ILR(0)-автомата.Тогда достаточно положить action(I, a) := (⊗номер(A → α))лишь для всех a ∈ follow(A).А. С.
Герасимов (СПбАУ РАН)Лекции по теории формальных языков13 мая 2011 г.15 / 30Алгоритм построения SLR(1)-анализатораВход. Расширенная грамматика G = (Σ, Γ, P, S 0 ).Выход. Таблица LR-анализа для грамматики G .1. построить LR(0)-автомат AG = (Q, Σ ∪ Γ, δ, I0 , Q);2. построить follow(A) для каждого A ∈ Γ;3. для каждого I ∈ Q4.для каждого i ∈ I5.если (i = [S 0 → S·]) action(I, a) := X;6.иначе если (i = [A → α·])7.для каждого a ∈ follow(A)8.action(I, a) := (⊗номер(A → α));9.иначе если (i = [A → β1 · aβ2 ])10.action(I, a) := ( δ(I, a));11.иначе (т.
е. i = [A → β1 · Bβ2 ])12.goto(I, B) := δ(I, B)А. С. Герасимов (СПбАУ РАН)Лекции по теории формальных языков13 мая 2011 г.16 / 30SLR(1)-грамматика: определение и примерГрамматика называется SLR(1)-грамматикой, если в таблицеaction, построенной алгоритмом на предыдущем слайде, нетконфликтов (т. е.
в каждой клетке не более одной записи).Пример. G2 : (0) S 0 → S, (1) S → aDb, (2) D → Db, (3) D → b.follow(S) = {a}, follow(D) = {b}.actionbaXb2b1⊗3⊗2 ⊗1aSDab1b2∇А. С. Герасимов (СПбАУ РАН)agotoS DDSЛекции по теории формальных языков13 мая 2011 г.17 / 30(0) E 0 → E ,(1) E → E + T ,(4) T → F ,А. С.
Герасимов (СПбАУ РАН)(2) E → T ,(5) F → (E ),Лекции по теории формальных языков(3) T → T ∗ F ,(6) F → x.13 мая 2011 г.18 / 30Пример построения SLR(1)-анализатора: окончаниеfollow(E ) = {+, ), a}, follow(T ) = follow(F ) = {∗, +, ), a}.E1T1F1(x+∗E2T2F2)∇++⊗2⊗4∗actionx(∗⊗4⊗2⊗4x⊗6А.
С. Герасимов (СПбАУ РАН)E2⊗6)⊗1⊗3⊗5T1F1T2F1F2T1F1⊗6((∗⊗3⊗5xaX⊗2⊗4(⊗6xx+⊗1⊗3⊗5)gotoETF⊗1⊗3⊗5(Лекции по теории формальных языковE113 мая 2011 г.19 / 30План1LR(0)-анализ2SLR(1)-анализ3LR(1)-анализ4LALR(1)-анализА. С. Герасимов (СПбАУ РАН)Лекции по теории формальных языков13 мая 2011 г.20 / 30Пример не SLR(1)-грамматикиG4 : S 0 → S, S → ac|bDc|Da, D → a.SLR(1)-анализатор для G4 содержит конфликт в состоянии a1 ,поскольку follow(D) = {c, a}. Разрешение конфликта: свёрткуделать, если очередной входной символ a, но не c.А. С.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
