Программирование
<<  Карельский детский фольклор Введение в разработку под Kinect  >>
Разработка SQL компилятора для СУБД «ОМЕГА»
Разработка SQL компилятора для СУБД «ОМЕГА»
Постановка задачи
Постановка задачи
Общая структура компилятора
Общая структура компилятора
Основные компоненты SQL компилятора лексический анализатор –
Основные компоненты SQL компилятора лексический анализатор –
Лексический анализатор
Лексический анализатор
Лексический анализатор строиться на основе детерминированного
Лексический анализатор строиться на основе детерминированного
Матрица состояний ДКА
Матрица состояний ДКА
Основные прототипы процедур, необходимых для работы ЛА:
Основные прототипы процедур, необходимых для работы ЛА:
Синтаксический анализатор
Синтаксический анализатор
Грамматика языка SQL
Грамматика языка SQL
Реализация синтаксического разбора
Реализация синтаксического разбора
Прототипы основных функций, реализующих семантический анализ
Прототипы основных функций, реализующих семантический анализ
Препроцессор
Препроцессор
Прототипы основных функций, реализующих работу препроцессора
Прототипы основных функций, реализующих работу препроцессора
Генератор логического плана
Генератор логического плана
Пример
Пример
Прототипы функций, реализующих генерацию логического плана запроса
Прототипы функций, реализующих генерацию логического плана запроса

Презентация: «Разработка SQL компилятора для СУБД «ОМЕГА»». Автор: 1. Файл: «Разработка SQL компилятора для СУБД «ОМЕГА».ppt». Размер zip-архива: 259 КБ.

Разработка SQL компилятора для СУБД «ОМЕГА»

содержание презентации «Разработка SQL компилятора для СУБД «ОМЕГА».ppt»
СлайдТекст
1 Разработка SQL компилятора для СУБД «ОМЕГА»

Разработка SQL компилятора для СУБД «ОМЕГА»

Докладчик Губин Максим Владимирович Научный руководитель Соколинский Леонид Борисович

Челябинск 2006 г.

1

2 Постановка задачи

Постановка задачи

Разработка SQL компилятора СУБД «ОМЕГА» Под компилятором будем понимать программу, которая преобразует цепочку входных символов, введенных пользователем, в дерево физических операций над данными СУБД «ОМЕГА». В работе можно выделить два направления: разработка компилятора, который на входе принимает некоторую строку запроса в терминах подмножества языка SQL, на выходе имеет физический план выполнения запроса SQL; определение языка SQL', который является некоторым подмножеством языка SQL (точнее, можно предположить, что язык SQL' имеет ряд дополнительных ограничений наложенных на язык SQL).

Челябинск 2006 г.

2

3 Общая структура компилятора

Общая структура компилятора

Челябинск 2006 г.

3

4 Основные компоненты SQL компилятора лексический анализатор –

Основные компоненты SQL компилятора лексический анализатор –

предназначен для выделения лексем из цепочки символов запроса, проверки их принадлежности одному из классов лексем и передачи их синтаксическому анализатору; синтаксический анализатор – предназначен для распознавания синтаксической структуры из представленных лексических композиций, и представления этой структуры в виде дерева разбора или синтаксического дерева; препроцессор – предназначен для контроля употребления имен отношений, имен атрибутов и типов самих атрибутов; генератор логического плана – предназначен для преобразования дерева разбора в логический план выполнения запроса с использованием набора операций реляционной алгебры; генератор физического плана выполнения запроса – формирует физический план исполнения запроса в известных физических операциях.

Челябинск 2006 г.

4

5 Лексический анализатор

Лексический анализатор

На входе лексического анализатора (ЛА) имеется цепочка символов некоторого алфавита. Алфавит может содержать следующие символы: английский алфавит – {A,B,C…Z,a,b,c…z}; арабские числа – {0,1,2,3..9}; разделители – {_, ’, ., ;}; операторы отношений – {=,<,>,*}. На выходе ЛА содержаться лексемы. Определим основные классы лексем: константа (например: 1 или 1.55); идентификатор (перем1 или атрибут2); строка (представляет произвольный набор символов ограниченный кавычкой «‘»); оператор «*»; точка «.»; запятая «,»; точка запятая «;»; пробел «_»; оператор отношения «=», «>», «<».

Челябинск 2006 г.

5

6 Лексический анализатор строиться на основе детерминированного

Лексический анализатор строиться на основе детерминированного

конечного автомата ДКА=(Q,V, ?,q0,F) , где Q – конечное множество состояний автомата; V – конечное множество допустимых входных символов; ? – функция переходов; q0 – начальное состояние автомата, q?Q; F – множество конечных состояний автомата, F?Q.

Детерминированный конечный автомат

Челябинск 2006 г.

6

7 Матрица состояний ДКА

Матрица состояний ДКА

Челябинск 2006 г.

7

ST

ST

ST

ST

ST

ST

ST

ST

ST

ST

ST

ST

ST

ST

ST

ST

CL - Классы символов

CL - Классы символов

CL - Классы символов

CL - Классы символов

CL - Классы символов

CL - Классы символов

CL - Классы символов

CL - Классы символов

CL - Классы символов

CL - Классы символов

CL - Классы символов

CL - Классы символов

CL - Классы символов

«’»

«*»

«/»

«.»

«,»

«;»

«=», «<», «>»

Начальное сост. Авт. Q0

Цифры

Буквы

Пробел

Другой

1

2

3

4

5

6

7

8

9

11

12

0

2

1

3

-4

-5

-6

-7

-8

-9

-11

-13

ident

1

1

1

-11

-1

-1

-1

-1

-1

-1

10

-1

constanta

2

2

1

-11

-2

-2

2

-2

-2

-2

10

-2

string

3

3

3

-3

3

3

3

3

3

3

3

3

multiply

4

2

1

3

-4

-5

-6

-11

-8

-9

10

-11

div

5

2

1

-11

-11

-11

-11

-11

-8

-11

10

-11

point

6

-11

1

-11

-11

-11

-11

-11

-11

-11

10

-11

comma

7

2

-11

-11

-11

-11

-11

-11

-8

-11

10

-11

spase

8

2

1

3

-4

-5

-6

-7

-8

-9

10

-13

point comma

9

-11

-11

-11

-11

-11

-11

-11

-8

-11

-11

-11

other

11

10

10

10

10

10

-6

-7

-8

-9

10

-11

error

12

-11

-11

-11

-11

-11

-11

-11

-11

-11

-11

-11

is

13

2

1

3

-11

-11

-11

-11

-8

-11

-11

-13

8 Основные прототипы процедур, необходимых для работы ЛА:

Основные прототипы процедур, необходимых для работы ЛА:

int D[13][12] //матрица состояний КА char *out[]= //классы лексем {"ident","constant","string","multiply","div","point","comma","spase","point comma","other","error","is" }; struct tabLexAn{ //структура таблицы лексем int id; //порядковый номер лексемы char name[]; //имя лексемы(содержание) char *type;} //тип лексемы void LexAn() //функция выполнения лексического анализа

Челябинск 2006 г.

8

9 Синтаксический анализатор

Синтаксический анализатор

Задача синтаксического анализатора состоит в преобразовании последовательности лексем в дерево разбора (синтаксическое дерево). Каждая вершина дерева разбора представляет одну из следующих сущностей: атомы – лексические единицы, такие как служебные слова (например, SELECT), наименования атрибутов или отношений, константы, скобки операторы и иные элементы; синтаксические конструкции – группа лексем объединенных в конструкцию по некоторому устойчивому смыслу над этой группой (например, <SFW> это такая синтаксическая конструкция как <select–from–where>).

Челябинск 2006 г.

9

10 Грамматика языка SQL

Грамматика языка SQL

При синтаксическом анализе проверяется цепочка распознанных лексем на принадлежность множеству цепочек, порождаемых грамматикой языка SQL?. Пример правил грамматики языка SQL? для синтаксической конструкции <select-from-where>: <SFW>:=Select <ListAtribute> From <ListForm> Where <ListCondition>; <ListAtribute>:=<Atribute>?<Atribute>,<Atribute> <Atribute>:=<Identifier>?<Identifier>.<Form> <ListForm>:=<Form>?<Form>,<Form> <Form>:=<Identifier> <ListCondition>:=<Condition>?(<Condition>) And (<Condition>) <Condition>:=<Atribute>=<Identifier>?<Atribute>=<Atribute> <Identifier>:=ident?*

Челябинск 2006 г.

10

11 Реализация синтаксического разбора

Реализация синтаксического разбора

При анализе цепочки лексем используется нисходящий метод разбора слева направо, т.е . Разбор осуществляется автоматом с магазинной памятью (МП-автомат) R=(Q,V,Z,?,q0,z0,F), где Q – конечное множество состояний автомата; V – алфавит входных символов; Z – алфавит магазинных символов автомата V?Z, ? – функция переходов; q0 – начальное состояние автомата, q?Q; z0 – начальный символ автомата, z?Z; F – множество конечных состояний автомата, F?Q. Конфигурацию МП-автомата можно описать в виде тройки (q,?,?) ?Q?V*?Z*, которая определяет состояние автомата q, цепочку еще не прочитанных символов ? на входе автомата и содержание магазина (стека) ?. Начальная конфигурация определяется (q0,?,z0), ??V*, множество конечных состояний автомата – (q,?,?), q?F, ??Z*. МП-автомат допускает цепочку символов с опустошением магазина, если при окончании разбора цепочки автомат находится в одном из конечных состояний, а стек автомата пуст.

Челябинск 2006 г.

11

12 Прототипы основных функций, реализующих семантический анализ

Прототипы основных функций, реализующих семантический анализ

stack stack_SemAn //организация стека для МП-автомата tree tree_sinAn //дерево синтаксического разбора char *terminal[] //список терминалов char *neterminal[] //список нетерминалов char *first[][] //множество fist char *follow[][] //множество follow struct Gram{ //структура правил грамматики int id; char Rul[][];} int M[][] //таблица состояний предикативного //синтаксического разбора int GetRul() //процедура чтения правил из внешнего файла int spisokTerminalov() //определение списка терминалов из правил int spisokNeTerminalov() //определение списка нетерминалов из правил int oprTerm() //определение терминалов в лексемах void FindFirst() //определяем множество FIRST () int FOLLOW() //определяем множество FOLLOW() int TablRazbora() //создание таблицы синтаксического разбора int SinAn() //синтаксический анализ

Челябинск 2006 г.

12

13 Препроцессор

Препроцессор

Для определения действительности синтаксического дерева разбора, необходимо выполнить контроль его следующих параметров: контроль употребления имен отношений, который определяет существование отношения, зарегистрированного в текущей схеме данных; контроль использования имен атрибутов и их разрешение, который определяет существование каждого атрибута и его принадлежность одному из отношений заявленных в синтаксическом дереве; контроль типов, который проверяет способ использования каждого атрибута на соответствие типу атрибута. При возникновении ошибки на любом из параметров контроля, формируется код ошибки и передается управление системе обработки ошибок. Например, препроцессор может обнаружить использование атрибута с одинаковым именем в двух отношениях, используемых при выборе в одном запросе.

Челябинск 2006 г.

13

14 Прототипы основных функций, реализующих работу препроцессора

Прототипы основных функций, реализующих работу препроцессора

Int existtable(char* name) //проверяем наличие таблицы int existatribut(char* name) //проверяем наличие атрибута int truetype() //проверяем соответствие типа

Челябинск 2006 г.

14

15 Генератор логического плана

Генератор логического плана

Генератор логического плана предназначен для преобразования дерева разбора в логический план выполнения запроса с использованием набора операций реляционной алгебры. Для примера преобразования синтаксического дерева разбора в логический план запроса, представленным выражениями реляционной алгебры, рассмотрим синтаксическую конструкцию <SFW>. Эта конструкция состоит из трех реляционных операций: - декартова произведения ? всех отношений из списка <FromList>; - оператора выбора ?C из условия <Condition>; - оператора проекции ?L соответствующего списку <AtributList>.

Челябинск 2006 г.

15

16 Пример

Пример

Если на входе мы имеем следующий подзапрос: Select Atr1, Atr2 From From1, Form2 Where Atr1=Atr2, то выражение реляционной алгебры имеет вид:

Челябинск 2006 г.

16

17 Прототипы функций, реализующих генерацию логического плана запроса

Прототипы функций, реализующих генерацию логического плана запроса

Tree tree_logplan //определение дерева логического плана char param[][] //определение дополнительных параметров void create_logplan() //функция генерации логического плана

«Разработка SQL компилятора для СУБД «ОМЕГА»»
http://900igr.net/prezentacija/informatika/razrabotka-sql-kompiljatora-dlja-subd-omega-139241.html
cсылка на страницу
Урок

Информатика

130 тем
Слайды
900igr.net > Презентации по информатике > Программирование > Разработка SQL компилятора для СУБД «ОМЕГА»