Хеш-адресация - раздел Программирование, СИНТАКСИЧЕСКИЙ И СЕМАНТИЧЕСКИЙ АНАЛИЗ Данный Метод В Целом Более Эффективен, Чем Линейные Списки, И Используется Дл...
Данный метод в целом более эффективен, чем линейные списки, и используется для таблиц символов в большинстве случаев [13]. Схема открытого хеширования (хеш-таблица размера 211) приведена на рис.5.16. Структура данных состоит из двух частей – хеш-таблицы и блоков.
1. Хеш-таблица представляет собой фиксированный массив из m указателей на записи таблицы.
2. Записи таблицы организованы в виде m отдельных связанных списков, именуемых блоками (некоторые блоки могут быть пустыми).
Каждая запись в таблице символов встречается только в одном из этих списков.
Для определения, существует ли в таблице символов запись для строки s, мы вычисляем хеш-функцию h от строки s, возвращающую целое число от 0 m-1. Если строка s имеется в таблице символов, то она находится в списке с номером h(s). Если s в таблице символов еще отсутствует, то она вносится в таблицу путем создания записи в начале списка с номером h(s) [13].
Используя такой алгоритм можно сделать время обращения к элементу таблицы константой. Пусть средняя длина списка при n записях в таблице символов и хеш-таблице размера m —m/n. Можно выбрать m настолько большим, чтобы n/m было ограничено небольшой величиной, например 2.
Пространство, занимаемое таблицей символов определяется как m+cn, где с – количество слов в одной записи таблицы символов.
Следует уделить особое внимание созданию хеш-функции, т.к. наибольшая эффективность работы алгоритма хеш-адресации достигается при равномерном распределении идентификаторов между списками и приемлемом времени вычисления значений хеш-функции. С точки зрения реализации хеш-функция – это некоторое преобразование строки символов в значение номера элемента таблицы. Нельзя не отметить что хеш-функция, учитывающая все символы строки, выглядит более разумной, чем функция, учитывающая только несколько символов. Пример хеш - функции приведен на рисунке 5.17.
Массив заголовков
списков, индексируемый
хеш-значением
Список элементов, созданный для указанных имён
Рис. 5.16.
Текст хеш-функции из компилятора С. Вайнбергера на языке С [13]:
На сайте allrefs.net читайте: "СИНТАКСИЧЕСКИЙ И СЕМАНТИЧЕСКИЙ АНАЛИЗ"
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
Хеш-адресация
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
ПРОЦЕССОР ЧИСЛОВЫХ КОНСТАНТ
Приведем грамматику числовых констант в следующем виде G[<Число>]:
1. <Число> ® [+ | -] <Число Без Знака>
2. <Число Без Знака> ® <Десят
Очистка мусора
Мусором будем называть вспомогательные сиволы, которые не являются носителями смыслового содержания текста. Такими символами являются символы табуляции ‘t’, символы перевода на новую строку
Декомпозиция программы при лексическом анализе
Основным функциональным назначением сканера является декомпозиция программы на её терминальные составляющие: идентификаторы, ключевые слова, числовые константы, знаки операций и так далее. Эти язык
Семантика целого числа при сканировании
Для целого в алгоритме предусмотрен генератор условного кода 2. Под кодом здесь понимается класс целых. Часто, при обработки целых требуется не только их указатель(код) целого числа, но и значение
Лексический анализ идентификатора
Выделение идентификаторов кодом 2 не является полной информацией о каждом идентификаторе в отдельности. На этапе лексического анализа информационной характеристикой идентификатора является кортеж &
Лексический анализ операций
Лексический разбор бинарных операций, как правило, ограничивается уже описанным алгоритмом генерации адресного (условного) кода. Следует добавить лишь, что в сгенерированные адреса (ссылки) необход
ОРГАНИЗАЦИЯ ТАБЛИЦ СИМВОЛОВ
Проверка правильности семантики и генерация кода требуют знания характеристик идентификаторов, констант, имён функций (библиотечных и внеших) и т.д.
Определение 5.1. Табли
Структуры линейного формата
Для структур линейного формата существует два способа хранения имен. Первый – хранить символы имени в записях таблицы символов рис. 5.10, второй - в записи для имени размещать только указатель на о
Блочные структуры
В некоторых языках один и тот же идентификатор может быть описан и использован много раз в различных блоках и процедурах. Каждое такое описание должно иметь единственный, связанный с ним элемент в
Древовидные структуры
Существует способ представления таблиц с использованием двоичных деревьев Каждый узел дерева представляет собой заполненный элемент таблицы, причем корневой узел является первым элементом. Добавлен
Неупорядоченный поиск
Неупорядоченный поиск – это простейший способ организации таблицы символов. Он состоит в том, чтобы добавлять элементы для аргументов в порядке их поступления, без каких-либо попыток упорядочения.
Бинарный поиск
Поиск может быть выполнен более эффективно, если элементы таблицы упорядочены (отсортированы) согласно некоторому естественному порядку аргументов.
Эффективным методом поиска в упорядоченн
Сравнение способов организации таблиц символов
Прямой поиск прост в реализации, но самый неэффективный, т.к. время поиска прямопропорционально размерности таблицы, а количество сравнений в среднем равно половине элементов таблицы. Бинарный поис
РЕКУРСИВНЫЙ СПУСК
Рассмотрим подкласс КС-грамматик - S-грамматики
Определение 5.2. S-грамматики — это подкласс контекстно-свободных грамматик, таких что:
1. Правая часть
ДИАГНОСТИКА И НЕЙТРАЛИЗАЦИЯ СИНТАКСИЧЕСКИХ ОШИБОК
Диагностика — установка места возникновения и типа синтаксической ошибки. Кроме того, обработанная ошибка должна быть визуализирована пользователем в виде, удобном для её обнаружения.
Нейт
Метод Айронса
Основная идея — по контексту без возврата отбрасывать литеры, которые привели к тупиковой ситуации (когда продолжение анализа по грамматике невозможно) и разбор продолжается. Для ил
Алгоритм Айронса по исправлению ошибок
Пусть xjy — куст исходной программы, где x — построенная часть, jy — недостроенная часть, jÎVT
1. Строим список L из литер недостающих час
ВОСХОДЯЩИЕ МЕТОДЫ АНАЛИЗА
Анализ методами слева направо является более приоритетным и занимает 60..80% для грамматик определённого класса. Менее популярными являются методы анализа снизу вверх или восходящие
Список элементов, созданный для указанных имён
Новости и инфо для студентов