Задача описания входного языка. (Лекция 2) - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Задача описания входного языка. (Лекция 2), слайд №1

Задача описания входного языка. (Лекция 2), слайд №2

Задача описания входного языка. (Лекция 2), слайд №3

Задача описания входного языка. (Лекция 2), слайд №4

Задача описания входного языка. (Лекция 2), слайд №5

Задача описания входного языка. (Лекция 2), слайд №6

Задача описания входного языка. (Лекция 2), слайд №7

Задача описания входного языка. (Лекция 2), слайд №8

Задача описания входного языка. (Лекция 2), слайд №9

Задача описания входного языка. (Лекция 2), слайд №10

Задача описания входного языка. (Лекция 2), слайд №11

Задача описания входного языка. (Лекция 2), слайд №12

Задача описания входного языка. (Лекция 2), слайд №13

Задача описания входного языка. (Лекция 2), слайд №14

Задача описания входного языка. (Лекция 2), слайд №15

Задача описания входного языка. (Лекция 2), слайд №16

Задача описания входного языка. (Лекция 2), слайд №17

Задача описания входного языка. (Лекция 2), слайд №18

Задача описания входного языка. (Лекция 2), слайд №19

Задача описания входного языка. (Лекция 2), слайд №20

Задача описания входного языка. (Лекция 2), слайд №21

Задача описания входного языка. (Лекция 2), слайд №22

Задача описания входного языка. (Лекция 2), слайд №23

Задача описания входного языка. (Лекция 2), слайд №24

Задача описания входного языка. (Лекция 2), слайд №25

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Задача описания входного языка. (Лекция 2). Доклад-сообщение содержит 25 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Лекция 02. Задача описания входного языка

Слайд 2

Описание слайда:

Основной аппарат Формальные языки и грамматики математические модели, использующие представление текстов в виде цепочек символов

Слайд 3

Описание слайда:

Замечания (1) Для описания языков программирования используются контекстно-свободные грамматики (КСГ). КСГ – мощный аппарат, но не может определить все возможные языки. Эффективны для описания вложенных структур, например, скобок и блоков в языках программирования.

Слайд 4

Описание слайда:

Замечания (2) Основная идея заключается в использовании «переменных» для определения «множеств» цепочек символов. Эти переменные определены рекурсивно (с помощь рекурсивных «правил вывода»). Рекурсивные правила для переменной («продукции") включают в себя только конкатенацию. Альтернативные правила для переменной позволяют объединять цепочки.

Слайд 5

Описание слайда:

Основные определения (1) Алфавит Определение: алфавит - это конечное множество символов. Например, алфавит A = {a, b, c, +, !} содержит 5 букв, а алфавит B = {00, 01, 10, 11} содержит 4 буквы, каждая из которых состоит из двух символов. Определение: цепочкой символов в алфавите V называется любая конечная последовательность символов этого алфавита. Определение: цепочка, которая не содержит ни одного символа, называется пустой цепочкой. Для ее обозначения будем использовать символ .

Слайд 6

Описание слайда:

Основные определения (2) Операции над цепочками Определение: если a и b - цепочки, то цепочка ab называется конкатенацией (или сцеплением) цепочек a и b. Например, если a = ab и b = cd, то ab = abcd. Для любой цепочки a всегда a = a = a. Определение: обращением (или реверсом) цепочки a называется цепочка, символы которой записаны в обратном порядке. Обращение цепочки a будем обозначать aR. Например, если a = abcdef, то aR = fedcba. Для пустой цепочки:  = R. Определение: n-ой степенью цепочки a (будем обозначать an) называется конкатенация n цепочек a. a0 = ; an = aan-1 = an-1a. Определение: длина цепочки - это число составляющих ее символов.

Слайд 7

Описание слайда:

Основные определения (3) Язык. Итерация Определение: язык в алфавите V - это подмножество цепочек конечной длины в этом алфавите. Определение: обозначим через V* множество, содержащее все цепочки в алфавите V, включая пустую цепочку . Например, если V={0,1}, то V* = {, 0, 1, 00, 11, 01, 10, 000, 001, 011, ...}. Определение: обозначим через V+ множество, содержащее все цепочки в алфавите V, исключая пустую цепочку . Следовательно, V* = V+  {}. Определение: декартовым произведением A × B множеств A и B называется множество {(a,b) | a  A, b  B}.

Слайд 8

Описание слайда:

Порождающая грамматика Определение: порождающая грамматика G - это четверка (VT, VN, P, S), где VT - алфавит терминальных символов (терминалов), VN - алфавит нетерминальных символов (нетерминалов, «переменных»), не пересекающийся с VT, P - конечное подмножество множества (VT  VN)+  (VT  VN)*; элемент (, ) множества P называется правилом вывода и записывается в виде   , S - начальный символ (цель, аксиома) грамматики, S  VN. Для записи правил вывода с одинаковыми левыми частями   1,    2, ...,    n будем пользоваться сокращенной записью    1 |  2 |...|  n. Каждое  i , i= 1, 2, ... ,n , будем называть альтернативой правила вывода из цепочки .

Слайд 9

Описание слайда:

Порождающая грамматика Пример грамматики: G1 = ({0,1}, {A,S}, P, S), VT = {0,1} VN = {A,S} P состоит из правил S  0A1 0A  00A1 A  

Слайд 10

Описание слайда:

Основные определения (4) Выводимость. Выводы Определение: цепочка   (VT  VN)* непосредственно выводима из цепочки   (VT  VN)+ в грамматике G = (VT, VN, P, S) (обозначим   ), если  = 12,  = 12, где 1, 2,   (VT  VN)*,   (VT  VN)+ и правило вывода    содержится в P. Например, цепочка 00A11 непосредственно выводима из 0A1 в G1. Определение: цепочка   (VT  VN)* выводима из цепочки   (VT  VN)+ в грамматике G = (VT, VN, P, S) (обозначим   ), если существуют цепочки 0, 1, ... , n (n ≥ 0), такие, что  = 0  1  ...  n= . Определение: последовательность 0, 1, ... , n называется выводом длины n. Например, S  000A111 в грамматике G1 (см. пример выше), т.к. существует вывод S  0A1  00A11  000A111. Длина вывода равна 3.

Слайд 11

Описание слайда:

Непосредственная выводимость Мы говорим, что A   (из A выводимо ), если A   правило грамматики. Пример: S  01; S  0S1. S  0S1  00S11  000111.

Слайд 12

Описание слайда:

Выводимость  означает “выводится за ноль или более шагов” Базис:    для самой цепочки . Индукция: если    и   , то   .

Слайд 13

Описание слайда:

Выводимость. Пример Пусть S  01; S  0S1 – правила грамматики. S  0S1  00S11  000111 – вывод в грамматике. Тогда S  S S  0S1 S  00S11 S  000111

Слайд 14

Описание слайда:

Пример: CFG для { 0n1n | n > 1} Правила: S -> 01 S -> 0S1 Базис (основа): цепочка 01 принадлежит языку. Индукция: если w принадлежит языку, то и 0w1 принадлежит языку.

Слайд 15

Описание слайда:

Основые определения (5) Язык. Сентенциальные формы Определение: языком, порождаемым грамматикой G = (VT, VN, P, S), называется множество L(G)={  VT* | S  }. Другими словами, L(G) - это все цепочки в алфавите VT, которые выводимы из S с помощью P. Например, L(G1) = {0n1n | n>0}. Определение: цепочка a  (VT  VN)*, для которой S  , называется сентенциальной формой в грамматике G = (VT, VN, P, S). Таким образом, язык, порождаемый грамматикой, можно определить как множество терминальных сентенциальных форм.

Слайд 16

Описание слайда:

Основные определения (6) Эквивалентные грамматики Определение: грамматики G1 и G2 называются эквивалентными, если L(G1) = L(G2). Например, G1 = ({0,1}, {A,S}, P1, S) и G2 = ({0,1}, {S}, P2, S), где P1: S  0A1 P2: S  0S1 | 01 0A  00A1 A   эквивалентны, т.к. обе порождают язык L(G1) = L(G2) = {0n1n | n>0}. Определение: грамматики G1 и G2 почти эквивалентны, если L(G1)  {} = L(G2)  {}.

Слайд 17

Описание слайда:

Классификация грамматик и языков по Хомскому ТИП 0: Грамматика G = (VT, VN, P, S) называется грамматикой типа 0, если на правила вывода не накладывается никаких ограничений (кроме тех, которые указаны в определении грамматики). ТИП 1: Грамматика G = (VT, VN, P, S) называется неукорачивающей грамматикой, если каждое правило из P имеет вид   , где   (VT  VN)+,   (VT  VN)+ и |  |  |  |. Грамматика G = (VT, VN, P, S) называется контекстно-зависимой (КЗ), если каждое правило из P имеет вид   , где  = 1A2;  = 12; A  VN;   (VT  VN)+; 1,2  (VT  VN)*.

Слайд 18

Описание слайда:

Классификация грамматик и языков по Хомскому ТИП 2: Грамматика G = (VT, VN, P, S) называется контекстно-свободной (КС), если каждое правило из Р имеет вид A  , где A  VN,   (VT  VN)+. Грамматика G = (VT, VN, P, S) называется укорачивающей контекстно-свободной (УКС), если каждое правило из Р имеет вид A  , где A  VN,   (VT  VN)*. ТИП 3: Грамматика G = (VT, VN, P, S) называется праволинейной, если каждое правило из Р имеет вид A  tB либо A  t, где A  VN, B  VN, t  VT. Грамматика G = (VT, VN, P, S) называется леволинейной, если каждое правило из Р имеет вид A  Bt либо A  t, где A  VN, B  VN, t  VT.

Слайд 19

Описание слайда:

Соотношения между типами грамматик любая регулярная грамматика является КС-грамматикой; любая регулярная грамматика является УКС-грамматикой; любая КС-грамматика является КЗ-грамматикой; любая КС-грамматика является неукорачивающей грамматикой; любая КЗ-грамматика является грамматикой типа 0. любая неукорачивающая грамматика является грамматикой типа 0. Замечание: УКС-грамматика, содержащая правила вида A  , не является КЗ-грамматикой и не является неукорачивающей грамматикой

Слайд 20

Описание слайда:

Соотношения между типами языков каждый регулярный язык является КС-языком, но существуют КС-языки, которые не являются регулярными (например, L = {anbn | n>0}). каждый КС-язык является КЗ-языком, но существуют КЗ-языки, которые не являются КС-языками (например, L = {anbncn | n>0}). каждый КЗ-язык является языком типа 0. Например, КЗ-грамматика G1 = ({0,1}, {A,S}, P1, S) и КС-грамматика G2 = ({0,1}, {S}, P2, S), где P1: S  0A1 P2: S  0S1 | 01 0A  00A1 A   описывают один и тот же язык L = L(G1) = L(G2) = { 0n1n | n>0}. Язык L будет КС-языком,