programming.systems.L13-14.slides (1119459)

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

Текст из файла

1Элементы теории трансляцииТрансляторпозволяет преобразовать программу, написанную на ЯП,отличном от машинного языка, к виду, допускающемувыполнение на ЭВМ.Компиляторна вход получает программу на некотором ЯП (немашинном), ана выходе выдает объектный модуль (программу на машинномязыке).Интерпретаторна вход получает программу на некотором ЯП (немашинном) и,считывая предложение за предложением исходной программы,анализирует их и тут же выполняет действия, указанные в этихпредложениях.2Система программирования компилирующего типаисходныеданныеисходнаяпр-ма наЯПкомпиляторпрограммана МЯрезультатПримеры: MASM, Tурбо Паскаль, gcc в UNIX3Система программирования интерпретирующего типаисходныеданныеисходнаяпр-ма на ЯПинтерпретаторрезультатПримеры: QBasic, командные интерпретаторы в UNIX -- bash, csh и др.4Смешаннаястратегияисходныеданныеисходнаяпр-мана ЯПкомпиляторпрограммана промежуточномязыке (ПЯ)интерпретаторрезультатПримеры: 1) язык Javaбайт-кодJVM (Java Virtual Machine)2) Языки на технологии .NET (Basic,C#,C++)промежуточный язык: CIL –Common Intermediate LanguageJIT-компилятор ( just-in-time)5Схема функционирования компилятораисходная программа на ЯПлексический анализпоследовательность лексемсинтаксический анализфазаанализапромежуточное представление программысемантический анализ(+ контроль контекстных условий)подготовка к генерацииобъектного модулягенерация объектного модуляобъектный модульфазасинтеза6Основные понятия теории формальных языковАлфавит:это конечное множество символов.Пример: V = {a,b,c}Цепочка символов в алфавите V :любая конечная последовательность символов этого алфавита.Пример: V = {a,b}.

Цепочка: abbbaПустая цепочка :цепочка, которая не содержит ни одного символа.Обозначение: ε(иногда для этой цели используется символ Λ)Конкатенация (сцепление) цепочек α и β:цепочка, полученная приписыванием последовательности βсправа к αОбозначение: α⋅β (или αβ)Пример: если α = ab и β = cd, тоαβ = abcd.•Для любой цепочки α верно αε = εα = α.(Аналог для чисел: ∀ x верно 1⋅x = x⋅1 = x)•Операция конкатенации ассоциативна: (α⋅β)⋅γ = α⋅(β⋅γ) длялюбых α, β, γ.•Операция конкатенации некоммутативна:например, для α = ab и β = cd α⋅β ≠ β⋅α7Обращение (или реверс) цепочки α:цепочка, символы которой записаны в обратном порядке.Обозначение: αRПример: если α = abcdef, то αR = fedcba.Для пустой цепочки: ε = εR.Рекурсивное определение:αR =ε,если α = ε;βR s, если α = s βR , где s — символ алфавита89n-я степень цепочки α (обозначается αn) :конкатенация n цепочек αα α α … α α = α nn разРекурсивное определение:ε,если n=0;αn =αn-1α, если n>010Длина цепочки :это число составляющих ее символовПример: если α = abcdefg, то длина α равна 7.Обозначение: | α ||ε|=0Рекурсивное определение:0,если α=ε;| α |=| β| +1, если α =  βs, где s — символ алфавитаОбозначение | α |s используется для числа вхождений символa s вцепочку α.11Язык в алфавите V :подмножество цепочек конечной длины в этом алфавите.V* :множество, содержащее все цепочки конечной длины валфавите V, включая пустую цепочку ε.Пример: V = {0,1},V* = {ε, 0, 1, 00, 11, 01, 10, 000, 001, 011, ...}.V+ :множество, содержащее все цепочки конечной длины валфавите V, исключая пустую цепочку ε.•V* = V+ ∪ {ε}•Для любого языка L ⊆ V*12способы описания языковЯвное перечисление:L = {ab, abb,ba, baa}Язык L — конечныйФормулы:L = {an bn | n≥0}Цепочки языка L: ε, ab, aabb, aaabbb, …Порождающие грамматики ХомскогоРаспознаватели (МТ, ЛОА, конечные автоматы, МП-автоматы)Декартово произведение множеств A и B :множество { (a,b) | a ∈ A, b ∈ B}Обозначение: A × BПорождающая грамматика G :это четверка 〈T, N, P, S〉, где•••T – алфавит терминальных символов ( терминалов ),N – алфавит нетерминальных символов (нетерминалов), непересекающийся с T,P – конечное подмножество множества (T ∪ N)+ × (T ∪ N)*;элемент (α, β) множества P называется правилом вывода изаписывается в виде α → β,α содержит хотя бы один нетерминал;S – начальный символ (цель) грамматики, S ∈ N.правилаα → β2 ...

α → βnα → β1записываются сокращенноα → β1 | β2 |...| βnβi для i = 1, 2, ... ,n , - альтернатива правилавывода из цепочки α.1314Порождающая грамматика G :это четверка 〈T, N, P, S〉, где••T – алфавит терминальных символов ( терминалов ),N – алфавит нетерминальных символов (нетерминалов),T∩N=∅,P – конечное подмножество множества (T ∪ N)+ × (T ∪ N)*;элемент (α, β) множества P называется правилом вывода изаписывается в виде α → β,S – начальный символ (цель) грамматики, S ∈ N.••Пример грамматики: G1 = 〈 {0,1}, {A, S}, P, S 〉P:S → 0A10A → 00A1A→ε15Пусть β ∈ (T ∪ N)*α ∈ (T ∪ N)+β непосредственно выводима из αв грамматике G = 〈 T, N, P, S 〉,если α = ξ1γξ2,β = ξ1δξ2,где ξ1, ξ2, δ ∈ (T ∪ N)*, γ ∈ (T ∪ N)+ и γ → δ ∈ P.Обозначение: α → βПример: G1 = 〈 {0,1}, {A, S}, P, S 〉P:S → 0A10A → 00A1A→εЦепочка 00A11 непосредственно выводима из 0A1 вграмматике G1 : 0A1 → 00A11 (по правилу 0A → 00A1)Цепочка β ∈ (T ∪ N)* выводима из цепочки α ∈ (T ∪ N)+в грамматике G = 〈T, N, P, S〉,если существуют цепочки γ0, γ1, ...

, γn (n≥0), такие, чтоα = γ0 → γ1 → ... → γn= β.Обозначение: α ⇒ βВывод длины n :последовательность γ0, γ1, ... , γnЛюбая цепочка выводится сама из себя за 0 шагов: α =γ0= αG1 = 〈 {0,1}, {A, S}, P, S 〉P:S → 0A10A → 00A1A→εS ⇒ 000A111 в G1, т. к.∃ вывод S → 0A1 → 00A11 → 000A111.Длина вывода равна 3.1617Сентенциальная форма в грамматике G = 〈T, N, P, S〉 :α ∈ (T ∪ N)*, для которой S ⇒ αЯзык, порождаемый грамматикой G = 〈T, N, P, S〉 :множество L(G) = {α ∈ T* | S ⇒ α}Грамматика — это не алгоритм, а система правилподстановки, позволяющих строить выводы.18Язык, порождаемый грамматикой G = 〈T, N, P, S〉 :множество L(G) = { α ∈ T* | S ⇒ α }Пример:G1 = 〈 {0,1}, {A,S}, P, S 〉,P:(1) S → 0A1(2) 0A → 00A1(3) A → εL(G) = ?S →(1) 0A1 →(3) 01S →(1) 0A1 →(2) 00A11 →(3) 0011S →(1) 0A1 →(2) 00A11 →(2) 000A111 →(3) 000111…Предположительно:L1 = {0n1n | n>0}19Язык, порождаемый грамматикой G = 〈T, N, P, S〉 :множество L(G) = { α ∈ T* | S ⇒ α }Пример:G1 = 〈 {0,1}, {A,S}, P, S 〉,P:(1) S → 0A1(2) 0A → 00A1(3) A → εПредположительно: L1 = {0n1n | n>0}Требуется доказать:L(G1) = L1:(1) L1 ⊆ L(G1), т.е.

∀ x∈ L1 ⇒ x ∈ L(G1) (индукция по n)(2) L(G1) ⊆ L1 , т.е. ∀ x∈ L(G1) ⇒ x ∈ L1 ( индукция по длиневывода)Эквивалентность грамматик G1 и G2:L(G1) = L(G2)Пример:G1 = 〈 {0,1}, {A,S}, P1, S 〉иG2 = 〈 {0,1}, {S}, P2, S 〉P1: S → 0A1P2 :S → 0S1 | 010A → 00A1A→εL(G1) = L(G2) = {0n1n | n>0}Грамматики G1 и G2 почти эквивалентны,еслиL(G1) ∪ {ε} = L(G2) ∪ {ε}.Пример:G1 = 〈{0,1}, {A,S}, P1, S〉иG2‘= 〈{0,1}, {S}, P2‘, S〉P1: S → 0A1P2 ‘ :S → 0S1 | ε0A → 00A1A→εL(G1)={0n1n | n>0}, а L(G2 ‘) = {0n1n | n≥0}т.е. L(G2 ‘)=L(G1) ∪ {ε}2022Классификация грамматик и языков по Хомскомуграмматики классифицируются по виду их правил выводаЧетыре типа грамматик:тип 0, тип 1, тип 2, тип 3Язык, порождаемый грамматикой типа k (k=0,1,2,3),является языком типа k.23G = 〈 T, N, P, S 〉Тип 0Любая порождающая грамматика является грамматикойтипа 0.На вид правил грамматик этого типа не накладываетсяникаких дополнительных ограничений.Класс языков типа 0 совпадает с классом рекурсивноперечислимых языков (распознаваемых МТ).24Грамматики с ограничениями на вид правил выводаТип 1Грамматика G = 〈 T, N, P, S 〉 называется неукорачивающей,если правая часть каждого правила из P не короче левой части(т.

е. для любого правила α → β ∈ P выполняется неравенство| α | ≤ | β | ).В виде исключения в неукорачивающей грамматикедопускается наличие правила S → ε, при условии, что S(начальный символ) не встречается в правых частях правил.Грамматикой типа 1 будем называть неукорачивающуюграмматику.25Тип 1 в некоторых источниках определяют с помощью такназываемых контекстно-зависимых грамматик.Грамматика G = 〈 T, N, P, S 〉 называется контекстнозависимой (КЗ), если каждое правило из P имеет вид α → β, гдеα = ξ1Aξ2, β = ξ1γξ2, A ∈ N, γ ∈ (T ∪ N )+, ξ1, ξ2 ∈ (T ∪ N)*.В виде исключения в КЗ-грамматике допускается наличиеправила S → ε, при условии, что S (начальный символ) невстречается в правых частях правил.КЗ-грамматика удовлетворяет определению неукорачивающей.Неукорачивающие и КЗ-грамматики определяют один и тот же классязыков.26Тип 2Грамматика G = 〈 T, N, P, S 〉 называется контекстносвободной (КС), если каждое правило из Р имеет вид A → β, гдеA ∈ N, β ∈ ( T ∪ N ) *.В КС-грамматикахправыми частями.допускаютсяправиласпустымиЯзык, порождаемый контекстно-свободной грамматикой,называется контекстно-свободным языком.Грамматикой типа 2 будем называть контекстно-свободнуюграмматику.27Любую КС-грамматику можно преобразовать в эквивалентнуюнеукорачивающую КС-грамматику.

(т.е. КС, удовлетворяющуютакже и определению неукорачивающей)Тип 3Грамматика G = 〈 T, N, P, S 〉 называется праволинейной,если каждое правило из Р имеет вид A → wB либо A → w,где A ∈ N, B ∈ N, w ∈ T *.Грамматика G = 〈 T, N, P, S 〉 называется леволинейной, есликаждое правило из Р имеет вид A → Bw либо A → w, где A ∈ N,B ∈ N, w ∈ T *.28Праволинейные и леволинейные грамматики определяютодин и тот же класс языков.

Такие языки называютсярегулярными.Право- и леволинейные грамматики тоженазывают регулярными.29Регулярная грамматика является грамматикой типа 3.Автоматной грамматикой называется праволинейная(леволинейная) грамматика, такая, что каждое правило снепустой правой частью имеет вид: A → a либо A → aB (длялеволинейной, соответственно, A → a либо A → Ba), где A ∈ N,B ∈ N, a ∈ T.Для любой регулярной (автоматной) грамматики Gсуществуетнеукорачивающаярегулярная(автоматная)грамматика G′, такая что L(G) = L(G′).30Иерархия ХомскогоСправедливы следующие соотношения:1) любая регулярная грамматика является КС-грамматикой;2) любая неукорачивающая КС-грамматика является КЗграмматикой;3)любаянеукорачивающаяграмматикаявляетсяграмматикой типа 0.Неукорачивающие Регулярные ⊂ Неукорачивающие КС ⊂ КЗ ⊂ Тип 0(Запись A ⊂ B означает, что A является собственным подклассом класса B)31Справедливы следующие соотношения для языков:ƒ каждый регулярный язык является КС-языком, носуществуют КС-языки, которые не являются регулярными,например:L = {an bn | n > 0};ƒ каждый КС-язык является КЗ-языком, но существуют КЗязыки, которые не являются КС-языками, например:L = {an bncn | n > 0};ƒ каждый КЗ-язык является языком типа 0 (т.

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

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

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