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

Почему же мы именно так выбираем конечные состояния в случае пересечения и произведения?Все просто: в случае пересечения нам надо, чтобы оба автомата остановились в своих конечных состояниях (потому что слово должно принадлежать обоим языкам).Соответсвенно, нам нужны состояния, состоящие из конечных состояний автоматов.Абсолютно аналогичная ситуация с объединением: нам нужно, чтобы хотя бы одиниз исходных автоматов остановился в своем конечном состоянии.23Глава 6Построение автомата поправолинейной грамматике6.1Алгоритм . Множество конечных → , тогда = {, }, иначе- аксиома грамматики.

Значит, начальное состояние у нас описывается так: если есть переход = {} ( это просто финальное состояние, такогосостоянийке быть не должно)Переходы строятся по следующим правилам:Возьмем такую грамматику: → || → || → || → ||24терминала вообще в граммати-Построим автомат по правилам выше:И что, все?Ну да, все6.2Почему это работаетПраволинейные грамматики очень хороши хотя бы тем, что если раскручивать их,начиная с аксиомы , мы ни в какой момент времени не сможем иметь больше одногонеобработанного нетерминала.Очень похоже на автомат: там мы тоже всегда находимся в одном состоянии (еслиавтомат один).

→ говорят как бы следующее: мы разобрались с нетерминалом , потому что увидели терминал и все для себя поняли, теперь надоразобраться с нетерминалом .Это уже самый натуральный автомат, где состояние соответствуте нетерминалу ,При этом правила видакоторый мы еще не успели раскрутить.25Глава 7Приведение КС-грамматики7.1Алгоритм удаления бесплодных символовБесплодные символы - те, из которых невозможно вывести цепочку.Алгоритм простой:Строим множества0 = {} = {; → , ∈ −1 ∪ * } ∪ −1То есть, мы последовательно добавляем в новое множество то, из чего можно былобы вывести предыдущее. Все это надо повторять до стаблилзации.Рассмотри на примере: → | → | → || → || → ||01234= {}= {, }, ( → , → |)= {, , }, ( → )= {, , , }, ( → )= 3После этого нужно удалить все правила, которые были связаны с бесплодными символами.XXX →X| → |hhhh((((h((h(h(→||h(h(hh((h → ||HH → ||267.2Почему это работаетВ данном случае мы просто идем с конца и смотрим, из чего мы могли бы вывестислово, состоящее только из терминальных символов.

В конце остается множество технетерминалов, из которых можно вывести что-то годное. Соответственно, другие намне нужны.7.3Алгоритм удаления недостижимых символовСразу скажу, что этот алгоритм есть смысл применять только после удаления бесплодных символов, потому что после этого алгоритма новые бесплодные символыпоявиться не могут, а после предыдущего новые недостижимые - легко.Алгоритм простой:Строим множества0 = {} = {; → , ∈ −1 , , ∈ * } ∪ −1То есть, мы последовательно добавляем в новое множество те нетерминалы, которыеможно с помощью правил грамматики получить из предыдущего.

Повторять до стабилизации.Рассмотрим на примере, оставшегося после работы предыдущего алгоритма: → → | → || → |0 = {}1 = {, , }, ( → )2 = 1Получили множество достижимых символов, осталось удалить все правила, связанные с недостижимыми. → → | → ||XXXX|→XX277.4Почему это работаетЕсли в предыдущем алгоритме мы шли с конца, то в этом мы идеологически делаемровно то же самое, только с начала.Потому что это логично: зачем нам нетерминалы, которые никогда не смогут раскрыться в цепочку? (незачем)7.5Алгоритм удаления -правил-правил не всегда возможноединственному -правилу → .На самом деле избавиться от всехно можно свести все к(если они уже есть),Алгоритм сложно описать без живого примера под рукой, поэтому сразу в бой: → | → | → ||, (потому что ни тот, ни другой не являютсясиомой грамматики, но имеют -правила).Начнем с .

Мы удалим из него -правило, но все другие правила, где есть ,дополним альтернативами "что было бы, если бы превратился в ": → |||||→ → |||У нас 2 "плохих"нетерминала:Теперь проделаем то же самое со вторым "плохим"нетерминалом:ак-мы. → ||||||||→ → ||||7.6Почему это работаетПотому что по сути мы просто расписываем все возможные варианты на случай еслинеприятный для нас нетерминал превратится в28. Тут алгоритм говорит сам за себя.7.7Алгоритм удаления левой рекурсии (примитивной)Этот алгоритм удаляет левую рекурсию глубины 1. Как удалять левую рекурсиюпроизвольной глубины не поняла даже сама Таня (с конспектов которой сдуваетсяэта методичка), поэтому максимум, что мы можем, это молиться, чтобы у нас такогоне было.Левая рекурсия, это когда есть правила вида → |.Удаляется она так:Правила вида → 1 |2 |...| |1 |2 |...|Переходят в наборы правил вида: → 1 * |2 * |...| ** → 1 * |2 * |...| * |!!!ВАЖНО не забыть пров конце.Рассмотрим на примере: → || → |Все это легким движением руки превращается в → * * → * | * | → ** → * |7.8Почему это работаетЧтобы лучше это понять для начала надо понять, какой язык получается из такогоправила → 1 |2 |...| |1 |2 |...|Наблюдательный читатель может заметить, что слова в этом языке по-любому будут начинаться на один из символов из{1 ...

}.При этом символ из множества{1 ... } встретится только один раз (допуская, что символы {1 ... } не пересекаются с {1 ... }). После первого символа идет произвольное число символов из {1 ... }.Переделав наше старое правило в два новых → 1 * |2 * |...| ** → 1 * |2 * |...| * |{1 ... },{1 ... }.мы первым правилом реализуем начало на любой символ изреализуем множество произвольной длины из символова вторым -А если языки совпадают, то должно ли нас волновать, что правила записаны поразному? (нет)297.9Алгоритм удаления левой факторизацииЛевая факторизация, это когда у нас есть множество "мусорных правил"у которыхсовпадают префиксы.Ошарашенный читательно может сильно нахмуриться от такой стремной фразы, поэтому куда понятнее все будет смотреться на примере: → 1 |2 |...| |...|Это левая факторизация.

Бесит она тем, что грамматику все время хочется привести к автомату, а из-за неоднозначности, это не очень хорошо получается.Поэтому эти терминалы надо просто разнести. Вот так: → * |...|* → 1 |2 |...|7.10Почему это работаетПо той же причине, по которой работало удаление левой рекурсии: языки совпадают. Здесь совпадение языков настолько очевидно, что я даже не возьмусь объяснить,почему они совпадают.Поэтому если это не очень очевидно, ну попробуйте погонять первый вариант правила, и второй: если сможете построить на их основе разные языки, напишите об этомсюда info@fskn.gov.ru30Глава 8Построение LL(1)-анализатораСразу есть смысл сказать, что этот LL(1)-анализатор полностью списан из инструкций от Тани, просто здесь, наверное, будет побольше письменных описаний, а у неебудут очень удобные схемы.

Поэтому советую эту тему рассматривать совместно спервоисточником.8.1АлгоритмLL(1)-анализатор это такая штука, которая умеет довольно быстро и эффективноработать с цепочками языка, который задается определенного вида грамматиками.Чтобы по грамматике можно было построить LL(1)-анализатор, нужно:1) Чтобы грамматика была нелеворекурсивна2) Чтобы грамматика была однозначнаВ противном случае удаляем левую рекурсию и, соответственно, факторизацию.Теперь надо ввести 2 уже немного знакомых нам понятия: () - множество терминалов с которых может начинаться цепочка . () - множество терминалов, которые могут следовать после цепочки .В обоих случаях- это цепочка из терминальных и нетерминальных символов, нопри раскрытии нетерминалов могут образовываться самые разные терминалы, поэтому тут надо быть аккуратным.Также грамматика должна удовлетворять следующему условию:Если в грамматике есть правило вида → | ,то () ∩ () = Ø2) Если ∈ (), то () ∩ () = Øвнимание, что здесь у нас не (), а ().1)31обращаю отдельноеОба эти правила нацелены на одну вещь: чтобы мы всегда могли по терминальномусимволу определить, какое правило грамматики нам надо применять сейчас.Начинаем строить и для всех нетерминалов грамматики.

Туткак и в построении ДКА по РВ довольно неплохо работает здравый смысл, но естьи строгие правила: : ∈ ⇒ () = {} → ⇒ () ∈ () → , ∈ (); ⇒ () ∈ ()этого правила не было вконспектах Тани, но мне кажется, что оно получается из здравого смысла :Для начала проинициализируем# ∈ ()(#- символ конца строки, - аксиома грамматики) → , ∈ ( ∪ )* ; ⇒ добавим () ∖ {} в () → или → , ⇒* ; ⇒ добавим () в ()Мне кажется, что все правила построения очень тяжело описать, а формальные определения тут не помогут совсем, поэтому очень-очень советую пользоваться методомпристального взгляда при построении множеств.Рассмотрим на примере: → * * → || → * | * → ** → |→Таблица для** ( )=, , () = , , (), ( * ) = , , , =, = , =32 ( )#, ( * ) = # (), () = # ( * ) = #, (* ) = () = ( * ) ∪ ( ( * ) ∖ ) = , , #Таблица для**Теперь надо построить таблицу анализатора.Но перед этим нужно взять нашуграмматику и пронумеровать все правила.

→ *1* → || 2, 3, 4 → * | *5, 6* → 7* → |8, 9→10Теперь для всех правил → (напомню, что у каждого правила есть номер ) про-делываем следующее: ∈ () ⇒ [, ] = ∈ () и ∈ () ⇒ [, ] = На основе всего этого получаем таблицу для нашего анализатора:**8.212678 #36465910Почему это работаетБлагодаря ограничениям, наложенным на грамматику, мы можем достаточно простым способом (это вам не LR-анализ) получить анализатор, который разбирает цепочку без возвратов. Все, что ему нужно знать - это какой нетерминал он сейчасразбирает и какой терминальный символ сейчас крайний в разбираемой цепочке.Благодаря однозначности (нет такой ситуации, что мы разбираем нетерминалприлетает терминал,а мы не понимаем, относится ли он к,, намили не относится)мы можем просто идти по таблице анализатора и выполнять правила, которые тамзаписаны.33Реально алгоритм сияет при разборе цепочки.

Все ограничения, введенные для LLанализатора, сразу становятся понятными (или почти понятными), когда с помощьюанализатора производится разбор. Чем мы сейчас и займемся.8.3Алгоритм разбора цепочки с помощью LL(1)анализатораНачинается все с магазина в котором аксиома грамматики и символ конца#|Пусть#.1 2 ... #- первый символ магазина,- первый символ разбираемой строки.Тогда действем по правилам: = = # ⇒ строка успешно разобрана2) = ̸= # ⇒ убираем и 3) ∈ (терминальный символ), ̸= ⇒ строка4) ∈ применяем к магазину слева правило [, ]1)Рассмотрим на живом примере:# * # *### * # * # *### *##||||||||||||############ [, ] = 1 = → [ * , ] = 3 = → [, ] = 5 [, ] = 10 = → [ * , ] = 3 = → [, #] = 6 [ * , #] = 4# = # → 34не принадлежит языку.Глава 9Построение LR(1)-анализаторапо КС-грамматикеКак в случае LL, так и в случае LR анализаторов у нас имеются непонятные цифрырядом в скобках.