Формальные языки и автоматы - Методичка для сдающих и пересдающих, страница 4

Поясняю: это вроде число терминальных символов, на которые намнадо посмотреть,чтобы однозначно определить, какому правилу анализатора нужноследовать.При этом LL(n)-анализаторов, где отличен от 1, среди моих знакомых вроде никтоне встречал (да и в вариантах прошлых лет их не было.Другое дело LR(n). Здесьвстречался и как 0, и как 1. Говорят, что когда-то да-же были LR(2), но сейчас нас вроде обнадежили, что такого сатанизма у нас не будет.LR(n)-анализатор делает ровно то же самое, что и LL-анализатор: по-хитрому разбирает цепочку. Разница в том, что LR(n) можно построить для любой КС грамматики(но это неточно).

При этом и выглядит он гораздо хуже.Также есть смысл сказать, что LR-анализатор это очень стремная и непонятнаяхрень. Все мои объяснения являются лишь плодом моего больного воображения, которое попробовала найти во всем этом нормальную человеческую логику.Мои объяснения по этой теме могут очень сильно расходиться с действительностью.9.1Алгоритм1) Первым делом мы пополняем нашу грамматику новым правиломстарая аксиома грамматики. Теперь у нас новая аксиома** → ,где.2) Введем понятие LR(1)-ситуации:[ → ., ],где → - правило грамматики, а- терминальны символ.Возмущенный читатель может спросить: что это вообще за хуйня?35-Отвечаю.

→ ,мы(слева от точки), в данный момент внимательно смотрим наСитуация выше означает, что сейчас мы пытаемся раскрыть правилоуже обработали (справа[ → ., #].(между точкой и запятой) , а впереди еще естьЗа начальную ситуацию принимаетсяот запятой).*Далее мы будем работать с множествами таких ситуаций, которые я для простоты икраткости буду называть группами.3) Строим замыкание группы.А строится оно просто:∀[ → ., ] ∈ , где - нетерминал сразу после точки∀ правил → и ∀ терминалов ∈ () добавляем[ → ., ]вситуации видаИ по старому сложившемуся обычаю повторяем до стабилизации группы.4) Оформляем переходы из группы в группу:Из группыгруппу , ,[ → ., ] мы по символу ситуацию → ., где есть ситуацияв которую добавимпереходим в новуюПри этом в какой-то момент новая группа может полность совпасть с группой, которую мы уже построили.

Это значит, что переход будет именно в старую группу:новую идентичную группу создавать не надо.365) Теперь нужно построить ВСЕ группы для грамматики, начиная с самой первойгруппы, в которой сначала есть только ситуация[ * → ., #].Вот живой пример:Грамматика:* → → | → |→01, 23, 45Анализатор с группами:6) А теперь строим таблицу анализатора. Сразу скажу, что схему с рисунками лучшесмотреть у Тани: у нее стрелочками помечено, что от каких правил получается. Я жепривожу только правила.∀ → , где - нетерминал, добавим в таблицу ( , ) = ∀ → , где - терминал, добавим ( , ) = ℎ ∀ , где есть ситуация вида → ., , добавим ( , ) = ( →)(номер правила)*При этом ( → ) = 0 записывается как Все остальное - 37Сама таблица: 0S4# S51123ACC2S63S84S7S105R56R39R37R18R29R4R410R5R57) Разбор цепочки (его по-прежнему лучше посмотреть у Тани)Все начинается с такого начального состояния:0|1 2 ...

#Теперь мы будем разбирать цепочку по таблице анализатора, гдеобозначаетвыполнение правила грамматики с указанным номером в обратную сторону.ℎ обозначает перенос терминального символа в левый магазин и установку цифры, идущей после туда же. обозначает принятие цепочки.Очень важно, чтобы в магазине в конце всегда была цифра!0|0a4|0a4b10|0a4B|0a4B9|0A|0A2|0A2a6|0A|0A2|0A2b7|0S|0S1|#############[0, a] = S4[4, b] = S10[10, a] = R5[4, B] = 9[9, a] = R4[0, A] = 2[2, a] = S6[6, b] = R3[0, A] = 2[2, b] = S7[7,#]= R1[0, S] = 1[1,#]= ACCПолучили Accept - цепочка принадлежит языку, ура!38Чтобы получить дерево разбора, нужно последовательно применять кправила сни-зу вверх.Для словаполучается такая последовательность:1, 3, 4, 5И само дерево разбора тоже имеется:8) По таблице LR(1)-анализатора можно определить, является ли наша грамматикаLR(0).

Для этого должны выполняться следующие условия:ℎ и не могут встречаться в одной строке. в одной строке относятся только к одному правилу.9.2Почему это работаетОбъяснить это очень сложно, но получить какое-то эфемерное понимание всего этогоужаса можно, если держать в голове уже изложенную мысль: → ., означает, что мы сейчас работаем на , мы уже обработали , в данныймомент пытаемся что-то сделать с , а после после разбора всего этого великолепиядолжен остаться символ .Соответственно переходы по НЕтерминальному символу символизируют фразу:"Окей, допустим, что мы разобрались с "Переходы по терминальному символу символизируют фразу: "Окей, мы обработали еще и "А конструкции вида → ., означает, что существует такой вариант, что мы раскрутим нетерминал по правилу → , и при этом справа останется .399.3Ловля ошибок в зародышеИногда бывает очень полезно понять, что данный вид анализатора не подходит (илибыла допущена ошибка), еще до разбора цепочки.

В процессе написания главы проLR-анализаторы я подметил для себя такую вещь:Если вдруг при построении анализатора в одной группе оказались ситуации вида: → ., → ., То можно смело сворачиваться или искать ошибку.Почему?Потому что первая ситуация будет интерпретирована, какпо сим-ℎ по символу .Получается конкуренция за символ , значит таблицу анализатора построить в такомволу, ( → )а вторая ситуация - каквиде не получится. Если поймать такую ошибку до построения всего анализатора,можно сэкономить очень много времени.Посмотреть на живые примеры таких неудач можно на примере грамматик:* → → ||Получаются такие конфликтующие ситуации: → ., # → ., Или более неочевидный пример:* → → | → | → |Конфликтующие ситуации там следующие: → ., # → ., Все эти грамматики являются LR(2) грамматиками, потому что есть ситуации, когдамы не можем по одному символу из цепочки определить, какое правило нужно применять.

В случае первой грамматики по символам1, а по символам#- 2.40нужно раскручивать правилоГлава 10Лемма о накачкеЛемма о накачке, а точнее ее отрицание, это, наверное, самый простой способ доказательства нерегулярности (как минимум потому, что других я не знаю).Лема звучит следующим образом: - регулярный язык над алфавитом .*Тогда ∃ ∈ N, что ∀ ∈ , || ≥ ∃, , ∈ : = , ̸= , || ≤ ∀ ≥ 0 ∈ ПустьиНо это было в общеобразовательных целях. А теперь реально полезная вещь: отрицание леммы о накачке. - язык над алфавитом .Если ∀ ∈ N найдется такое ∈ , || ≥ , что при ∀, , : = , || ≥ 1, || ≤ ∃ ∈ N : ∈/ , тогда язык нерегулярный.ПустьЕсли простым плебейским языком, то1) Берем некоторое ∈ N.2) Ему в соответствие ищем особое слово∈длины не меньше3) Разбиваем его случайным образом на 3 слованепустым, а длинане превосходила4) Ищем такое ∈ N,чтобы таким образом, чтобыбыл).не принадлежал языку.5) Доказываем, что мы сможем найти особое слово для пункта 2 при любомиз пункта 1:(все следующие условия должны выпол-няться при любом возможном разбиении слова, , .∈Nязык нерегулярный.Часто эта лемма нужна в задачах, где спрашивают "регулярен ли вот этот язык?".Как несложно догадаться, как правило, он нерегулярен.41Есть довольно неплохой способ (на мой взгляд) быстрой прикидки регулярности языка: на язык нужно внимательно смотреть 30 секунд и пытаться придумать для негорегулярное выражение (только честное каноническое РВ, а не какое-нибудь стероидное из Perl).Если за 30 секунд пристального взгляда это не удается сделать, значит, язык, скореевсего, нерегулярен и можно пробовать раскрутить его через отрицание леммы.Очень часто даются языки, где количества букв в двух разных местах каким-то образом связаны.

= . У меня не получилось придумать для него честное каноническоеНапример,регулярное выражение, поэтому применяем лемму.1) Выбрали и зафиксировали случайное значение . может2) В качестве особого слова возьмем слово3) При таком выборе особого слова слово−1{, , ..., , },4) Берем- как−1{, , ..., }. Слово максимум из − 1 буквы . = 2.быть одним из множестватак как его длина не превосходитним из следующих слова слово. .При этомПолучаем набор слов, где как минимумПочему это работаетПотому что.Объяснил?Хочется реально почитать доказательство?Если да, можно просто загуглить.Работает и черт бы с ней.Серьезно.У нее нет человеческого объяснения.Как и других лемм/теорем в курсе.А ты думал, тут сейчас все понятно распишут?42может быть од-как минимум состоит из 1 буквы+1буквэто слово, очевидно, не принадлежит исходному языку.

Радуемся.10.1ибукв.,АГлава 11Немножко полезных советов отчеловека, который не сдал1) Кажду задачу можно решать с чуть-чуть различающимися обозначениями. Попробуйте найти удобную для себя нотацию к каждой задаче и отработайте ее.2) Используйте цветные ручки/карандаши. Нет, это не гейство, это вынужденныйгомосексуализм. Размечайте цветом все, что нужно потом будет быстро друг от друга отличать.

Это повышает скорость обработки в дальнейшем, а главное - повышаетточность.Из того, что могу подсказать я: , в дереве РВ.Начальные, конечные состояния автоматов.Переходы по терминалам/нетерминалам в LR-анализаторах.ситуации в LR-анализаторах.3) Используйте более короткую и более емкую запись. Ни в коем случае не рисуйтеавтоматы так, как я рисовал их для этой методички: я изрядно заебался штриховатьэти круги по 8 секунд каждый, но делал это, чтобы было как можно лучше видно вЧБ исполнении. На мой взгляд достаточно поставить звездочку у конечного состояния (или, как уже предлагалось выше, использовать цвета)Очень не советую полность расписывать похожие ситуации в LR-анализаторах так → ., → ., → ., #Они вполне неплохо помещается в таком виде → ., #(но опять же, к такой форме нужно чуть-чуть привыкнуть, чтобы некосячить)4) Берегите себя и своих близких.43Глава 12БлагодарностиСпасибо корешам, перед которыми я в свое время зарекнулся написать это все.Спасибо Владиславу Грубову и Вадиму Глазкову за стилистические замечания (да,раньше язык был еще хуже) и помощь в поиске ответов на вопросы по сути предмета.Спасибо Роману Лозко за найденные ошибки.Спасибо Михаилу Валентиновичу Федотову за то, что этот потрясающий курс преподается в стенах факультета ВМК.ВЖУХ, и у тебя неуд44.