сумма кодов первой и последней букв упорядоченный список с логарифмическим поиском

19.09.202222.09.2022 admin 0 Comments

Работа с таблицей символов

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Вложения

сумма кодов первой и последней букв упорядоченный список с логарифмическим поиском

лаба 3(список).zip (267.5 Кб, 27 просмотров)

Работа с таблицей
как заполнить 1ую строчку нулями,но так же сдвинуть все значения на 1 вниз,чтобы не потерялись.

Работа с таблицей
Помогите реализовать программу, нужно параметр l занести в таблицу и чтобы его данные посчитать, а.

работа с таблицей
задача состоит в следующем: есть таблица (DBGrid) при нажатии на ячейку строки «вылазиет».

Работа с таблицей
Всем драсте. Возник такой вопрос. есть таблица и кнопка удалить столбец. Когда.

работа с таблицей
привет,подскажите как в stringgrid сделать сортировку по столбцу,так что бы если в таблице.

Работа с таблицей StringGrid
Всем привет, перейду сразу к теме, мне нужно в таблице(StringGrid) между числами произвести.

Подключение к бд и работа с таблицей
Программа должна подключиться к бд «Шоколадный магазин» и вывести на форму содержимое таблицы.

Источник

Готовый код: Сумма кодов первой и второй букв

Народ, нужна помощь! по готовому коду
Условие задания
Во всех вариантах требуется разработать программу, реализующую комбинированный способ
организации таблицы идентификаторов. Для организации таблицы используется простейшая хэш-
функция, указанная в варианте задания, а при возникновении коллизий используется
дополнительный метод размещения идентификаторов в памяти. Если в качестве этого метода
используется дерево или список, то они должны быть связаны с элементом главной хэш-таблицы.
В каждом варианте требуется, чтобы программа сообщала среднее число коллизий и среднее
количество сравнений, выполненных для поиска идентификатора.

В готовом коде сделан вариант:
Тип хеш-функции (таблицы): Сумма кодов первой и последней букв
Способ разрешения коллизий: Список с простым перебором

нужно исправить на Сумма кодов первой и второй букв

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Сумма кодов первой и второй буквы
:help: Как из переменной AnsiStrihg d, например «привет», получить число (int), равное сумме кодов.

Определить количество букв в первой последовательности, встречающихся и во второй
Здравствуйте, помогите пожалуйста). Даны две последовательности (любых). Определите кол-во букв.

Источник

Работа с таблицей символов

На помощь особо не расчитываю, но всё же.

Задание:
«Требуется разработать программу, реализующую комбинированный способ организации таблицы идентификаторов. Для организации таблицы используется простейшая хэш-функция, а при возникновении коллизий используется дополнительный метод размещения идентификаторов в памяти. Если в качестве этого метода используется дерево или список, то они должны быть связаны с элементом главной хэш-таблицы.
Требуется, чтобы программа сообщала среднее число коллизий и среднее количество сравнений, выполненных для поиска идентификатора.
Тип хеш-функции (таблицы): сумма кодов первой и последней букв; способ разрешения коллизий: упорядоченный список с логарифмическим поиском.»

Сама сделать не могу вообще ничего Помогите, кто может

Выглядеть должно так:
Lab4.rar

Помощь в написании контрольных, курсовых и дипломных работ здесь.

работа с таблицей
задача состоит в следующем: есть таблица (DBGrid) при нажатии на ячейку строки «вылазиет».

работа с таблицей
привет,подскажите как в stringgrid сделать сортировку по столбцу,так что бы если в таблице.

Работа с таблицей
Всем драсте. Возник такой вопрос. есть таблица и кнопка удалить столбец. Когда.

Работа с таблицей
как заполнить 1ую строчку нулями,но так же сдвинуть все значения на 1 вниз,чтобы не потерялись.

Работа с таблицей
Помогите реализовать программу, нужно параметр l занести в таблицу и чтобы его данные посчитать, а.

Источник

Доступные файлы (5):

Аннотация.doc	48kb.	14.01.2010 21:50	скачать
Пояснительная записка.doc	600kb.	18.12.2009 05:12	скачать
Приложения.doc	180kb.	18.12.2009 05:13	скачать
Содержание.doc	37kb.	14.01.2010 21:50	скачать
Титульник.doc	21kb.	14.01.2010 21:47	скачать

Пояснительная записка.doc

Введение

Компилятор – программный модуль, задачей которого является перевод программы, написанной на одном из языков программирования (исходный язык) в программу на язык ассемблера или язык машинных команд.

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

Курсовая работа заключается в реализации отдельных фаз компиляции заданного языка.

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

Во второй части работы требуется разработать программный модуль, выполняющий лексический анализ входного текста по заданной грамматике и порождающий таблицу лексем с указанием их типов.

В третьей части работы требуется разработать программу, которая на основании таблицы лексем выполняет синтаксический разбор текста по заданной грамматике с построением цепочки вывода и дерева разбора.

В качестве среды разработки для реализации программы был использован Borland Delphi 7.
1. Организация таблицы идентификаторов

1.1. Задание

Разработать программу, реализующую комбинированный способ организации таблицы идентификаторов. Для организации таблицы используется простейшая хэш-функция (сумма кодов первой и второй букв), а при возникновении коллизий используется дополнительный метод размещения идентификаторов в памяти (рехеширование с использованием случайных чисел). Если в качестве этого метода используется дерево или список, то они должны быть связаны с элементом главной хэш-таблицы.

В каждом варианте требуется, чтобы программа сообщала среднее число коллизий и среднее количество сравнений, выполненных для поиска идентификатора.
^

1.2. Назначение таблицы идентификаторов

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

Под идентификаторами подразумеваются константы, переменные, имена процедур и функций, формальные и фактические параметры.[1]
^

1.3. Метод рехеширования с использованием случайных чисел

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

Согласно этому методу, если для элемента A адрес h(A), вычисленный с помощью хеш-функции h, указывает на уже занятую ячейку, то необходимо

вычислить значение функции n₁=h₁(A) и проверить занятость ячейки по адресу n₁. Если и она занята, то вычисляется значение h₂(A) и так до тех пор, пока либо не будет найдена свободная ячейка, либо очередное значение h_i(A) совпадет с h(A). В последнем случае считается, что таблица идентификаторов заполнена, и места в ней больше нет — выдается информация об ошибке размещения идентификатора в таблице.

Такую таблицу идентификаторов можно организовать по следующему алгоритму размещения элемента:

^ Шаг 1: Вычислить значение хеш-функции n = h(A) для нового элемента A.

Шаг 2: Если ячейка по адресу n пустая, то поместить в нее элемент A и завершить алгоритм, иначе i:=1 и перейти к шагу 3.

Шаг 3: Вычислить n_i = h_i(A). Если ячейка по адресу n_i пустая, то поместить в нее элемент A и завершить алгоритм, иначе перейти к шагу 4.

Шаг 4: Если n = n_i, то сообщить об ошибке и завершить алгоритм, иначе i:=i+1 и вернуться к шагу 3.

Тогда поиск элемента A в таблице идентификаторов, организованной таким образом, будет выполняться по следующему алгоритму:

^ Шаг 1: Вычислить значение хеш-функции n = h(A) для искомого элемента A.

Шаг 2: Если ячейка по адресу n пустая, то элемент не найден, алгоритм завершен, иначе сравнить имя элемента в ячейке n с именем искомого элемента A. Если они совпадают, то элемент найден и алгоритм завершен, иначе i:=1 и перейти к шагу 3.

Шаг 3: Вычислить n_i = h_i(A). Если ячейка по адресу n_i пустая или n = n_i, то элемент не найден и алгоритм завершен, иначе сравнить имя элемента в ячейке n_i с именем искомого элемента A. Если они совпадают, то элемент найден и алгоритм завершен, иначе i:=i+1 и повторить шаг 3.

Схема алгоритма добавления идентификатора приведена на рис. 1.1.

Рис. 1. 1 Схема алгоритма добавления идентификатора
Схема алгоритма поиска идентификатора приведена на рис. 1.2.

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

1.4. Метод упорядоченного списка

Этот метод является простым методом построения таблиц идентификаторов. Элементы записываются в таблицу в порядке возрастания. Так как упорядочивание таблицы идентификаторов происходит на всех этапах обращения к таблице, то для ее построения можно пользоваться только алгоритмом прямого упорядоченного включения элементов. При добавлении нового элемента в таблицу идентификаторов он сначала добавляется в конец таблицы, а затем идет переупорядочивание элементов таблицы идентификаторов. Эффективным методом для поиска элементов является логарифмический поиск, на каждом шаге которого, число элементов, которые могут содержать искомый элемент, сокращается в два раза. Максимально число сравнений при поиске 1+log₂(N). [1]

Схема алгоритма добавления идентификатора представлена на рис. 1.3.

Рис. 1.3. Схема алгоритма добавления идентификатора
Схема алгоритма поиска идентификатора представлена на рис. 1.4.

Рис. 1.4. Схема алгоритма поиска идентификатора

Недостатком такого метода является требование упорядочивания таблицы идентификаторов на всех этапах обращения к этой таблице.

К положительным качествам метода можно отнести простоту его организации.

^ 1.5. Основные используемые функции

if dlina=0 then Result:=0

else begin
sred:=(dlina+1)div 2;

if dlina=1 then Result:=ord(St[1])-64 else

if dlina=2 then Result:=ord(St[1])+ord(St[dlina])-64 else

end;
^ Заполнение хэш-таблицы и таблицы идентификаторов,
подсчет коллизий.

NRow, i, Kol, u, KolO, Com, Key, Key1: Integer;

with StringGrid1 do

For NRow:=1 to 302 do

for i:=0 to Words.Count-1 do

s:=Words[i];

if StringGrid1.Cells[1,Key]=» then begin

Key1:=((Key + Sl[u]) mod 302)+64;

if StringGrid1.Cells[1,Key1]=» then begin

if Key1=Key then begin

ShowMessage(‘Ошибка! В ХТ нет свободного места’);

goto Shag3;
end

Form1.Memo2.Lines.Add(‘ПРИ ДОБАВЛЕНИИ ВСЕХ ЭЛЕМЕНТОВ:’);

Form1.Memo2.Lines.Add(‘Количество колизей ‘+Word);

Form1.Memo2.Lines.Add(‘Количество сравнений ‘+Word);

Поиск в таблице идентификаторов.
var j,i,t,k,a,b,m,n:integer;s1:string;

k:=0; t:=memo1.Lines.Count; s1:=Edit1.text;

if StringGrid2.Cells[1,j]<>» then k:=k+1;

MessageDlg(‘Поле ввода пусто’, mtInformation,[mbOk],0);

1: if ((a+b) div 2)=0 then m:=(a+b) div 2 else m:=(a+b) div 2;

if s1=StringGrid2.Cells[1,m] then

MessageDlg(‘Элемент найден’, mtInformation,[mbOk],0);

if s1 ^ 1.6. Результаты сравнения методов

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

На рис. 1.5 представлена экранная форма метода рехеширования с использованием случайных чисел и упорядоченного списка.

Рис. 1.5. Экранная форма организации таблицы идентификаторов
В данном случае при наличии во входном файле двенадцати идентификаторов количество требуемых сравнений для заполнения таблицы идентификаторов методом рехеширования с использованием случайных чисел оказалось меньше, чем методом упорядоченного списка (методом рехеширования с использованием случайных чисел количество сравнений равно 15, а методом упорядоченного списка количество сравнений равно 50).

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

Экранная форма поиска существующего идентификатора представлена на рис. 1.8.

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

Экранная форма поиска несуществующего идентификатора представлена на рис. 1.9.

Рис. 1.9. Экранная форма поиска несуществующего идентификатора
При поиске несуществующего идентификатора, выводится сообщение о неуспешном поиске и указывается выполненное число сравнений для обнаружения отсутствия идентификатора в таблице идентификаторов по каждому методу.

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

^ 2. Проектирование лексического анализатора

2.1. Задание

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

Длину идентификаторов и строковых констант считать ограниченной 32 символами. Программа должна допускать наличие комментариев неограниченной длины во входном файле. Форму организации комментариев предлагается выбрать самостоятельно.

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

Основная задача лексического анализа – разбить входной текст, состоящий из последовательности одиночных символов, на последовательность слов, или лексем, то есть выделить эти слова из непрерывной последовательности символов с исключением из входного текста комментариев, незначащих пробелов и переводов строк. Все символы входной последовательности с этой точки зрения разделяются на символы, принадлежащие каким-либо лексемам, и символы, разделяющие лексемы (разделители).

Результатом работы лексического анализатора является перечень всех найденных в тексте исходной программы лексем. Этот перечень представляется в виде таблицы, называемой таблицей лексем.

Язык описания констант и идентификаторов в большинстве случаев является регулярным, то есть может быть описан с помощью регулярных грамматик. Распознавателями для регулярных языков являются конечные автоматы (КА).

Любой КА может быть задан с помощью пяти параметров:

где: Q – конечное множество состояний автомата;

V – конечное множество допустимых входных символов (алфавит автомата);

δ – функция переходов, отображающая декартовое произведение множеств VQ во множество подмножеств Q: R(Q);

q₀ Q – начальное состояние автомата;

F ^ Q – непустое множество конечных состояний автомата.

Работа автомата выполняется по тактам. На каждом очередном такте i автомат, находясь в некотором состоянии q_iQ, считывает очередной символ vV из входной цепочки символов и изменяет свое состояние на q_i₊₁=(q_i,w), после чего указатель в цепочке входных символов передвигается на следующий символ и начинается такт i+1. Так продолжается до тех пор, пока цепочка входных символов не закончится. Конец цепочки символов часто помечают особым символом . Считается также, что перед первым тактом автомат находится в начальном состоянии q₀. На каждом такте автомат описывается конфигурацией в виде:
(q,w,n), (2.2)

где: q – текущее состояние автомата;

w – цепочка входных символов автомата;

n – положение указателя;

Графически автомат отображается нагруженным однонаправленным графом, в котором вершины представляют состояния, дуги отображают переходы из одного состояния в другое, а пометки дуг соответствуют функции перехода. Если функция перехода предусматривает переход из состояния q_i в q_i₊₁ по нескольким символам, то между ними строится одна дуга, которая помечается всеми символами, по которым происходит переход из q_i в q_i₊₁.[1]

^ 2.3. Схема распознавателя

Распознавателем лексем входного языка является конечный детерминированный автомат без внешней памяти (приложение Б).

Допустимые лексемы входного языка: идентификаторы и римские числа

H – начальное состояние автомата

E – конечное состояние автомата
Запишем КС-грамматику входного языка в форме Бэкуса-Наура:

VT – множество терминальных символов;

VN – множество нетерминальных символов;

P – множество правил;

E – целевой символ.
Регулярная грамматика входного языка имеет вид:

<N, L, E, I, F1, F2, O1, O2, T1>, P, E )
P: E® N | L | E| I| F2| O1| O2| T1| H _

N® I |V|X|e|.|-|H0|H1|H2|H3|H4|H5|H6|H7|H8|H9

H® N_| L _| E_| I_| F2_| O1_| O2_| T1_| H_| _
^ 2.4. Алгоритм лексического анализатора.

2.5. Основные используемые функции.

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

case stroka[j] of // 1

‘;’: begin sost:=Auto_L; str:=str+st; end;

‘I’,’X’,’V’: begin sost:=Auto_N; str:=str+st; end;

‘:’: begin sost:=Auto_F1; str:=str+st; end;

‘(‘: begin sost:=Auto_O2; str:=str+st; end;

‘)’: begin sost:=Auto_O1; str:=str+st; end;

‘ ‘: begin sost:=Auto_H; str:=»; end;