Языки и их представления

Языки и их представления Цепочки символов α и β равны (α = β), если они имеют один и тот же состав символов, одно и то же их количество и одинаковый порядок следования символов в цепочке. Количество символов в цепочке определяет её длину. Длина цепочки α обозначается как | α |. ПРИМЕР Для цепочки abbba префиксом является любая цепочка из множества L1 = {e, a, ab, abb, abbb, abbba}, суффиксом является любая цепочка из множества L2 = {e, a, ba, bba, bbba, abbba}, подцепочкой является любая цепочка из множества L1 U L2. Длиной цепочки w (обозначается |w|) называется число символов в ней. Например, |abababa| = 7, а |e| = 0. Язык в алфавите V - это некоторое множество цепочек в алфавите V Пример Пусть дан алфавит V = {a, b}. Вот некоторые языки в алфавите V : L1 = Ø - пустой язык; L2 = {e} - язык, содержащий только пустую цепочку (заметим, что L1 и L2 - различные языки); L3 = {e, a, b, aa, ab, ba, bb} - язык, содержащий цепочки из a и b, длина которых не превосходит 2; L4 - язык, включающий всевозможные цепочки из a и b, содержащие четное число a и четное число b; L5 = {an2 |n > 0} - язык цепочек из a, длины которых представляют собой квадраты натуральных чисел. Определения Если V – некоторый алфавит, то: V+ – множество всех цепочек над алфавитом V без пустой цепочки; V* – множество всех цепочек над алфавитом V, включая пустую цепочку. Языком L над алфавитом V (L (V)) называется некоторое счётное под-множество цепочек конечной длины из множества всех цепочек над алфавитом V. Операции над цепочками символов • • • • • Конкатенация Замена (подстановка ) обращение итерация Регулярные множества Пусть T - конечный алфавит. Регулярное множество в алфавите T определяется рекурсивно следующим образом : 1.{}∅(пустое множество) - регулярное множество в алфавите T; 2.{a}-регулярное множество в алфавите T для каждого a∈T ; 3.{e}-регулярное множество в алфавите T (e-пустая цепочка); 4.Если P и Q - регулярные множества в алфавите T, то таковы же и множества ● a) P∪Q (объединение), ● б) PQ(конкатенация, т.е. множество pq|p∈P, q∈Q), ● в) P*(итерация):P*={e}PPPPPP... ;(замыкание Клини) 5. Ничто другое не является регулярным множеством в алфавите T. Регулярные выражения Регулярное выражение в алфавите T и обозначаемое им регулярное множество в алфавите T определяются рекурсивно следующим образом: ∅ – регулярное выражение, обозначающее множество ∅; e – регулярное выражение, обозначающее множество {e}; a – регулярное выражение, обозначающее множество {a}; если p и q – регулярные выражения, обозначающие регулярные множества P и Q соответственно, то (а) (p|q) – регулярное выражение, обозначающее регулярное множество P ∪Q, (б) (pq) – регулярное выражение, обозначающее регулярное мно- жество P Q, (в) (p ) – регулярное выражение, обозначающее регулярное множество P ; ∗ ∗ Допущение Мы будем опускать лишние скобки в регулярных выражениях, договорившись о том, что операция итерации имеет наивысший приоритет, затем идет операции конкатенации, наконец, операция объединения имеет наименьший приоритет. Кроме того, мы будем пользоваться записью p+ для обозначения pp∗. Таким образом, запись (a|((ba)(a∗))) эквивалентна a|ba+. Наконец, мы будем использовать запись L(r) для регулярного множества, обозначаемого регулярным выражением r. Пример а) a(e|a)|b – обозначает множество {a, b, aa}; б) a(a|b)∗– обозначает множество всевозможных цепочек, состоящих из a и b, начинающихся с a; в) (a|b)∗(a|b)(a|b)∗– обозначает множество всех непустых цепочек, состоя+ щих из a и b, т.е. множество {a, b} ; г) ((0|1)(0|1)(0|1))∗– обозначает множество всех цепочек, состоящих из нулей и единиц, длины которых делятся на 3. Лемма. Пусть p, q и r - регулярные выражения. Тогда справедливы следующие соотношения: p|q = q|p ; ● {*}∅* = e ; ● p|(q|r) = (p|q)|r ; ● p(qr) = (pq)r ; ● p(q|r) = pq|pr ; ● (p|q)r = pr|qr ; ● pe = ep = p ; ● ∅p = p∅ = ∅ ; ● p* = p|p* ; ● (p*)* = p* ; ● p|p = p ; ● p|∅ = p ; ● Регулярные выражения для множества идентификаторов Letter = a | b| c| d| ...|x|y|z| Digit=0|1|...| 9 Identifier = Letter(Letter | Digit)* Язык можно определить тремя способами 1.перечислением всех допустимых цепочек языка; 2.указанием способа порождения цепочек языка (заданием грамматики языка); 3.определением метода распознавания цепочек языка. Порождающая грамматика G ● ● ● ● ● это четверка (VT, VN, P, S), где VT - алфавит терминальных символов (терминалов), VN - алфавит нетерминальных символов (нетерминалов), не пересекающийся с VT, P - конечное подмножество множества (VT Ս VN)+ ´ (VT Ս VN)*; элемент (a, b) множества P называется правилом вывода и записывается в виде a -> b, S - начальный символ (цель) грамматики, S ϵ VN. Язык, заданный грамматикой G, обозначается как L (G). Две грамматики, G и G', называются эквивалентными, если они определяют один и тот же язык: L (G) = L (G'). Две грамматики, G и G', называются почти эквивалент-ными, если заданные ими языки различаются не более чем на пустую цепочку символов: L (G) {ε} = L (G') {ε}. α → β1, α → β2, …, α → βn α → β1 | β2 | … | βn форма Бэкуса-Наура (БНФ) G ({0, 1, 2, 3, 4, 5, 6, 7, 8, 9, –, +}, {<число>, <чс>, <цифра>}, Р, <число>) Р: <число> → <чс> | +<чс> | –<чс> <чс> → <цифра> | <чс><цифра> <цифра> → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 Грамматика для языка целых десятичных чисел со знаком G' ({0, 1, 2, 3, 4, 5, 6, 7, 8, 9, –, +}, {S, T, F}, Р, S) Р: S → Т | +Т | –Т Т → F | TF F→0|l|2|3|4|5|6|7|8|9 Пример ● ● ● ● ● Грамматика G = ({S, B, C}, {a, b, c}, P, S), где P = {S →aSBC, S → aBC, CB → BC, aB → ab, bB → bb, bC → bc, cC→ cc}, порождает язык L(G) = {anbncn|n > 0}. Действительно, применяем n- 1 раз правило 1 и получаем an1S(BC)n-1, затем один раз правило 2 и получаем an(BC)n, затем n(n- 1)/2 раз правило 3 и получаем anBnCn. Затем используем правило 4 и получаем anbBn-1Cn. Затем применяем n- 1 раз правило 5 и получаем anbnCn. Затем применяем правило 6 и n - 1 раз правило 7 и получаем anbncn. Можно показать, что язык L(G) состоит из цепочек только такого вида. Классификация грамматик по Хомскому Тип 0: G (VT, VN, P, S), V = VN VT, правила имеют вид α → β, где α V+, βV*. Тип 1: контекстно-зависимые (КЗ) и неукорачивающие грамматики КЗ G (VT, VN, P, S), V = VN VT, правила вида α1Аα2 → α1βα2, где α1,α2 ∈V*, А∈ VN, β ∈V+. G (VT, VN, P, S), V = VN VT, имеют правила вида: α → β, где α, β V+, |β| ≥ |α|. Классификация грамматик по Хомскому Тип 2: контекстно-свободные (КС) грамматики (НКС) G (VT, VN, P, S), V = VN VT, имеют правила вида А → β, где А ∈VN, β∈ V+ (УКС) G (VT, N, P, S), V = VN VT, правила которых могут иметь вид: А →β, где А∈VN, β∈ V*. Классификация грамматик по Хомскому Тип 3: регулярные грамматики: леволинейные и праволинейные. Леволинейные G (VT, VN, P, S), V = VN VT, могут иметь правила двух видов: А → Bγ или А → γ, где А, В∈ VN, γ∈ VT*. Праволинейные G (VT, VN, P, S), V = VN VT, могут иметь правила тоже двух видов: А → γВ или А → γ, где А, В∈ VN, γ ∈VT*. Сентенциальная форма грамматики G (VT, VN, P, S), V = VT U VN, если она выводима из целевого символа грамматики S: S ═>* α. Если цепочка α ∈ VT* получена в результате законченного вывода, то она называется конечной сентенциальной формой. G' ({0, 1, 2, 3, 4, 5, 6, 7, 8, 9, –, +}, {S, T, F}, Р, S) Р: S → Т | +Т | –Т Т → F | TF F→0|l|2|3|4|5|6|7|8|9 S ═>–T ═>–TF═> –TFF═> –FFF═> –4FF═> –47F═> –479 2) S═> T═> TF═> T8═> F8═> 18 3) T═> TF═> T0═> TF0═> T50═> F50═> 350 4) F ═>5 Пример для цепочки a+b+a G ({a, b, +}, {S, T}, P, S) P: S → T | T+S; T→a|b можно построить выводы: 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 Пример праволинейной грамматики ● G2 = ({S,}, {0,1}, P, S), где ● P: ● S → 0S; ● S → 1S; ● S → ε, Пример КС-грамматики ● G3 = ({E, T, F}, {a, +, *, (,)}, P, E) где ● P: ● E →T ● E→E+T ● T→F ● T→T*F ● F → (E) ● F → a. Пример КЗ грамматики ● G4 = ({B, C, S}, {a, b, c}, P, S) где ● P: ● 1. S → aSBC; ● 2. S → abc; ● 3. CB → BC; ● 4. bB → bb; ● 5. bC → bc; ● 6. cC → сc, Деревом вывода грамматики G (VT, VN, P, S) называется 1.каждая вершина дерева обозначается символом грамматики А∈(VT U VN U {ε}); 2.корнем дерева является вершина, обозначенная целевым символом грамматики – S; 3.листьями дерева (концевыми вершинами) являются вершины, обозна-ченные терминальными символами грамматики или символом пустой цепочки ε; 4.если некоторый узел дерева обозначен нетерминальным символом А∈ VN, а связанные с ним узлы – символами b1, b2, …, bn; n > 0 для любого i, 0 ≤ i≤ n: bi ∈(VT U VN U {ε}), то в грамматике G (VT, VN, P, S) существует правило A → b1 | b2 | … | bn ∈Р Примеры деревьев вывода для грамматики целых десятичных чисел со знаком S → if b then S else S | if b then S | a if b then if b then a else a: 1) S =>if b then S else S =>if b then if b then S else S=> if b then if b then a else S => if b then if b then a else a 2) S=> if b then S=> if b then if b then S else S=> if b then if b then a else S=> if b then if b then a else a первая из них – if b then (if b then a) else a, вторая – if b then (if b then a else a). Правила неоднозначности 1) А → АА | α 2) А → АαА | β 3) А → αА | Aβ | γ 4) А → αА | αAβA | γ Здесь A VN; α, β, γ (VN VT)*. Алгоритм удаления бесплодных символов Вход: КС-грамматика G (VT, VN, P, S). Выход: КС-грамматика G (VT, VN, P, S), не содержащая бесплодных сим-волов, для которой L (G) = L (G). Метод: Рекурсивно строим множества N0, N1, ..., Nm 1. N0 =∅ , i = 1. 2. Ni = {A | (A → α) ∈P и α ∈(Ni–1 VT)*}U Ni–1. 3. Если Ni ≠ Ni–1, то i = i + 1 и переходим к шагу 2, иначе VN = Ni; P состоит из правил множества P, содержащих только символы из VN U VT; G (VT, VN, P, S). Пример Дана грамматика G ({a, b, c}, {A, B, C, D, E, F, G, S}, P, S) с правилами P: S aAB | E A aA | bB B ACb | b C A | bA | cC | aE E cE | aE | Eb | ED | FG D a | c | Fb F BC | EC | AC G Ga | Gb G ({a, b, c}, {A, B, C, D, F, S}, P, S) P: S aAB A aA | bB B ACb | b C A | bA | cC D a | c | Fb F BC | AC Алгоритм удаления недостижимых символов Вход: КС-грамматика G (VT, VN, P, S) Выход: КС-грамматика G' (VT', VN', P', S), не содержащая недостижимых символов, для которой L (G) = L (G). Метод: 1. V0 = {S}; i = 1. 2. Vi = {x | x ∈(VT VN), в P есть A → αхβ и A∈ Vi–1, α, β ∈(VT UVN)*} U Vi–1. 3. Если Vi≠ Vi–1, то i = i + 1 и переходим к шагу 2, иначе VN = Vi ∩VN; VT = Vi∩ VT; P состоит из правил множества P, содержащих только сим-волы из Vi; G' (VT', VN', P', S). Пример G ({a, b, c}, {A, B, C, D, F, S}, P, S) P’: S aAB Gʺ ({a, b, c}, {A, B, C, S}, Pʺ, S)Pʺ: A aA | bB B ACb | b C A | bA | cC D a | c | Fb F BC | AC S aAB A aA | bB B ACb | b C A | bA | cC Алгоритм устранения ε-правил: Вход: КС-грамматика G (VT, VN, P, S). Выход: КС-грамматика G '(VT, VN', P', S), не содержащая ε-правил, для которой L (G) = L (G). Метод: 1. W0 = {A: (A→ε )∈ P}, i = 1. 2. Wi = Wi–1 {A: (A ) P, Wi–1}*. 3. Если Wi ≠Wi–1, i = i + 1, то перейти к шагу 2, иначе перейти к шагу 4. 4. VN' = VN, VT' = VT, в P' входят все правила из Р, кроме правил вида A →ε. 5. Если A →α0B1α1B2 … Bkαk ∈P, где k≥ 0, Bj ∈Wi и ни один из сим-волов цепочек i не содержит символов из Wi, то включить в Р все правила вида A→ α0X1α1X2 … Xkαk, где Xj = Bj или X = ε. 6. Если S ∈Wi , то значит ε∈ L (G), и тогда в VN добавляется новый символ S', который становится целевым символом грамматики, а в Р' добавляются правила: S'→ε | S. Пример Дана грамматика G ({a, b, c}, {A, B, C, S}, P, S) с правилами Р: S AaB | aB | cC A AB | a | b | B B Ba | C AB | c VN' = {A, B, C, S}, VT' = {a, b, c} P': S AaB | aB | cC A AB | a | b | B B Ba C AB | c Алгоритм устранения цепных правил Для всех нетерминальных символов повторять шаги 2-4, затем перейти к 5. 1. NX0 = {X}, i = 1. 2. NXi = NХi–1 U{B: (A→ B)∈ P, A∈ NХi–1}. Если NXi ≠ NХi–1 , то i = i + 1 и перейти к 3, иначе NX= NХi–1 – {Х} и продол-жить цикл по шагу 1. VN' = VN, VT' = VT, в P' входят все правила из Р, кроме правил вида A →B, S' = S. Для всех правил (B→ α)∈ P', если В∈ NА, В≠ А, то в P' добавляются пра-вила вида A→α . Алгоритм приведения грамматики: 1) обнаруживаются и удаляются все бесплодные нетерминалы; 2) обнаруживаются и удаляются все недостижимые символы; 3) удаляются правила с пустыми цепочками (-правила); 4) удаляются цепные правила. Удаление символов сопровождается удалением правил вывода, содержащих эти символы. Замечание: шаги преобразования должны выполняться в указанном порядке! A=> +α Aβ, где α,β (VT U VN)*. Если α=ε и β≠ε Вход: КС-грамматика G (VT, VN, P, S) Выход: КС-грамматика G' (VT', VN', P', S), не содержащая левой рекурсии, для которой L (G) = L (G'). Метод: 1. VN = {A1, A2, …, An}, i = 1 2. Правила для Ai. Если в правилах нет левой рекурсии, то они записываются в P' без изменений, а Ai добавляется в VN'. Иначе правила для Аi записываются в виде Ai Ai1 | Ai2 | … | Aim | 1 | 2 | … | p , где ни одна из цепочек j не начинается с Ak таких, что k i. Вместо этих правил в P записываются правила вида: Ai 1 | 2 | … | p | 1Ai | 2Ai | … | pAi Ai 1 |2 |…|m | 1Ai | 2Ai | … | mAi Аi и Аi включаются в VN. 3. Если i = n, то G построена, перейти к 6, иначе i = i + 1, j = 1, перейти к 4. 4. Для Ai в P заменить все правила вида Ai-> Aj, где (VT VN)*, на правила вида Ai 1α | 2 α | … | αm, причём Aj 1 | 2 | … | m – все правила для Aj. 5. Если j = i – 1, перейти к 2, иначе j = j + 1 и перейти к 4. 6. Целевым символом грамматики G становится Ak, соответствующий сим-волу S исходной грамматики.