А.А. Вылиток - Алгоритмы преобразования контекстно-свободных грамматик с помощью графов (1115011)
Текст из файла
А. А. ВылитокАлгоритмы преобразования контекстно-свободных грамматик спомощью графов1. Устранение бесполезных символовРассмотрим пример контекстно-свободной грамматики c алфавитом терминальныхсимволов {a, b} и начальным символом S:S → aS | A | aB→bНетрудно заметить, что для данной грамматики вспомогательные (нетерминальные) символы Aи B не могут встречаться в сентенциальных формах выводов терминальных цепочек изначального символа S. Другими словами, они не принимают участия в порождении цепочекязыка, то есть являются в этом смысле бесполезными.Любую контекстно-свободную грамматику можно привести к форме, не содержащейбесполезных символов.Пусть G = (VT, VN, P, S) — контекстно-свободная грамматика (КС-грамматика).Символ x ∈ (VT ∪ VN) называется недостижимым в грамматике G, если он не появляетсяни в одной сентенциальной форме этой грамматики.Символ А ∈ VN называется бесплодным в грамматике G, если множество выводимых изэтого символа терминальных цепочек пусто.КС-грамматика называется приведенной, если в ней нет недостижимых и бесплодныхсимволов.1.1.
Алгоритм приведения контекстно-свободной грамматики к форме, несодержащей бесполезных символовАлгоритм приведения состоит из двух шагов. Каждый шаг в свою очередь реализуетсяотдельным алгоритмом. Эти алгоритмы используют граф грамматики и будут рассмотреныниже.Алгоритм приведения КС-грамматики1. Найти и удалить все бесплодные символы и правила, их содержащие.2. Найти и удалить все недостижимые символы и правила, их содержащие.После первого шага данного алгоритма для грамматики G = (VT, VN, P, S) получаемэквивалентную грамматику G1 = (VT, VN1, P1, S), такую, что для любого А ∈ VN1 справедливонеравенство1): {A ⇒* ω | ω ∈ VT*} ≠ ∅.1)Исключение может быть сделано для начального символа S грамматики G, если он окажется бесплодным(т.е.
грамматика G порождает пустой язык). Тогда на первом шаге следует включить S в алфавит VN1, так каксогласно определению грамматики, начальный символ является ее обязательной частью и принадлежиталфавиту нетерминальных символов. Однако правила, содержащие бесплодный символ S, в множество P1 невключаются.На втором шаге из G1 получим эквивалентную грамматику G2 = (VT2, VN2, P2, S), обладающуюсвойствами приведенной грамматики2:(1) для любого символа x ∈ (VT2 ∪ VN2) существуют α1, α2 ∈ (VT2 ∪ VN2)* такие, чтоS ⇒* α1xα2;(2) либо для любого А ∈ VN2 справедливо неравенство {A ⇒* ω | ω ∈ VT2*} ≠ ∅ либо VN2 = {S}и {S ⇒* ω | ω ∈ VT2*} = ∅.1.2.
Граф контекстно-свободной грамматикиДля нахождения бесплодных и недостижимых символов полезен граф КС-грамматики: каждому символу из VT ∪ VN соответствует единственная вершина, помеченная этимсимволом; если в P есть правило с пустой правой частью ε, то граф имеет вершину,помеченную ε; вершина, помеченная символом X, соединяется с вершиной Y дугой (стрелкой), если вграмматике есть правило X → αY β, где α, β ∈ (VT ∪ VN)*; X соединяется с вершиной ε, если в грамматике есть правило X → ε.Пример. Грамматика G0:G0 = ({a, b, c, d, e}, {S, A, B, C, D}, P0, S)P0:Граф грамматики G0:S → aAB | CD → cDc | dC → aCDA → aA | a | εB→bSBaACcDbεde1.3. Алгоритм удаления бесплодных символовДля заданной грамматики G построить граф и выполнить следующие шаги:1. Отметить (выделить) вершины графа, помеченные терминальными символами, а такжевершину ε, если такая имеется.2.
Если в Р есть правило А → α, где α состоит из символов уже отмеченных вершин, авершина А еще не отмечена, то отметить эту вершину. Повторять шаг 2 пока возможно.3. Из грамматики удалить символы неотмеченных вершин, а также правила, содержащиехотя бы один символ неотмеченной вершины.Пример. Рассмотрим грамматику G0 из п. 1.2.G0 = ({a, b, c, d, e}, {S, A, B, C, D}, P0, S)P0:2)S → aAB | CD → cDc | dC → aCDA → aA | a | εB→bГраф G0 после шагов 1, 2 алгоритма:(отмеченные вершины выделены двойнымкружком)Может оказаться, что все терминальные символы недостижимы.
Тогда хотя бы один терминальный символдолжен быть оставлен в алфавите терминалов, так как алфавит не может быть пустым.SBaAbCDcdεeНеотмеченной на графе оказалась вершина C. Вычеркиваем в грамматике G0 символ C иправила, его содержащие: ({a, b, c, d, e}, {S, A, B, C , D}, P0, S)P0:S → aAB | CD → cDc | dC → aCDA → aA | a | εB→bПолучаем эквивалентную грамматику G1, не содержащую бесплодных символов:G1 = ({a, b, c, d}, {S, A, B, D}, P1, S)P1:S → aABD → cDc | dA → aA | a | εB→b1.4. Алгоритм удаления недостижимых символовПостроить граф грамматики.
Используя граф, выполнить следующие шаги:1. Отметить вершины графа, в которые есть путь из вершины S.2. Удалить из грамматики символы неотмеченных вершин и правила, содержащие хотя быодин такой символ.Пример. Рассмотрим грамматику G1, полученную в п. 1.3.G1 = ({a, b, c, d, e}, {S, A, B, D}, P1, S)P1:S → aABD → cDc | dA → aA | a | εB→bГраф грамматики G1:SBaAcDbεdeНаходим недостижимые символы и вычеркиваем их из алфавита нетерминалов и правилграмматики G1.G1 = ({a, b , c, d, e }, {S, A, B , D }, P1, S)P1:S → aABD → cDc | dA → aA | a | εГраф грамматики G1:(отмеченные на шаге 1 вершины выделеныдвойным кружком)B→bSBaAcDbεdeНеотмеченные в графе символы являются недостижимыми и подлежат удалению.После удаления недостижимых символов из G1, получим эквивалентную грамматикуG2 = ({a, b}, {S, A, B}, P2, S)P2:S → aABA → aA | a | εB→bГрамматика G2 — приведенная, она получена из G0 последовательным применениемшагов 1 и 2 алгоритма приведения грамматики (п.
1.1)nL(G0) = L(G1) = L(G2) = {a b | n ≥ 1}.1.5. О последовательности шагов в алгоритме приведенияПорядок шагов 1 и 2 в алгоритме приведения КС-грамматики важен. Их нельзя поменятьместами.Задача. Показать, что если к грамматике G0 из п. 1.2 сначала применить алгоритмудаления недостижимых символов, а затем к результату применить алгоритм удалениябесплодных символов, то полученная таким способом грамматика не будет приведенной.2.
Устранение правил с пустой правой частьюНекоторые применяемые на практике алгоритмы разбора по КС-грамматикам требуют,чтобы в грамматиках не было правил с пустой правой частью.Любую КС-грамматику, не порождающую пустую цепочку, можно преобразовать вэквивалентную, не имеющую правил с пустыми правыми частями.
Если исходная грамматикапорождает пустую цепочку, то по ней можно построить эквивалентную грамматику,содержащую единственное правило с пустой правой частью: S → ε, где S — начальный символ;правые части остальных правил непустые и не содержат S.Ниже приводится алгоритм, позволяющий преобразовать грамматику в описаннуюформу. На первом шаге алгоритма строится множество нетерминалов грамматики, из которыхвыводима пустая цепочка. Построение этого множества можно провести с помощью графаграмматики аналогично построению множества бесплодных символов (п. 1.3), отметив вначалелишь вершину, помеченную символом ε.Пусть G = (VT, VN, P, S) — КС-грамматика.Алгоритм устранения правил с пустой правой частью1.
Построить множество Х = {A ∈ VN | A ⇒* ε}.2. Удалить из множества правил P все правила с пустой правой частью.3. Если S ∈ X, то ввести новый начальный символ S′, в множество правил P добавитьправило S′ → S | ε.4. Для любого A ∈ X правило вида B → α1Aα2A...αnAαn + 1, где αi ∈ ((VN − {A}) ∪ VT)*,заменить 2n правилами, соответствующими всем возможным комбинациям вхождений Амежду αi:B → α1α2...αnαn + 1B → α1α2...αnAαn + 1…B → α1α2A...αnAαn + 1B → α1Aα2A...αnAαn + 1Замечание: если αi = ε для всех i = 1, …, n + 1, то получившееся на данном шаге правилоB → ε не включать в множество P.5. Удалить бесполезные символы и правила, их содержащие.Пример.
Исходная грамматика:G = ({a, b, c}, {S, A, B, C}, P, S)P:S → BC | AbB→εC→cA → Aa | εЭквивалентная грамматика, не содержащая правил с пустой правой частью:G′ = ({a, b, c}, {S, A, C}, P′, S)P′:S → C | b | AbC→cA → Aa | a.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
