М.Ю. Харламов, ВНУ им. В.Даля, 2009

Алфавит (словарь) V Алфавит (словарь) V– это непустое конечное множество элементов (символов) Цепочка в алфавите V Цепочка в алфавите V - любая упорядоченная строчка конечно длины, составленная из символов алфавита V важен порядок и количество символов e e – пустая цепочка xyz Для цепочки xyz x – префикс цепочки z – суффикс цепочки x, y, z – подцепочки e – может быть суффиксом, префиксом и подцепочкой Тема 2. Элементы теории языков Цепочка: abbba Префиксы: L 1 = {е,а,аb,abb,abbb, abbba} Суффиксы: L 2 = {e, а, be,bbe, bbbe, abbbe} Подцепочки: L 1 L 2 Цепочка: abbba Префиксы: L 1 = {е,а,аb,abb,abbb, abbba} Суффиксы: L 2 = {e, а, be,bbe, bbbe, abbbe} Подцепочки: L 1 L 2

Операции над цепочками: Операции над цепочками: Длина цепочки |w| - число символов в ней |abababa| = 7; |е| = 0 Конкатенация (объединение) - дописывание 2 ой цепочки в конец 1 ой: Обращение цепочки запись символов цепочки в обратном порядке: R Итерация (повторение) цепочки n, где n N, n > 0 это конкатенация цепочки самой с собой n раз α 0 =e, α 1 = α, α 2 = αα, α 3 = ααα… Тема 2. Элементы теории языков Свойства пустой цепочки 1.|e|=0 2. : e = e= 3. e R =e 4. n>0: e n =e 5. : 0 =e Свойства пустой цепочки 1.|e|=0 2. : e = e= 3. e R =e 4. n>0: e n =e 5. : 0 =e

L(V) Язык L в алфавите 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) и L(V) L'(V) L'(V) L(V)L'(V) {e}=L(V) {e} Два языка L(V) и L'(V) почти эквивалентны - L'(V) L(V), если L'(V) {e}=L(V) {e} Тема 2. Элементы теории языков

Основные операции над языками: Конкатенацией языков L 1 и L 2 называется язык L 1 L 2 ={xy, x L 1, y L 2 } L * - множество всех цепочек над алфавитом V без e L + - множество всех цепочек над алфавитом V, включая e Тема 2. Элементы теории языков Пусть L 1 = {а, bb) и L 2 = {е, а, bb}. Тогда L 1 L 2 = {aa, bb, aaa, bbe, aabb, bbbb} Пусть L 1 = {а, bb) и L 2 = {е, а, bb}. Тогда L 1 L 2 = {aa, bb, aaa, bbe, aabb, bbbb}

1. перечислением всех допустимых цепочек языка 2. указанием способа порождения цепочек языка (заданием грамматики языка) 3. определением метода распознавания цепочек языка (распознаватель) Тема 2. Элементы теории языков

Синтаксис языка набор правил, определяющий допустимые конструкции языка определяет «форму языка» задает набор цепочек символов, которые принадлежат языку Чаще всего синтаксис можно задать в виде строгого набора правил Семантика языка раздел языка, определяющий значение предложений языка определяет «содержание языка» задает смысл для всех допустимых цепочек языка обычно определяется неформальными методами Лексика это совокупность слов (словарный запас) языка Тема 2. Элементы теории языков

Грамматика Грамматика - это описание способа построения предложений некоторого языка Грамматика определяется как: VT VT множество (алфавит) терминальных символов; VN VN множество нетерминальных символов (служат для порождения слов языка) P P – правила (продукции) - упорядоченная пара цепочек символов (α,β), описывающая процесс порождения цепочек языка: α β S S целевой (начальный) символ грамматики: S VN Тема 2. Элементы теории языков G(VT, VN, P, S)

эквивалентными Различные грамматики могут порождать один и тот же язык. Такие грамматики называются эквивалентными Левые части правил могут содержать другие не терминалы (помимо определяемого) | По соглашению, можно объединять несколько правил с одинаковой левой частью, записывая правые части через символ '|' ("или") - форма Бэкуса Наура Тема 2. Элементы теории языков

Рекурсия в правилах грамматики выражается в том, что один из нетерминальных символов определяется сам через себя непосредственная (явная) - когда символ определяется сам через себя в одном правиле косвенная (неявная) когда то же самое происходит через цепочку правил Тема 2. Элементы теории языков G({0,1,2,3,4,5,6,7,8,9,-,+},{,, },Р, ) Р: «число> | + | - «чс> | «цифра> 0|1|2|3|4|5|6|7|6|9 G({0,1,2,3,4,5,6,7,8,9,-,+},{,, },Р, ) Р: «число> | + | - «чс> | «цифра> 0|1|2|3|4|5|6|7|6|9 G({0,1,2,3,4,5,6,7,8,9,-,+},{S,T,F},Р,S) Р: S T | +T | -T T F |TF F 0|1|2|3|4|5|6|7|6|9 G({0,1,2,3,4,5,6,7,8,9,-,+},{S,T,F},Р,S) Р: S T | +T | -T T F |TF F 0|1|2|3|4|5|6|7|6|9

( ) ( ) - из всех перечисленных внутри скобок цепочек символов в данном месте правила грамматики может стоять только 1 [ ] [ ] - указанная в [] цепочка может встречаться, а может и не встречаться в данном месте правила грамматики { } { } - указанная внутри {} цепочка может не встречаться в данном месте правила грамматики ни одного раза, встречаться один раз или сколь угодно много раз,, – для разделения цепочек грамматики – для включения метасимволов в цепочку Тема 2. Элементы теории языков 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,-,+},{,, },Р, ) Р: [(+.->)] { } 0|1|2|3|4|5|6|7|8|9

Тема 2. Элементы теории языков + - Цифра Число Терминальные символы Нетерминальные символы Точки входа и выхода Узловые точки

Распознаватель Распознаватель (разборщик) специальный автомат, который позволяет определить принадлежность цепочки символов некоторому языку Тема 2. Элементы теории языков a1a1 a2a2 anan … Входная цепочка символов УУ Рабочая (внешняя) память

Операции распознавателя: чтение очередного символа из входной цепочки сдвиг входной цепочки на заданное количество символов (вправо или влево) доступ к рабочей памяти для чтения или записи информации преобразование информации в памяти УУ, изменение состояния УУ Конфигурация распознавателя определяется: содержимым входной цепочки символов и положением считывающей головки в ней состоянием УУ содержимым внешней памяти Тема 2. Элементы теории языков

Задача разбора заключается в следующем: на основе имеющейся грамматики некоторого языка построить распознаватель для этого языка В отношении исходной программы компилятор выступает как распознаватель человек, созвавший программу, - генератор цепочек этого языка При создании компилятора для некоторого языка программирования необходимо связать Грамматики и Распознаватели – как 2 независимых метода, кот. могут быть использованы для определения какого-либо языка Тема 2. Элементы теории языков

Выводом Выводом называется процесс порождения предложения языка на основе правил определяющей язык грамматики Цепочка = 1 2 называется непосредственно выводимой из цепочки = 1 2 в грамматике G(VT,VN,P,S), V = VT VN, 1,, 2 V*, V +, если в G существует правило P Цепочка β называется выводимой из цепочки α если β непосредственно выводима из α γ такая, что γ выводима из α и β непосредственно выводима из γ цепочкой вывода Такая последовательность называется выводом, или цепочкой вывода Тема 2. Элементы теории языков

G({0,1,2,3,4,5,6,7,8,9,-,+},{S,T,F},Р,S) Р: S T | +T | -T T F |TF F 0|1|2|3|4|5|6|7|6|9 G({0,1,2,3,4,5,6,7,8,9,-,+},{S,T,F},Р,S) Р: S T | +T | -T T F |TF F 0|1|2|3|4|5|6|7|6|9 1. S -Т -TF -TFF -FFF -4FF -47F S Т TF Т8 F Т TF Т0 TF0 Т50 F TFT TFFT TFFF FFFF 1FFF 1FF4 10F F 5 1. S -Т -TF -TFF -FFF -4FF -47F S Т TF Т8 F Т TF Т0 TF0 Т50 F TFT TFFT TFFF FFFF 1FFF 1FF4 10F F 5 Грамматика для целых десятичных чисел со знаком: Произвольные цепочки вывода: Итоговые выводы: 1. S * -479 или S или S S * 18 или S + 18 или S Т * 350 или Т или Т TFT * 1004 или TFT или TFT F * 5 или F 1 5 (утверждение F + 5 неверно) 1. S * -479 или S или S S * 18 или S + 18 или S Т * 350 или Т или Т TFT * 1004 или TFT или TFT F * 5 или F 1 5 (утверждение F + 5 неверно) Конечные цепочки Левосторонний вывод Правосторонний вывод

Дерево вывода Дерево вывода грамматики G - граф, соответствующий некоторой цепочке вывода Тема 2. Элементы теории языков S -T TF FT F7 4 9 S TF F8 1 Построение дерева сверху вниз (как правило левосторонний вывод) Построение дерева снизу вверх (как правило правосторонний вывод)