Формальные грамматики и языки (1119467)
Текст из файла
Основные определения• Аксиоматика: “символ” и “множество”• Алфавит – непустое конечное множество символов,будет обозначаться символом V• Цепочка символов в алфавите V – любая конечнаяпоследовательность символов этого алфавита• Цепочка, которая не содержит ни одного символа,называется пустой цепочкой, для её обозначенияиспользуется символ ε, который по предположению сам валфавит V не входит• Длина цепочки – число составляющих её символов,например, если α = abcdefgh, то длина α равна 8Длина цепочки α обозначается как |α|Длина пустой цепочки ε равна 0, то есть |ε| = 01Основные определения• Если α и β – цепочки, то цепочка αβ (результатприписывания цепочки β в конец цепочки α) называетсяконкатенацией (или сцеплением) цепочек α и β• Конкатенацию αβ можно считать двуместной операциейнад цепочками α и β (α ⋅ β = αβ), например, если α = ab иβ = cd, то α ⋅ β = abcd• Для любой цепочки α всегда α ⋅ ε = ε ⋅ α = α• Конкатенация некоммутативна, то есть α ⋅ β ≠ β ⋅ αНапример, если α = ab и β = cd, имеем β ⋅ α = cdab• Конкатенация цепочек ассоциативна, для любых цепочекα, β и γ всегда верно: α ⋅ β ⋅ γ = (α ⋅ β) ⋅ γ = α ⋅ (β ⋅ γ)2Основные определения• Цепочки символов можно разбивать на подцепочки• Цепочки символов можно заменять на другие цепочки• В результате замены (подстановки) цепочек получаютсяновые цепочки символов• Цепочку γ = abcd можно разбить (в том числе) на триподцепочки: α = a, ω = b и β = cd, то есть исходную цепочкуможно представить как γ = αωβ• Если для цепочки ω выполнить подстановку υ = aba,получится новая цепочка γ = aabacd (γ = αυβ)• Любая подстановка выполняется с помощью операцийразбиения и конкатенации3Основные определения• Обращением (реверсом) цепочки α называется цепочка,символы которой записаны в обратном порядке,обращение цепочки α обозначается как αR• Например, если α = abcdefgh, то αR = hgfedcba• Для пустой цепочки ε = εR, εR = ε• Справедливо тождество: ∀α, β: (αβ)R = βRαR• n-ой степенью цепочки α (αn) называется конкатенация nцепочек α (повторение этой цепочки n раз)• Справедливо: ∀α: α0 = ε; α1 = α; α2 = αα; αn = ααn-1 = αn-1α• Для пустой цепочки: ∀n ≥ 0: ε n = ε• Число вхождений символа s в цепочку α обозначается как|α|s, например: |babb|a = 1, |babb|b = 3, |babb|c = 0 4Основные определения• Множество V*, содержащее все цепочки в алфавите V,включая пустую цепочку ε, называется итерациеймножества V• Если V={0,1}, то V* = {ε, 0, 1, 00, 11, 01, 10, 000, 001, 011, ...}• Множество V+, содержащее все цепочки в алфавите V,исключая пустую цепочку ε, называется усечённойитерацией множества V, следовательно, V* = V+ ∪ {ε}• Язык в алфавите V – это счётное подмножество цепочекконечной длины из множества всех цепочек надалфавитом V• Цепочку символов, принадлежащую некоторому языку,называют предложением языка, а множество цепочек5языка – множеством предложений этого языкаОсновные определения• Каждый язык в алфавите V является подмножествоммножества V*, то есть выполняется отношение L(V) ⊆ V*• Язык L(V) включает в себя язык L’(V), если любая цепочка,входящая в первый язык, одновременно входит и вовторой:L’ (V) ⊆ L (V), если ∀α ∈ L’ (V): α ∈ L (V)• Два языка L(V) и L’(V) совпадают (равны), если каждый изних включает в себя второй язык:L’ (V) = L (V), если L’ (V) ⊆ L (V) и L (V) ⊆ L’ (V)• Два языка L(V) и L’(V) почти совпадают, если ониразличаются только на пустую цепочку символов:L’(V) ≅ L(V), если L’(V) ∪ {ε} = L (V) ∪ {ε}6Основные определения• Язык можно определить1.
Перечислением всех допустимых цепочек языка2. Выбором механизма порождения (генерации), то естьуказанием способа формирования (порождения)цепочек (заданием грамматики языка)3. Выбором механизма распознавания, то естьопределением метода распознавания цепочек языка• Первый метод – иллюстративный:L ({a,b}) = {aa, ab, ba, bb}• Иногда этот метод модифицируют описанием множестввходящих в язык цепочек с помощью формул:L = {α ∈ (a, b)+, |α| = 2} (только что показанный язык)L({0,1}) = {01, 0011, 000111, …} ≡ L({0,1}) = {0n1n, n > 0}7Основные определения• Второй способ связан с определением правил, с помощьюкоторых можно строить правильные цепочки языка изсимволов алфавита языка, в этом случае используютсяпорождающие грамматики (грамматиками Холмского),которые представляют собой основной способ реализациимеханизма порождения• Третий способ требует наличия логического устройства(распознавателя) – автомата, который, получая входнуюцепочку символов алфавита, на выходе выдаёт ответ,принадлежит ли заданная цепочка данному языку или нет8Основные определения• Примеры распознавателей:1.
Машина Тьюринга (МТ) для рекурсивноперечислимым языков2. Линейно ограниченный автомат (ЛОА) дляконтекстно-зависимых языков3. Автомат с магазинной (внешней) памятью (МПавтомат) для контекстно-свободных языков4. Конечный автомат (КА – детерминированный ДКА илинедетерминированный НКА) для регулярных языков9Основные определения• При изучении языков выделяют их лексику, синтаксис исемантику• Лексика языка – это совокупность слов (словарный запас)языка• Слово языка или его лексическая единица (лексема)состоит из элементов алфавита языка и не содержит всебе никаких других конструкций• Синтаксис определяет форму языка, задаёт наборцепочек символов, которые принадлежат этому языку,фиксирует набор правил, определяющих допустимыеконструкции языка• Семантика языка определяет значение (смысл)предложений языка10Основные определения• Грамматикой языка называется способпостроения предложений этого языка• Для языков программирования используетсяформальное описание грамматики,построенной на основе правил (продукций)• Правило (продукция) есть упорядоченная парацепочек символов (α, β)• Правила записывают в виде α → βЧитается: “α порождает β”, “из α следует β”11Основные определения• Декартовым произведением A × B множеств A и Bназывается множество пар {(a, b) | a ∈ A, b ∈ B}• Определение порождающей грамматикиПорождающая грамматика G – это четвёрка (T, N, P, S),где• T – алфавит терминальных символов• N – алфавит нетерминальных символовМножества N и T не пересекаются друг с другом: N ∩ T = ∅• P – конечное множество правил – подмножествомножества (T ∪ N)+ × (T ∪ N)* (первый элементпроизведения не может быть пустой цепочкой)• S – начальный символ (цель) грамматики, S ∈ N12Основные определения• Множество V = T ∪ N называется полным алфавитомграмматики G• Элемент (α, β) множества P называется правилом выводаи записывается в виде α → β, здесь α ∈ (T ∪ N)+ – леваячасть правила, а β ∈ (T ∪ N)* – правая часть правила• Левая часть любого правила из P обязана содержать хотябы один нетерминальный символ• Для записи совокупности правил вывода с одинаковымилевыми частямиα → β1 α → β2 α → βnпользуются сокращённой записью α → β1 | β2 |...| βn• Каждое βi, i = 1, 2, ..., n называется альтернативойправила вывода из цепочки α13Основные определения• Цепочка β ∈ (T ∪ N)* непосредственно выводима изцепочки α ∈ (T ∪ N)+ в грамматике G = (T, N, P, S) (α → G β),если α = ξ1γξ2, β = ξ1δξ2, где ξ1, ξ2, δ ∈ (T ∪ N)*, γ ∈ (T ∪ N)+и правило вывода γ → δ содержится в P• Цепочка β ∈ (T ∪ N)* выводима из цепочки α ∈ (T ∪ N)+ вграмматике G = (T, N, P, S) (α ⇒G β), если существуютцепочки γ0, γ1, ...
, γn (n >= 0): α = γ0 → γ1 → ... → γn = β• Последовательность цепочек γ0, γ1, ..., γn называетсявыводом цепочки β из цепочки α длины n•Цепочка 00A11 непосредственно выводима из 0A1 в G1•Цепочка 000A111 выводима из S (S ⇒ 000A111) в G1, так как имеется выводS → 0A1→ 00A11 → 000A111 (длина вывода равна 3)14Основные определения• Определение языка, порождаемого грамматикойЯзыком, порождаемым грамматикой G = (T, N, P, S),называется множество L (G) = {α ∈ T* | S ⇒ α}• L (G) – это все цепочки в алфавите T, которые выводимы изS с помощью P. Например, L (G1) = { 0n1n | n > 0 }• Задачи на поиск языка, порождаемого некоторойграмматикой, решаются путём последовательногоприменения подстановок в правилах грамматики:S → 0A1 → (A → ε) 01S → 0A1 → (0A → 00A1) 00A11 → (A → ε) 0011S → 0A1 → (0A → 00A1) 00A11 → (0A → 00A1) 000A111 →… ⇒ (0A → 00A1) 0nA1n → (A → ε) 0n1n15Основные определения• Цепочка α ∈ (T ∪ N)*, для которой S ⇒ α, называетсясентенциальной формой в грамматике G = (T, N, P, S)• Цепочка α ∈ T*, полученная в результате законченноговывода, называется конечной сентенциальнойформой• Язык, порождаемый грамматикой G, можноопределить как множество конечных (терминальных)сентенциальных форм грамматики G• Алфавитом языка L (G) является множествотерминальных символов грамматики T16Основные определения• Определение эквивалентности грамматикГрамматики G1 и G2 называются эквивалентными, если ихязыки совпадают: L (G1) = L (G2)• G1 и G2 эквивалентны, порождается язык L = { 0n1n | n > 0 }:G1 = ({0,1}, {A,S}, P1, S)иG2 = ({0,1}, {S}, P2, S)P1: S → 0A1P2: S → 0S1 | 010A → 00A1A→ε• Грамматики G1 и G2 почти эквивалентны, если совпадаютязыки L(G1) ∪ {ε} = L(G2) ∪ {ε}• G1 и G3 почти эквивалентны: L(G3) = { 0n1n | n >=0 }:G3 = ({0,1}, {S}, P3, S)P3: S → 0S1 | ε17Основные определения• Грамматики обладают свойством эквивалентности,если совпадают заданные ими языки,то есть, если L (G) = L (G’)• Эквивалентные грамматики должны иметь, покрайней мере, пересекающиеся (чаще совпадающие)множества терминальных символов T ∩ T’ ≠ ∅• Множества нетерминальных символов, правила иначальный символ эквивалентных грамматик могутсущественно различаться• Следствие: один язык может описываться разнымиграмматиками, что влияет на выбор методов анализаязыков в компиляторах18Типы грамматик и языков• Выделяют четыре входящих друг в друга категории(типа) языков с соответствующими входящими друг вдруга грамматиками• Грамматики классифицируются по виду их правилвывода• Чтобы отнести грамматику к какому-либо типу, всеправила этой грамматики должны относиться к этомутипу• Каждому типу грамматик соответствует свой классязыков• Если язык порождается грамматикой типа i (для i = 0,1, 2, 3), то он является языком типа i19Типы грамматик и языков• ТИП 0: Грамматика G = (T, N, P, S) называетсяграмматикой типа 0, если на правила вывода ненакладывается никаких ограничений (кроме тех,которые указаны в определении грамматики):α→βα ∈ (T ∪ N)+, β ∈ (T ∪ N)*• В грамматиках типа 0 можно встретить такиеправила:a) aAbCD → aHD (то есть AbC → H в контексте a … D)b) PQ → QP• Класс языков типа 0 совпадает с классомрекурсивно-перечислимых языков20Типы грамматик и языков• ТИП 1: Грамматика G = (T, N, P, S) называетсянеукорачивающей грамматикой, если левая частькаждого правила из P не длинее правой части, то естькаждое правило из P имеет вид:α → β, где α ∈ V+, β ∈ V+ и |α| ≤ |β|• В неукорачивающей грамматике допускается наличиеправила S → ε, при условии, что S (начальный символ)не встречается в правых частях правил грамматики• Грамматика с правилами { S→ Aaa |ε, Aa→ Sa } не являетсянеукорачивающей: Символ S встречается в правой частиправила Aa → Sa, и при выводе сентенциальная форма“укорачивается”: S → Aaa → Saa → aa21Типы грамматик и языков• ТИП 1: Грамматика G = (T, N, P, S) называетсяконтекстно-зависимой, если каждое правило из P снепустой правой частью имеет вид:α → β, где α = ξ1Aξ2, β = ξ1γξ2, A ∈ N, γ ∈ V+, ξ1, ξ2 ∈ V*• В контекстно-зависимой грамматике допускаетсяналичие правила S → ε, при условии, что S (начальныйсимвол) не встречается в правых частях правилграмматики• Цепочку ξ1 называют левым контекстом, а цепочкуξ2 называют правым контекстом• Язык, порождаемый контекстно-зависимойграмматикой, называется контекстно-зависимымТипы грамматик и языков• ТИП 1: Грамматика типа 1 определяется какнеукорачивающая грамматика• ТИП 1: Грамматика типа 1 определяется какконтекстно-зависимая грамматика• Из определений следует, что если язык, порождаемыйконтекстно-зависимой или неукорачивающейграмматикой G = (T, N, P, S), содержит пустую цепочку,то эта цепочка выводится в G за один шаг с помощьюправила S → ε• Других выводов для цепочки ε в грамматике G несуществует23Типы грамматик и языков• Если L — формальный язык, то такие утвержденияэквивалентны:• ∃ такая контекстно-зависимая грамматика G1, что L = L (G1)• ∃ такая неукорачивающая грамматика G2, что L = L (G2)• Контекстно-зависимая грамматика являетсянеукорачивающей: в правилах контекстно-зависимыхграмматик (ξ1Aξ2→ ξ1γξ2) из сохранения контекстаследует, что его длина (|ξ1| + |ξ2|) не меняется,|A| = 1, |γ| > 0, |A| ≤ |γ|• Существует доказательство и обратнойэквивалентности24Типы грамматик и языков• ТИП 2: Грамматика G = (T, N, P, S) называетсяконтекстно-свободной, если каждое правило из Римеет вид:A → β,где A ∈ N,β ∈ (T ∪ N)*• Цепочка β (правая часть правила) может быть пустой• Грамматика типа 2 – это контекстно-свободнаяграмматика• Язык, порождаемый контекстно-свободнойграмматикой, называется контекстно-свободнымязыком25Типы грамматик и языков• Среди контекстно-свободных грамматик выделяютнеукорачивающие контекстно-свободныеграмматики• Такие грамматики имеют только правила с непустымиправыми частями (за одним исключением: S → ε),они являются частным случаем контекстно-зависимыхграмматик с пустым контекстом, |ξ1| + |ξ2| = 0• Неукорачивающие контекстно-свободные грамматикиотличаются тем, что правая часть их правил всегда некороче соответствующей левой части, то естьβ ∈ (T ∪ N)+ и |β| ≥ 126Типы грамматик и языков• ТИП 3: Грамматика G = (T, N, P, S) называетсяправолинейной, если каждое правило из Р имеет вид:A → γB либо A → γгде A ∈ N, B ∈ N, γ ∈ T*• ТИП 3: Грамматика G = (T, N, P, S) называетсялеволинейной, если каждое правило из Р имеет вид:• A → Bγ либо A → γгде A ∈ N, B ∈ N, γ ∈ T*• Грамматика типа 3 – это праволинейная грамматика• Множество языков, порождаемых праволинейнымиграмматиками, совпадает с множеством языков, порождаемыхлеволинейными грамматиками• Если для некоторого формального языка существуетправо(лево-)линейная грамматика, то одновременно для него27существует и лево(право-)линейная грамматикаТипы грамматик и языков• Языки, порождаемые грамматиками типа 3,называются регулярными• Каждая грамматика типа 1 (а значит, и типа 2) можетбыть преобразована к грамматике типа 3, еслиможно избавиться от правил вида A → φAψ (где φ и ψне пусты), в противном случае они называютсяграмматиками с самовставлением• К регулярным грамматикам не относятся грамматики,в которых смешаны праволинейные и леволинейныеправила, такие грамматики следует относить к классуконтекстно-свободных грамматик28Типы грамматик и языков• Регулярные грамматики могут бытьнеукорачивающими, если в них не встречаютсяправила с пустой правой частью• Среди неукорачивающих регулярных грамматиквыделяются автоматные грамматики• Автоматные грамматики могут быть лево- иправолинейными• Леволинейные автоматные грамматики имеютправила видов: А → Вt или А → t, где А, В ∈ N, t ∈ T• Праволинейные автоматные грамматики имеютправила видов: А → tВ или А → t, где А, В ∈ N, t ∈ T29Типы грамматик и языков• Классы обычных и автоматных регулярныхграмматик почти эквивалентны• Чтобы классы этих грамматик стали полностьюэквивалентными, в автоматные грамматики вводятдополнительное правило вида S → ε, где S –начальный символ грамматики• Существует алгоритм преобразования произвольнойрегулярной грамматики к автоматному виду• Для любой регулярной (автоматной) грамматики Gсуществует неукорачивающая регулярная(автоматная) грамматика G′, такая что L (G) = L (G′)30Отношения между грамматиками• Регулярные грамматики являются контекстносвободными• Неукорачивающие контекстно-свободные грамматикиявляются контекстно-зависимыми• Неукорачивающие грамматики относятся к типу 0• Иерархия типов грамматикНеукорачивающие регулярные⊂ Неукорачивающие контекстно-свободные⊂ Контекстно-зависимые (либо неукорачивающие)⊂ тип 0• Не все контекстно-свободные грамматики являютсянеукорачивающими: тип 2 не вкладывается в тип 131Соотношения между языками• Язык L (G) является языком типа k, если его можноописать грамматикой типа k• Языки классифицируются в соответствии с типамиграмматик, с помощью которых они описываются• Для классификации языка выбирается грамматика смаксимальным классификационным типом• Грамматика типа 0G1 = ({0,1}, {A,S}, P1, S)и грамматика типа 2 G2 = ({0,1}, {S}, P2, S)P2: S → 0S1 | 01где P1: S → 0A10A → 00A1описывают контекстноA→εсвободный языкL = L (G1) = L (G2) = { 0n1n | n > 0 }32Соотношения между языками• Языки с фразовой структурой (рекурсивноперечислимые множества) могут быть заданы толькограмматикой типа 0• Контекстно-зависимые языки применяются ванализе и переводе текстов на естественных языках,алгоритмы разбора контекстно-зависимых текстовимеют экспоненциальную сложность• Современные языки программирования описываютсяс помощью контекстно-свободных грамматик• Регулярные языки используются для лексическогораспознавания идентификаторов и констант33Соотношения между языками• Для языков существуют доказанные факты, которыеможно использовать при их классификации:языки L = { an|n≥1 }языки L = { anbn|n≥1 }языки L = { anbncn|n≥1 }регулярныеконтекстно-свободныеконтекстно-зависимые• В регулярных языках повторяется только однапоследовательность символов – f (ab)nc• В контекстно-свободных языках повторяются двецепочки – a3n+1bn-2• В контекстно-зависимых языках повторяются трицепочки34Соотношения между языками• Каждый регулярный язык является контекстносвободным языком, но существуют контекстносвободные языки, которые не являются регулярнымине регулярныйязык L = { anbn|n > 0 }язык L = { anbm|n, m > 0 } регулярный• Каждый контекстно-свободный язык являетсяконтекстно-зависимым, но существуют контекстнозависимые языки, которые не являются контекстносвободными (L = {anbncn | n > 0})• Каждый контекстно-зависимый язык является языкомтипа 0, но существуют языки типа 0, которые неявляются контекстно-зависимыми35Соотношения между языками• Иерархия классов языков:Тип 3 (регулярные)⊂ Тип 2 (контекстно-свободные)⊂ Тип 1 (контекстно-зависимые)⊂ Тип 0• Диаграммы Венна36Цепочки вывода• Цепочка принадлежит языку, порождаемомуграмматикой, если существует её вывод из начальногосимвола этой грамматики• Процесс построения такого вывода называетсяразбором (нисходящим или восходящим)• Последовательность непосредственно выводимыхцепочек языка называется выводом или цепочкойвывода• Каждый переход от одной непосредственновыводимой цепочки к следующей называется шагомвывода37Цепочки вывода• Цепочка β может быть выводима из цепочки α (α ⇒ β)за 0 или более шагов• Если цепочка β непосредственно выводима изцепочки α (α→β), то имеется ровно один шаг вывода• Если цепочка вывода из α к β содержит одну илиболее промежуточных цепочек, цепочка β называетсянетривиально выводимой из цепочки α• Вывод цепочки β называется законченным, если на еёоснове нельзя сделать ни одного шага вывода• Законченный вывод возможен, если конечнаяцепочка вывода β пуста, или содержит только38терминальные символыРазбор по КС-грамматике• Вывод цепочки β ∈ 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+a39Дерево вывода• Ориентированное упорядоченное помеченное дерево(граф) называется деревом вывода (или деревомразбора) в контекстно-свободной грамматикеG = {T, N, P, S), если выполнены следующие условия:a) каждая вершина и каждый лист дерева помеченысимволом из множества терминальных инетерминальных символов N ∪ T ∪ {ε}, при этомкорень дерева помечен начальным(нетерминальным) символом S, промежуточныевершины помечены нетерминальными символамииз N, а листья – символами из множества T ∪ {ε}40Дерево вывода• Ориентированное упорядоченное помеченное дерево(граф) называется деревом вывода (или деревомразбора) в контекстно-свободной грамматикеG = {T, N, P, S), если выполнены следующие условия:b) если вершина дерева помечена нетерминальнымсимволом A ∈ N, а её непосредственные потомкипомечены перечисленными слева направотерминальными или нетерминальными символамиa1, a2, ..., an, где каждое ai ∈ (T ∪ N), то в грамматикеG существует правило вывода A → a1a2...an ∈ P41Дерево вывода• Ориентированное упорядоченное помеченное дерево(граф) называется деревом вывода (или деревомразбора) в контекстно-свободной грамматикеG = {T, N, P, S), если выполнены следующие условия:c) если вершина дерева помечена нетерминальнымсимволом A ∈ N, а её непосредственный потомокпомечен символом ε, то этот потомок являетсялистом дерева, а в грамматике G существует правиловывода A → ε42Дерево вывода• Два разных упорядоченных дерева:SabSba• Дерево вывода для цепочки a+b+a в грамматикеG = ({a, b, +}, {S, T}, P, S)P: S → T | T+ST→a|bTaS+ TbSST+a43Проблема однозначности• Грамматика G называется неоднозначной, еслисуществует (хотя бы одна) цепочка α ∈ L (G), длякоторой может быть построено два или болееразличных деревьев вывода• G1 = ({a, +}, {S, A}, P1, S)G2 = ({a, +}, {S}, P2, S)P2: S → S + S | aP1: S → S + A | AA→aSSSAaS+A+AaaSSS+SS+S+SaaS+aЦепочка a + a + aaSaa44Проблема однозначности• Язык, порождаемый грамматикой, называетсянеоднозначным, если он не может быть порождённикакой однозначной грамматикой• G = ({if, then, else, a, b}, {S}, P, S)P: S → if b then S else S | if b then S | aSifbifthenSbthennЦепочка if b then if b then a else aelseSSaa45Проблема однозначности• Язык, порождаемый грамматикой, называетсянеоднозначным, если он не может быть порождённикакой однозначной грамматикой• G = ({if, then, else, a, b}, {S}, P, S)P: S → if b then S else S | if b then S | aSifbifthenSbthennЦепочка if b then if b then a else aS elseSaa46Проблема однозначности• Неоднозначность - это свойство грамматики, а неязыка: для некоторых неоднозначных грамматиксуществуют эквивалентные им однозначныеграмматики• G = ({+, –, *, /, (, ), a, b}, {S}, P, S)PН: S → S + S | S – S | S * S | S / S | (S) | a | bPО: S → S + T | S – T | TT→T*E|T/E|EE → (S) | a | b47Проблема однозначности• Грамматика, используемая для определения языкапрограммирования, должна быть однозначной• G = ({if, then, else, a, b}, {S, R}, P, S)P: S → if b then R else S | if b then S | aR → if b then R else R | aSifbifthenSbthennЦепочка if b then if b then a else aR elseSaa48Проблема однозначности• Для контекстно-свободных грамматик можно указатьнекоторые виды правил вывода, которые заведомоприводят к неоднозначности:A → AA | αA∈NA → AαA | βα, β, γ ∈ (N ∪ T)*A → αA | Aβ | γA → αA | αAβA | γ• Отсутствие перечисленных правил являетсянеобходимым, но не достаточным условиемоднозначности49Бесплодные символы• Символ A ∈ N называется бесплодным в грамматикеG = (T, N, P, S), если множество { α ∈ T* | A ⇒ α } пусто• Алгоритм удаления бесплодных символовВход:Грамматика G = (T, N, P, S)Выход:Грамматика G’ = (T’, N’, P’, S’)Метод:Рекурсивно строятся множества символов N0, N1, …1.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
