Материалы (1) (Материалы к лекциям)

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Пустая цепочка :цепочка, которая не содержит ни одного символа.Обозначение: (иногда для этой цели используется символ )7Конкатенация (сцепление) цепочек  и :цепочка, полученная приписыванием последовательности справа к Обозначение:  (или )Пример: если  = ab и  = cd, то = abcd.•Для любой цепочки  верно  =  = .(Аналог для чисел:  x верно 1x = x1 = x)•Операция конкатенации ассоциативна: () = () длялюбых , , .•Операция конкатенации некоммутативна:например, для  = ab и  = cd   Обращение (или реверс) цепочки :цепочка, символы которой записаны в обратном порядке.Обозначение: RПример: если  = abcdef, то R = fedcba.Для пустой цепочки:  = R.Рекурсивное определение:,если  = ;R =R s, если  = s  , где 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.правила  1  2 ...

  nзаписываются сокращенно  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)  {}2021G1 = ( {0,1}, {A,S}, P1, S )P1: S  0A10A  00A1AРассмотримG3 = ( {0,1}, {S}, P, S ), где P:(1) S  0S(2) S  1S(3) S  Любая цепочка вида 0n1n порождается следующим способом:-- n раз применить правило (1), затем-- n раз применить правило (2)-- и на последнем шаге применить правило (3).Однако L(G3) L(G1),т.к. S  1S  10S  10  L(G3),10  L(G1).