Каким должен быть тип данных токенов, которые лексер возвращает своему парсеру?

Как сказано в заголовке, какой тип данных должен возвращать / передавать синтаксический анализатор? Читая статью о лексическом анализе, которая есть в Википедии, она заявила, что:

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

Однако, в полном противоречии с приведенным выше утверждением, когда на другой вопрос, который я задал на другом сайте ( Code Code, если вам интересно), ответивший сказал, что:

Лексер обычно читает строку и преобразует ее в поток ... лексем. Лексемы должны быть только потоком чисел .

и он дал это визуальное:

nl_output => 256
output    => 257
<string>  => 258

Позже в статье он упомянул Flexуже существующий лексер и сказал, что написание «правил» с ним будет проще, чем написание лексера вручную. Он продолжил давать мне этот пример:

Space              [ \r\n\t]
QuotedString       "[^"]*"
%%
nl_output          {return 256;}
output             {return 257;}
{QuotedString}     {return 258;}
{Space}            {/* Ignore */}
.                  {error("Unmatched character");}
%%

Чтобы глубже понять и получить больше информации, я прочитал статью о Flex в Википедии . статья о Flex показала, что вы можете определить набор синтаксических правил с токенами следующим образом:

digit         [0-9]
letter        [a-zA-Z]

%%
"+"                  { return PLUS;       }
"-"                  { return MINUS;      }
"*"                  { return TIMES;      }
"/"                  { return SLASH;      }
"("                  { return LPAREN;     }
")"                  { return RPAREN;     }
";"                  { return SEMICOLON;  }
","                  { return COMMA;      }
"."                  { return PERIOD;     }
":="                 { return BECOMES;    }
"="                  { return EQL;        }
"<>"                 { return NEQ;        }
"<"                  { return LSS;        }
">"                  { return GTR;        }
"<="                 { return LEQ;        }
">="                 { return GEQ;        }
"begin"              { return BEGINSYM;   }
"call"               { return CALLSYM;    }
"const"              { return CONSTSYM;   }
"do"                 { return DOSYM;      }
"end"                { return ENDSYM;     }
"if"                 { return IFSYM;      }
"odd"                { return ODDSYM;     }
"procedure"          { return PROCSYM;    }
"then"               { return THENSYM;    }
"var"                { return VARSYM;     }
"while"              { return WHILESYM;   }

Мне кажется, что лексер Flex возвращает строки ключевых слов \ токенов. Но это может быть возвращение констант, которые равны определенным числам.

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

Или может ли лексер вернуть оба? Я пытался написать простой лексер на c ++, который позволяет вам иметь только один тип возврата для ваших функций. Таким образом, побуждает меня задать свой вопрос.

Чтобы сжать мой вопрос в абзаце: при написании лексера и предположении, что он может возвращать только один тип данных (строки или числа), что было бы более логичным выбором?

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

NUMBER ::= [0-9]+
ID     ::= [a-Z]+, except for keywords
IF     ::= 'if'
LPAREN ::= '('
RPAREN ::= ')'
COMMA  ::= ','
LBRACE ::= '{'
RBRACE ::= '}'
SEMICOLON ::= ';'
...

и у вас есть грамматика для парсера:

STATEMENT ::= IF LPAREN EXPR RPAREN STATEMENT
            | LBRACE STATEMENT BRACE
            | EXPR SEMICOLON
EXPR      ::= ID
            | NUMBER
            | ID LPAREN EXPRS RPAREN
...

Ваш лексер принимает входной поток и генерирует поток токенов. Поток токенов используется синтаксическим анализатором для создания дерева синтаксического анализа. В некоторых случаях достаточно просто знать тип токена (например, LPAREN, RBRACE, FOR), но в некоторых случаях вам потребуется фактическое значение , связанное с токеном. Например, когда вы сталкиваетесь с токеном идентификатора, вам понадобятся настоящие символы, из которых будет составлен идентификатор, когда вы будете пытаться выяснить, на какой идентификатор вы пытаетесь ссылаться.

Итак, у вас обычно есть что-то более или менее похожее на это:

enum TokenType {
  NUMBER, ID, IF, LPAREN, RPAREN, ...;
}

class Token {
  TokenType type;
  String value;
}

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

if (2 > 0) {
  print("2 > 0");
}

if (0 > 2) {
  print("0 > 2");
}

Они производят одинаковую последовательность типов токенов : IF, LPAREN, NUMBER, GREATER_THAN, NUMBER, RPAREN, LBRACE, ID, LPAREN, STRING, RPAREN, SEMICOLON, RBRACE. Это значит, что они тоже разбираются . Но когда вы действительно что-то делаете с деревом разбора, вы позаботитесь о том, чтобы значение первого числа было «2» (или «0»), а значение второго числа было «0» (или «2»). '), и что значение строки' 2> 0 '(или' 0> 2 ').

Как сказано в заголовке, какой тип данных должен возвращать / передавать синтаксический анализатор?

«Токен», очевидно. Лексер создает поток токенов, поэтому он должен возвращать поток токенов .

Он упомянул Flex, уже существующий лексер, и сказал, что написание «правил» с ним будет проще, чем написание лексера вручную.

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

Тем не менее, кого это волнует, если это «проще»? Написание лексера обычно не самая сложная часть!

При написании лексера и предположении, что он может возвращать только один тип данных (строки или числа), что будет более логичным выбором?

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

Последний лексер, который я написал, был лексером «полной верности», что означало, что он вернул токен, который отслеживал местоположение всех пробелов и комментариев - которые мы называем «пустяками» - в программе, а также токен. В моем лексере токен был определен как:

• Массив ведущих мелочей
• Токен
• Ширина токена в символах
• Массив замыкающих мелочей

Общая информация была определена как:

• Тип пустяков - пробел, новая строка, комментарий и т. Д.
• Ширина пустяков в символах

Так что, если бы у нас было что-то вроде

    foo + /* comment */
/* another comment */ bar;

что бы LEX в виде четырех маркеров с лексемами видов Identifier, Plus, Identifier, Semicolon, и шириной 3, 1, 3, 1. Первым идентификатор имеет ведущую мелочь , состоящую из Whitespaceшириной 4 и задняя мелочь Whitespaceс шириной 1. Plusне имеют ведущие и мелочей завершающие пустяки, состоящие из одного пробела, комментария и новой строки. Финальный идентификатор имеет начальные мелочи из комментария, пробела и так далее.

При такой схеме каждый символ в файле учитывается в выводе лексера, который является удобным свойством для таких вещей, как раскраска синтаксиса.

Конечно, если вам не нужны пустяки, вы можете просто сделать токен две вещи: вид и ширина.

Вы можете заметить, что токен и пустяки содержат только их ширину, а не их абсолютную позицию в исходном коде. Это умышленно. Такая схема имеет преимущества:

• Он компактен в памяти и в проводном формате
• Позволяет пересматривать правки; это полезно, если лексер работает внутри IDE. То есть, если вы обнаружите редактирование в токене, вы просто создадите резервную копию своего лексера на пару токенов перед редактированием и снова начнете выполнять лексинг до тех пор, пока не синхронизируетесь с предыдущим потоком токенов. Когда вы набираете символ, позиция каждого токена после этого символа изменяется, но обычно только один или два токена меняются по ширине, поэтому вы можете повторно использовать все это состояние.
• Точные смещения символов каждого токена могут быть легко получены путем итерации по потоку токенов и отслеживания текущего смещения. Если у вас есть точные смещения символов, то при необходимости легко извлечь текст.

Если вас не волнует ни один из этих сценариев, то токен может быть представлен как вид и смещение, а не как вид и ширина.

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

Как правило, вы возвращаете небольшую структуру, у которой есть число, обозначающее токен (или значение enum для простоты использования) и необязательное значение (строка или, возможно, общее / шаблонное значение). Другой подход заключается в возвращении производного типа для элементов, которые должны содержать дополнительные данные. Оба являются слегка неприятными, но достаточно хорошими решениями практической проблемы.