Информационные технологии

Определение. Алфавитом V называется конечное множество символов. Примеры алфавитов – алфавит русского языка, алфавит английского языка. Определение. Цепочкой над алфавитом или в алфавите V называется строка конечной длины, составленная из символов алфавита. Определение. Длиной цепочки Х называется количество символов в этой цепочке. Обозначается |X|. Определение. Пустая цепочка  – цепочка нулевой длины, не содержащая символов. Определение. Конкатенацией цепочек X и Y называется цепочка Z, полученная приписыванием цепочки Y к цепочке X справа. Это соответствует записи Z=XY. Для любой цепочки X=X=X. Обозначим через V* множество всевозможных цепочек над алфавитом V, включая пустую цепочку. Например, пусть V={a,b}. тогда V*={e,a,b,aa,ab,bb,aaa,aab,aba,abb,baa,bab,bba,bbb,….}. Множество, полученное из V* исключением пустой цепочки, обозначается V+. Определение. Языком L над алфавитом или в алфавите называется некоторое подмножество V*. Введем операции над языками. Пусть L1 и L2 – языки в алфавите V. Определение. Конкатенацией или произведением языков L1 и L2 называется язык L= L1L2={xy| xL1,yL2}. Пусть L- язык над алфавитом V. Определение. Итерацией языка L называется язык L*, определяемый следующим образом: 1. L0={e} 2. Ln=LLn-1, n1 3. L*=. Например, если язык L состоит из единственного слова L={a}, то L*={e,a,aa,aaa,….}. Определение. Усеченной итерацией языка L называется язык L+, определяемый следующим образом: 1. Ln=LLn-1, n2 2. L+=. То есть если язык L состоит из единственного слова L={a}, то L+={a, aa, aaa,….}. Определение. Объединением языков L1 и L2 называется язык L= L1L2={x| xL1 или хL2}. Однако теоретико-множественное описание языка непригодно для определения факта принадлежности некоторой цепочки языку, так как не все цепочки из символов алфавита принадлежат языку, а перебор множества всевозможных цепочек нерационален, так как большинство языков содержат бесконечное количество цепочек. В связи с этим целесообразно рассмотреть другое определение языка, связанное с их формированием. Можно генерировать цепочки из V* и проверять их принадлежность языку L. Определение. Формальной грамматикой G называется совокупность четырех объектов: G = { VТ, VN, S, R }, где: - VT - терминальный алфавит, буквы этого алфавита называются терминальными символами; из них строятся цепочки языка, для обозначения терминальных символов будем использовать строчные буквы латинского алфавита; - VN - нетерминальный алфавит; буквы этого алфавита используются при построении цепочек; для обозначения нетерминальных символов будем использовать прописные буквы латинского алфавита и идентификаторы, заключенные в угловые скобки; - S - начальный символ или аксиома грамматики SVN. С аксиомы начинается формирование любой цепочки языка. - R - множество правил вывода или порождающих правил вида , где  и  - цепочки, построенные из букв алфавита VТ È VN. Определение. Если цепочка  может быть получена из цепочки  путем однократного применения правила r, то говорят, что цепочка  непосредственно выведена из цепочки  и обозначают . Определение. Если цепочка  может быть получена из цепочки  с помощью многократного применения правил грамматики (путем последовательности непосредственных выводов), то говорят, что цепочка  выведена из цепочки  и обозначают *. : Определение. Множество конечных цепочек терминального алфавита Vт грамматики G, выводимых из начального символа S, называется языком, порождаемым грамматикой G и обозначается L(G). L(G) = {wVТ* | S *w }. Пример 1 Задана грамматика G: VN = {S, A}, VТ= {a, b, c}, R = {S aA, A  bccc}. Рассмотрим, какой язык она порождает. Из аксиомы S можно получить сначала цепочку aA, но она итоговой цепочкой языка быть не может, так как содержит нетерминальный вспомогательный символ A. Этот символ порождает цепочку bccc. Тогда в итоге аксиома порождает цепочку abccc. Пример 2 Задана грамматика и требуется определить язык, порождаемый этой грамматикой: G: VN = {S, A}, VТ= {a, b}, R = {S  aA, A Ab, A  }. Для удобства будем записывать последовательность правил, первое правило соответствует аксиоме. Если для одного нетерминала имеются несколько правил, то они разделяются вертикальной чертой. G: S  aA A Ab |  Грамматика содержит три правила. Второе правило содержит нетерминальный символ А как в левой, так и в правой части правила. Такие правила называют рекурсивными. Применение такого правила к цепочке, содержащей нетерминал А, приводит к получению новой цепочки, в которую снова входит А. Таким образом, замену нетерминала А правой частью правила можно выполнять многократно, что позволяет строить сколь угодно длинные цепочки. Чтобы вывод с применением рекурсивного правила не был бесконечным, в грамматике должно быть хотя бы одно правило с символом А в левой части и с отсутствием его в правой. Такое правило завершает рекурсию. В рассматриваемой грамматике для завершения вывода используется правило А®. Рассмотрим построение выводов с помощью правил грамматики. Применив первое и второе правило, получим цепочку aAb. Применив второе правило многократно и третье правило, чтобы избавиться от нетерминала А, получим цепочки, которые начинаются с символа a, за которым следуют буквы b. Однако букв b в цепочке может и не быть, если не пользоваться рекурсивным правилом. Тогда из аксиомы выведется цепочка a. В целом из аксиомы S порождается язык ab*. Пример 3. G: S  aSb |  Применяя рекурсивное правило, получим в результате цепочку, содержащую слева буквы а, а справа буквы b. Отметим, что количество этих букв ВСЕГДА совпадает! Если рекурсивное правило применить n раз, то можно записать, что грамматика порождает язык L=0n1n, n0. n=0 соответствует неприменению рекурсивного правила, когда сразу порождается пустая цепочка. В зависимости от вида правил грамматики выделяют 4 типа грамматик, которым соответствуют 4 типа языков (классификация Хомского). Грамматики типа 0 (грамматики общего вида) не имеют никаких ограничений на правила порождения, в левой и правой частях правил стоят цепочки из терминалов и нетерминалов. Грамматики типа 1 требуют, чтобы в левой и правой части правил оставалась неизменной некоторая часть правила (контекст), поэтому эти грамматики называют контекстно-зависимыми. Грамматики типа 2 называют контектно-свободными грамматиками (КС-грамматики). Правила вывода таких грамматик имеют вид: A, где AVN и (VТ VN)*. Грамматики типа 3 называют автоматными грамматиками. Правила вывода в таких грамматиках имеют вид: Aa или Aa B или AB a, где a VТ, и A, BVN, причем грамматика может иметь только правила, где нетерминал стоит либо только справа, либо только слева. Наибольшее практическое применение находят грамматики типов 2 и 3, поэтому рассмотрим синтез таких грамматик. Пусть языки L1 и L2 порождаются грамматиками G1={ VТ1, VN1, S1, R1}, G2={ VТ2, VN2, S2, R2}. Тогда произведение языков L1 и L2 порождается грамматикой G={ VТ1 VТ2, VN1 VN2S, S, R1R2SS1S2}, причем множества нетерминальных символов не должны пересекаться. Объединение языков L1 и L2 порождается грамматикой G={VТ1VТ2,VN1VN2S,S,R1R2SS1S2} Усеченная итерация языка L1 порождается грамматикой G={VТ1, VN1 S, S, R1 SSS1S1}. Итерация языка L1 порождается грамматикой G={VТ1,VN1S, S, R1 SSS1}. Основой создания правил грамматики по формальному языку является способ выделения структуры заданного множества цепочек. Этот способ предусматривает расчленение цепочек на части таким образом, чтобы выявить повторяющиеся части цепочек и части, входящие во все цепочки в неизменном виде. Для каждого выявленного элемента структуры вводятся обозначения. Множество таких обозначений составляет основу словаря нетерминальных символов синтезируемой грамматики. Процесс выделения нетерминалов является итерационным, на каждом шаге анализируется, какая операция над более простыми языками выполнялась последней, и используются правила для аксиомы этой операции. Пример 4. Построить КС-грамматику, порождающую формальный язык L=b*c+ Пусть язык L порождается из аксиомы S. Последней операцией при синтезе языка L была операция объединения более простых языков b* и с+. Будем считать, что язык b* был порожден из нетерминала А, который для него являлся аксиомой, а язык с+ порожден из нетерминала В. Тогда в грамматике должны быть правила для объединения языков: SA | B Рассмотрим теперь правила для нетерминалов А и В. Нетерминал A порождает итерацию простейшего языка, состоящего из единственного символа b, значит, правила для нетерминала A имеют вид: AAb |  Нетерминал В порождает усеченную итерацию языка {c}, значит правила будут иметь вид: BBc | c Для всех нетерминалов правила расписаны вплоть до порождения терминальных цепочек, значит, процесс построения грамматики завершен. Она имеет вид: SA | B AAb |  BBc | c Пример 5. Построить КС-грамматику, порождающую формальный язык L=anbncd*, n0. Последней операцией для синтеза L было произведение, поэтому правило для аксиомы имеет вид: SAcB Нетерминал A будет порождать язык anbn, нетерминал B – язык d*. ВАЖНО! Нельзя разрывать цепочки языка, связанные друг с другом одинаковым количеством повторений (n)! Такие конструкции ВСЕГДА должны порождаться одним и тем же нетерминалом. Распишем правила для новых нетерминалов А и В. AaAb |  Если n=0, то применяется второе правило, и в цепочке не будет букв a и b. Если бы в языке было бы условие n1, то для нетерминала A правила будут иметь вид: AaAb | ab, то есть буквы ab хотя бы один раз будут порождаться. Нетерминал B порождает итерацию: BBd |  Итоговая грамматика: SAcB AaAb |  BBd |  Порождению цепочек в КС-грамматике соответствуют деревья разбора. Определение. Деревом разбора для КС-грамматики называется дерево, удовлетворяющее следующим условиям: 1. Корень дерева соответствует аксиоме. 2. Листья дерева (или крона дерева) соответствуют терминальным символам. 3. Вершины, имеющие потомков, соответствуют нетерминальным символам. 4. Если в дереве вершина A имеет потомков α1,α2,…,αn, то в грамматике есть правило A  α1α2…αn. Например, рассмотрим дерево разбора цепочки =aabbcdd для примера 5, представленное на рисунке 1. Рисунок 1 Различают 2 способа построения дерева разбора – нисходящий и восходящий. При нисходящем разбор начинается от корня, и на каждом шаге строятся дуги от некоторой вершины к ее потомкам (рисунок 2). В итоге все терминальные символы цепочки должны стать листьями дерева. Рисунок 2. При восходящем разборе на каждом шаге осуществляется замена правой части некоторого правила на терминал – левую часть правила (рисунок 3). Это называется редукцией. Редукция обратна порождению. Рисунок 3. Введем несколько понятий, связанных с восходящим разбором. Определение. Цепочка α называется фразой сентенциальной формы  для нетерминала А, если =1α2 , A*α. Определение. Цепочка α называется простой фразой сентенциальной формы  для нетерминала А, если =1α2, AαR. Определение. Основой называется самая левая простая фраза. При восходящем разборе на каждом шаге анализируется сентенциальная форма (на первом шаге форма является терминальной), выделяется основа, которая редуцируется. В результате восходящего разбора должна получиться аксиома. Если дерево разбора построено успешно, то это означает, что цепочка принадлежит языку. Для удобства и ускорения грамматического разбора КС-грамматики анализируют и преобразуют. Эквивалентные преобразования КС-грамматик. При синтезе грамматик и их преобразовании в грамматике могут появиться бесполезные нетерминалы. Различают непродуктивные нетерминалы и нетерминалы, от которых не зависит аксиома. Определение. Нетерминал называется непродуктивным, если он не порождает ни одной терминальной цепочки. При нисходящем разборе появление непродуктивного нетерминала в дереве не позволит завершить грамматический разбор. Рассмотрим алгоритм удаления из грамматики непродуктивных нетерминалов: 1. Создать множество нетерминалов W0, куда включить нетерминалы, из которых выводится терминальная цепочка (в том числе пустая) за один шаг. 2. На последующих шагах включать во множество Wn+1 нетерминалы предыдущего множества Wn и нетерминалы, правые части правил которых включают терминалы и нетерминалы из Wn. 3. Когда Wn+1=Wn, в грамматике удалим все правила с нетерминалами, не вошедшими в последнее множество Wn+1. Алгоритм остановится не более, чем через количество шагов, равному числу нетерминалов грамматики. Пример 6. Удалить непродуктивные нетерминалы из грамматики. S  aB | rA A  FA | T B  aB | c F  Tc T  aT | Fw W0={B}, так как только из В в исходной грамматике выводится терминальный символ. W1={B,S}, так как есть правило SaB, а – терминал, В включен в предыдущее множество продуктивных нетерминалов. W2={В,S}=W1. Грамматика после преобразования: S  aB B  aB | c Определение. Аксиома зависит от нетерминала А, если существует сентенциальная форма, в которой он содержится. Определение. Если аксиома не зависит от нетерминала, то он называется недостижимым. При восходящем грамматическом разборе появление в основе недостижимых нетерминалов приведет к тому, что аксиома не будет редуцирована, а значит, дерево не сможет быть построено. Рассмотрим алгоритм удаления недостижимых нетерминалов. 1. Создать множество нетерминалов W0, куда включить только аксиому S; 2. На последующих шагах включать во множество Wn+1 нетерминалы предыдущего множества Wn и нетерминалы, из правых частей правил для нетерминалов из Wn. 3. Когда Wn+1=Wn, в грамматике удалим все нетерминалы, не вошедшие в последнее множество. Пример 7. S  A k | Rt R  R a | c L  a L b | A A  cA |c W0={S}. W1={S, A, R}, так как из S выводятся нетерминалы A и R, W2={S, A, R}, так как из A и R новых нетерминалов не выводится. Грамматика после преобразования: S  A k | Rt R  R a | c A  cA |c Определение. Грамматика называется неукорачивающей, если она не содержит правил с пустой правой частью (цепочкой ).. Определение. Грамматики называются эквивалентными с точностью до пустой цепочки, если языки, порождаемые ими, отличаются пустой цепочкой. Термин «укорачиваемость» связан с количеством символов в порождаемой цепочке, когда имеется правило А  , то длина выводимой цепочки уменьшается. Недостатком укорачивающей грамматики является сложность выбора основы при восходящем разборе, так как  есть в любом месте цепочки в любых количествах. Рассмотрим алгоритм преобразования грамматики к эквивалентной неукорачивающей грамматике: 1. Создать множество нетерминалов W0, куда включить нетерминалы, из которых выводится  за один шаг. 2. На последующих шагах включать во множество Wn+1 нетерминалы предыдущего множества Wn и нетерминалы, в правых частях правил которых есть только нетерминалы из Wn. 3. Когда Wn+1=Wn, в грамматике вместо всех нетерминалов, вошедших в последнее множество W, подставить  всеми возможными способами. Пример 8. Исходная грамматика S  SA | B| Ac A  BDc | bD B  aB |  D  aDb |  В качестве упражнения попробуйте построить дерево разбора цепочки =aabcc в исходной грамматике по восходящей стратегии. Так как в грамматике нет правил с терминальными правыми частями, то очень трудно понять, откуда начинать строить дерево, так как пустая цепочка есть везде. Преобразуем грамматику. W0={B, D} W1={B, D, S} W2={B, D, S} Вместо нетерминалов В, D и S подставим пустые цепочки всеми возможными способами, сохранив исходные правила с непустыми правыми частями в неизменном виде. Преобразованная грамматика: S  SA | B| Ac | A A  BDc | bD | Bc | Dc | c | b B  aB | a D  aDb | ab Задание: постройте дерево разбора той же цепочки  для преобразованной грамматики. При выполнении нисходящего разбора леворекурсивные правила не позволяют при построении дерева определить, сколько раз их применять, так как цепочка начинается с терминала, а порождается слева нетерминал (например, AAa). Так как совсем избавиться от рекурсии невозможно, то требуется заменить левую рекурсию на правую. Алгоритм устранения левой рекурсии. Пусть есть леворекурсивное правило A  A |  Рассмотрим вывод из А с применением рекурсивного правила: A  AA…An n Обозначим n как вывод из некоторого нетерминала Т. Тогда рекурсивное правило можно заменить на нерекурсивное, а последовательность  можно получить с помощью правой рекурсии: A  T T  T |  Правая рекурсия устраняется аналогично. Пример 9. Устранить левую рекурсию. S  Sb | R | M R  Ra | a M  Mt |  Преобразованная грамматика: S  RT | MT TbT |  R  aR | a M  tM | 