Диссертация на степень магистра наук по направлению «Математика, компьютерные науки»
Скачать 354.13 Kb.
|
.3. СинтаксисВсе синтаксические конструкции CSeL – выражения. Это и атомарные операнды, и более сложные структуры, сформированные из них, символов операций и скобок. Синтаксис в таких случаях определяют неоднозначной грамматикой и таблицей ассоциативности/приоритетов операций, так как в этом случае есть алгоритм построения минимального SLR(1)-анализатора, при котором вариативность устраняется автоматически [16, Приложение 2]. Кроме того, если появится необходимость что-то поменять, конфигурировать таблицы проще, чем пытаться переделать грамматику. Итак, грамматика: Параметризация бинарных операций приведена в Таблице 3.2. Таблица 3.2. Приоритет и ассоциативность бинарных операций
.4. Генерация промежуточного кода Итак, дерево синтаксического разбора построено. Последним этапом, предваряющим генерацию кода, является преобразование поддеревьев colon и semicolon только учитывающее порядок, но не вложенность:
С этого момента с каждым узлом синтаксического дерева связывается две переменные value (результат) и code (промежуточный код –реализация), и в процесс компиляции включается генератор кода. Далее под компиляцией будем понимать вычисление значений этих переменных для некоторого узла. С учётом этого определения, задача генератора –компиляция корня дерева. Рассмотрим элементы языка, отвечающие за этот процесс: IR7-вставку и механизм вывода на её основе. IR-вставкаСинтаксически вставка имеет вид:
x, y, … z –необязательные аргументы, строка –текст из инструкций. Инструкции описываются формально:
Метки инструкций должны использоваться без повторений (SSA). Операнды могут быть метками или указателями на аргументы вставки: на узел соответствующий аргументу (#), на результат узла (%) и на лексему узла-идентификатора (&). Заметим, что аргументы нумеруются с нуля, а при обращении % вызывается процедура компиляции узла. Следует иметь в виду общее правило, если узел уже был скомпилирован, то дублирующего вызова не происходит. Инструкции подразделяются на две группы:
Абстракции языкаТипыВ CSeL три базовых типа: type, number и string. Первый тип имеют все значения конструкторов типов, а второй –числовые константы, третий –строковые. Все типы характеризуются двумя параметрами: сигнатурой, обеспечивающей уникальность, и объёмом памяти в байтах, необходимым для хранения одного значения данного типа. Базовые типы относятся к значениям времени компиляции, поэтому память для них не выделяется. ПеременныеПеременные описываются некоторым типом, уникальным именем и меткой, указывающей либо на выделенную память (не нулевой размер типа), либо на ячейку в хранилище времени компиляции. Предопределенными переменными в CSeL являются type, number, string все типа type, в их ячейках которых находятся соответствующие уже упомянутые базовые типы. Синтаксические подстановкиПодстановки лежат в основе работы механизма вывода CSeL, любая из них определяются тройкой (P, R, A), где P и R – это указатели на узлы в дереве; P – шаблон, R – замена. A – словарь аргументов: имя аргумента → его тип. Именованные меткиИменованные метки CSeL – это переменные без типов, не связанные с хранилищем. Области видимостиСинтаксически области видимости задаются парой фигурных скобок и ограничивают доступ к структурам языка, позволяя повторно использовать их имена и логически разделяя ответственность за возможные ошибки. Такими структурами являются все абстракции и метки. Для абстракций действуют строгие правила регистрации, иногда допускающие перекрывание имён, иногда – нет. Метки переименовываются автоматически, например:
ДирективыБудем далее считать, что все операнды % уже заменены на результаты компиляции соответствующих узлов-аргументов. На данный момент в CSeL реализовано шесть директив. Рассмотрим их синтаксис и семантику. _store Копирует значение времени компиляции из ячейки с меткой from в ячейку с меткой to. Регистрирует новый тип во внешней области видимости (родительской по отношению к текущей), указывая в качестве объёма памяти операнд size, если он есть, или нуль –иначе, и вычисляя сигнатуру по алгоритму:
Под идентификатором понимается операнд &. Если такой тип существует хотя бы в рамках одной области видимости в иерархии, то в ячейку с меткой r переносится первое найденное значение, иначе создаётся новый тип и используется уже его значение. Регистрирует во внешней области видимости новую переменную с именем name и типом type. Если такой переменной нет вообще или она определена в области видимости выше внешней в иерархии, то переменная создаётся успешно, иначе генерируется ошибка. В случае успеха оценивается тип переменной, если для значения требуется ненулевой объем памяти, то к реализации компилируемого узла добавляется инструкция <r> #allocN, где N – число байт. _syntax Узлы передаются как операнды #. Регистрирует во внешней области видимости новую синтаксическую подстановку (pattern, replace, A), где словарь А строится по алгоритму: split(n) = если метка узла n –colon, то возвращаем список его сыновей, иначе – список, состоящий из него самого. ids = split ids. types = split types. компилируем все элементы types. если длина ids и types не совпадает, то генерируем ошибку. цикл по индексам ids (i) A[ids[i]] = types[i] –тип, иначе undef _link Регистрирует в текущей области видимости именованную метку e под именем name. Если такой переменной нет вообще или она определена в области видимости выше внешней в иерархии, то переменная создаётся успешно, иначе генерируется ошибка. Под идентификатором понимается операнд &. Если именованная метка с именем name существует хотя бы в одной области видимости в иерархии, то соответствующая ей метка переименует метку r далее во всей текущей области видимости. Под идентификатором понимается операнд &. Таким образом, в CSeL четыре группы языковых абстракции: типы, переменные, подстановки и именованные метки. IR-вставки могут содержать описанные директивы для работы с этими абстракциями, интерпретируемые в процессе компиляции и в отличие от обычных инструкций не относящиеся к реализации вставки. Механизм выводаПримитивные конструкцииПеред тем как переходить собственно к применению синтаксических подстановок, следует определить, каким образом происходит компиляция примитивных конструкций: атомов и списков *colon. Атомами являются идентификаторы и константы. В обоих случаях реализация не содержит ни одной инструкции. Для узлов-идентификаторов результатом служат метки соответствующих им переменных. Если какой-то переменной не зарегистрировано, генерируется ошибка. Для узлов-констант отводятся метки и ячейки, хранящие лексемы, для строк с типом string, для чисел –number, эти метки и становится результатами. Списки, как было отмечено выше, тоже примитивные конструкции, в том смысле, что механизм их компиляции не связан с подстановками. Общим для списков является компиляция всех дочерних узлов с результатом списка равным результату последнего дочернего узла, вся разница в формировании реализации: для semicolon это склеенная реализация всех дочерних узлов, а для colon – всех, кроме последнего. Итак, смысл основных всех элементов языка кроме одного раскрыт. Речь идёт о механизме синтаксических подстановок. Рассмотрим этапы, из которых он состоит: выбор и применение. ВыборНа первом этапе происходит сопоставление структуры поддерева, к которому нужно применить подстановку, со всеми зарегистрированными подстановками, с выбором наилучшего совпадения. Сначала выбираются все наилучшие синтаксические совпадения так, как если бы подстановки были обычными макросами: match(syntax, node) = обход в ширину одновременно syntax.P (a) и node (b) если a –узел-идентификатор и syntax.A[a] –определено, то сохраняем совпадение a → b в syntax.match иначе если в a и b не совпадают либо типы узлов, либо лексемы, либо число дочерних узлов, то return false. return true. cmp(s1, s2) = если match(s1, s2.P), то если в s1.match все правые стороны из s2.A, то return 0 т.е. аргументы в s1 являются аргументами в s2. return -1. return 1. matches = [] X –корень поддерева, для которого проводим поиск цикл по всем подстановкам (s) если match(s, X), то если matches –пусто, то matches.add(s) иначе sx –элемент из matches варианты cmp(sx, s) если -1: matches = [s] т.е. s –лучшее совпадение если 0: matches.add(s) т.е. s –не лучше и не хуже. Теперь необходимо провести отбор на основе типов: цикл по matches слева направо (match.a, match.b) если в matches есть подстановки, у которых A[a] – undef, то это должны быть все подстановки, или ошибка иначе компилируем b фильтруем matches, так чтобы A[a] равнялось типу результата b если в matches ничего не осталось, то ошибка. если в matches более одной подстановки, то ошибка. Наилучшее совпадение выбрано. Заметим, что возможно вложенное использование подстановок, и в этом случае информацию о последнем успешном сопоставлении (.match) следует реализовывать в виде стека. Например, есть подстановка с шаблоном a+b, где a и b – аргументы. Выбор подстановки для выражения (x+y)+z при сопоставлении a → x+y приведет к рекурсивному вызову {a → x, b → y}, и если .match была обычной переменной, то данные о первом сопоставлении потеряются. ПрименениеКогда синтаксическая подстановка выбрана, остаётся её применить: X –корень дерева, компилируемого с помощью механизма вывода S –подстановка компилируем S.R с замещением всех узлов из левых частей S.A на соответствующие правые. X.code = S.code X.value = S.value Ясно, что замена R в подстановках будет, скорее всего, не один раз компилироваться, но с разными аргументами, поэтому для её внутренних узлов отказ от повторного компилирования отменяется. Итоговая схема компиляцииcompile(X) = варианты X если примитивная конструкция: … если IR-вставка: … иначе запускаем механизм подстановок. Управление памятьюВ архитектуре x86 есть пара специальных инструкций enter/leave для реализации стековых переменных в высокоуровневых языках. Схема очень проста, поэтому именно её предполагается взять за основу в управлении памятью CSeL в первом приближении. Каждый раз, когда нужна новая метка, она запрашивается у фабрики меток и запоминается в той области видимости, в рамках которой она потребовалась. Когда процесс компиляции доходит до границы этой области, все связанные с ней метки, кроме результата, уже не нужны, так как к ним нет доступа извне. Среди них могут оказаться и те, с которыми через #alloc связана выделенная память, тогда её можно будет высвободить. В связи с этим имеет место следующая поправка к основному алгоритму: compile(X) = варианты X если {Y}: вызвать compile(Y) в новой области видимости S list = [] цикл по меткам S (a) если под a –выделена память, то list.add(a) вернуть a фабрике. если list –пусто, то X.code = Y.code иначе X.code = #enter + Y.code + #free list X.value = Y.value если … В текущей версии CSeL не высвобождаются только метки констант, так как константы довольно часто повторяются, и запрашивать/освобождать метки каждый раз, когда они потребуется, может быть проблематично. Приведённое описание языка –единственное на данный момент. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Похожие:
 | Реферат: Коваленко А. Е. Разработка системы научной визуализации.... Коваленко А. Е. Разработка системы научной визуализации. Квалификационная работа на степень магистра наук по направлению «Математика.... | | Реферат: Шайдуров А. Г. Исследование и разработка некоторых графических... Шайдуров А. Г. Исследование и разработка некоторых графических алгоритмов. Квалификационная работа на степень магистра наук по направлению... |
| Реферат Флягина Т. А. Проблемы разработки многооконных интерфейсов,... Флягина Т. А. Проблемы разработки многооконных интерфейсов, квалификационная работа на степень бакалавра наук |  | Рабочая программа составлена в соответствии с требованиями фгос впо... Математика и компьютерные науки по профилю подготовки: «Вычислительные, программные, информационные системы и компьютерные технологии»... |
| Рабочая программа для студентов очной формы обучения, направление... Иванов Д. И. Криптография и криптоанализ. Учебно-методический комплекс. Рабочая программа для студентов очной формы обучения, направления... | | Рабочая программа для студентов очной формы обучения, направление... Иванов Д. И. Дополнительные главы дискретной математики. Учебно-методический комплекс. Рабочая программа для студентов очной формы... |
| Литература Погрешности вычислений Программа предназначена для подготовки к вступительным испытаниям в аспирантуру по направлению 02. 06. 01 «Компьютерные и информационные... | | Учебно-методический комплекс Программа для студентов направления... Рассмотрено на заседании умк института математики и компьютерных наук, протокол №2013 г |
| Рабочая программа дисциплины (модуля) опубликована на сайте ТюмГУ «Математика и компьютерные науки» по профилю подготовки «Вычислительные, программные, информационные системы и компьютерные технологии... | | Г. Л. Воронин Н. В ларшина социология учебно-методическое пособие Программа предназначена для бакалавров очной формы обучения механико-математического факультета математика 010100, математика и компьютерные... |
| Учебно-методический комплекс учебной дисциплины «Философские образы... Аспирантура – самостоятельный уровень высшего образования, нацеленный на подготовку специалистов высшей квалификации. К поступлению... | | Рабочая программа для студентов направления 010200. 62 Математика... Девятков А. П. Банаховы алгебры и гармонический анализ. Учебно-методический комплекс. Рабочая программа для студентов направления... |
| Учебно-методический комплекс для студентов не психологических специальностей... Гидрология 010100. 62 Математика 010101. 65 Математика 010101. 65 Математика 010101. 65 Математика 010300. 62 Математика. Компьютерные... | | Рабочая программа и методические указания для студентов очной формы... Рабочая программа и методические указания для студентов очной формы обучения направлений 010300. 62 «Математика. Компьютерные науки»... |
| Диссертация На соискание степени Магистра по направлению 030100 Философия... Едеральное государственное бюджетное образовательное учреждение высшего профессионального образования | | Рабочая программа составлена в соответствии с требованиями фгос впо... Дёгтев А. Н. Теория алгоритмов. Учебно-методический комплекс. Рабочая программа для студентов направления 010200. 62 – математика... |
