Самый эффективный способ поиска ключевых слов

Question

Хорошо, поэтому я пишу функцию как часть лексического анализатора, который «ищет» или ищет совпадение с ключевым словом. Мой лексер перехватывает все очевидные токены, такие как одно- и многосимвольные операторы (+ - * / > < = == etc) (также комментарии и пробелы уже удалены), поэтому я вызываю функцию после того, как собрал поток только буквенно-цифровых символов (включая подчеркивания) в string, эта строка должна соответствовать либо известному ключевому слову, либо идентификатору.

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

Answer 1

Если ваш набор ключевых слов является фиксированным, для поиска O (1) можно построить совершенный хэш .Проверьте gperf или cmph .

Answer 2

Это для языка с определенным набором ключевых слов, которые никогда не меняются, и их не очень много?

Если так, то, вероятно, не имеет значения, что вы используете. У вас будет больше рыбы, чтобы жарить.

Однако, поскольку список не меняется, было бы трудно обойти поиск с жестким кодом, подобный этому:

// search on first letter
switch(s[0]){
  case 'a':
    // search on 2nd letter, etc.
    break;
  case 'b':
    // search on 2nd letter, etc.
    break;
  ........
  case '_':
    // search on 2nd letter, etc.
    break;
}

Answer 3

Какой бы реализации std :: map у вас не было, вероятно, будет достаточно.

Answer 4

A "trie" , безусловно, будет наиболее эффективным способом.

Answer 5

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

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