Челябинск 2006 г. 1 Разработка SQL компилятора для СУБД «ОМЕГА» Докладчик Губин Максим Владимирович Научный руководитель Соколинский Леонид Борисович

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

Челябинск 2006 г.3 Общая структура компилятора Лексический анализатор Синтаксический и семантический анализатор Генератор логического плана Генератор физического плана Система анализа ошибок Цепочка символов запроса Таблицы лексем Дерево разбора Логический план запроса в терминах реляционной алгебры Препроцессор

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

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

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

Челябинск 2006 г.7 ST CL - Классы символов ЦифрыБуквы « »«*»«*»«/»«/»«.»«.»«,»«,» пробел «;»«;» другой «=»,«»«=»,«» начальное сост. авт. q ident constanta string multiply div point comma spase point comma other error12-11 is Матрица состояний ДКА

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

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

Челябинск 2006 г. 10 Грамматика языка SQL Грамматика языка SQL При синтаксическом анализе проверяется цепочка распознанных лексем на принадлежность множеству цепочек, порождаемых грамматикой языка SQL. Пример правил грамматики языка SQL для синтаксической конструкции : :=Select From Where ; :=Select From Where ; :=, :=, :=. :=. :=, :=, := := ( ) And ( ) := ( ) And ( ) := = = := = = :=ident * :=ident *

Челябинск 2006 г. 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 г.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 г.13 Препроцессор Для определения действительности синтаксического дерева разбора, необходимо выполнить контроль его следующих параметров: контроль употребления имен отношений, который определяет существование отношения, зарегистрированного в текущей схеме данных; контроль употребления имен отношений, который определяет существование отношения, зарегистрированного в текущей схеме данных; контроль использования имен атрибутов и их разрешение, который определяет существование каждого атрибута и его принадлежность одному из отношений заявленных в синтаксическом дереве; контроль использования имен атрибутов и их разрешение, который определяет существование каждого атрибута и его принадлежность одному из отношений заявленных в синтаксическом дереве; контроль типов, который проверяет способ использования каждого атрибута на соответствие типу атрибута. контроль типов, который проверяет способ использования каждого атрибута на соответствие типу атрибута. При возникновении ошибки на любом из параметров контроля, формируется код ошибки и передается управление системе обработки ошибок. Например, препроцессор может обнаружить использование атрибута с одинаковым именем в двух отношениях, используемых при выборе в одном запросе.

Челябинск 2006 г.14 Прототипы основных функций, реализующих работу препроцессора int existTable(char* name)//проверяем наличие таблицы int existAtribut(char* name)//проверяем наличие атрибута int trueType()//проверяем соответствие типа

Челябинск 2006 г.15 Генератор логического плана Генератор логического плана предназначен для преобразования дерева разбора в логический план выполнения запроса с использованием набора операций реляционной алгебры. Для примера преобразования синтаксического дерева разбора в логический план запроса, представленным выражениями реляционной алгебры, рассмотрим синтаксическую конструкцию. Эта конструкция состоит из трех реляционных операций: - декартова произведения всех отношений из списка ; - декартова произведения всех отношений из списка ; - оператора выбора C из условия ; - оператора выбора C из условия ; - оператора проекции L соответствующего списку. - оператора проекции L соответствующего списку.

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

Прототипы функций, реализующих генерацию логического плана запроса tree tree_logPlan//определение дерева логического плана char param[][]//определение дополнительных параметров void Create_logPlan()//функция генерации логического плана