Лекции (17) (Презентации лекций (PDF))

КС-грамматикиРазбор цепочки - процесс построения вывода цепочки  из цели S грамматикиG = (T, N, P, S).Вывод цепочки   T* из S  N в КС-грамматике G = (T, N, P, S), называется:- левосторонним, если в нем каждая очередная сентенциальная формаполучается из предыдущей заменой самого левого нетерминала.- правосторонним, если в нем каждая очередная сентенциальная формаполучается из предыдущей заменой самого правого нетерминала.Например, для цепочки a+b+a в грамматикеG = ( {a, b, +}, { S,T }, { S → T | T+S; T → a | b }, S)можно построить выводы:(1) S → T+S → T+T+S → T+T+T → a+T+T → a+b+T → a+b+a - произвольный(2) S → T+S → a+S → a+T+S → a+b+S → a+b+T → a+b+a - левый(3) S → T+S → T+T+S → T+T+T → T+T+a → T+b+a → a+b+a - правыйВыводы (1) – (3) являются эквивалентными в том смысле, что в них в одних итех же местах применяются одни и те же правила вывода, но в различномпорядке.Дерево выводаДерево вывода (или дерево разбора) в КС-грамматике G = (T, N, P, S) –дерево, для которого выполнены следующие условия:(1) дерево ориентировано и упорядочено;(2) каждая вершина дерева помечена символом из множества N  T  {},при этом корень дерева помечен символом S; листья - символами из T  {};(3) если вершина дерева помечена символом A  N, а ее непосредственныепотомки - символами a1, a2, ...

, an , где каждое ai  T  N, тоA → a1 a2 ... an - правило вывода в этой грамматике;(4) если вершина дерева помечена символом A  N, а ее единственныйнепосредственный потомок помечен символом , то A →  - правило вывода вэтой грамматике.Пример дерева вывода для цепочки a + b + a в грамматике G:STS+aST+TbaДерево вывода можно строить нисходящим либо восходящим способом.Неоднозначность грамматикКС-грамматика G неоднозначная, если существует хотя бы однацепочка   L(G), для которой может быть построено два или болееразличных деревьев вывода.В противном случае грамматика является однозначной.Если грамматика однозначная, то при любом способе построения,нисходящем или восходящем, будет получено одно и то же дереворазбора.Пример неоднозначной грамматики:G_if = ( { if, then, else, a, b }, { S }, P, S),где P = {S → if b then S else S | if b then S | aВ этой грамматике для цепочкиif b then if b then a else aможно построить два различных дерева вывода.}.Неоднозначность грамматикНеоднозначность - это свойство грамматики, а неязыка.Если грамматика используется для определения языкапрограммирования, то она должна быть однозначной.Можно преобразовать грамматику G_if, устранивнеоднозначность:S → if b then S | TT → if b then T else S | aПроблема определения, является ли заданная КСграмматика однозначной, является алгоритмическинеразрешимой.Деревья вывода для цепочкиif b then if b then a else aв грамматике G_ifSSSifbthenifbSthenaelseaSSSifbthenifbthenSaelseaГрамматика G_if неоднозначна, однако, это не означает,что язык L(G_if) неоднозначный.Преобразование неоднозначных грамматикНекоторые виды правил вывода, которые приводят к неоднозначности инекоторые способы эквивалентных преобразований неоднозначныхграмматик к однозначным:1.

A → AA | A → A | (док-во для ) – порождаются подцепочки n (n >= 1);2. A → AA | A → A | (док-во для ) – порождаются подцепочки  ( )n (n >= 0);3. A → A | A | A → A | B;B → B |  ,BN(док-во для ) – порождаются подцепочки n  m (n, m >= 0);4. A → A | AA | A → A | В;В → ВA |  , B  N(док-во для ) – порождаются подцепочки δ = nm (δ)m (n,m >=0)Таким приемом преобразована грамматика G_if :( ≡ if_b_then,  ≡ else, a ≡ , A ≡ S, B ≡ T).Неоднозначные языкиЯзык, порождаемый грамматикой неоднозначный, если он не можетбыть порожден никакой однозначной грамматикой.Проблема определения, порождает ли данная КС-грамматикаоднозначный язык (т.е.

существует ли эквивалентная ей однозначнаяграмматика), является алгоритмически неразрешимой.Пример неоднозначного КС-языка:L = {ai bj ck | i = j или j = k} .Одна из грамматик, порождающих L, такова:S→A→B→C→D→AB | DCaA | bBc | cC | aDb | ( док-во для цепочки abc )Бесплодные символы грамматики.Символ A  N является бесплодным в грамматике G = (T, N, P, S),если множество {   T* | A   } пусто.Алгоритм удаления бесплодных символов:Вход:КС-грамматика G  (T, N, P, S ),Выход:КС-грамматика G'  (T, N', P', S ), не содержащаябесплодных символов, для которой L(G) = L(G').Метод:Строим множества N0, N1, ...1.

N0 : ; i : 1.2. Ni : Ni − 1  { A | A →   P и   (T  Ni − 1 )} .Если Ni  Ni − 1, то i : i + 1 и переходим к шагу 2,иначе N' : Ni ; P' состоит из правил множества P,содержащих только символы из Ni  T ; G' : (T, N', P', S).Удаление бесплодных символов грамматики.Пример.S → AC | Bb | A → aCbB → bBC → cCc | cD → Aa | Bb | dШаг 0:N0 : ; i : 1.Шаг 1:N1 : {S, C, D}; i : 2.Шаг 2:N2 : {S, C, D, A}; i : 3.Шаг 3:N3 : {S, C, D, A} = N2, т.е. искомое множество построено.Удаляем все правила, содержащие нетерминал B, не вошедший впостроенное множество:S → AC | A → aCbC → cCc | cD → Aa | dНедостижимые символы грамматикиСимвол x  (T  N) является недостижимым в грамматикеG = (T, N, P, S), если он не появляется ни в одной сентенциальнойформе этой грамматики.Алгоритм удаления недостижимых символов:Вход:КС-грамматика G  (T, N, P, S ),Выход:КС-грамматика G'  (T', N', P', S ), не содержащаянедостижимых символов, для которой L(G) = L(G').Метод:Строим множества V0, V1, ...1.

V0 : {S }; i : 1.2. Vi : Vi − 1  { x | x  T  N,A → x  P, A  Vi − 1, ,   (T  N )} .Если Vi  Vi − 1, то i : i + 1 и переходим к шагу 2,иначе N' : Vi  N ; T' : Vi  T ; P' состоит из правил множества P,содержащих только символы из Vi ; G' : (T', N', P', S).Удаление недостижимых символов грамматики.Пример.S → AC | A → aCbC → cCc | cD → Aa | dШаг 0:Шаг 1:Шаг 2:Шаг 3:V0 : {S}; i : 1.V1 : {S, A, C, }; i : 2.V2 : {S, A, C, , a, b, c}; i : 3.V3 : {S, A, C, , a, b, c} = V2, т.е.

искомое множествопостроеноУдаляем все правила, содержащие символы D и d, не вошедшие впостроенное множество:S → AC | A → aCbC → cCc | cПриведенные грамматикиНедостижимые и бесплодные символы в грамматике G = (T, N, P, S)называются бесполезными символами в этой грамматике.КС-грамматика G называется приведенной, если в ней нетбесполезных символов.Алгоритм приведения грамматики:1)2)обнаруживаются и удаляются все бесплодные нетерминалы.обнаруживаются и удаляются все недостижимые символы.Удаление символов сопровождается удалением правил вывода,содержащих эти символы.Если в алгоритме переставить шаги 1) и 2), то не всегда результатомбудет приведенная грамматика.

Например, при такой перестановке шаговграмматикаS → AB | аA→ bB → BAостанется неприведенной.Алгоритм устранения правил с пустой правой частьюВход: КС-грамматика G  (T, N, P, S ).Выход: КС-грамматика G'  (T, N', P', S' ) - неукорачивающая, L(G')  L(G).Метод:1. Построить множество Х  {A  N | A  } ; N′:N .2.

Построить P′, удалив из множества правил P все правилас пустой правой частью.3. Если S  X, то ввести новый начальный символ S′, добавив его в N′,и в множество правил P′ добавить правило S′ S | .Иначе просто переименовать S в S′.4. Изменить P′ следующим образом. Каждое правило видаB → 1A12A2...n Ann +1, где Ai  X для i  1,..., n, i  ( (N′ − X)  T )*для i  1,..., n + 1 (т. е. i — цепочка, не содержащая символов из X ),заменить 2n правилами, соответствующими всем возможнымкомбинациям вхождений Аi между i:B → 12...nn + 1B→ 12...nAnn + 1...B → 12A2...nAnn + 1B → 1A12A2...nAnn + 1Если i   для всех i  1, ..., n + 1, то получившееся на данном шаге правилоB →  не включать в множество P′.5.

Удалить бесполезные символы и правила, их содержащие.Устранение правил с пустой правой частью.Пример.S → BC | Ab | ABA → Aa | B→C→cШаг 1:N1 : { A, B };Шаг 2:N2 : { A, B, S };.S1 → S | S → BC | C | Ab | b | AB | A | BA → Aa | aC→cПриводим грамматику:S1 → S | S → C | Ab | b | AA → Aa | aC→c.