Как вы пишете парсер лексера, где идентификаторы могут начинаться с ключевых слов?

Question

Предположим, у вас есть язык, на котором идентификаторы могут начинаться с ключевых слов. Например, предположим, что «case» является ключевым словом, но «caser» является допустимым идентификатором. Предположим также, что правила lexer могут обрабатывать только регулярные выражения. Тогда кажется, что я не могу размещать правила ключевых слов перед правилом идентификатора в lexer, потому что это будет анализировать «caser» как «case», за которым следует «r». Я также не могу устанавливать правила лексинга ключевых слов после правила идентификатора, так как правило идентификатора будет соответствовать ключевым словам, и правила ключевых слов никогда не будут запускаться.

Таким образом, вместо этого я мог бы создать правило keyword_or_identifier в lexer и определить, является ли ключевой_и_идентификатор ключевым словом или идентификатором. Это то, что обычно делается?

Я понимаю, что «использовать другой лексер, который имеет взгляд» - это ответ (вид), но меня также интересует, как это делается в традиционном лексере на основе DFA, поскольку мой текущий лексер, похоже, работает сюда.

Answer 1

Большинство лексеров, начиная с оригинальной lex, матч альтернатив следующим образом:

1. Используйте самый длинный матч.

2. Если есть две или более альтернативы, которые связываются для самого длинного совпадения, используйте первую в определении lexer.

Это позволяет следующий стиль:

"case"     { return CASE; } 
[[:alpha:]][[:alnum:]]* { return ID; } 

Если шаблон вход caser, то вторая альтернатива будет использоваться, потому что это самый длинный матч. Если входной шаблон равен case r, тогда будет использован первый вариант, потому что оба они соответствуют case, а по правилу (2) выше выигрывает первый.

Хотя это может показаться немного произвольным, в основном это согласуется с подходом DFA. Прежде всего, DFA не останавливается при первом достижении принимающего состояния. Если бы это было так, то шаблоны, подобные [[:alpha:]][[:alnum:]]*, были бы бесполезны, потому что они вводят принимающее состояние на первом символе (при условии его алфавита). Вместо этого лексеры, основанные на DFA, продолжаются до тех пор, пока не произойдет никаких возможных переходов из текущего состояния, а затем они вернутся до последнего принимающего состояния. (См. Ниже.)

Данное состояние DFA может быть принято из-за двух разных правил, но это тоже не проблема; записывается только первое правило приема.

Справедливости ради, это немного отличается от математической модели DFA, которая имеет переход для каждого символа в каждом состоянии (хотя многие из них могут быть переходами в состояние «сток») и который соответствует полный ввод в зависимости от того, находится ли автомат в принимающем состоянии, когда считывается последний символ ввода. Модель лексера несколько отличается, но ее можно легко формализовать.

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

Большинство языков не требуют резервного копирования очень часто, и очень немногим требуется неограниченное резервное копирование. Некоторые генераторы лексеров могут генерировать более быстрый код, если нет резервных состояний.(flex будет это делать, если вы используете -Cf или -CF.)

Один общий случай, который приводит к неопределенному резервного копирования не в состоянии обеспечить соответствующий возврат ошибки для строковых литералов:

["][^"\n]*["] { return STRING; } 
/* ... */ 
.    { return INVALID; } 

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

["][^"\n]*["] { return STRING; } 
["][^"\n]*  { return INVALID_STRING; } 

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