Хэш-функции

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

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

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

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

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

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

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

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