Студопедия

КАТЕГОРИИ:

АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника


Хэш-функции




Хэш-функция должна равномерно распределять идентификаторы по таблице представлений. Для этого желательно, чтобы хэш-функция зависела от всех символов идентификатора. Например, для идентификторов длины n удовлетворительным вариантом хэш-функции является следующий: Hash (id) = (id0 + … + idn-1) / H, где H - длина оглавления хэш-списка.

Так как хэширование используется в самых разнообразных приложениях, система классов .NET содержит специальный класс HashTable, с помощью которого легко реализовать функциональность хэш-функций и хэш-таблиц. Объекты, хранящиеся в HashTable должны явно переопределять методы GetHashCode и Equals.

При работе с идентификаторами достаточно воспользоваться методом String.GetHashCode, реализующим чувствительную к регистру хэш-функцию для строк, и String.Equals, выдающую true при равенстве строк (а не в случае совпадения указателей на объекты, как по умолчанию реализовано в Object.Equals ).

 

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

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

Действительно, легко выписать, например, праволинейную грамматику для распознавания идентификаторов:

letter -> 'a'..'z' | 'A'..'Z' | '_'digit -> '0'..'9'ident -> letter | letter tailtail -> letter | digit | letter tail | digit tail

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

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

 


Поделиться:

Дата добавления: 2015-01-29; просмотров: 64; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.008 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты