Это зависит от точной природы лексической структуры языка, который вы анализируете, но обычно резервное копирование может быть устранено. Однако часто бывает удобнее оставить его, тем самым избегая некоторого количества дублирования кода и / или неуклюжих структур управления.
Полезно уточнить, что вы имеете в виду под "резервным копированием", потому что я обычно не рассматриваю пример в вашем вопросе как пример. Подавляющее большинство токенов не может быть распознано, если не смотреть на символ, следующий за токеном (например, идентификатор расширяется до тех пор, пока следующий символ не станет буквенно-цифровым). Хотя этого можно избежать при некоторой работе, нормально рассматривать завершающий символ дважды: один раз, чтобы определить, что он не может быть частью предыдущего токена, и затем снова, чтобы определить, какой токен он может инициировать.
Будет ли это похоже на резервное копирование или нет, будет в некоторой степени зависеть от парадигмы, которую вы используете для чтения ввода. В общих чертах, есть две возможные парадигмы (и несколько реализаций смешивания и сопоставления, которые не совсем соответствуют ни одной модели):
peek и accept.
peek возвращает следующий входной символ без изменения позиции курсора чтения, поэтому два последовательных просмотра будут видеть один и тот же символ. accept перемещает курсор чтения на следующую позицию, ничего не возвращая. Поэтому для обработки символа потребуется одна (или несколько) peek операций и ровно одна accept.
Возможно, это более эффективная парадигма, но писать ее вручную неудобно из-за необходимости явного accept.
Для простого входного буфера в памяти peek() в основном return inputBuffer.charAt(pos);, а accept() - ++pos;; оба они, как правило, вставляются компилятором или программистом.
get и unaccept.
get возвращает следующий входной символ и перемещает курсор чтения на одну позицию, так что следующий get будет читать следующий символ. unaccept перемещает курсор чтения на один символ назад, так что следующий get перечитает предыдущий символ. (Это не совсем то же самое, что и стандартная библиотека C ungetc, которая позволяет вставлять другой символ в буфер чтения и которая может позволять более одного символа быть незаданным. Подробнее об этом позже.)
Для простого входного буфера в памяти get() в основном c = peek(); accept(); return c;, а unaccept() - --pos. Опять же, они обычно будут встроены.
Поскольку последовательность get(); unaccept(); точно такая же, как и peek();, две парадигмы довольно хорошо изоморфны. Несмотря на то, что unaccept() включает в себя декремент до pos, мне трудно думать о нем как о «резервном копировании». Это просто перечитывание символа, как в случае с парадигмой peek/accept.
Выдержка из сильно упрощенного и частичного лексического анализатора (не контекстуального) может выглядеть примерно так:
c = peek();
while (isblank(c)) { accept(); c = peek(); }
if (c == '<') {
accept();
c = peek();
if (c == '=') { accept(); return Token_LessEquals; }
else if (c == '<') { accept(); return Token_LeftShift; }
else return Token_Less;
}
if (isalpha(c)) {
tstart = pos;
accept();
while (isalnum(peek())) { accept(); }
return makeIdToken(tstart, pos);
}
// etc.
Тот же фрагмент, написанный в стиле get / unaccept:
c = get();
while (isblank(c)) { c = get(); }
if (c == '<') {
c = get();
if (c == '=') { return Token_LessEquals; }
else if (c == '<') { return Token_LeftShift; }
else { unaccept(); return Token_Less; }
}
if (isalpha(c)) {
tstart = pos - 1;
while (isalnum(get())) { }
unaccept();
return makeIdToken(tstart, pos);
}
// etc.
Поскольку unaccept() является обычным (хотя и не универсальным), когда принимаются токены, заманчиво удалить его из действия и просто поставить префикс перед тем, как мы начнем пытаться распознать токен. Конечно, если мы это сделаем, нам нужно добавить избыточный get() (или accept()) в тех случаях, когда мы нашли конец токена без предварительного просмотра:
unaccept();
c = get();
while (isblank(c)) { c = get(); }
if (c == '<') {
c = get();
if (c == '=') { accept(); return Token_LessEquals; }
else if (c == '<') { accept(); return Token_LeftShift; }
else { return Token_Less; }
}
if (isalpha(c)) {
tstart = pos - 1;
while (isalnum(get())) { }
return makeIdToken(tstart, pos);
}
// etc.
Теперь только unaccept() надежно спрятан в прологе к tokeniser. (Как это происходит, это эффективно стиль, используемый Flex. «Лишний» accept() s фактически спрятан в таблицах переходов. Там нет «фишки принять» действия, поэтому после просмотра второго символа << </kbd>, сканер продолжает читать опережения характера, а затем обнаруживает, что нет никакого перехода, используя этот символ. затем он принимает маркер и опережение символа перечитать на следующем вызов yylex();. это может кажусь немного неуклюжим, но получается, что упрощение основного контура стоит больше, чем время от времени чтения ненужного опережающего просмотра.
Можно ли избавиться от этого последнего оставшегося unaccept()? Да, мы можем, если мы готовы, чтобы инвертировать поток управления с помощью нажимного анализатора. (Я очень люблю это решение, я.) В этой модели, лексический сканер управляет процессом синтаксического анализа, вызова анализатор каждый раз, когда он имеет маркер. Это не очень хорошо с рекурсивных спускаемых анализаторами, но он может прекрасно работать с анализатором, который поддерживает свой собственный стек. Это, очевидно, проще сгенерированного анализатором, чем рукописном один, а несколько LALR (1) парсер генераторы поддерживают этот стиль. (Ничто не мешает сверху вниз парсер использовать свой собственный стек, а не стек вызовов, но я не знаю, если какой-либо сверху вниз генераторы взаимодействуют.)
В этой модели лексер имеет свой собственный цикл для чтения лексем, и опережение символ сохраняется на звонки в парсер:
c = get(); /* Start by reading the first character */
for (;;) { /* Token loop assumes that every action will read a lookahead */
while (isblank(c)) { c = get(); }
if (c == '<') {
c = get();
if (c == '=') { c = get(); parse(Token_LessEquals); }
else if (c == '<') { c = get(); parse(Token_LeftShift); }
else { parse(Token_Less); }
}
if (isalpha(c)) {
tstart = pos - 1;
while (isalnum(get())) { }
parse(makeIdToken(tstart, pos));
}
// etc.
}
Существует еще одна интересной альтернативы, если вы используете толчок парсер, но я только когда-либо видел, как это реализовано с генерированными сканерами с таблицами переходными; для открытых кодировки сканеров, было бы много дублирования кода.
В действии сканера для нажимной синтаксического анализа, ничто не мешает нам называть анализатор дважды (или даже больше). И если вы думаете об этом, самый распространенный случай в формате JSON, например, является то, что значение должно быть сразу после запятой или закрывающей скобкой. Если это так, то мы могли бы сохранить отправку действий, используя набор шаблонов, которые соответствуют значения и следующий символ оператора, и кормить их обоих в анализатор. (Если значение следует пробел, то символ пробела может быть просто отброшены;. Нет необходимости отсканировать его Таким образом, если значение не следует знак мульти-символьный - и в формате JSON, что это не возможно AFAIK - это оптимизация будет победа.)
На самом деле реализация этой оптимизации является раздражающим, но генератор сканера мог легко выполнить его. Я не знаю ни одного, который делает, хотя.
Все вышеперечисленное было довольно хорошо стилистические, и я не уверен, что это действительно решает этот вопрос. Потому что есть случаи во многих, если не в большинстве языков, где отслеживание источников - реальные откатах, а не только перечитывать переходный характер - гораздо труднее избавиться от
.
Предположим, что язык имеет маркер, который является префиксом другого маркера, но промежуточные префиксы не являются допустимыми лексемы. В качестве конкретного примера, C лексемы включают . и ... но не .. . Таким образом, последовательность a..b должен быть tokenised как а . . б , а a..b есть а ... б . Перед лексемы . может срабатывать в первом случае, как второй . и следующее b должен быть прочитан. И если оказывается, чтобы быть b, то сканер должен создать резервную копию дополнительный характер. Это резервное копирование очень трудно избавиться.
Несколько похожий пример встречается в Rust с оператором диапазона .. . Здесь проблема в том, что 1..5 является выражением диапазона 1 .. 5 , а 1.0 - литерал с плавающей запятой. Опять же, токен 1 не может быть выдан до тех пор, пока не будут использованы два символа предпросмотра, и если оба они равны ., то либо они должны быть возвращены во входной поток, либо (если инверсия потока управления доступны) два токена должны быть выпущены. Таким образом, в этом случае легче избавиться от резервного копирования, но только с определенной архитектурой. Это было бы сложнее в случае C, потому что a..3 - это два токена и начало третьего, a . .3 & hellip; .
Flex может попросить вас предупредить вас, если вы пишете лексические спецификации, которые требуют резервного копирования (в смысле последней пары абзацев; т. Е. Более одного символа). Это потому что:
Обработка возможности резервного копирования делает сгенерированный сканер немного медленнее, хотя замедление далеко не столь актуально сегодня, как это было, когда Flex был впервые написан, и что более важно,
Такие лексические спецификации обычно являются ошибками.
В качестве примера такой ошибки рассмотрим следующие два правила в сканере:
["][^"\n]*["] { yylval = strndup(yytext + 1, yyleng - 2); return STRING; }
// ...
. { return *yytext; /* Standard fallback rule */ }
Неопределенный строковый литерал приведет к выбору правила возврата, которое включает в себя резервное копирование всей длины строки. Эта резервная копия не нужна и может привести к путанице, только если парсер попытается восстановить ошибки.
Языки, которые на самом деле требуют длинных резервных копий, довольно редки, но я, конечно, не собираюсь выходить из строя и говорить, что их не существует. Я уверен, что есть некоторые. Если возможное резервное копирование не ограничено фиксированной длиной, тогда стандартный алгоритм сканирования максимального жука становится квадратичным. С некоторой работой можно выполнить сканирование в линейном времени даже при произвольном резервном копировании, но стоимость увеличивает потребление пространства.