Формальные грамматики и языки (1119467), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

N0 = ∅, i = 12. Ni = Ni-1 ∪ { A | (A → α) ∈ P, A ∈ N и α ∈ (Ni-1 ∪ T)* }3. Если Ni ≠ Ni-1, то i = i + 1 и переход к шагу 24. Иначе N’ = NiT’ = TS’ = S• P’ состоит из правил множества P, содержащих только символыиз N’ ∪ T’• В грамматике G’ нет бесплодных символов, L (G) = L (G’)50Недостижимые символы• Символ x ∈ (T ∪ N) называется недостижимым вграмматике G = (T, N, P, S), если он не появляется ни водной сентенциальной форме этой грамматики• Алгоритм удаления недостижимых символовВход:Грамматика G = (T, N, P, S)Выход:Грамматика G’ = (T’, N’, P’, S’)Метод:Рекурсивно строятся множества символов V0, V1, ...1. V0 = {S}, i = 12.

Vi = Vi-1 ∪ {x | x ∈ (T∪N), (A → αxβ) ∈ P, A ∈ Vi-1, α,β ∈ (T∪N)∗}3. Если Vi ≠ Vi-1, то i = i + 1 и переход к шагу 24. Иначе N’ = Vi ∩ NT’ = Vi ∩ TS’ = S• P’ состоит из правил множества P, содержащих только символыиз Vi• В грамматике G’ нет недостижимых символов, L (G) = L (G’) 51Правила с пустой правой частью• ε-правилами называются все правила вида А→ε, А∈N• Контекстно-свободная грамматика называетсяграмматикой без ε-правил, если в ней не существуетправил (А → ε) ∈ P, A ≠ S и существует только одноправило (S → ε) ∈ P в том случае, когда ε ∈ L (G), и приэтом S не встречается в правой части ни одногоправила• Существует алгоритм преобразования произвольнойконтекстно-свободной грамматики к виду безε-правил, то есть её преобразования кнеукорачивающей контекстно-свободной52грамматикеУдаление ε-правил• Алгоритм удаления ε-правилВход:Выход:Грамматика G = (T, N, P, S)Грамматика G’ = (T’, N’, P’, S’)1.

X0 = {A: (А → ε) ∈ P}; i = 12. Xi = Xi-1 ∪ {A: А ∈ N, (А → α) ∈ P, α ∈ Xi-1*}3. Если Xi ≠ Xi-1, то i = i + 1 и переход к шагу 2, иначе к шагу 4В Xi входят символы из N, из которых выводится ε4. N’ = NT’ = Tв P’ входят все правила из P,кроме правил вида А → ε5. Если (А → α) ∈ P и в цепочку α входят символы измножества Xi, на основе этой цепочки α строится новоемножество цепочек {α’} путём поочерёдного исключения изα всех возможных комбинаций вхождений символов Xi,53все правила вида А → α’ добавляются в P’Удаление ε-правил• Изменять P’ нужно следующим образом: для любого А ∈ Xiправило вида B →α1Аα2А…αnАαn+1, где αi∈((N – {А}) ∪ T),заменить 2n правилами, соответствующими всем возможнымкомбинациям вхождений А между αi:B →α1α2…αnαn+1B →α1α2…αnAαn+1…B →α1α2А…αnАαn+1B →α1Аα2А…αnАαn+1• Правила вида B → ε в множество P’ не включаются6.

Если S ∈ Xi, значит ε ∈ L (G), в N’ добавляется новый символS’, который становится начальным символом грамматики G’,в P’ добавляются два новых правила: S’ → ε | S; иначе S’ = S7. G’ = (T’, N’, P’, S’)54Циклические правила• Циклом (циклическим выводом) в грамматикеG (T, N, P, S) называется вывод вида А ⇒ A• Циклы возможны только в том случае, если вграмматиках языков присутствуют цепныеправила вида А → В, где А, В ∈ N• В процессе работы алгоритма цепных правилмогут вновь возникать бесплодные инедостижимые символы и правила, ихсодержащие55Циклические правила• Алгоритм удаления цепных правилВход:Грамматика G = (T, N, P, S)Выход:Грамматика G’ = (T’, N’, P’, S’)1. Для всех символов Х из N повторять шаги 2-4, затем переходк шагу 52.

Nx 0 = {Х}; i = 13. Nx i = Nx i-1 ∪ {В: (А → В) ∈ P, В ∈ Nx i-1*}4. Если Nx i ≠ Nx i-1, то i = i + 1 и переход к шагу 3, иначеустановить Nx i = Nx i-1 – {X} и продолжить цикл по шагу 15. N’ = N; T’ = T; S’ = Sв P’ входят все правила из P, кроме правил вида А → В6. Для всех правил (А → α) ∈ P’, если В ∈ NA, В ≠ Ав P’ добавляются правила вида В → α7. G’ = (T’, N’, P’, S’)56Приведение грамматик• В процессе работы алгоритма удаления ε-правил могут вновьвозникать бесплодные и недостижимые символы и правила, ихсодержащие• Если применить алгоритм удаления ε-правил к регулярной(автоматной) грамматике, результатом будет неукорачивающаярегулярная (автоматная) грамматика• Контекстно-свободная грамматика называетсяприведённой, если в ней нет бесполезных (бесплодных инедостижимых) символов• Алгоритм приведения контекстно-свободной грамматики1.

Обнаруживаются и удаляются все бесплодные символы2. Обнаруживаются и удаляются все недостижимые символы• Удаление символов сопровождается удалением правил57вывода, содержащих эти символыСоглашения о грамматиках• Под регулярной грамматикой будем пониматьнеукорачивающую леволинейнуюавтоматную грамматику (в их правилах нетпустых правых частей): А → Вt или А → tгде А, В ∈ N, t ∈ T• Аналогичные праволинейные грамматикиимеют правила видов: А → tВ или А → tгде А, В ∈ N, t ∈ T• Все анализируемые цепочки заканчиваютсяспециальным терминальным символом ⊥– признаком конца цепочки58Алгоритм определенияпринадлежности цепочки языку• Алгоритм определения принадлежности цепочкиязыку, порождаемому регулярной грамматикой:1.

Первый символ исходной цепочки a1a2...an⊥заменить нетерминалом A1, для которого вграмматике есть правило вывода A1 → a12. Многократно (до признака конца цепочки)выполнять шаги: полученный нетерминал Ai-1 иочередной терминал ai цепочки заменитьнетерминалом Ai, для которого в грамматике естьправило вывода Ai → Ai-1ai (i = 2, 3, ..., n)59Построение дерева разбораметодом “снизу-вверх”• Работа алгоритма разбора цепочки языка,порождаемого регулярной грамматикой:An-1всего n – 1разAi+1Ai=1a1a2an60Работа алгоритма разбора порегулярной грамматикеG = ({a, b}, {A, B, S}, P, S}a) на последнем шаге свёрткаP: A → Ab | Bb | bпроизошла к символу S: цепочкаB → Aaпринадлежит языку (a1a2...an⊥ ∈ L(G))S → A⊥SРазбор правильнойцепочки babb⊥Aприменением правилAAabb⊥A→bB → AaBbb⊥BA → BbAb⊥A → AbA⊥AS → A⊥Sbabb⊥61Работа алгоритма разбора порегулярной грамматикеG = ({a, b}, {A, B, S}, P, S}b) на последнем шаге свёрткапроизошла к символу, отличному от S: P: A → Ab | Bb | bB → Aaцепочка не принадлежит языкуS → A⊥(a1a2...an⊥ ∉ L(G))Разбор неправильнойцепочки babприменением правилAAabA→bB → AaBbBA → BbAСимвол A не являетсяAцелью грамматикиbab62Работа алгоритма разбора порегулярной грамматикеG = ({a, b}, {A, B, S}, P, S}c) для нетерминала Ak-1 и очередногоP: A → Ab | Bb | bтерминала ak не нашлосьB → Aaнетерминала Ak, для которого естьS → A⊥правило Ak → Ak-1ak: цепочка непринадлежит языку (a1a2...an⊥ ∉ L(G)) Разбор неправильнойцепочки bba⊥?применением правилBAba⊥A→bA → AbAa⊥AB → AaB⊥Правила для B⊥ вAграмматике нетbba⊥63Работа алгоритма разбора порегулярной грамматикеd) в грамматике разные нетерминалыимеют правила вывода содинаковыми правыми частями, ккакому из них производить свёртку?BA или B?AbabG = ({a, b}, {A, B, S}, P, S}P: A → Ab | Bb | bB → AaS → A⊥B → BbПопытка разборацепочки bab вграмматике сдополнительнымправилом B → Bb,неоднозначность:A → BbB → Bb64Детерминированный автомат• Детерминированный конечный автомат (ДКА) – этопятёрка (K, T, δ, H, S), где• K – конечное множество состояний• T – алфавит автомата, конечноемножество допустимых входных символов• δ – функция переходов: отображение K × T → K(отображение декартова произведениямножеств К и T на множество К)• H ∈ K – начальное состояние автомата• S ⊆ K – непустое (S ≠ ∅) конечноемножество заключительных состояний65Детерминированный автомат (ДКА)• Запись δ (A, t) = B означает, что из состояния A повходному символу t происходит переход автоматаДКА в состояние B• Автомат ДКА называют полностью определённым,если в каждом его состоянии существует функцияперехода для всех возможных входных символов, тоесть ∀ a ∈ T, ∀ q ∈ K ∃ δ (a, q) = R, где R ∈ K• Функция переходов может быть определена лишь дляподмножества K × T (частичная функция)• Если значение δ (A, t) не определено, автомат неможет продолжать работу и останавливается всостоянии “Ошибка”66Детерминированный автомат (ДКА)• Конечный автомат допускает (принимает) цепочкусимволов a1a2...an, если существуют переходыδ (A1, a2) = A2 .

. .δ (An-1, an) = Sδ (H, a1) = A1– алфавит автоматагде ai ∈ T, i = 1, 2, …, nAj ∈ K, j = 1, 2 , …, n – 1 – состояния автоматаH– начальное состояниеS– одно из заключительных состояний• Множество цепочек, допускаемых конечнымавтоматом, составляет определяемый им язык• Автоматы эквивалентны, если они задают один язык• Все конечные автоматы являютсяраспознавателями для регулярных языков67ДКА и леволинейные грамматики• Построение ДКА по леволинейной грамматикеВход: Леволинейная грамматика G = (T, N, P, S)Выход: Конечный автомат ДКА = (K, V, δ, H, C), L(G) = L(ДКА)• Привести грамматику G к автоматному виду• Установить, чтоK = N ∪ {H}V=T• Для каждого правила A → t ∈ P, где t ∈ T и А ∈ N вфункцию перехода включается правило δ (H, t) = A• Для каждого правила A → Bt ∈ P, где t ∈ T и А, B ∈ N вфункцию перехода включается правило δ (B, t) = A• В множество конечных состояний автомата включаетсяэлемент, соответствующий цели грамматики G: C = {S}68ДКА и леволинейные грамматики• Построение леволинейной грамматики по ДКАВход: Конечный автомат ДКА = (K, V, δ, H, C)Выход: Леволинейная грамматикаG = (T, N, P, S), L (G) = L (ДКА)•N = K \ {H}T=V• Для всех возможных состояний из множества К и всехвозможных входных символов из множества V:• Если δ (A, t) = ∅, где A∈ K, t ∈ V, никаких действий невыполняется• Если δ (A, t) = B, где A∈ K, B ∈ K, t ∈ V:• если А = Н, в Р включается правило B → t• если А ≠ Н, в Р включается правило B → Аt69ДКА и леволинейные грамматики• Построение леволинейной грамматики по ДКА• Если множество конечных состояний С автомата ДКАсодержит только одно состояние С = {C0}, целевымсимволом S грамматики G становится символ множестваN, соответствующий этому состоянию: S = C0• Если множество конечных состояний С автомата ДКАсодержит более одного состояния С = {C1, C2, …, Cn}, n > 1, вмножество нетерминальных символов N грамматики Gдобавляется новый нетерминальный символ S: N = N ∪ {S}• В множество правил Р грамматики G добавляются правилаS → C1 | C2 | …| Cn• G = (T, N, P, S)70Диаграмма состояний• Диаграмма состояний конечного автомата – этонеупорядоченный ориентированный помеченный граф,который строится следующим образом:• вершины графа (называемые состояниями)помечаются нетерминалами грамматики• добавляется ещё одна вершина (называемаяначальным состоянием), помечаемая символом,отличным от нетерминальных (например, H)• для каждого правила вида W → t соединяются дугойсостояния от H к W, дуга помечается символом t• для каждого правила вида W → Vt соединяются дугойсостояния от V к W, дуга помечается символом t71ДC и леволинейные грамматики• Построение леволинейной грамматики по ДC• Каждой дуге из начального состояния Н в состояние W,помеченной символом t, соответствует правило W → t• Каждой дуге из состояния V в состояние W, помеченнойсимволом t, соответствует правило W → Vt• Заключительное состояние S объявляется начальнымсимволом грамматики72Алгоритм разбора цепочки подиаграмме состояний• Текущим объявляется состояние H• Многократно (до тех пор, пока не прочитанпризнак конца цепочки) выполняютсяследующие шаги: читается очередной символисходной цепочки и осуществляется переход изтекущего состояния в новое состояние по дуге,помеченной прочитанным символом; новоесостояние становится текущим73Алгоритм разбора цепочки подиаграмме состояний• Прочитана вся цепочка; на каждом шаге находиласьединственная дуга, помеченная очередным символоманализируемой цепочки; в результате последнего переходадостигнуто состояние S, цепочка принадлежит языку L (G)• Прочитана вся цепочка; на каждом шаге находиласьединственная дуга; в результате последнего шага достигнутосостояние, отличное от S, цепочка не принадлежит языку L (G)• На некотором шаге не нашлось дуги, выходящей из текущегосостояния и помеченной очередным анализируемымсимволом, цепочка не принадлежит языку L (G)• На некотором шаге оказалось, что из текущего состояния естьнесколько дуг, помеченных очередным символом, ведущих в74разные состояния, разбор недетерминированПрограмма анализатораHabAbBbaCaГрамматика:S → C⊥С → Ab | BaA → a | CaB → b | CbAnalyze () { FA_State= H;try { do { switch (FA_State){ case H:if (c == ‘a’) { GetS (); FA_State = A; }else if (c == ‘b’) { GetS (); FA_State = B; }elseFA_State = Error;break;case A:if (c == ‘b’) { GetS (); FA_State = C; }elseFA_State = Error;break;⊥case B:if (c == ‘a’) { GetS (); FA_State = C; }elseFA_State = Error;break;case C:if (c == ‘a’) { GetS (); FA_State = A; }else if (c == ‘b’) { GetS (); FA_State = B; }FA_State = S;else if (c == ‘⊥’)elseFA_State = Error;break;case Error: throw c;}} while (FA_State != S);}catch (char c) { cout << “Плохой символ ” << c << endl; }75}SРазбор цепочки анализатором• При анализе цепочки abba⊥ возникаеттакая последовательность переходов:⊥H→A→C→B→C→Sabba• Каждая смена состояния означает “свёртку”сентенциальной формы путём замены вней пары “нетерминал-терминал” Nt нанетерминал L, где L → Nt есть правиловывода в грамматикеГрамматика:S → C⊥С → Ab | BaA → a | CaB → b | Cb• Возникает такая последовательность свёрток,соответствующая сменам состояний:abba⊥ ← Abba⊥ ← Cba⊥ ← Ba⊥ ← C⊥ ← S76Недетерминированность разбора• Дана грамматика G = ({a,b, ⊥}, {S,A,B}, P, S)где P: S → A⊥A → a | BbB → b | Bb• Для этой грамматики разбор будетнедетерминированным, так как унетерминальных символов A и B естьодинаковые правые части – Bb• Такой грамматике будет соответствоватьнедетерминированный конечный автомат77Недетерминированный автомат• Недетерминированный конечный автомат (НКА) –это пятёрка (K, T, δ, H, S), где• K – конечное множество состояний• T – конечное множество допустимых входныхсимволов (алфавит автомата)• δ – функция переходов: отображение K × T → ρ (K)(отображение декартова произведения множеств К иT в множество подмножеств К)• H ⊂ K – конечное множество начальных состояний• S ⊂ K – конечное множество заключительныхсостояний78Детерминированный автомат (ДКА)• Запись δ (A, t) = {B1, B2, …, Bn} означает, что изсостояния A по входному символу t происходитпереход автомата ДКА в любое из состояний Bi(i = 1, 2, …, n)Класс языков, определяемых НКА, совпадает склассом языков, определяемых ДКА• Для языка L эквивалентны утверждения:1.

Характеристики

Список файлов лекций